A central tool for constructing adaptively secure protocols is non-committing encryption (Canetti, Feige, Goldreich and Naor, STOC '96). The original protocol of Canetti et al. had ciphertext expansion that was quadratic in the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was linear in the security parameter.
In this work, we present the first non-committing encryption scheme that achieves ciphertext expansion that is logarithmic in the message length. Our construction has optimal round complexity (2-rounds), where (just as in all previous constructions) the first message consists of a public-key of size $\tilde{\bigoh}(n \secpar)$ where $n$ is the message length and $\secpar$ is the security parameter. The second message consists of a ciphertext of size $\bigoh( n \log n + \secpar )$. The security of our scheme is proved based on the $\Phi$-hiding problem.
Category / Keywords: public-key cryptography / non committing encryption, public key cryptography, phi-hiding Original Publication (in the same form): IACR-TCC-2015 Date: received 22 Jan 2015 Contact author: fbrett at cis upenn edu Available format(s): PDF | BibTeX Citation Version: 20150123:141604 (All versions of this report) Short URL: ia.cr/2015/054