Study Group: Non-Committing Encryption

The latest study group was presented by Arpita on the topic of non-committing encryption with material from the following papers:

• Improved Non-Committing Encryption Schemes based on a General Complexity Assumption by Ivan Damgård and Jesper Buus Nielsen
• Improved Non-Committing Encryption with Applications to Adaptively Secure Protocols by Seung Geol Choi, Dana Dachman-Soled, Tal Malkin, and Hoeteck Wee
• Somewhat Non-Committing Encryption and Efficient Adaptively Secure Oblivious Transfer by Juan A. Garay, Daniel Wichs, and Hong-Sheng Zhou

Non-committing encryption denotes semantically secure public-key encryption with the additional possibility of producing fake public keys and fake ciphertexts. Those should be computationally indistinguishable from real public keys and ciphertexts, respectively, but the fake ciphertexts can efficiently be opened to any message. A stronger notion is deniable encryption, where a real ciphertext can be opened to any message, and it is even possible to compute a secret key that decrypts a ciphertext to any message. Obviously, this would be helpful for individuals in jurisdictions that require key disclosure.

The main motivation for non-committing encryption (NCE) is adaptive security, that is, against an adversary that can corrupted parties in a protocol at any time in a protocol unlike a static adversary that has commit himself at the beginning. NCE can be used to achieve adaptive security in several circumstances such as secure channels, security against selective opening attacks (SOA), and oblivious transfer (implying multiparty computation). For selective opening attacks, the adversary is given a number of ciphertexts under the same public key, of which he can select some to learn the message and tge encryption randomness. A SOA-secure encryption scheme will guarantee that no information on the remaining ciphertexts can be deduced.

Non-commiting encryption was introduced by Canetti et al. in 1996. Damgård and Nielsen proved that NCE can be constructed from simulatable public-key encryption and that ElGamal achieves this property. A simulatable cryptosystem allows to generate a public key and a ciphertext without generating a secret key and inputting message, respectively, and it is possible to extract adequate generation randomness from such a fake public key or ciphertext. The construction involves the sender and the receiver agreeing on a random bit to encrypt one bit as follows: The receiver generates a real and a fake public key and sends them in random order. The sender then encrypts one out two public messages using one of the keys at random, generates a fake ciphertext for the other key, and sends both ciphertexts. If the receiver can decrypt the ciphertext corresponding to the real key to the right public message, they have both chosen the same random bit, which can be used to encrypt one bit. Otherwise, they repeat the protocol.

Unlike simple public-key encryption, this protocol requires interactivity. Nielsen proved in a paper at Crypto 2002  that non-interactive non-committing encryption implies that the secret key has to be as long as the message. However, Choi et al. introduced an NCE scheme that requires only expected two rounds, that is, it is non-interactive with high probability.