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

Benoît Libert 1, 2 Amin Sakzad 3 Damien Stehlé 2 Ron Steinfeld 3
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
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.
Type de document :
Communication dans un congrès
Crypto 2017 - 37th International Cryptology Conference, Aug 2017, Santa Barbara, United States. Springer, 10403, pp.332 - 364, 2017, LNCS. 〈https://www.iacr.org/conferences/crypto2017/〉. 〈10.1007/978-3-662-53018-4_18〉
Liste complète des métadonnées

Littérature citée [82 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01621025
Contributeur : Benoit Libert <>
Soumis le : dimanche 22 octobre 2017 - 19:01:40
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : mardi 23 janvier 2018 - 12:28:51

Fichier

ABM-LWE-tight-SO-v3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Benoît Libert, Amin Sakzad, Damien Stehlé, Ron Steinfeld. All-But-Many Lossy Trapdoor Functions and Selective Opening Chosen-Ciphertext Security from LWE. Crypto 2017 - 37th International Cryptology Conference, Aug 2017, Santa Barbara, United States. Springer, 10403, pp.332 - 364, 2017, LNCS. 〈https://www.iacr.org/conferences/crypto2017/〉. 〈10.1007/978-3-662-53018-4_18〉. 〈hal-01621025〉

Partager

Métriques

Consultations de la notice

99

Téléchargements de fichiers

44