On the Circular Security of Bit-Encryption

Date Added: Mar 2012
Format: PDF

Motivated by recent developments in fully homomorphic encryption, the authors consider the folklore conjecture that every semantically-secure bit-encryption scheme is circular secure, or in other words, that every bit-encryption scheme remains secure even when the adversary is given encryptions of the individual bits of the private-key. They show the following obstacles to proving this conjecture: they construct a public-key bit-encryption scheme that is plausibly semantically secure, but is not circular secure. The circular security attack manages to fully recover the private-key.