Paper 2012/102
On the Circular Security of BitEncryption
Ron Rothblum
Abstract
Motivated by recent developments in fully homomorphic encryption, we consider the folklore conjecture that every semanticallysecure bitencryption scheme is circular secure, or in other words, that every bitencryption scheme remains secure even when the adversary is given encryptions of the individual bits of the privatekey. We show the following obstacles to proving this conjecture: 1. We construct a publickey bitencryption scheme that is plausibly semantically secure, but is not circular secure. The circular security attack manages to fully recover the privatekey. The construction is based on an extension of the Symmetric External DiffieHellman assumption (SXDH) from bilinear groups, to $\ell$multilinear groups of order $p$ where $\ell \geq c \cdot \log p$ for some $c>1$. While there do exist $\ell$multilinear groups (unconditionally), for $\ell \geq 3$ there are no known candidates for which the SXDH problem is believed to be hard. Nevertheless, there is also no evidence that such groups do not exist. Our result shows that in order to prove the folklore conjecture, one must rule out the possibility that there exist $\ell$multilinear groups for which SXDH is hard. 2. We show that the folklore conjecture cannot be proved using a blackbox reduction. That is, there is no reduction of circular security of a bitencryption scheme to semantic security of that very same scheme that uses both the encryption scheme and the adversary as blackboxes. Both of our negative results extend also to the (seemingly) weaker conjecture that every CCA secure bitencryption scheme is circular secure. As a final contribution, we show an equivalence between three seemingly distinct notions of circular security for publickey bitencryption schemes. In particular, we give a general search to decision reduction that shows that an adversary that distinguishes between encryptions of the bits of the privatekey and encryptions of zeros can be used to actually recover the privatekey.
Note: Fixed a typo
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published elsewhere. Unknown where it was published
 Keywords
 Circular SecurityKDM
 Contact author(s)
 ron rothblum @ weizmann ac il
 History
 20120307: revised
 20120229: received
 See all versions
 Short URL
 https://ia.cr/2012/102
 License

CC BY
BibTeX
@misc{cryptoeprint:2012/102, author = {Ron Rothblum}, title = {On the Circular Security of BitEncryption}, howpublished = {Cryptology {ePrint} Archive, Paper 2012/102}, year = {2012}, url = {https://eprint.iacr.org/2012/102} }