Paper 2012/191

Security Analysis and Enhancement for Prefix-Preserving Encryption Schemes

Liangliang Xiao and I-Ling Yen


Prefix-preserving encryption (PPE) is an important type of encryption scheme, having a wide range of applications, such as IP addresses anonymization, prefix-matching search, and rang search. There are two issues in PPE schemes, security proof and single key requirement. Existing security proofs for PPE only reduce the security of a real PPE scheme to that of the ideal PPE object by showing their computational indistinguishability \cite{Ama07,Xu02}. Such security proof is incomplete since the security of the ideal encryption object is unknown. Also, existing prefix-preserving encryption schemes only consider a single encryption key, which is infeasible for a practical system with multiple users (Implying that all users should have the single encryption key in order to encrypt or decrypt confidential data). In this paper we develop a novel mechanism to analyze the security of the ideal PPE object. We follow the modern cryptographic approach and create a new security notion IND-PCPA. Then, we show that such weakened security notion is necessary and the ideal PPE object is secure under IND-PCPA. We also design a new, security-enhanced PPE protocol to support its use in multi-user systems, where no single entity in the system knows the PPE key. The protocol secret shares and distributes the PPE key to a group of key agents and let them ``distributedly encrypt'' critical data. We develop a novel distributed PPE algorithm and the corresponding request and response protocols. Experimental results show that the protocol is feasible in practical systems.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
xll052000 @ utdallas edu
2012-04-13: received
Short URL
Creative Commons Attribution


      author = {Liangliang Xiao and I-Ling Yen},
      title = {Security Analysis and Enhancement for Prefix-Preserving Encryption Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/191},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.