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