Paper 2017/876

All-But-Many Lossy Trapdoor Functions and Selective Opening Chosen-Ciphertext Security from LWE

Benoit Libert, Amin Sakzad, Damien Stehle, and Ron Steinfeld

Abstract

Selective opening (SO) security refers to adversaries that receive a number of ciphertexts and, after having corrupted a subset of the senders (thus obtaining the plaintexts and the senders' random coins), aim at breaking the security of remaining ciphertexts. So far, very few public-key encryption schemes are known to provide simulation-based selective opening (SIM-SO-CCA2) security under chosen-ciphertext attacks and most of them encrypt messages bit-wise. The only exceptions to date rely on all-but-many lossy trapdoor functions (as introduced by Hofheinz; Eurocrypt'12) and the Composite Residuosity assumption. In this paper, we describe the first all-but-many lossy trapdoor function with security relying on the presumed hardness of the Learning-With-Errors problem (LWE) with standard parameters. Our construction exploits homomorphic computations on lattice trapdoors for lossy LWE matrices. By carefully embedding a lattice trapdoor in lossy public keys, we are able to prove SIM-SO-CCA2 security under the LWE assumption. As a result of independent interest, we describe a variant of our scheme whose multi-challenge CCA2 security tightly relates to the hardness of LWE and the security of a pseudo-random function.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2017
Keywords
LWElossy trapdoor functionschosen-ciphertext securityselective-opening securitytight security reductions
Contact author(s)
benoit libert @ ens-lyon fr
History
2017-09-13: received
Short URL
https://ia.cr/2017/876
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/876,
      author = {Benoit Libert and Amin Sakzad and Damien Stehle and Ron Steinfeld},
      title = {All-But-Many Lossy Trapdoor Functions and Selective Opening Chosen-Ciphertext Security from {LWE}},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/876},
      year = {2017},
      url = {https://eprint.iacr.org/2017/876}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.