Decentralized Evaluation of Quadratic Polynomials on Encrypted Data 

Get Complete Project Material File(s) Now! »

Provable Security

The first definition and proof of security dates back to Shannon [Sha49] in 1949. In his article, he defines the notion of perfect secrecy in the sense of information theory and gives the example of the One-Time Pad scheme which is perfectly secure. However, this scheme is not convenient as the size of the key needs to be at least equal to the size of the message.
To avoid this limitation, security proofs are no longer necessarily made in the sense of infor-mation theory but are most often reductions of mathematical problems for which the complexity is widely accepted.
For example, the RSA encryption scheme is based on the factoring problem: given a very large number product of two prime numbers n = pq, the goal is to find the two prime factors p and q. The decomposition being part of the secret key of the encryption scheme, breaking the problem directly breaks the security of RSA.
In this manuscript, we will use two other mathematical problems often used in cryptography defined on a group G generated by g. The Discrete Logarithm (DL) problem is, given an element X of G, to find the exponent x such that X = gx. The other is the Computational Diffie-Hellman (CDH) problem [DH76] (1976): given two elements X = gx and Y = gy of G, the goal is to compute Z = gxy. For these two problems, the bigger is the number of elements in G, the more difficult is the problem. The security of cryptographic schemes is thus usually defined with a security parameter configuring the size of the group. Then, we make the assumption that the problem is difficult and if attacks are improved or found, it is possible to adapt the level of security with the security parameter.
A variant of the CDH problem is the Decisional Diffie-Hellman (DDH) problem: given three elements X = gx, Y = gy and Z of a cyclic group, the goal is this time to decide if Z = gxy or not. It is at the core of the El Gamal cryptosystem [ElG84] (1984), the second main public-key encryption scheme that we will use a lot all along this manuscript.

Advanced Security Goals

The cryptographic world where Alice and Bob are discussing secretly together is not relevant anymore. We live in a connected world where some scenarios imply to deal with thousands of users while still achieving some kind of security. There are users and servers, different access rights for each of them and sometimes there are various authorities at the same time having different abilities. As the number of persons involved increases and the technologies are improv-ing, more specific definitions of security notions are necessary. In this section, we broach the advanced and modern thematic to improve the privacy of users by a better control of his data or guarantees on sensitive systems.
A Multi-User World. Working in a multi-user setting means having to consider different roles for each user. An honest user follows the protocol, an honest-but-curious user follows the protocol but tries to retrieve information from the communications he sees passing by and finally a malicious user tries to actively attack the protocol. If several users try to attack together with a common goal, we talk about collusion but an attacker can also corrupt others. Some schemes allow a limited number of collusions/corruptions, i.e. they are proven safe until this threshold is reached.
Privacy in a World of Information. For the scenarios studied in this manuscript, we will consider Uma, a user who wants to protect her privacy while wishing to take advantage of the technological advances of her time. She therefore uses a cloud to store her data but would like to allow a company to study her records, such as allowing it to do statistical studies of cancers on her medical record but only if the company is forced by the system to recover only this information and nothing more. Uma would also like to vote electronically at the next election but requests that anonymity is guaranteed as well as the result of the election. Finally, Uma would like to be able to log in anonymously while being properly authenticated to a system. She accepts that, in return, if she misuses and abuses the system, her anonymity may be revoked by a judge.
All of these scenarios require new and more complex security concepts than the one histori-cally used. Cryptology should not be a hindrance to the use of new technological advances.


Decentralized Cryptography is one of the main directions of research in cryptography, espe-cially in a concurrent environment of multi-user applications, where there is no way to trust any authority. Recently, the rise of blockchain’s applications also showed the importance of decen-tralized applications. However, the blockchain mainly addresses the decentralized validation of transactions, but it does not help in decentralizing computations. For the computational pur-pose, though general solutions can be achieved via multi-party computation, reasonably efficient solutions only exist for a limited number of protocols, as decentralization usually adds design constraints to protocols: in broadcast encryption [FN94], the decentralized protocol in [PPS12] is much less efficient than the underlying original protocol [NNL01]; in attribute-based encryp-tion [SW05], the decentralized scheme [CC09] implies some constraints on the access control policy, that are removed in [LW11], but at the cost of using bilinear groups of composite order with 3 prime factors, etc…
In the last decade, the most active research direction was about computing over encrypted data, with the seminal papers on Fully Homomorphic Encryption (FHE) [Gen09] and on Func-tional Encryption (FE) [BSW11, GKP+13, GGH+13]. FE was generalized to the case of multi-user setting via the notion of multi-input/multi-client FE [GGG+ 14, GGJS13, GKL+13]. It is of practical interest to consider the decentralization for FHE and FE without need of trust in any authority. In FE, the question in the multi-client setting was recently addressed by Chotard et al. [CDG+ 18a] for the inner product function and then improved in [ABKW19, CDG+ 18b], where all the clients agree and contribute to generate the functional decryption keys, there is no need of central authority anymore. Note that, in FE, there are efficient solutions for quadratic functions [Gay16, BCFG17] but actually, only linear function evaluations can be decentralized as none of the methods to decentralize linear schemes seems to apply, and no new method has been proposed so far.


Sometimes confidentiality is not the most desired property for a system as it does not protect the sender or the receiver. In 1981, Chaum wrote the first article [Cha81] proposing a scheme able to hide the participants of a communication.
A user is anonymous when his name is either not known or not given. In practice, the anonymity is defined as the property to not be identifiable within a set. Hence, the anonymity notion can be obtained throught an unlinkability property. In the next two sections we will see use-cases of anonymity addressed in this thesis.
Electronic voting
There are mainly three ways to construct electronic voting schemes: from blind signatures, from additively homomorphic encryption and from shuffles performed by mix-networks. The first method requires to have interactions during the voting phase: the voter needs to communicate with an authority so that, she can blindly sign his vote. The second method requires to make a proof at the time of the vote that the ballot is a valid one (e.g. the ballot is the encryption of 0 or 1 but nothing else). The last one is the solution studied in this thesis.
A shuffle of ciphertexts is a set of ciphertexts of the same plaintexts but in a permuted order such that it is not possible to trace back the senders after decryption. It can be used as a building block to anonymously send messages: if several servers perform a shuffle successively, nobody can trace the messages. More precisely, one honest mix-server suffices to mask the order of the ciphertexts even if all the other ones are dishonest. Moreover increasing the number of mix-servers leads to a safer protocol but also increases its cost. The succession of shuffles constitutes the notion of a mix-net protocol introduced by Chaum [Cha81], with applications to anonymous emails, anonymous routing, but also eletronic voting.
Anonymous authentication
In an anonymous credential scheme, a user asks an organization (a credential issuer) for a credential on an attribute, so that he can later claim its possession, even multiple times, but in an anonymous and unlinkable way.
Usually, a credential on one attribute is not enough and the user needs credentials on multiple attributes. Hence the interest in attribute-based anonymous credential schemes (ABC in short): depending on the construction, the user receives one credential per attribute or directly for a set of attributes. One goal is to be able to express relations between attributes (or at least selective disclosure), with one showing. As attributes may have different meanings (e.g. a university delivers diploma while a city hall delivers a birth certificat), there should be several credential issuers. Besides multi credential issuers, it can be useful to have a multi-show credential system to allow a user to prove an arbitrary number of times one credential still without breaking anonymity. For that, the showings are required to be unlinkable to each other.


Nevertheless, with perfect anonymity comes the threat of malicious use of the system as it is not possible to identify anyone, even in case of misbehavior. Thus, in tracing scheme, one takes advantage of computational anonymity to find guilty members who can be at any level: a guilty sender of an encrypted message, a guilty signer, a guilty verifyer or a guilty authority. Collusions between users with different parts can also help to combine powers.
Here comes the traitor-tracing schemes [CFN94, CFNP00] with application to group sig-natures, group encryption [LYJP14], broadcast encryption, inner-product functional encryp-tion [DPP20] or identity-based encryption [BBP19]. When the number of traitors is not bounded, the scheme is said fully traceable. To identify a culprit, one can add a new authority possessing a secret or one can request public traceability and in such a case, no secret is needed: everyone can find a traitor in case of misbehavior.
However, finding a guilty is not enough. When someone is declared guilty one needs to have guarantees against defamation of users or authorities. In particular, the exculpability property ensures that no coalition of authorities can convincingly accuse an innocent user in a group signature scheme. After finding a traitor and having the guarantee of its culpability, one can eventually revoke him but revokability is usually a more difficult property to achieve. When it is not possible, a solution is to combine traceability with decentralization. Hence, even a malicious authority cannot defame a user easily, its ability to judge or revoke being shared among parties.



The presented scenarios require to develop new cryptographic tools. Secret sharing techniques allow decentralization by replacing an authority by a group of members. Indeed, thanks to Shamir [Sha79], it is possible to decompose a secret key s in parts so that s = i si, each user Ui of a group possesses s ciphertext alone.
However, they can decrypt by playing with the other members of the group which implicitly reconstruct the secret s = i si.
All along this manuscript we will use another key ingredient: the homomorphism.

Homomorphic Encryptions

For some generic encryption scheme, if we modify a ciphertext it becomes a completely random string and the content is lost as it is not decryptable anymore even with the secret key. Not being able to manipulate ciphertexts is called non-malleability. For a long time, this property ensured the security of encryption schemes: either we know the secret key and we can find the message again or we do not know it and all the operations we can do will not help.
However, with the RSA encryption scheme, if we multiply two encryptions of m1 and m2 together, we obtain the ciphertext of the message m1 × m2 : if c1 = me1 mod n and c2 = me2 mod n then c1 • c2 = (m1 × m2 )e mod n. A cryptosystem with such property is said to be multiplicatively homomorphic as one can operate on the clears by multiplication. With the Paillier cryptosystem [Pai99], if we multiply two encryptions of m1 and m2 together, we obtain the ciphertext of the message m1 + m2. This scheme is thus additively homomorphic.
The homomorphism property can be of great interest: if Alice and Bob want to give a com-mon gift to Charlie but none of them want to tell how much he gave. They both encrypt the amount with an additively homomorphic scheme and can, thanks to the property of homomor-phism, multiply their two encryptions together and send the result to Charlie. She will be able to decrypt it and the message will correspond directly to the sum of the two amounts.
Another common usage of homomorphism with encryption is for refreshing a ciphertext: by multiplying an encryption of 1 by a ciphertext of m, encrypted with a multiplicatively homomorphic scheme, one can obtain a new encryption of m thanks to the usage of the neutral element 1 for the multiplication. The new ciphertext while still encrypting the same message can be indistinguishable from the original one. A similar relation can be obtained with an encryption of 0 and an additively homomorphic scheme.
Generically, an encryption scheme in which making an operation on ciphertexts is equivalent to encrypting the result of a “twin operation” on the clears is called homomorphic. The seminal paper of Gentry [Gen09] published in 2009 combines for the first time both multiplicative and additive properties, and thus, allows the evaluatation of any function on ciphertexts. This scheme is called fully homomorphic encryption (FHE).

Homomorphic Signatures

Similarly to homomorphic encryption, one can define homomorphic signatures. The notion dates back to Rivest in a series of talks [Riv00] and Johnson et al. [JMSW02], with notions in [ABC+12].
They can help for computations on certified data. For example, Alice has n grades mi all individualy signed into σi on a remote server. Later, the server is asked to perform an authenticated computation of a mean of the data. Thus, it computes σ = f(σ1, . . . , σn) possible thanks to homomorphism and M = f(m1, . . . , mn) and publishes the result (M, σ). Then, anyone can check that the server correctly applied f to the data by verifying that σ is a valid signature.
The linearly-homomorphic signatures, that allow to sign vector sub-spaces, were introduced in [BFKW09], with several follow-ups by Boneh and Freeman [BF11b, BF11a]. With a linearly homomorphic signature scheme, from a signature σ1 on the message m1 and σ2 a signature on the message m2, it is possible to compute for all α, β, the signature σ = ασ1 + βσ2, a valid signature on the message m = αm1 + βm2.
As for encryption, a signature scheme can also be multiplicatively homomorphic: with the RSA signature, if we compute σ1 ×σ2 = (m1 •m2)d mod n, this is a valid signature of the message m1 • m2 from two valid signatures σ1 of m1 and σ2 of m2. Even if this scheme illustrated the homomorphism, it is, as presented, not secure.

Security with Homomorphism

The security of an homomorphic scheme is different and needs to be strengthen. For example, an attacker seeing a signature of a message m, could simply forge the signature of m + m, which would break the basic notion of security. He does not know the keys but he is able to compute a valid signature of a new message (here m + m).
With the RSA signature scheme above, an attacker can forge any message of his choice: if an attacker asks the signature σ = (m • re)d mod n, this is a valid signature of the message m • re. However with that, the attacker can forge the signature σ∗ = σ/r which is a valid signature of m while the signer does not know m.
To include the malleability in the security, we will require that it is not possible for an attacker to provide a signature outside the space generated by the signatures already given. A similar change in the security definition is of course needed for all the homomorphic schemes and thus, encryption ones.

Homomorphic Zero-Knowledge Proofs

The last kind of schemes we will intensively use in this thesis is the zero-knowledge proofs. They were introduced for the first time by Goldwasser, Micali and Rackoff [GMR85] in 1985.
A zero-knowledge proof is a protocol where a prover knowing a witness w makes a proof that a statement x ∈ L is true to a verifier. The zero-knowledge property implies that the verifier does not learn more than the fact is true or false and nothing about the witness. In 1986, Goldreich, Micali and Wigderson [GMW87] shows that any language in NP possess zero-knowledge proofs.
For example, Bob can make a proof of Diffie-Hellman tuple to Alice: Alice thanks to the proof can verify if the tuple (X = gx, Y = gy , Z) is or not a Diffie-Hellman (if Z = gxy or not) but she will not learn any of the exponents involved. The language is this case is the set of Diffie-Hellman tuples and the witness of Bob can be the pair of scalars x and y.
The showing of a proof can be interactive or non-interactive if the verifier after having received elements from the prover can check the proof latter without any further interaction with the prover. Moreover, the zero-knowledge proofs is said of statements if it proves a relation (as a proof of Diffie-Hellman tuple), or of knowledge if it proves the knowledge of a witness: when Bob wants to authenticate himself to a system, he needs to show he knows the password. A non-interactive zero-knowledge proof of knowledge is also called signature of knowledge.
With the Groth-Sahai [GS08] scheme, it is possible to combine together different proofs into a unique one. This property can be viewed as an homomorphic property: the combinations of the proofs creates a proof of a relation of statements.
In this thesis, zero-knowledge proofs will be used sometimes enhanced of the homomorphic property to prove that a ciphertext is correctly construted or for authentication.

Table of contents :

1 Introduction 
1.1 Classical Cryptography
1.1.1 Confidentiality
1.1.2 Authentication
1.1.3 Provable Security
1.2 Advanced Security Goals
1.2.1 Decentralization
1.2.2 Anonymity
1.2.3 Traceability
1.3 Homomorphism
1.3.1 Homomorphic Encryptions
1.3.2 Homomorphic Signatures
1.3.3 Security with Homomorphism
1.3.4 Homomorphic Zero-Knowledge Proofs
1.4 Contributions
1.5 Organization of the Manuscript
2 Preliminaries 
2.1 Notations and Usefull Notions
2.2 Provable Security
2.3 Computational Assumptions
2.4 Cryptographic Primitives
2.4.1 (Homomorphic) Encryption
2.4.2 (Homomorphic) Signature
2.4.3 (Homomorphic) Proof
3 Decentralized Evaluation of Quadratic Polynomials on Encrypted Data 
3.1 Freeman’s Approach
3.1.1 Notations
3.1.2 Freeman’s Scheme with Projections
3.1.3 Homomorphic Properties
3.1.4 Security Properties
3.1.5 Re-Encryption
3.1.6 Verifiability
3.1.7 Distributed Decryption
3.2 Optimized Version
3.2.1 Instantiation
3.2.2 Security Properties
3.2.3 Decentralized Homomorphic Encryption
3.2.4 Efficiency
3.3 Applications
3.3.1 Encryption for Boolean Formulae
3.3.2 Group Testing on Encrypted Data
3.3.3 Consistency Model on Encrypted Data
4 Linearly-Homomorphic Signatures 
4.1 Definition, Properties and Security
4.2 Our One-Time LH-Sign Scheme
4.3 FSH LH-Sign Scheme
4.4 Square Diffie-Hellman
4.5 SqDH LH-Sign Scheme
4.5.1 A First Generic Conversion
4.5.2 A Second Generic Conversion
5 MixNet 
5.1 Our Scheme: General Description
5.2 Our Scheme: Full Description
5.3 Scalability
5.3.1 Constant-Size Proof
5.3.2 Efficiency
5.4 Security Analysis
5.4.1 Proof of Soundness
5.4.2 Proof of Privacy: Unlinkability
5.4.3 Proof of Correctness
5.5 Applications
5.5.1 Electronic Voting
5.5.2 Message Routing
6 Anonymous Credentials 
6.1 Overview of our New Primitives
6.1.1 Tag-based Signatures
6.1.2 Signatures with Randomizable Tags
6.1.3 Aggregate Signatures
6.2 Aggregate Signatures with Randomizable Tags
6.2.1 Anonymous Ephemeral Identities
6.2.2 Aggregate Signatures with Randomizable Tags
6.2.3 One-Time ART-Sign Scheme with Square Diffie-Hellman Tags (SqDH)
6.2.4 Bounded ART-Sign Scheme with Square Diffie-Hellman Tags (SqDH)
6.3 Multi-Authority Anonymous Crendentials
6.3.1 Definition
6.3.2 Security Model
6.3.3 Anonymous Credential from EphemerId and ART-Sign Scheme
6.4 SqDH-based Anonymous Credentials
6.4.1 The Basic SqDH-based Anonymous Credential Scheme
6.4.2 A Compact SqDH-based Anonymous Credential Scheme
6.5 Traceable Anonymous Credentials
6.5.1 Traceable Anonymous Credentials
6.5.2 Traceable SqDH-based Anonymous Credentials
6.5.3 Groth-Sahai Proof for Square Diffie-Hellman Tracing
6.6 Related Work
7 Conclusion 
A Joint Generation of Square Diffie-Hellman Tuples
B Another Bounded SqDH-Based ART-Sign


Related Posts