Paper 2013/830

Property Preserving Symmetric Encryption Revisited

Sanjit Chatterjee and M. Prem Laxman Das


At EUROCRYPT~2012 Pandey and Rouselakis introduced the notion of property preserving symmetric encryption which enables checking for a property on plaintexts by running a public test on the corresponding ciphertexts. Their primary contributions are: (i) a separation between `find-then-guess' and `left-or-right' security notions; (ii) a concrete construction for left-or-right secure orthogonality testing in composite order bilinear groups. This work undertakes a comprehensive (crypt)analysis of property preserving symmetric encryption on both these fronts. We observe that the quadratic residue based property used in their separation result is a special case of testing equality of one-bit messages, suggest a very simple and efficient deterministic encryption scheme for testing equality and show that the two security notions, find-then-guess and left-or-right, are tightly equivalent in this setting. On the other hand, the separation result easily generalizes for the equality property. So contextualized, we posit that the question of separation between security notions is property specific and subtler than what the authors envisaged; mandating further critical investigation. Next, 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, giving further evidence that find-then-guess is indeed a meaningful notion of security for property preserving encryption. Finally, we cryptanalyze the scheme for testing orthogonality. A simple distinguishing attack establishes that it is not even the weakest selective find-then-guess secure. Our main attack extracts out the subgroup elements used to mask the message vector and indicates greater vulnerabilities in the construction beyond indistinguishability. Overall, our work underlines the importance of cryptanalysis in provable security.

Note: Major Revision

Available format(s)
Publication info
Preprint. MINOR revision.
bilinear pairingsproperty preserving encryptionpredicate private encryptionsymmetric key
Contact author(s)
prem lax @ gmail com
2015-09-17: last of 7 revisions
2013-12-16: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sanjit Chatterjee and M.  Prem Laxman Das},
      title = {Property Preserving Symmetric Encryption Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2013/830},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.