Paper 2020/1186

Constant Ciphertext-Rate Non-Committing Encryption from Standard Assumptions

Zvika Brakerski
Pedro Branco
Nico Döttling
Sanjam Garg
Giulio Malavolta
Abstract

Non-committing encryption (NCE) is a type of public key encryption which comes with the ability to equivocate ciphertexts to encryptions of arbitrary messages, i.e., it allows one to find coins for key generation and encryption which ``explain'' a given ciphertext as an encryption of any message. NCE is the cornerstone to construct adaptively secure multiparty computation [Canetti et al. STOC'96] and can be seen as the quintessential notion of security for public key encryption to realize ideal communication channels. A large body of literature investigates what is the best message-to-ciphertext ratio (i.e., the rate) that one can hope to achieve for NCE. In this work we propose a near complete resolution to this question and we show how to construct NCE with constant rate in the plain model from a variety of assumptions, such as the hardness of the learning with errors (LWE) or the decisional Diffie-Hellman (DDH). Prior to our work, constructing NCE with constant rate required a trusted setup and indistinguishability obfuscation [Canetti et al. ASIACRYPT'17].

Note: A previous version of this work claimed a constant ciphertext-rate NCE from the quadratic residuosity (QR) assumption. This result was retracted due to a bug in the QR construction.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
A minor revision of an IACR publication in TCC 2020
Keywords
non-committing encryption ciphertext-rate
Contact author(s)
zvika brakersky @ weizmann ac il
pmbranco @ math tecnico ulisboa pt
nico doettling @ gmail com
sanjamg @ berkeley edu
giulio malavolta @ hotmail it
History
2022-06-13: last of 3 revisions
2020-09-30: received
See all versions
Short URL
https://ia.cr/2020/1186
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1186,
      author = {Zvika Brakerski and Pedro Branco and Nico Döttling and Sanjam Garg and Giulio Malavolta},
      title = {Constant Ciphertext-Rate Non-Committing Encryption from Standard Assumptions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/1186},
      year = {2020},
      url = {https://eprint.iacr.org/2020/1186}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.