All-But-Many Encryption.

We present a new cryptographic primitive, called all-but-many encryption (ABME). An ABME scheme is a tag-based public-key encryption scheme with the following additional properties: A sender given the secret key can generate a fake ciphertext to open to any message with consistent randomness. In addition, anyone who does not own the secret key can neither distinguish a fake ciphertext from a real (honestly generated) one, nor produce a fake one (on a fresh tag) even after seeing many fake ciphertexts and their opening. A motivating application of ABME is universally composable (UC) commitment schemes. We prove that an ABME scheme implies a non-interactive UC commitment scheme that is secure against adaptive adversaries in the non-erasure model under a reusable common reference string. Previously, such a 'fully equipped' UC commitment scheme has been known only in Canetti and Fischlin (CRYPTO 2001, vol 2139, Lecture notes in computer science. Springer, Heidelberg, pp 19-40, 2001), Canetti et al. (STOC 2002, pp 494-503, 2002), with expansion factor $$O(\kappa )$$ , meaning that to commit $$\lambda $$ bits, communication strictly requires $$O(\lambda \kappa )$$ bits, where $$\kappa $$ denotes the security parameter. We provide a general framework for constructing ABME and several concrete instantiations from a variety of assumptions. In particular, we present an ABME scheme with expansion factor O(1) from DCR-related assumptions, which results in showing the first fully equipped UC commitment scheme with a constant expansion factor. In addition, the DCR-based ABME scheme can be transformed to an all-but-many lossy trapdoor function (ABM-LTF), proposed by Hofheinz (EUROCRYPT 2012, vol 7237, Lecture notes in computer science. Springer, Heidelberg, pp 209-227, 2012), with a better lossy rate than Hofheinz (2012). [ABSTRACT FROM AUTHOR]