Skip to Main content Skip to Navigation
New interface
Conference papers

Encoding-Free ElGamal-Type Encryption Schemes on Elliptic Curves

Marc Joye 1 Benoît Libert 2, 3 
2 ARIC - Arithmetic and Computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : At PKC 2006, Chevallier-Mames, Paillier, and Pointcheval proposed a very elegant technique over cyclic subgroups of F * p eliminating the need to encode the message as a group element in the ElGa-mal encryption scheme. Unfortunately, it is unclear how to adapt their scheme over elliptic curves. In a previous attempt, Virat suggested an adaptation of ElGamal to elliptic curves over the ring of dual numbers as a way to address the message encoding issue. Advantageously the resulting cryptosystem does not require encoding messages as points on an elliptic curve prior to their encryption. Unfortunately, it only provides one-wayness and, in particular, it is not (and was not claimed to be) semantically secure. This paper revisits Virat's cryptosystem and extends the Chevallier-Mames et al.'s technique to the elliptic curve setting. We consider elliptic curves over the ring Z/p 2 Z and define the underlying class function. This yields complexity assumptions whereupon we build new ElGamal-type encryption schemes. The so-obtained schemes are shown to be semantically secure and make use of a very simple message encoding: messages being encrypted are viewed as elements in the range [0, p − 1]. Further, our schemes come equipped with a partial ring-homomorphism property: anyone can add a constant to an encrypted message –or– multiply an encrypted message by a constant. This can prove helpful as a blinding method in a number of applications. Finally, in addition to practicability, the proposed schemes also offer better performance in terms of speed, memory, and bandwidth.
Document type :
Conference papers
Complete list of metadata

Cited literature [31 references]  Display  Hide  Download
Contributor : Benoit Libert Connect in order to contact the contributor
Submitted on : Sunday, October 22, 2017 - 6:50:13 PM
Last modification on : Friday, November 18, 2022 - 9:24:49 AM
Long-term archiving on: : Tuesday, January 23, 2018 - 12:30:22 PM


Files produced by the author(s)




Marc Joye, Benoît Libert. Encoding-Free ElGamal-Type Encryption Schemes on Elliptic Curves. CT-RSA 2017 - RSA Conference 2017 -- Cryptographers' Track, Feb 2017, San Francisco, United States. pp.19 - 35, ⟨10.1007/978-3-540-72738-5_21⟩. ⟨hal-01621014⟩



Record views


Files downloads