Advertisement
Published in:
2016 | OriginalPaper | Chapter
Adaptive Security with Quasi-Optimal Rate
Authors : Brett Hemenway, Rafail Ostrovsky, Silas Richelson, Alon Rosen
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
A multiparty computation protocol is said to be adaptively secure if it retains its security in the presence of an adversary who can adaptively corrupt participants as the protocol proceeds. This is in contrast to a static corruption model where the adversary is forced to choose which participants to corrupt before the protocol begins. 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 \(\mathcal {O}(k^2)\) where \(k\) is the security parameter, and prior to this work, the best known constructions had ciphertext expansion that was either \(\mathcal {O}(k)\) under general assumptions, or alternatively \(\mathcal {O}(\log (n))\), where n is the length of the message, based on a specific factoring-based hardness assumption.
In this work, we build a new non-committing encryption scheme from lattice problems, and specifically based on the hardness of (Ring) Learning With Errors (LWE). Our scheme achieves ciphertext expansion as small as \(\mathrm{polylog}(k)\). Moreover when instantiated with Ring-LWE, the public-key is of size \(\mathcal {O}(n\mathrm{polylog}(k))\). All previously proposed schemes had public-keys of size \(\varOmega (n^2\mathrm{polylog}(k))\).