Difference between revisions of "CertSGN"

From certFHE Community KB
Jump to navigation Jump to search
 
(17 intermediate revisions by 2 users not shown)
Line 5: Line 5:
 
The authors use this technique to construct examples of encryption schemes that, theoretically can handle any algebraic function on encrypted data.  
 
The authors use this technique to construct examples of encryption schemes that, theoretically can handle any algebraic function on encrypted data.  
  
The homomorphic encryption scheme <b>CSGN</b>, a symmetric homomorphic encryption scheme with plaintext <math> \mathbb F_2 </math> was introduced in the same article. The latter plays an essential role the architecture of a privacy-preserving contact tracing application, developed by certSign as part of the TAMEC project <ref>https://www.certsign.ro/en/projects </ref>.
+
The homomorphic encryption scheme <b>CSGN</b>, a symmetric homomorphic encryption scheme with plaintext <math> \mathbb F_2 </math> (the field with two elements) was introduced in the same article. The latter plays an essential role the architecture of a privacy-preserving contact tracing application, developed by certSign as part of the TAMEC project. <ref>https://www.certsign.ro/en/projects </ref>
  
 
The content of the article is protected under the law by two patents. <ref>U.S. Patent Appln. No. 14/936,097 and
 
The content of the article is protected under the law by two patents. <ref>U.S. Patent Appln. No. 14/936,097 and
 
European Patent Appln. No. EP 15193706.7</ref>
 
European Patent Appln. No. EP 15193706.7</ref>
 +
 +
A toy implementation can be found here : https://github.com/certfhe/CSGN
 +
 +
== Ring homomorphic encryption schemes from monoidal ones. The blueprint ==
 +
 +
Given a monoid <math> M </math> and any commutative ring <math> R </math> with unity, one can associate to these an algebra <math>R[M] </math>. As an <math>R</math>-module, the monoid algebra <math> R[M]</math> is free with a basis consisting of the symbols <math>[x] </math>, where <math>x \in M </math>.
 +
 +
The multiplication in this algebra is defined by extending <math> [x] \cdot [y] = [xy]</math> in an <math>R</math>-bilinear manner. Any element <math> a \in R[M]</math> has a unique representation
 +
 +
<center><math>  a = \sum_{x \in M} a_x[x],</math> </center>
 +
 +
where <math>a_x=0 </math> for all but finitely many <math> x\in M </math>. The product of two elements <math>a,b \in R[M] </math> is given by
 +
 +
<center><math>  ab = \sum_{x \in M} \left( \sum_{yz=x} a_yb_z \right)[x]. </math> </center>
 +
 +
We note that the identity element with respect to multiplication is <math>1[e] </math>, where <math> e</math> is the identity element of <math> M</math>. If <math> M </math> is a group then the monoid algebra described above is called a group algebra.
 +
 +
If <math>M,N </math> are two monoids, a monoid homomorphism  <math>\phi : M \to N </math> induces a natural <math>R</math>-algebra homomorphism <math>\phi_R : R[M] \to R[N] </math>.
 +
 +
We also remark that for any <math>R</math>-algebra <math> A </math>, there is a natural <math>R</math>-algebra homomorphism <math> \epsilon : R[A] \to A </math> given by
 +
 +
<center><math>\epsilon \left( \sum_{x \in R} r_x[x] \right) = \sum_{x \in R} r_x x</math>.</center>
 +
 +
=== The patented blueprint ===
 +
 +
Let <math>R </math> be a finite ring and let <math>(G,H,E,D)</math> be a monoid homomorphic encryption scheme. This implies that the ciphertext <math>G</math> and the plaintext <math>H</math> are monoids and the decryption algorithm <math>D: G \to H</math> is a monoid homomorphism.
 +
 +
Consider an efficiently computable <math>R</math>-character <math> \chi : H \to A</math>, where <math>A </math> is a finite <math>R</math>-algebra.
 +
 +
As explained above, the monoid homomorphism <math>D:G\to H </math> induces the <math>R </math>-algebra homomorphism <math>D_R : R[G] \to R[H]</math>. At the same time, <math>\chi </math> induces an <math> R</math>-algebra homomorphism <math>\chi_R : R[H] \to R[A] </math>. The <math>R</math>-algebra homomorphism <math>\mathrm{Dec}</math> is defined as
 +
 +
<center><math>\mathrm{Dec} = \epsilon \circ \chi_R \circ D_R : R[G] \to R[H] \to R[A] \to A </math>,</center>
 +
 +
defined by the formula
 +
 +
<center><math>\mathrm{Dec} \left( \sum_{g \in G} a_g[g] \right) = \sum_{g \in G} a_g \chi(D(g)) </math>.</center>
 +
 +
Let us denote by <math>S </math> the image of <math>\chi </math> in <math> A </math>. For the decryption algorithm to remain secure, one needs the assumption that <math>\chi </math> is not the trivial character, a condition that is always assumed in the blueprint.
 +
 +
We now describe a <b>ring</b> homomorphic encryption scheme with plaintext <math>A</math> and ciphertext <math>R[G]</math>. Let <math>S</math> be the image of <math>\chi </math> in <math> A </math> and fix some integer <math> k \geq 1 </math> such that the elements of the form <math> \sum_{i=1}^k r_i s_i </math>, with <math>s_i \in S </math> is the whole <math> R</math>-algebra <math>A</math>.   
 +
 +
* <math>\mathrm{Enc}: </math>  Consider a fixed tuple <math>(r_1, \dots, r_k) \in R^k </math>. For a plaintext <math>m \in A </math> consider <math>(h_1, \dots, h_k) \in H^k </math> such that <math>m = \sum_{i=1}^k r_i \chi(h_i) </math>. Then
 +
 +
<center><math> \mathrm{Enc}(m) = \sum_{i=1}^k r_i[E(h_i)]</math> .
 +
</center>
 +
 +
* <math>\mathrm{Dec}: </math> The decryption algorithm is given by
 +
 +
<center> <math>\mathrm{Dec}\left(\sum_{g \in G} a_g[g] \right) = \sum_{g \in G} a_g \chi(D(g)).</math> </center>
 +
 +
The authors of the article prove that <math>(R[G], R, \mathrm{Enc}, \mathrm{Dec}) </math> is a ring homomorphic encryption scheme and the security of this scheme is the same as the security of the monoid encryption scheme <math>(G,H,E,D)</math> that one starts with.
 +
 +
== A symmetric ring homomorphic encryption scheme ==
 +
 +
In this section we describe the <b> CertSGN </b> scheme. As ciphertext space we take <math>G= \mathbb F_2^n </math>, where we consider the monoid structure defined by component-wise multiplication. Basically, <math> G </math> is the commutative monoid generated by <math>n </math> idempotents with no other relations between these. As plaintext, we consider the monoid <math>\mathbb F_2</math>. The <b> CertSGN </b> scheme is defined as follows:
 +
 +
* Setup(<math>1^{\lambda} </math>): Choose the dimension parameter <math>n = n(\lambda) </math> and the integers <math> d= d(\lambda) </math>, <math>s=s(\lambda) </math> such that <math>n=2sd </math>.
 +
 +
* SecretKeygen: Choose a subset <math>S</math> of <math>\{1,2,\dots, n\} </math> of size <math> s </math>. Set the secret key to be <math> S </math>.
 +
 +
* <math>E: </math> To encrypt a bit <math> m \in \mathbb F_2 </math>, choose <math> d</math> random numbers <math>i_1, i_2, \dots, i_d </math> from the set <math>\{1,2,\dots, n \} </math> such that there are exactly <math>m </math> of them in the secret key <math>S</math>. Set <math>E(m)</math> to be the vector in <math>G</math>, whose components corresponding to the indices <math>i_1, i_2, \dots, i_d </math> are equal to <math>0</math> and the others are equal to <math> 1</math>.
 +
 +
* <math>D</math>: To decrypt a ciphertext <math>c \in \mathbb F_2^n</math>, set <math>D(c)=0 </math> if <math>c</math> has at least one component equal to <math>0</math> corresponding to an index from <math> S </math> and <math> D(c)=1 </math> otherwise.
 +
 +
Remark that if one represents the secret key as the indicator vector of <math>S </math>, namely <math> \overline s \in \mathbb F_2^n </math> then the decryption algorithm <math>D</math> can be expressed as an inner product over <math>\mathbb F_2 </math> between <math>c </math> and <math>\overline s </math>.
 +
 +
One can check that the scheme <math>(\mathbb F_2^n, \mathbb F_2, E, D) </math> described above is a monoidal encryption scheme, so one can use the recipe in the blueprint to obtain a ring homomorphic encryption scheme <math>(\mathbb F_2[\mathbb F_2^n], \mathbb F_2, \mathrm{Enc}, \mathrm Dec) </math>. 
 +
 +
We refer to the paper [1] for a proof of the correction of this scheme and for security and efficiency analyses.
 +
 +
== Differences from homomorphic schemes based on LWE ==
 +
 +
 +
In the ring homomorphic encryption scheme obtained above, we remark that the multiplication operation on fresh ciphertext is extremely efficient. It consists of only <math> n</math> multiplications of two bits.
 +
 +
However, addition of ciphertexts makes the ciphertext grow. This phenomenon is exactly the opposite to the situation which appears in homomorphic schemes which are based on (R)-LWE problem. In the latter, the message is hidden using "noise", a quantity that grows upon homomorphic operations. If the noise is too large, then a message cannot be decrypted. When performing homomorphic operations on ciphertext, the noise grows linearly with the number of additions, but it grows exponentially with the multiplication depth of the circuit.
 +
 +
The <b>CertSGN</b> scheme brings huge advantages if somebody wants to homomorphically evaluate a circuit whose polynomial representation consists of a sum of few very large power monomials.
 +
 +
== References ==

Latest revision as of 12:30, 4 May 2021

We will briefly describe here the contributions of the article[1], in which members of the certSign research group introduced a new method for producing the following:

  • Starting with an encryption scheme which is homomorphic with respect to one operation (such as multiplication), the recipe of the authors produces another encryption scheme which is now homomorphic with respect to two operations (for example, addition and multiplication).

The authors use this technique to construct examples of encryption schemes that, theoretically can handle any algebraic function on encrypted data.

The homomorphic encryption scheme CSGN, a symmetric homomorphic encryption scheme with plaintext (the field with two elements) was introduced in the same article. The latter plays an essential role the architecture of a privacy-preserving contact tracing application, developed by certSign as part of the TAMEC project. [2]

The content of the article is protected under the law by two patents. [3]

A toy implementation can be found here : https://github.com/certfhe/CSGN

Ring homomorphic encryption schemes from monoidal ones. The blueprint

Given a monoid and any commutative ring with unity, one can associate to these an algebra . As an -module, the monoid algebra is free with a basis consisting of the symbols , where .

The multiplication in this algebra is defined by extending in an -bilinear manner. Any element has a unique representation

where for all but finitely many . The product of two elements is given by

We note that the identity element with respect to multiplication is , where is the identity element of . If is a group then the monoid algebra described above is called a group algebra.

If are two monoids, a monoid homomorphism induces a natural -algebra homomorphism .

We also remark that for any -algebra , there is a natural -algebra homomorphism given by

.

The patented blueprint

Let be a finite ring and let be a monoid homomorphic encryption scheme. This implies that the ciphertext and the plaintext are monoids and the decryption algorithm is a monoid homomorphism.

Consider an efficiently computable -character , where is a finite -algebra.

As explained above, the monoid homomorphism induces the -algebra homomorphism . At the same time, induces an -algebra homomorphism . The -algebra homomorphism is defined as

,

defined by the formula

.

Let us denote by the image of in . For the decryption algorithm to remain secure, one needs the assumption that is not the trivial character, a condition that is always assumed in the blueprint.

We now describe a ring homomorphic encryption scheme with plaintext and ciphertext . Let be the image of in and fix some integer such that the elements of the form , with is the whole -algebra .

  • Consider a fixed tuple . For a plaintext consider such that . Then
.
  • The decryption algorithm is given by

The authors of the article prove that is a ring homomorphic encryption scheme and the security of this scheme is the same as the security of the monoid encryption scheme that one starts with.

A symmetric ring homomorphic encryption scheme

In this section we describe the CertSGN scheme. As ciphertext space we take , where we consider the monoid structure defined by component-wise multiplication. Basically, is the commutative monoid generated by idempotents with no other relations between these. As plaintext, we consider the monoid . The CertSGN scheme is defined as follows:

  • Setup(): Choose the dimension parameter and the integers , such that .
  • SecretKeygen: Choose a subset of of size . Set the secret key to be .
  • To encrypt a bit , choose random numbers from the set such that there are exactly of them in the secret key . Set to be the vector in , whose components corresponding to the indices are equal to and the others are equal to .
  • : To decrypt a ciphertext , set if has at least one component equal to corresponding to an index from and otherwise.

Remark that if one represents the secret key as the indicator vector of , namely then the decryption algorithm can be expressed as an inner product over between and .

One can check that the scheme described above is a monoidal encryption scheme, so one can use the recipe in the blueprint to obtain a ring homomorphic encryption scheme .

We refer to the paper [1] for a proof of the correction of this scheme and for security and efficiency analyses.

Differences from homomorphic schemes based on LWE

In the ring homomorphic encryption scheme obtained above, we remark that the multiplication operation on fresh ciphertext is extremely efficient. It consists of only multiplications of two bits.

However, addition of ciphertexts makes the ciphertext grow. This phenomenon is exactly the opposite to the situation which appears in homomorphic schemes which are based on (R)-LWE problem. In the latter, the message is hidden using "noise", a quantity that grows upon homomorphic operations. If the noise is too large, then a message cannot be decrypted. When performing homomorphic operations on ciphertext, the noise grows linearly with the number of additions, but it grows exponentially with the multiplication depth of the circuit.

The CertSGN scheme brings huge advantages if somebody wants to homomorphically evaluate a circuit whose polynomial representation consists of a sum of few very large power monomials.

References

  1. M. Barcau and V. Pasol, Bounded Fully Homomorphic Encryption from Monoid Algebras, https://eprint.iacr.org/2018/584
  2. https://www.certsign.ro/en/projects
  3. U.S. Patent Appln. No. 14/936,097 and European Patent Appln. No. EP 15193706.7