# Efficient Cryptosystems From $2^k$ -th Power Residue Symbols

2 CASCADE - Construction and Analysis of Systems for Confidentiality and Authenticity of Data and Entities
DI-ENS - Département d'informatique de l'École normale supérieure, CNRS - Centre National de la Recherche Scientifique : UMR 8548, Inria de Paris
6 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : Goldwasser and Micali (1984) highlighted the importance of randomizing the plaintext for public-key encryption and introduced the notion of semantic security. They also realized a cryptosystem meeting this security notion under the standard complexity assumption of deciding quadratic residuosity modulo a composite number. The Goldwasser-Micali cryptosystem is simple and elegant but is quite wasteful in bandwidth when encrypting large messages. A number of works followed to address this issue and proposed various modifications. This paper revisits the original Goldwasser-Micali cryptosystem using 2 k-th power residue symbols. The so-obtained cryptosystems appear as a very natural generalization for k ≥ 2 (the case k 1 corresponds exactly to the Goldwasser-Micali cryptosystem). Advantageously, they are efficient in both bandwidth and speed; in particular, they allow for fast decryption. Further, the cryptosystems described in this paper inherit the useful features of the original cryptosystem (like its homomorphic property) and are shown to be secure under a similar complexity assumption. As a prominent application, this paper describes an efficient lossy trapdoor function based thereon.
Keywords :
Type de document :
Article dans une revue
Journal of Cryptology, Springer Verlag, 2016, 〈10.1007/s00145-016-9229-5〉

Littérature citée [30 références]

https://hal.inria.fr/hal-01394400
Contributeur : Benoit Libert <>
Soumis le : mercredi 9 novembre 2016 - 12:44:59
Dernière modification le : jeudi 26 avril 2018 - 10:29:00
Document(s) archivé(s) le : mardi 14 mars 2017 - 23:12:29

### Fichier

435.pdf
Fichiers produits par l'(les) auteur(s)

### Citation

Fabrice Benhamouda, Javier Herranz, Marc Joye, Benoît Libert. Efficient Cryptosystems From $2^k$ -th Power Residue Symbols. Journal of Cryptology, Springer Verlag, 2016, 〈10.1007/s00145-016-9229-5〉. 〈hal-01394400〉

### Métriques

Consultations de la notice

## 318

Téléchargements de fichiers