CertSGN - Revision history

Clupascu at 12:30, 4 May 2021

2021-05-04T12:30:12Z

Clupascu at 11:55, 1 February 2021

2021-02-01T11:55:11Z

Gturcas: /* Differences from homomorphic schemes based on LWE */

2021-01-11T14:54:45Z

Differences from homomorphic schemes based on LWE

Gturcas: /* Differences from homomorphic schemes based on LWE */

2020-12-22T14:43:08Z

Differences from homomorphic schemes based on LWE

Gturcas: /* Differences from homomorphic schemes based on LWE */

2020-12-22T14:42:19Z

Differences from homomorphic schemes based on LWE

Gturcas: /* A symmetric ring homomorphic encryption scheme */

2020-12-22T14:28:46Z

A symmetric ring homomorphic encryption scheme

Gturcas: /* Differences from homomorphic schemes based on LWE */

2020-12-22T14:26:06Z

Differences from homomorphic schemes based on LWE

Gturcas: /* A symmetric ring homomorphic encryption scheme */

2020-12-22T14:25:03Z

A symmetric ring homomorphic encryption scheme

Gturcas: /* A symmetric ring homomorphic encryption scheme */

2020-12-22T14:22:54Z

A symmetric ring homomorphic encryption scheme

Gturcas at 13:30, 22 December 2020

2020-12-22T13:30:29Z

@@ Line 10: / Line 10: @@
 European Patent Appln. No. EP 15193706.7</ref>
-A toy implementation can be found here : https://github.com/certfhe/certfhe
+A toy implementation can be found here : https://github.com/certfhe/CSGN
 == Ring homomorphic encryption schemes from monoidal ones. The blueprint ==

← Older revision		Revision as of 11:55, 1 February 2021
Line 10:		Line 10:
	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/certfhe

	== Ring homomorphic encryption schemes from monoidal ones. The blueprint ==		== Ring homomorphic encryption schemes from monoidal ones. The blueprint ==

← Older revision		Revision as of 14:54, 11 January 2021
Line 81:		Line 81:


−	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.	+	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.		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.

← Older revision		Revision as of 14:43, 22 December 2020
Line 86:		Line 86:

	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.		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 ==

← Older revision		Revision as of 14:42, 22 December 2020
Line 81:		Line 81:


−	In the scheme ~~described~~ above,	+	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.

← Older revision		Revision as of 14:28, 22 December 2020
Line 73:		Line 73:

	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>.		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.		We refer to the paper [1] for a proof of the correction of this scheme and for security and efficiency analyses.

← Older revision		Revision as of 14:26, 22 December 2020
Line 77:		Line 77:

	== Differences from homomorphic schemes based on LWE ==		== Differences from homomorphic schemes based on LWE ==
		+
		+
		+	In the scheme described above,

← Older revision		Revision as of 14:25, 22 December 2020
Line 75:		Line 75:

	We refer to the paper [1] for a proof of the correction of this scheme and for security and efficiency analyses.		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 ==

← Older revision		Revision as of 14:22, 22 December 2020
Line 61:		Line 61:

	== A symmetric ring homomorphic encryption scheme ==		== 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>.
		+
		+	We refer to the paper [1] for a proof of the correction of this scheme and for security and efficiency analyses.

← Older revision		Revision as of 13:30, 22 December 2020
Line 59:		Line 59:

	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.		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 ==