In passive network measurement and packet header trace collection, it is necessary to preserve user privacy by ?sanitizing? header fields and IP addresses.  This invention is an algorithm to implement prefix-preserving anonymization of network traces.  This is the preferred way of anonymizing traces to balance user privacy and usefulness for network measurement and management.  The algorithm performs all complex cryptographic calculations once, off-line, and then stores the results. When an address needs to be anonymized, several lookups are performed.  Despite its simplicity, our method achieves a security level comparable to current, more complex anonymization methods.