Jean-Louis Kraus
email: jean-louis.kraus@univ-amu.fr

Keywords: Steroids, cholesterol, sitosterol, plants, animals, metabolism

Cholesterol and Sitosterol, two members of the steroid family which structures differ by a single ethyl group, but which maintain the right balance between plant and animal kingdoms.

Introduction

Liver is an organ only found in vertebrates, which has a significant capacity to regenerate.

Remember the myth of Prometheus, bound to a mountain in the Caucasus, where an eagle ate a piece of his liver every day, only to have it grow back to be eaten the next day. Liver has many important metabolic functions, mainly it converts diet nutrients into substances easily metabolized. Among these substances Cholesterol, produced and cleared by the liver, is essential. Since plants don't have liver, a large majority of people, believe that plants do not synthesized cholesterol and consequently a plant-based diet ensures to be cholesterol free.

This belief is due to several reasons. Generally, plants contain only small quantities of cholesterol, and analytical methods for cholesterol detection in plants are not as developed as they are for mammals. Moreover very often legalities of food labelling, allow small quantities of cholesterol in foods which are still called ''zero cholesterol '' [START_REF] Gyling | Phytosterols, phytostanols and lipoprotein Metabolism[END_REF][START_REF] Valitova | Plant sterols: diversity, biosynthesis and Physiological functions[END_REF]. Sitosterol, which differs from cholesterol (scheme 1), by an ethyl susbtituent at position 24, is the most common, but depending on the species, plants also contain amounts of free or esterified cholesterol [START_REF] Behrman | Cholesterol and plants[END_REF]. In plants, cholesterol is a major sterol mainly found on the surfaces of leaves, and localized in membranes. Nevertheless, it should be underlined that cholesterol averages are around 50mg /kg in plants and around 5g/kg in animals. Besides the little contents of cholesterol, the most common sterol components of plants membranes are sitosterol (βform), and stigmasterol. The differences in cholesterol levels between plants and animals and the presence of specific sterols in plants not found in humans, have opened up number of questions:

-Why does the parent precursor epoxysqualene (scheme 1) gives birth to lanosterol and cycloartenol, each other giving rise respectively to cholesterol in larger quantities in animals and sitosterol and stigmasterol in larger quantities in plants? -Do plant sterols affect cholesterol levels in humans -Do animals metabolize plant steroids by the same mechanism with which they metabolize cholesterol? -Why, if some animals need an external supply of cholesterol, they eat preferentially another animal and not plants?

Finally, those issues lead to raise a basic question directly linked to the darwinian evolutionist theory: ''Why plant don't have a liver? ''

Discussion

-Plants and animals, steroids biosynthesis

Answering the above questions requests to take into account other matters. Since plants unlike animals, cannot move; they must protect themselves from cold and heat. In this feature, Sitosterol allows plants to have a better adaptation to large temperature variations.

In contrast, nature has endowed animals with a liver, a specific organ dedicated to cholesterol production. Since animals move, first they can exploit other sources of cholesterol in eating other animal species, and second they can adapt themselves to different climatic conditions in finding a shelter to protect themselves from heat and cold. Lanosterol pathway leading to cholesterol is more developed in animal kingdom. In contrast cycloartenol pathway leading to sitosterol and stigmasterol is specific to plant kingdom, both sterols cannot be metabolized by animals. It can be concluded that in contrast to cholesterol, precursor of sexual steroids hormones in mammals (estrogens and androgens), sitosterol cannot be converted in animal sexual hormones [START_REF] Raquel | Integrative Medicine[END_REF]. Taking into account these observations, it is tempting to conclude that nature has allowed plants to remain motionless, by endowing them with a system of sterol production, available directly from soil nutriments, and not metabolized by animals.

The above considerations suggest that a profound coupling between nutrition and reproduction exists. This coupling is after all logical, since in the course of evolution, only those who have been well fed, have been able to successfully launch into reproduction, which is a very expensive activity in energy. This coupling nutrition /reproduction implies that hormones constantly ensure a coordination between the physiological state and the entry into phase of reproduction.

2-What are the effects of plant steroids on cholesterol levels in humans?

Some uncomplete answers to the question, ''what are the effects of plant sterols on cholesterol levels on humans'' have been brought by Garett [START_REF] Garrett | [END_REF], but the question still remains hot. Levels of cholesterol in western diet are still major sources of conflict among dietetic specialists. It is likely that some therapists recommend medicinal plants for lowering cholesterol and glucose levels [START_REF] Tappia | Reduction of cholesterol and other cardiovascular disease risk factors by alternative therapies[END_REF] and in the same time, controversies agitate the world of medicine between pro and anti-statins for the treatment against high levels of blood cholesterol [START_REF] Even | La vérité sur le cholestérol[END_REF]. The paradox is that when rice is cultivated in the presence of yeast species such as monacus purpureus, it produced compounds like lovastatin or compactin, which are statin drugs, which inhibit cholesterol synthesis by blocking action of the enzyme HMG-CoA reductase [START_REF] Edwards | Statins in hypercholesterolaemia: A dose-specific meta-analysis of lipid changes in randomised, double blind trials[END_REF]. That being said, cholesterol remains an appealing molecule which best illustrates the relationships that have been developed during evolution between animal and plant kingdoms. For animals, that need a lot of energy to get around, nature has provided them with a liver that allows them to synthesize significant amounts of cholesterol for the biosynthesis of hormones necessary for their reproduction. In contrast plants that are motionless, synthesize their own specific sterols (sitosterol and stigmasterol) and only low amounts of cholesterol. Mother nature has made that less than 5% of plant sitosterol are absorbed by the intestine of the animals. This was possible since nature has allowed plants to lower cholesterol levels in animal, simply in organizing a competition between plants sterols and cholesterol for packaging into mixed micelles that are taken up by polytopic transmembrane protein called Niemann-Pick C1-Like 1 (NPC1L1) [START_REF] Betters | NPC1L1 and cholesterol transport[END_REF] which is highly expressed in human liver.

3-Steroids and determinism.

In the light of what has been said above, it is interesting to reassess the key role of both steroids, Cholesterol and Sitosterol, in the life evolution process on earth.

Those two legitimate signaling molecules, have helped and continue to maintain the right balance between the two kingdoms : plants and animals. Upsetting this balance, would have had profound effect on life earth, mainly in weathering changes due to the content of CO 2 . The story is quite simple: Herbivores evolve to eat plants, the plants evolve ways of eluding the herbivores, and the herbivores evolve again. As each side gets the upper hand, it changes the weathering rate, which in turn steers the planet between balmy and cold climates.

Plants have been land-colonizers for around roughly 700 million years. Vertebrates first came on land about 360 million years ago, almost without exception they were carnivore.

Humans have been only around for the last 200,000 years or so. During the paleozoic era, plants did well, because nothing was around yet to eat them. CO 2 level in the air was low.

To handle terrestrial plants, animal evolved with a digestive system completed with grinding teeth, symbiotic gut bacteria, and powerful gastrointestinal tract; at the same time as plants struggled under attacks from herbivores, earth basked in a heat wave for the next 200 million years due to an increase of CO 2 level in air. Could someone seeing cows grazing placidly in a lush grass meadow, imagine that life on earth has been possible because nature has provided animals not only a liver, but also a digestive system that allowed them to handle plants? This system works through the molecular language based on two steroids molecules: Cholesterol provided by the liver of the animals, and sitosterol synthesized by plants.

Conclusion.

What can we have learned from this steroid story? Confirmation that a communication exists between animals and plants. It is well known that plants can release coercive chemicals to pollinators or attractants to species that eat their pests, eventually they can exudate substances from their roots, but cherry on the cake, plants can synthesize secret hypoglycemic statins that have the property of inhibiting cholesterol animal production [START_REF] Khanimov | High-intensity statins are associated with increased incidence of hypoglycemia during hospitalization of individuals not critically III[END_REF]. Unfortunately nobody knows to what end or whether this is truly intentional. Nevertheless, if the deterministic theory is true, all the events that occur, were necessitated by a past situation. Therefore weathering or climates changes which occur millions year ago, for which to-day humans are still responsible, are associated at least in part, to the communication that exist between plants and animals, through a simple fundamental molecular steroid language based on two molecules cholesterol and sitosterol .

Scheme 1 As

 1 Scheme 1

Acknowledgments.

Institut de Biologie du Développement de Marseille (IBDM), Aix-Marseille-University and CNRS-UMR 7288 from France are acknowledged for financial support. A. Le Bivic and L.

Kodjabachian, IBDM-CNRS Marseille directors, are greatly acknowledged for facilities offered.


Mohamad El Laz
email: mohamad.el-laz@inria.fr

Benjamin Grégoire
email: benjamin.gregoire@inria.fr

Tamara Rezk
email: tamara.rezk@inria.fr

Security Analysis of ElGamal Implementations

Keywords: ElGamal, DDH Assumption, Quadratic Residues, Voting Systems, Message Encoding Generator Encoding Decoding DDH Belenios (Belenios, 2016) T3

The ElGamal encryption scheme is not only the most extensively used alternative to RSA, but is also almost exclusively used in voting systems as an effective homomorphic encryption scheme. Being easily adaptable to a wide range of cryptographic groups, the ElGamal encryption scheme enjoys homomorphic properties while remaining semantically secure. This is subject to the upholding of the Decisional Diffie-Hellman (DDH) assumption on the chosen group. We analyze 26 libraries that implement the ElGamal encryption scheme and discover that 20 of them are semantically insecure as they do not respect the Decisional Diffie-Hellman (DDH) assumption. From the five libraries that do satisfy the DDH assumption, we identify and compare four different message encoding and decoding techniques.

) .

INTRODUCTION

Throughout the last century, especially with the beginning of public key cryptography due to Diffie-Hellman [START_REF] Diffie | New directions in cryptography[END_REF], many cryptographic schemes have been proposed. Their security depends on mathematically complex problems such as integer factorization and discrete logarithm. In fact, it is thought that a cryptographic scheme is secure if it resists cryptographic attacks over a long period of time. On one hand, since certain schemes may take several years before being widely studied in depth, they become vulnerable as time passes. On the other hand, a cryptographic scheme is a provable one, if it resists cryptographic attacks relying on mathematical hypothesis. Being easily adaptable to many kinds of cryptographic groups, the ElGamal encryption scheme enjoys homomorphic properties while remaining semantically secure [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF], provided that the Decisional Diffie-Hellman (DDH) assumption holds on the chosen group. While the homomorphic property forbids resistance against chosen ciphertext attacks, it is very convenient for voting systems [START_REF] Cortier | Beleniosrf: A strongly receipt-free electronic voting scheme[END_REF]. The ElGamal encryption scheme [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] is the most extensively used homomorphic encryption scheme for voting systems (see also Paillier [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]). Moreover, ElGamal is the only homomorphic encryption scheme implemented by default in many hardware security modules [START_REF] Volkamer | Evaluation of Electronic Voting[END_REF][START_REF] Orr | SAC '15[END_REF]. In order to be provably secure, the El-Gamal encryption needs to be implemented on top of a group verifying the Decisional Diffie-Hellman (DDH) assumption. Since this assumption does not hold for all groups, one may have to wrap an encoding and a decoding phase to ElGamal to be able to have a generic encryption scheme. In this paper, our main goal is to study ElGamal encryption scheme libraries to identify which implementations respect the DDH assumption.

We manually analyze the source code of 26 libraries that implement the ElGamal encryption scheme in the wild. We focus our analysis on understanding whether the DDH assumption is respected in these implementations, ensuring a secure scheme in which no information about the original message could be leaked. The DDH assumption is crucial for the security of ElGamal because it ensures indistinguishability under chosen-plaintext attacks (IND-CPA). Without a group satisfying the DDH assumption, encryption mechanisms may leak one bit of information about the plaintext and endanger the security of the electoral system, thus threatening the privacy in an election. For instance, when considering an approval ballot with a yes or no vote, leaking one bit of information signifies a full leakage of the vote. One way to comply with the DDH assumption is by using groups of prime order. In particular, when adopting safe primes, one can ensure the existence of a large prime order subgroup [START_REF] Milne | Fields and galois theory (v4.22)[END_REF] and restrict messages to belong to this subgroup. Mapping plaintexts into subgroups is called message encoding. Such encoding necessitates to be efficient and precisely invertible to allow decoding after the decryption. In Table 1, we give an overview of our results : out of 26 analyzed libraries, 20 are wrongly implemented because they do not respect the conditions to achieve IND-CPA security under the DDH assumption. This means that encryptions using ElGamal from any of these 20 libraries leak one bit of information (see Section 4). From the 6 libraries which respect the DDH assumption, we also study and compare various encoding and decoding techniques. We identify four different message encoding and decoding techniques summarized in Table 2. Finally, we discuss the different designs and conclude which implementation is more efficient for voting systems.

RELATED WORK

The ElGamal Scheme. The ElGamal encryption scheme was introduced in 1985 by Taher ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF]. It relies on Diffie-Hellman key exchange and is known to be semantically secure under the Decisional Diffie-Hellman (DDH) assumption where the discrete logarithm problem is hard to solve. In 2009, [START_REF] Barthe | Formal certification of code-based cryptographic proofs[END_REF] proved that the ElGamal encryption scheme is secure against chosen-plaintext attacks (CPA) in the standard model assuming that the DDH problem is hard in the underlying group family by using the proof assistant Coq. The Cramer-Shoup cryptosystem (CS) [START_REF] Cramer | A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack[END_REF] was developed by Ronald Cramer and Victor Shoup in 1998. It is a generalization of ElGamal's protocol and is provably secure against adaptive chosen ciphertext attacks (CCA), under the DDH assumption. Even though it is a modified version of ElGamal, the Cramer-Shoup cryptosystem cannot be used however as a substitute of ElGamal in voting systems. In fact, being resistant to CCA results in losing the homomorphic property of the scheme, which is fundamental for voting systems. [START_REF] Chevallier-Mames | Encoding-free elgamal encryption without random oracles[END_REF], Benoît Chevallier-Mames et al. (Chevallier-Mames et al., 2006) proposed an ElGamal encryption alternative, using a new encoding-free technique. Their approach holds better performance than plain ElGamal without the necessity to map the message into a subgroup. The authors introduce the notion of the class function based on the difficulty of the Decisional Class Diffie-Hellman (DCDH) assumption. An essential improvement of the Encoding-Free version scheme is to avoid message conversion, providing a wider message space. ElGamal encoding-free is IND-CPA. However, to date, it is not known how to identify whether a group satisfies the DCDH assumption or not.

Semantic Security. The mental poker [START_REF] Rivest | Mental poker[END_REF] is the first protocol known to be vulnerable to attacks because its encryption scheme does not respect the DDH assumption. The game of mental poker is an ordinary poker game and communications between players are done via messages since it is a game without physical cards. Being exposed to attacks, the mental poker game can leak one bit of information about the cards by observing whether the encryption scheme preserves the quadratic residuosity of a number [START_REF] Lipton | How to Cheat at Mental Poker[END_REF]. Consequently, in 1982, Goldwasser and Micali introduced the first probabilistic public-key encryption scheme [START_REF] Goldwasser | Probabilistic encryption and how to play mental poker keeping secret all partial information[END_REF] which is provably secure under standard cryptographic assumptions. It is based on the intractability of Quadratic Residuosity Assumption modulo a composite n. Considering that the distribution of quadratic residues and quadratic non-residues is not the same, one restricts oneself to a subset where the number of quadratic residues is equal to the number of quadratic non-residues, and takes only the messages that are quadratic residues to prevent an attacker from gaining any information about the original message.

Encoding Mechanisms. What we call message encoding refers to the mechanism that maps a message into a specific group. An approach to encode a message is the hash-ElGamal encoding. This scheme consists of including a hash function during the encryption process. Let h : G → {0, 1} l , w → h(w) be a hash function mapping elements to l-bit strings. The encryption of a message m ∈ M where the message space is defined as M = {0, 1} l is then given by (g r , m ⊕ h(y r )). This encoding mechanism solves the problem of leaking information about the original message but unfortunately, it cannot be used for voting systems as it loses its homomorphic property. Another option to encode messages is exponent-ElGamal encoding [START_REF] Cramer | A secure and optimally efficient multiauthority election scheme[END_REF]. This technique takes advantage of a property where any element w ∈ G =< g > is uniquely represented as w = g z for some z ∈ Z/qZ. For any message m ∈ Z/qZ, the resulting encoding is g m . The corresponding ciphertext is given by (c 1 , c 2 ) = (g r , g m y r ). In this case, the problem is in the decryption process: to retrieve the original message, the computation of the discrete logarithm in G is needed. Considering that the discrete logarithms are hard to solve in G, this leads to limit the message space to a small set where the discrete logarithm problem is easy to solve by using brute force or Pollard's rho algorithm [START_REF] Pollard | Monte carlo methods for index computation[END_REF].

Elliptic curve ElGamal is a different variant where a message m is represented as a point on an elliptic curve, more accurately, as a point on a prime order subgroup. Elliptic curve cryptography [START_REF] Koblitz | The state of elliptic curve cryptography[END_REF][START_REF] Miller | Use of elliptic curves in cryptography[END_REF] offers smaller key sizes resulting in gains in speed and memory, and benefits of the absence of sub-exponential algorithms that solve the elliptic curve discrete logarithm problem. However, encodings [START_REF] Farashahi | Hashing into hessian curves[END_REF][START_REF] Fadavi | Injective encodings to binary ordinary elliptic curves[END_REF][START_REF] Bernstein | Elligator: elliptic-curve points indistinguishable from uniform random strings[END_REF] mostly do not handle prime-order elliptic curves as there is no known polynomial time algorithm for finding a large number of points on an arbitrary curve. Furthermore, several encodings are hash-to-curve that are not invertible and therefore not compatible with group operation which destroys the homomorphic property [START_REF] Faz-Hernandez | Hashing to Elliptic Curves[END_REF].

Application to E-voting. We briefly discuss electronic voting systems that use ElGamal encryption. To get familiar with voting systems, we refer the interested reader to [START_REF] Ne Oo | A survey of different electronic voting systems[END_REF][START_REF] Cortier | Sok: Verifiability notions for e-voting protocols[END_REF][START_REF] Volkamer | Evaluation of Electronic Voting[END_REF]. E-voting systems are important as they expand the participation of voters and offer an efficient way to count votes. However, without employing secure systems, the use of voting systems would be meaningless. E-voting uses publickey cryptography: ElGamal is the most common used encryption algorithm as it enjoys multiplicative homomorphic properties that allows the addition on the ciphertexts in order to count ballots without revealing the identity of the voters. Additionally, ElGamal enables re-encryption which results in a different ciphertext containing the same information. (Paillier encryption scheme [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]) is a possible option as well, relying on the DCR assumption). Various studies demonstrated the importance of ElGamal as an encryption scheme for electronic voting systems [START_REF] Haines | Verified verifiers for verifying elections[END_REF][START_REF] Adida | Helios: Web-based open-audit voting[END_REF]. Additionally, several countries (e.g. Estonia [START_REF] Kubjas | Estonian voting verification mechanism revisited again[END_REF], Norway [START_REF] Puigalli | Cast-as-intended verification in norway[END_REF] and Russia [START_REF] Babenko | A model of a secure electronic voting system based on blind intermediaries using russian cryptographic algorithms[END_REF]) are using e-voting systems as a main mechanism for elections and are employing ElGamal to count and verify votes. Moreover, in a note of 15 November 2019, Pierrick Gaudry [START_REF] Gaudry | Breaking the encryption scheme of the moscow internet voting system[END_REF] reveals an attack about the Moscow voting system because it does not comply with the DDH assumption.

BACKGROUND

Notions and Preliminaries

The ElGamal encryption scheme is known to be IND-CPA secure under the decisional Diffie-Hellman as-sumption. In this section we recall some basic definitions and notations that will be used throughout this paper.

Definition 3.1 (Decisional Diffie-Hellman) Given two distributions DDH 0 = (g x , g y , g xy ) and DDH 1 = (g x , g y , g z ) where x, y, z are randomly distributed in Z q , a cyclic group with generator g. It is hard to distinguish between DDH 0 and DDH 1 .

An encryption scheme is said to be IND-CPA secure if a polynomial time adversary choosing two plaintexts cannot distinguish between the resulting ciphertexts. If the adversary can distinguish between the ciphertexts better than guessing blindly, we say that the adversary achieves an advantage. The advantage of any efficient adversary is expressed as a negligible function of the security parameter in the formal definition of IND-CPA . For ElGamal, the security parameter is the key length. To satisfy IND-CPA, an encryption scheme must necessarily be probabilistic, otherwise an adversary could trivially detect which message corresponds to the challenge ciphertext by simply encrypting one of the messages it has chosen and compare the resulting ciphertext with the challenge ciphertext.

The ElGamal Encryption Scheme

ElGamal [START_REF] Elgamal | A public key cryptosystem and a signature scheme based on discrete logarithms[END_REF] is an asymmetric encryption scheme, it enjoys homomorphic properties that are fundamental for the electronic voting systems. El-Gamal scheme (see Algorithm 1) consists of three algorithms: key generation(η), η being a security parameter, encryption E(m, pk) with m being a plaintext and pk a public key, and decryption D(c, sk) where c is a ciphertext and sk is a private key.

Algorithm 1 ElGamal Scheme K G: Pick randomly a secret key x ∈ Z q , then compute y = g x to obtain the public key.

E(m):

Let m ∈ G and r ∈ Z q randomly selected. The resulting ciphertext is c = (u, v) = (g r , m.y r ).

D(c):

To recover the plaintext, one computes

m = v • u -x .

Security of ElGamal

A key point for the security of the ElGamal encryption scheme resides in the group G and its order. One should start by generating a pair of keys (public and private), then map the message into a group where the Decisional Diffie-Hellman assumption holds. Hence, the difficulty consists in finding an efficient invertible group encoding procedure so that one can recover the original message when decrypting. The ElGamal cryptosystem operates in a finite cyclic group, which by convention is written multiplicatively. For the sake of simplicity, we will restrict our discussion to the group of integers from {1} to {p -1} under multiplication mod p for some prime p, commonly denoted Z * p and subgroups of Z * p of prime order. Moreover, we will also use |g| to denote the order of an element g in Z *

p and < g > to denote the cyclic subgroup of Z * p generated by g. Unless otherwise noted, assume multiplications and exponentiations involving elements of Z * p are done mod p. As if all subgroups of a cyclic group are cyclic and if G = g is cyclic, then for every divisor d of |G| there exists exactly one subgroup of order d which may be generated [START_REF] Rotman | An Introduction to the Theory of Groups[END_REF]. One may rely on this property to form a unique subgroup of quadratic residues elements. To achieve this goal, the idea is to use a Sophie Germain prime [START_REF] Pollard | Monte carlo methods for index computation[END_REF]: it is a safe prime p of the form 2q + 1 where q is also prime. Safe primes of that form are important for modulo groups as they guarantee the existence of a subgroup of prime order. For ElGamal, using a safe prime p, where the order is p -1 = 2q permits to form a subgroup of prime order q that forms the message space we need in order to encrypt messages. One may take advantage of the Lagrange theorem [START_REF] Pollard | Monte carlo methods for index computation[END_REF] that states that in a finite group G, the order of any subgroup H divides the order of the group, to conclude that the prime order subgroup has no subgroups being prime. Finally, the message space must be restrained to this prime order subgroup.

Quadratic Residues. To make the ElGamal cryptosystem IND-CPA secure, the Decisional Diffie-Hellman assumption must be respected. As a matter of fact, one needs to find which type of groups satisfies the underlying assumption. A good technique is to restrict the messages to form the subgroup of prime order q of quadratic residues. In what follows we will introduce further explanations and examples to better understand the role of quadratic residues for the security of the ElGamal encryption scheme. Definition 3.2 (Quadratic Residue) An element a ∈ Z * n is said to be a Quadratic Residue modulo n if there exists x ∈ Z * n , such that x 2 ≡ a(mod n). Every such x is called a square root of a modulo n. If no such x exists, then a is called a Quadratic Non-Residue modulo n. We denote the set of all quadratic residues modulo n by QR n and the set of all quadratic non-residues by QNR n Quadratic residues are exactly those elements which can be written of the form g i where i is even: {g 2 , ..., g p-1 } are distinct quadratic residues, while {g, gg 2 , ..., gg p-1 } are quadratic non-residues. There exists an efficient algorithm based on Euler's criterion for deciding quadratic residuosity in Z * p , with p prime: Definition 3.3 (Euler's Criterion) Let p be an odd prime. Then a ∈ Z * p is a quadratic residue modulo p iff a p-1 2 ≡ 1 (mod p).

Therefore, by restricting all the messages to be Quadratic residues in a safe prime group, a polynomial time adversary cannot distinguish between elements as all the elements are then quadratic residues. Hereinafter, we will be using the Legendre symbol based on Euler's criterion for its convenient notation that reports the quadratic residuosity of a mod p. Definition 3.4 ( Legendre symbol) Let p be an odd prime , a an integer, such that gcd(a, p) = 1. The Legendre symbol (LS) is defined to be

a p = 1 if a ∈ QR p -1 if a ∈ QNR p

BREAKING ELGAMAL

Let p be a prime and g ∈ Z * p . Given a public key g x , the ElGamal encryption scheme encrypts a message m ∈ Z p by computing (g r , m.g xr ), with r chosen randomly in Z * p . Using the private key x, decryption can be done by first computing (g xr ) and then dividing to retrieve m. The cryptosystem is not semantically secure when g is a generator of Z * p , as some information about the plaintext is leaked. Specifically, the Legendre symbol of (m.g xr ) uncovers the Legendre symbolof the message m. In order to prove that ElGamal is IND-CPA under the DDH assumption, one may choose g to be the generator of the group in which the DDH assumption holds and restrict the message space to this group. This way, the system is semantically secure as given (g x ) and (g r ), the secret value (g xr ) cannot be distinguished from a random element in the group. Therefore, (m.g xr ) cannot be distinguished from a random element and an attacker cannot learn any information about the original message. In what follows, we will show an example on how to break the DDH assumption and ElGamal encryption scheme for Z * p groups. Example 4.1 (Breaking the DDH Assumption) In order to break the DDH assumption, one should be able to distinguish between two distributions having elements randomly distributed in a group.

Let p = 2q + 1 = 11 be the group on which we want to perform the attack (to ease the comprehension of the example, we consider small parameters size and not secure). Being prime, p has {p -1} elements, half being quadratic residues (QR) and the other half being quadratic non-residues (QNR). Given a tuple (g x , g y , g c ) it is hard to decide whether c = xy or c = z, where z is randomly generated. By LS, we can check the quadratic residuosity of the elements g x , g y and g c : x p = 1 if x is a square (i.e., quadratic residue), then g x p = 1 if x is even. Therefore, g x is quadratic residue if x is a quadratic residue too. In addition, if x or y are even, then xy is even and g xy is quadratic residue. Taking advantage of all the before-mentioned notions, we will give a detailed example on how to break the DDH assumption. A tuple is a valid DDH tuple if xy ≡ c mod p and can be written as (g x , g y , g xy ).

Let p = 11, the challenge is to distinguish whether (4, 5, 9) is DDH 0 or DDH 1 in G 11 . For Euler's criterion, a ∈ Z * p is a QR iff a p-1

2 ≡ 1 (mod p).

4 5 ≡ 1 mod11 5 5 ≡ 1 mod11 9 5 ≡ 1 mod11

By testing the quadratic residuosity of the three elements, one can notice that all of them are quadratic residues. In this case, we cannot distinguish between xy and z. Since the multiplication between two elements that are quadratic residues, results in an quadratic residue element, it might be that the third element of the tuple belongs to DDH 0 or DDH 1 . Consequently, we are not able to break the DDH assumption.

In this second example, the challenge is to distinguish whether (4, 5, 8) is (g x , g y , g xy ) or (g x , g y , g z ) in G 11 .

4 5 ≡ 1 mod11 5 5 ≡ 1 mod11 8 5 ≡ 1 mod11

One can notice that the third element of the tuple is not a quadratic residue. Being both quadratic residues, the multiplication between g x = 4 and g y = 5 must result in an quadratic residue element. However, g c = 8 results being a non quadratic residue element.

In this case, we are able to distinguish between xy and z by ensuring that (4, 5, 8) is DDH 1 and break the DDH assumption as a consequence. We emphasize on the importance of choosing a safe prime group p, to be able to work in the subgroup of prime order q by restricting the elements to form the subgroup of quadratic residues. This guarantees the difficulty of such attacks on the DDH assumption.

Example 4.2 (Breaking the ElGamal Scheme using a QR generator) Being in a group in which the DDH does not hold may leak information about the original

plaintext. An attacker able to calculate the quadratic residuosity of an encrypted message, can learn one bit of information about the original message. An attacker can check whether the encryption of a message is a QR or not and therefore deduce whether the original message is a QR too. In fact, by taking g xr ∈ QR

and encrypting the message as E(m,k) = (g r , m.g xr ),

one can notice that if m.g xr ∈ QR then m ∈ QR.

Consider the group G 11 , let x = 4 ∈ sk, r = 2 ∈ rnd, g = 3 ∈ QR and y = g x = 4 ∈ pk.

In the above example, the group G 11 has {1, 3, 4, 5, 9} as a subgroup of quadratic residues. Actually, encrypting a message m ∈ QR with a public key pk ∈ QR, results always in an encryption E(m,k) ∈ QR.

Thus, by using G 11 and taking messages belonging to its entire message space, one endangers the security of the scheme as he allows QR and QNR messages to be encrypted. An attacker able to calculate the quadratic residuosity of an element could learn one bit of information about the original message by performing the following attack: (c) Being m.g xr ∈ QR leaks the quadratic residuosity of m. In fact 1 11 = 1 ⇒ m ∈ QR. The previous example could also be adopted for QNR messages. In summary, the feasibility of calculating the quadratic residuosity of an element in a modulo prime groups, may leak information about the original message on top of groups that do not respect DDH.

(a) g ∈ QR, then (g xr ) is QR. (b) Check if E(m,k) p is QR or not. (c) If E(m,k) p ∈ QR,

STUDY OF LIBRARIES

We focus our study on manually checking whether the underlying groups in ElGamal implementations satisfy the Decisional Diffie-Hellman assumption. A summary of our results regarding 26 analyzed libraries can be found in Table 1. We split our work into three tasks to measure the correctness of the implementations. We first verify that the implementations use safe primes, next we check if they adopt quadratic residue generators to generate subgroups in which the DDH assumption holds. Finally, we analyze the message encoding techniques deployed to map the messages into the before-mentioned subgroups. This study led us to notice that a large number of the considered libraries are not IND-CPA secure as the encryption may leak at least one bit of information on the plaintext: 20 libraries do not respect the DDH assumption. Moreover, among these 20 libraries, 10 do not use a safe prime. In what follows, we describe in details the problems found in the investigated libraries using the following classification:

(A) Libraries that do not respect the DDH assumption. There are 20 libraries in this category. In this class we further classify the libraries that do not respect the DDH assumption due to 3 different concerns: libraries that do not deploy a safe prime, libraries that do not adopt a quadratic residue generator, and libraries that do not use a correct message encoding technique to map the messages into the intended subgroup.

(B) Libraries that do respect the DDH assumption.

There are 6 libraries in this category. However, they do not all use the same encoding technique. Thus, we describe in detail the 4 different encoding techniques, discussing their advantages and drawbacks.

Libraries' Relevance. This paper will provide a brief description on the relevance some of the chosen libraries for analysis. Belenios [START_REF] Belenios | Public source code of library n.1[END_REF] has been deployed on an online platform and it is used in more than 200 elections, both in academia and in education. Similarly, Helios [START_REF] Helios | Public source code of library n[END_REF] is used for the election of the International Association for Cryptographic Research members board, the ACM general elections, the election of UCLouvain president and for other student elections. On the other hand, the Estonian voting system (Estonia, 2017) has been used for the European Parliament elections, local government council elections and the election of the president of the Republic. Swisspost (Swisspost, 2018) then offers voting system services for cantons and municipalities in Switzerland, while Verificatum (Verificatum, 2017) is used in binding elections, student body elections and intra-party elections.

Libraries That Do Not Respect DDH

In this section, we will present the implementations that do not respect the conditions to achieve an IND-CPA secure ElGamal scheme. Working on groups modulo p, a secure ElGamal scheme has to adopt safe primes, a quadratic residue generator, and a message encoding technique to map the messages into a subgroup that respects the Decisional Diffie-Hellman assumption. Twenty out of twenty six libraries violate one or more of the before-mentioned conditions: all the libraries in this section do not employ message encoding techniques. Lack of Safe Prime. In this category, 10 libraries [START_REF] Diaz | Public source code of library n.4[END_REF][START_REF] Alves | Public source code of library n[END_REF][START_REF] Sidorov | Public source code of library n[END_REF][START_REF] Lee | Public source code of library n[END_REF][START_REF] Wang | Public source code of library n.9[END_REF][START_REF] Pankratiew | Public source code of library n.10[END_REF][START_REF] Pellegrini | Public source code of library n[END_REF][START_REF] Musat | Public source code of library n[END_REF]Libgcrypt, 2013;Moscow, 2019a) do not use safe primes. Instead, these implementations focus on generating large numbers and checking their primality. This method does not guarantee the generation of a safe prime. In fact, a safe prime of the form p = 2q + 1 where q is also a large prime, is essential as it forms a large prime subgroup of order q.

Conversely, using an arbitrary large prime results in a p -1 group order, that can be decomposed into small prime order subgroups. Hence, small prime order subgroups are exposed to subgroup attacks in which the discrete logarithm is easy to compute by using the Pohlig-Hellman algorithm [START_REF] Pohlig | An improved algorithm for computing logarithms over gf(p) and its cryptographic significance (corresp.)[END_REF] or the Pollard's rho algorithm [START_REF] Pollard | Monte carlo methods for index computation[END_REF].

Lack of QR Generators. In this category, we discuss the libraries that do not use quadratic residue generators. Among the 20 libraries that do not respect DDH, 5 libraries [START_REF] Nasr | Public source code of library n[END_REF][START_REF] Ridhuan | Public source code of library n.8[END_REF][START_REF] Elgamir | Public source code of library n[END_REF][START_REF] Pycrypto | Public source code of library n[END_REF][START_REF] Ioannou | Public source code of library n[END_REF] use a safe prime p = 2q + 1 but do not choose a quadratic residue generator. Using a safe prime without a quadratic residue generator does not guarantee a subgroup of prime order q in which the DDH assumption stands. In what follows we show an example on the feasibility of learning information about the plaintext when we do not employ a quadratic residue generator.

Example 5.1 (Breaking ElGamal without a QR generator) To break ElGamal without a QR generator, it is sufficient to break the underlying assumption. The DDH assumption does not hold in Z * p if g is a generator of Z * p . This is because the Legendre symbol of g a reveals whether a is even or odd. Given (g a , g b , g ab ), one can compute the LS and compare the least significant bit of a, b and ab, which allows to distinguish between g ab and a random element group. Having a distinguisher against DDH means having a distinguisher against ElGamal and therefore break ElGamal.

Lack of Encoding. We point out the relevance of message encoding mechanisms as a crucial requirement in ElGamal scheme. Despite generating a safe prime and choosing a quadratic residue generator, 5 libraries [START_REF] Botan | Public source code of library n[END_REF][START_REF] Riddle | Public source code of library n[END_REF][START_REF] Norvegia | Public source code of library n[END_REF]Pycryptodome, 2018;Swisspost, 2018) do not use a message encoding to map the messages into a valid subgroup. However, by adopting the standard encryption scheme of ElGamal, the message space is not restricted to the expected subgroup. This imply that even in the presence of a safe prime and consequently the presence of a subgroup of prime order generated by a quadratic residue generator, the message to encrypt is not mapped into the designed subgroup. Hence, an attacker can gain knowledge about the original message and expose the entire scheme to total insecurity. To better understand the importance of using a message encoding method, we display an attack on how to break a scheme that does not map messages into the intended subgroup (see example in Section 4).

Libraries That Do Respect DDH

In this section, we will present the implementations that respect the DDH assumption and therefore implement an IND-CPA secure ElGamal scheme. As mentioned in the previous section, a well implemented li-brary should adopt a safe prime, a quadratic residue generator, and a message encoding technique. Only 6 out of the 26 analyzed libraries [START_REF] Belenios | Public source code of library n.1[END_REF]Estonia, 2017;[START_REF] Helios | Public source code of library n[END_REF]Microsoft, 2019;Moscow, 2019b;Verificatum, 2017) respect all of the previously mentioned conditions. In the following paragraphs, we will discuss in detail the message encoding techniques implemented in these libraries. In particular, we can categorize four different techniques.

Limited Message Space and q-exponentiations

The Estonian and Verificatum In this paragraph, we will present two libraries that implement ElGamal using the same technique: the Estonian voting system and Verificatum. The Estonian government relies on Internet voting in a significant way for national elections. While the Estonian voting system (Estonia, 2017) is implemented in Java, Verificatum (Verificatum, 2017), which implements provably secure cryptography libraries for electronic voting systems, is implemented in JavaScript. To comply with the IND-CPA security of ElGamal, these two implementations adopt a safe prime, and generate the subgroup of prime order in which the DDH assumption holds. Both implementations allow messages m to be any integer from [1, p -1]. Hence, before encrypting, one checks if m is a QR by checking m q ≡ 1 mod p:

Proof 1 Euler's criterion states that a ∈ Z * p is a quadratic residue modulo p iff a p-1 2 ≡ 1 (mod p). Being q = p-1 2 , then a p-1 2 = a q ≡ 1 (mod p). If the equivalence is confirmed then m is encrypted as a QR, else the message is rejected and an error is raised (see Listing 1). In fact, these two implementations take as an input messages in Z * p and rejects half of the messages that are not QR instead of encoding them (also see Helios in Subsection 5.2.2). Besides that, using q-exponentiations to encrypt messages can be optimized as we will explain in Section 6. £ switch ( legendre (m)) { case 1:

return new ModPGroupElement(this, m); case -1:

throw new IllegalArgumentException("Can not encode as quadratic residue ") ; } // Negate if not a quadratic residue . var value = new LargeInteger (bytesToUse); return new ModPGroupElement(this, value);

¢ ¡

Listing 1: Limited space and q-exponentiations ElGamal encoding (Verificatum, 2017).

Encoding with q-exponentiations

Helios Helios [START_REF] Helios | Public source code of library n[END_REF], is a known library implemented in Python. It is used for voting systems and can be manipulated to meet the needs of the users. Helios, is vulnerable to ballot stuffing as a dishonest bulletin board could add ballots without anyone noticing [START_REF] Belenios | Public source code of library n.1[END_REF]. Being IND-CPA secure, ElGamal in Helios is implemented by generating a safe prime p = 2q + 1 where p and q are both large primes. It then selects a generator g of the subgroup of prime order q. Before encrypting a message m, a mapping to the prime order subgroup is done. As the implementation allows the message m to be any integer from [0, p -1], one computes m 0 = m + 1 (to avoid picking m = 0) and checks whether m 0 is a QR. If m 0 q ≡ 1 mod p then it outputs m 0 which belongs to the QR elements (as in Subsection 5.2.1), else, it outputs -m 0 . Please note that -m 0 mod p belongs also to the QR elements. Being a safe prime p and p ≡ 3 mod 4, ensures the fact that 1 is a square element and -1 is a non-square element. This is essential in turning a non-square element m into a square element -m.

After decryption, one obtains m and checks if m ≤ q. If m ≤ q then m 0 = m otherwise m 0 = -m. To recover the message, one computes m = m 0 -1 (see Listing 2).

Proof 2 This is because x 2 ≡ (-x) 2 mod p. So the squares of the first half of the nonzero numbers mod p give a complete list of the nonzero quadratic residues mod p. If p is an odd prime, the residue classes of {1 2 , 2 2 , ..., ( p-1 2 ) 2 } are distinct and give a complete list of the quadratic residues modulo p. So there are p-1 2 residues and p-1 2 non-residues. This gives a complete list as x 2 and (px) 2 are equivalent mod p:

x 2 ≡ y 2 mod p ⇔ p|x 2 -y 2 ⇔ p|(x -y)(x + y) ⇔ p|(x -y) or p|(x + y)
which is impossible if x and y are two different members of the set.

As we will see in the Section 6, it is possible to reduce to 2 the q-exponentiations, and therefore obtain a more efficient encoding process. £ if (encode m) { var y = m.add(BigInt .ONE); var test = y.modPow(pk.q, pk.p); if ( test . equals ( BigInt .ONE)) { this .m = y; } else this .m = y. negate () .mod(pk.p); }

¢ ¡

Listing 2: ElGamal encoding with q-exponentiations [START_REF] Helios | Public source code of library n[END_REF].

Hard Decoding

Belenios and Microsoft Belenios [START_REF] Belenios | Public source code of library n.1[END_REF] is a verifiable voting system built upon Helios. It can be used to organize elections and perform verification. Contrary to Helios, Belenios provides eligibility verifiability as anyone can check that ballots are coming from legitimate voters: each voter receives a private credential, while the election server receives only the corresponding public credential. Therefore, even if the election server is compromised, no ballot can be added. Microsoft Election guard (Microsoft, 2019) is a library that verifies voting ballots. Concerning ElGamal encryption scheme a message m is encoded as g m where g is the QR generator of the prime order subgroup: every element written in the form of g m belongs to the subgroup generated by g. The choice of using the exponential version of ElGamal is to benefit from turning the multiplicative homomorphism of ElGamal into an additive one. After decryption, one should compute the discrete logarithm of g m in order

to recover the initial message m. This is possible by using Pollard-lambda algorithm or brute force only if m is taken from a small subset and not from the entire interval {0, ..., q -1}. Being in a subgroup of prime order q, where q is a large prime, it is not possible to decompose the subgroup in smaller subgroups (Lagrange Theorem [START_REF] Pollard | Monte carlo methods for index computation[END_REF]) since the computation of the discrete logarithm is unfeasible in general (see Listing 3). £

¢ ¡

Listing 3: Hard decoding implementation [START_REF] Belenios | Public source code of library n.1[END_REF].

Encoding with 2-exponentiations

Moscow Voting System For the elections of September 2019, the Russian government decided to employ an electronic voting system (Moscow, 2019a) to elect governors for local parliaments in Moscow. In July 2019, the source code, developed by the Moscow Department of Information Technology, was made public to test its vulnerabilities. At that time, the Moscow voting system was discovered to be subjected to two attacks by researchers [START_REF] Gaudry | Breaking the encryption scheme of the moscow internet voting system[END_REF].

In the first test, the researchers exploited the fact that the keys used are small: three keys of 256 bits were used. Discrete logarithms defined by small primes are easy to calculate in feasible time. Therefore, one can compute the discrete logarithm and recover the secret keys used for decryption. Moreover, one can decrypt messages employing the same time as a legitimate possessor of secret keys. After reporting this issue, the developers of Moscow voting system increased the key size to 1024 bits. However, a second test was made to verify the security of the modified version. In this version, the message space was not restricted to the subgroup of quadratic residues as any message was allowed to be encrypted. By relying on subgroup attacks, one can get enough information about the voter's choice and indeed can reveal one bit of information about the original message (see Section 4). Therefore the Decisional Diffie-Hellman assumption did not hold and the system leaked strong information. Two days before the elections, the developers modify the source code (Moscow, 2019b) and adopt an efficient method to secure their voting system. To map a message m into the QR subgroup, it is sufficient to square the message: m → m 2 (see Listing 4).

Proof 3 The quadratic residue theorem states that a ∈ QR if ∃ x s.t. x 2 ≡ a(p). Let m = x, then m 2 ∈ QR if m 2 ≡ m 2 (p), which can be trivially satisfied.

After decryption, one obtains m by calculating its modular square root: m = c q+1 2 [START_REF] Nishihara | A remark on the computation of cube roots in finite fields[END_REF]. The algorithm computes the square root of c iff p ≡ 3 mod 4, which is always the case when using a safe prime. As a matter of fact, the underlying group in this last version respects the DDH assumption. We will discuss the adopted method in Section 6. £ const sessionKey = trimBigInt (xoredRandomBigInt, this .moduleP.bitLength() -1); const squaredData = dataAsBI.modPow(new BigInt('2 ') , this .moduleP); const a = this . generatorG .modPow(sessionKey, this .moduleP). toString () ; const b = this .publicKey .modPow(sessionKey, this .moduleP) . multiply (squaredData) .remainder( this .moduleP) . toString () ;

¢ ¡

Listing 4: ElGamal encoding with 2-exponentiations (Moscow, 2019b).

COMPARISON OF ENCODINGS

In the previous section, we have seen 4 different encoding techniques of ElGamal that comply with the DDH assumption. In Table 2, we summarize the four techniques by giving a general overview on the encoding and the decoding processes.

T1 The first message encoding technique (T1) checks whether a message m is a QR or not by checking the following equivalence: m q ≡ 1 (p).

If the equivalence holds, then the message is encrypted, otherwise an error is raised and the message is rejected. The decoding operation is simple as one outputs directly the message m.

T2

The second message encoding technique (T2) uses the same method as the previous one, but instead of raising an error and rejecting the messages, it maps the message as -m. For what concerns the decoding process, one first checks if m < q and output m, otherwise it outputs -m.

T3

The third message encoding technique (T3) maps a message m as g m . The decoding mechanism is hard in general and can be only applied on a small subset of messages in which the computation of discrete logarithm can be solved by brute force. T1: Limited msg space & q-expon. T2: q-expon. T3: m-expon. T4: 2-expon.

Encoding m q ≡ 1 (p)? m : error m q ≡ 1 (p)? m : -m g m m 2 Decoding m m < q ?: m : -m log g (g m ) m q+1 2

T4 Concerning the fourth message encoding technique (T4), one maps a message m as m 2 into the subgroup of order q. This squaring technique is sufficient to map any message as a QR element.

In addition, it is efficient as it needs only 2 exponentiations for encoding any message. To decode, one computes the square root by modular exponentiation of m: m q+1 2 to recover the original message.

Whereas in T4, the encoding technique is faster than T1 and T2 (2-exponentiations is more performant than q-exponentiations as q is large), the decoding process is T1 and T2 is faster. However, for what concerns electronic voting systems, usually several encryptions are made and only one decryption is needed to reveal the result of an election. We conclude that T4 is more efficient to apply to electronic voting systems. Additionally, as reported in the note on Moscow voting systems [START_REF] Gaudry | Breaking the encryption scheme of the moscow internet voting system[END_REF], this technique is efficient since the decryption (q-exponentiations) is usually done on high-end servers, while the encryption (2-exponentiations) is done on the voter's device. In addition, T1, T2, T3, and T4 implement a QR generator using q-exponenentiations since they check its quadratic residuosity by calculating g q (p). However, one can simply implement a quadratic residue generator by using only 2-exponentiations instead of using q-exponentiations (q-exponentiations are used in [START_REF] Belenios | Public source code of library n.1[END_REF][START_REF] Helios | Public source code of library n[END_REF]Microsoft, 2019;Moscow, 2019b;Verificatum, 2017) for the quadratic residue generator). But clearly, a more direct and efficient way to calculate the generator is by fixing it in advance. For example g = 4 if we are working in Z * p . Note that the performance of the encoding is more important than the performance of the generator calculation, which occurs only once at the initial phase of the voting process. Moreover, the performance of the decoding is also less important than the encoding in a voting process as discussed previously. We provide a reference implementation in Ocaml [START_REF] Rémy | Using, understanding, and unraveling the ocaml language. from practice to theory and vice versa[END_REF] (see Listing 5) in which we apply the encoding and decoding process as in T4. In addition, in our implementation, the generation of the quadratic residue generator differs from all the other implementations as we use 2-exponentiations instead of q-exponentiations.

£

( * Generate a safe prime of the form p = 2q + 1 * ) let rec random safe prime nbits = let q = sample ( nbits -1) in let q = Z.nextprime q in let p = Z.succ (Z. shift left q 1) in if Z.probab prime q 10 <> 0 && Z.probab prime p 10 <> 0 then p else random safe prime nbits ( * Generate a QR generator * ) let generator pbits p = let q = Z. shift right p 1 in let g = Z.succ ( sample le pbits (Z.sub p (Z. of int 2)) ) in Z.powm g (Z. of int 2) p ( * Define the group * ) let sample group pbits = let p = random safe prime pbits in let g = generator pbits p in { pbits = pbits } ( * Encode the message as a QR element * ) let encode gr m = Z.powm (Z.succ m) (Z. of int 2) gr .p ( * Encryption * ) let encrypt gr pk m = if (( Z.leq Z.zero m) && (Z.lt m (Z.pred (q gr) ) ) ) then let r = sample le (gr . pbits -1) (q gr) in (Z.powm gr.g r gr .p, mulm gr (Z.powm pk r gr . p) (encode gr m)) else raise ( Invalid argument "ElG encryption") ( * Decryption * ) let decrypt gr sk (u,v) = let mult = Z.mul (Z.pred (q gr) ) sk in let modulo = Z.powm u mult gr.p in let dec = mulm gr v modulo in decode gr dec ( * Decoding * ) let decode gr m = let p = gr .p in let q = q gr in let r = Z.powm m (Z. shift right (Z.succ q) 1) p in let m = if Z.leq r q then r else (Z.sub p r ) in (Z.pred m)

¢ ¡

Listing 5: Our Ocaml implementation using a QR Generator & 2-exponentiations for an efficient message encoding.

During our analysis, we have discovered a number of ElGamal scheme implementations that are not IND-CPA secure since they do not respect the DDH assumption. On one hand, some implementations do not employ safe primes, an essential condition to form subgroups of large prime order in which the DDH assumption holds. mer, 2009;[START_REF] Orr | SAC '15[END_REF], which are used e.g. in the Estonian I-voting system [START_REF] Springall | Security analysis of the estonian internet voting system[END_REF]. We leave this as future work.

  the attacker can learn that the message m ∈ QR, as the multiplication between QR elements result always in a QR element. (d) If E(m,k) p ∈ QNR, then the attacker can learn that the message m ∈ QNR. Let us check E(1,5) = (9, 5): (a) 3 11 = 1 ⇒ g ∈ QR, 3 8 11 = 1 ⇒ (g xr ) ∈ QR. (b) 5 11 = 1 ⇒ E(1,5) ∈ QR.

  type factor = elt partial decryption let eg factor x {alpha ; } = let zkp = "decrypt |" ˆG. to string (g ** ˜x) "|" in alpha ** ˜x, fs prove [| g; alpha |] x (hash zkp) let check ciphertext c = Shape. forall (fun {alpha ; beta} -> G.check alpha && G.check beta) c

Table 2 :

 2 Message Encoding Comparison.

  On the other hand, other implementations do not apply message encoding mechanisms or use Quadratic Residue Generators. As a consequence, 20 out of the 26 analyzed libraries may leak one bit of information about the original message and therefore, may endanger the validity of an election. Finally, after comparing four different message encoding techniques that satisfy the DDH assumption, we conclude which implementation is most convenient for voting systems. We focused the current study on manually analyzing the IND-CPA security of open source code libraries of ElGamal encryption scheme. However, it is also possible to check the IND-CPA (in-) security when source code is not available. In fact, by applying the technique discussed in the Example 4.2 of Section 4, one can black-box test applications. In particular, such tests can be applied to ElGamal encryptions obtained by Hardware Security Modules (HSM) (Volka-