[Resource Topic] 2012/191: Security Analysis and Enhancement for Prefix-Preserving Encryption Schemes

Welcome to the resource topic for 2012/191

Security Analysis and Enhancement for Prefix-Preserving Encryption Schemes

Authors: Liangliang Xiao, 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.

ePrint: https://eprint.iacr.org/2012/191

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .