Difference between revisions of "CertSGN"
| Line 14: | Line 14: | ||
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>. | 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 === | ||
Revision as of 14:24, 21 December 2020
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]
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 .
![{\displaystyle R[M] }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/0e12485051772e4d284039b68a9865b7c7805e00)
![{\displaystyle [x] }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/07548563c21e128890501e14eb7c80ee2d6fda4d)
The multiplication in this algebra is defined by extending in an -bilinear manner. Any element has a unique representation
![{\displaystyle [x] \cdot [y] = [xy]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/b388b37dad4cfb6852ee4409af4463316368c483)
![{\displaystyle a \in R[M]}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/3d7c98baa759cc359f72ea39489348ab41dfe944)
![{\displaystyle a = \sum_{x \in M} a_x[x],}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/a560d336a04f5d7a9e093988cd496c12bdcccf1c)
where for all but finitely many . The product of two elements is given by
![{\displaystyle a,b \in R[M] }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/e174341661d4aa827d46b4b9bd499600dd16041e)
![{\displaystyle ab = \sum_{x \in M} \left( \sum_{yz=x} a_yb_z \right)[x]. }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/149d2e24acef7765be3a57b3021441758398da60)
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.
![{\displaystyle 1[e] }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/ecec9492f5b853eff691b74e524b16b16dd3a088)
If are two monoids, a monoid homomorphism induces a natural -algebra homomorphism .
![{\displaystyle \phi_R : R[M] \to R[N] }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/8fe604d5232e4cd3155adabf94d630485bef7d47)
We also remark that for any -algebra , there is a natural -algebra homomorphism given by
![{\displaystyle \epsilon : R[A] \to A }](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/42d1f14f5e77be4eb791528855df04e0da730dbc)
![{\displaystyle \epsilon \left( \sum_{x \in R} r_x[x] \right) = \sum_{x \in R} r_x x}](https://en.wikipedia.org/api/rest_v1/media/math/render/svg/bed57cd5901f7f444ca248d119d8a1139a9c235f)
The patented blueprint
- ↑ M. Barcau and V. Pasol, Bounded Fully Homomorphic Encryption from Monoid Algebras, https://eprint.iacr.org/2018/584
- ↑ https://www.certsign.ro/en/projects
- ↑ U.S. Patent Appln. No. 14/936,097 and European Patent Appln. No. EP 15193706.7
