Cryptology ePrint Archive: Report 2013/830

Property Preserving Symmetric Encryption Revisited

Sanjit Chatterjee and M. Prem Laxman Das

Abstract: At EUROCRYPT 2012 Pandey and Rouselakis introduced the notion of property preserving symmetric encryption. Such encryption schemes may be used for checking for a property on plaintexts by running a public test on the corresponding ciphertexts. It is claimed that they hold great promise in designing private algorithms for data classification. The main contributions of their work, the authors say, are a thorough investigation of property preserving symmetric encryption and consists of two main parts. On the definitional front the paper formalizes several notions of security, establish a separation between the weaker find-then-guess and the stronger left-or-right security notions and show that there exists a hierarchy of find-then-guess notions which do not collapse. The other main contribution is a concrete left-or-right secure construction for orthogonality testing.

In this work our primary focus is a critical analysis of property preserving symmetric encryption on both these fronts -- security definition and provably secure construction. The separation results of Pandey-Rouselakis are conditioned on the assumed existence of a find-then-guess secure encryption of a quadratic residue based property. We observe that this property is captured by testing equality of encryption of one-bit messages and suggest a very simple and efficient scheme for testing equality. We show that the two security notions, find-then-guess and left-or-right, effectively collapse for the equality property. On the other hand, the separation results easily generalize for the equality property. Based on these results we contextualize the question of whether the separation is an artifact or indicate some real difference between the notions of find-then-guess and left-or-right for property preserving encryption. Next we cryptanalyze the scheme for testing orthogonality described in the Pandey and Rouselakis work, which was claimed to be secure in the strongest left-or-right model. We demonstrate a simple and elegant attack on the scheme which establishes that it is not even the weakest selective find-then-guess secure.

Finally, we show that given a find-then-guess secure orthogonality-preserving encryption of vectors of length 2n, there exists left-or-right secure orthogonality-preserving encryption of vectors of length n. This result gives further credence to our already established evidence that the find-then-guess is indeed a meaningful notion of security for property-preserving encryption.

Category / Keywords: secret-key cryptography, applications

Date: received 3 Dec 2013, last revised 15 Dec 2014

Contact author: prem lax at gmail com

Available format(s): PDF | BibTeX Citation

Note: Major revision

Version: 20141215:072953 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]