Stateless address translation at an Autonomous System (AS) boundary for host privacy may be provided. An address associated with a host device in the AS may be received. The address may comprise a network prefix and an interface identifier (ID). Then a cypher value may be assigned to a cypher bit range in the network prefix. The cypher value may be associated with a first cypher algorithm of a plurality of cypher algorithms. Next, the address may be encoded wherein encoding the address comprises applying the first cypher algorithm to encode a coding bit range in the address that is less significant than the cypher bit range. The encoded address may then be used for flows from the host that egress the AS.