Data Leakage
Data Leakage in Format-Preserving Protection of Variable-Length Domains
With an increase in both the amount of data and data privacy regulations, there is an increasing need for protecting Personally Identifiable Information (PII). Ideally, this is done through encoding the data such that the PII is removed, whilst still allowing the encoded data to be used in place of the original data. This approach is called format-preserving, where the encoded data keeps the same format as the original, allowing it to be readily used in place of it.
The format of data can include things like length, special characters, character types and checksums. There are generally two format types: fixed and variable length. Fixed length formats include CCN, postal codes, and SSN, whereas variable lengths formats include emails, names, addresses, and phone numbers.
Format-preserving protection
Substitution-based
A widely used approach to protect PII is to apply substitution-based techniques to remove or hide the identities of the entities referred to in the data. Such techniques include
- Straight substitution, where elements are replaced with (possibly random) elements of similar types.
- Suppose an email is. An example of a random substibution of all non-domain letters is ...
- Pseudo-anonymisation, where a mapping table is maintained, ensuring that the process is invertible.
- Masking, where a predefined mask is applied to replace certain elements with static elements.
- Replacing all non-domain letters with 'x' gives
Format-Preserving Encryption (FPE)
Another approach to such format-preserving protection is FPE, where data is encrypted such that a given format is preserved, with NIST specifing the FF1 FPE method [1]. Specifically, FPE methods are given any finite set of symbols, and transform the data into a sequence of the symbols in such a way that the encrypted data has the same format as the original data, including the length. This set of symbols is termed the radix and is typically digits (0-9) or alphanumeric (0-9, a-z (can also include A-Z)). Generally, all the elements in the plaintext share this radix, meaning that it is not possible to ensure more specific domains for each element [1].
Data Leakage
The approaches described all have problems handling variable length domains. Emails are an example of variable-length data. Suppose that the encoding method preserves the ‘@’ and ‘.’ characters that are required in emails. This could be done using any of the substitution techniques where these special characters are fixed, or by splitting it based on these characters and encrypting each part separately using FPE. Whchever method used, the encoding method is one-to-one in the lengths of inputs and outputs. If single-letter substitutions are used (or FPE), the exact length is preserved. The encoded email then gives the exact length of the original one, and as emails can be up to 254 characters in length [2], knowing the length greatly restricts the possible values of the original email. Supposing that the domain is distributed unevenly across the different possible lengths, such as in the case of phone numbers where some lengths can be reserved for special phone numbers, the length being one of these special ones greatly restricts the possible original values.
Statistical inference attack
Even if the length of an encoded value does not restrict the original value itself too much, i.e. the domain is evenly distributed across lengths, knowing the length can expose information about other values. This could be something as simple as certain name lengths being more common for a specific gender, some address lengths being more common in rural versus urban areas, or email domain lengths differing for personal versus corporate.
The degree of data-leakage can be summarized by k-anonomity, which is a number describing how many people cannot be distinguished from one another. Knowing the length, how many instances of values in the domain have this length? It is when combining the lengths of several different data values for the same identity that problems truly arise. It then becomes a question of given all these lengths for each of these data types, how many combinations of actual values fit. Using lengths to narrow down possible values of the original data, information about the distribution of the lengths in the domain is required, i.e. knowing the popularity of names, or all street addresses. Such information is often readily available through things like national statistical databases, or can be scraped from online sources. If the length distribution of the gathered data matches that of the protected PII data, then it is likely representative of the greater dataset, and statistical analyses can be made to narrow the possible values.
Mitigating data leakage
These length-based data leakages necessitates using other approaches to encode PII, such that length is not preserved in variable-length domains. Essentially, the length of data should be randomized to some degree, though referential integrity may also be desired, meaning that the lengthening (or shortening) of data should be consistent for the same data values.
References
- ↑ 1.0 1.1 Dowkin, Morris; Mouha, Nicky (February 2025). "Recommendation for Block Cipher Modes of Operation: Methods for Format-Preserving Encryption" (PDF). NIST Special Publication. 800-38Gr1 – via NIST Technical Series Publications.
- ↑ "RFC 3696 Errata". RFC Editor. Retrieved 8 August 2025.
This article "Data Leakage" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Data Leakage. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.
