## Property Preserving Symmetric Encryption Revisited

Sanjit Chatterjee and M. Prem Laxman Das

*Advances in Cryptology - Asiacrypt 2015*,
Lecture Notes in Computer Science, 9453 (2015), 658-682.

Abstract:
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 2*n*, 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-thenguess 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.

Proceedings
paper
Eprint paper