Efficient homomorphic encryption scheme for bilinear forms
In one exemplary embodiment, a computer readable storage medium tangibly embodying a program of instructions executable by a machine for performing operations including: receiving information B to be encrypted as a ciphertext C in accordance with an encryption scheme having an encrypt function; and encrypting B in accordance with the encrypt function to obtain C, the scheme utilizes at least one public key A, where B, C, and A are matrices, the encrypt function receives as inputs A and B and outputs C as C→AS+pX+B (mod q), S is a random matrix, X is an error matrix, p is in integer, q is an odd prime number. In other exemplary embodiments, the encryption scheme includes a decrypt function that receives as inputs at least one private key T (a matrix) and C and outputs B as B=T −1 ·(TCT t mod q)·(T t ) −1 mod p.
1. A computer readable storage device tangibly embodying a program of instructions executable by a machine for performing operations, the operations comprising:
receiving information B to be encrypted as a ciphertext C in accordance with an encryption scheme that comprises an encrypt function; and
encrypting the information B in accordance with the encrypt function of the encryption scheme to obtain the ciphertext C,
where the encryption scheme utilizes at least one public key A, where the information B, the ciphertext C, and the at least one public key A are matrices,
where the encrypt function receives as inputs the at least one public key A and the information B and outputs the ciphertext C as C←AS+pX+B(mod q), where S is a random matrix, where X is an error matrix, where p is an integer, where q is an odd prime number.
2. The computer readable storage device of claim 1 , where Bε p m×m , Cε q m×m , Aε q m×n , S q n×m and X Ψ β (q) m×m , where n denotes a security parameter and m, q=poly(n), where Ψ β is an error distribution, where β is a Gaussian error parameter given by β=1/poly(n).
3. The computer readable storage device of claim 1 , where the encryption scheme is homomorphic and supports computing bilinear forms.
4. The computer readable storage device of claim 1 , where p=2 and the information B comprises a matrix of binary values.
5. The computer readable storage device of claim 1 , where =c(n)>0, q>2 20 p 2 (c+4) 3 n 3c+4 log 5 n, m=└8n log q┘ and
β
=
1
27
p
n
1
+
(
3
c
/
2
)
log
n
log
q
q
m
.
6. The computer readable storage device of claim 5 , where the encryption scheme supports n c additions and one multiplication in any order over a matrix ring p m×m .
7. An apparatus comprising:
at least one storage medium configured to store information B to be encrypted as a ciphertext C in accordance with an encryption scheme that comprises an encrypt function; and
at least one processor configured to encrypt the information B in accordance with encrypt function of the encryption scheme to obtain the ciphertext C,
where the encryption scheme utilizes at least one public key A, where the information B, the ciphertext C, and the at least one public key A are matrices,
where the encrypt function receives as inputs the at least one public key A and the information B and outputs the ciphertext C as C←AS+pX+B(mod q), where S is a random matrix, where X is an error matrix, where p is an integer, where q is an odd prime number.
8. The apparatus of claim 7 , where Bε p m×m , Cε q m×m , Aε q m×n , S q n×m and X Ψ β (q) m×m , where n denotes a security parameter and m, q=poly(n), where Ψ β is an error distribution, where β is a Gaussian error parameter given by β=1/poly(n).
9. The apparatus of claim 7 , where the encryption scheme is homomorphic and supports computing bilinear forms.
10. The apparatus of claim 7 , where p=2 and the information B comprises a matrix of binary values.
11. The apparatus of claim 7 , where =c(n)>0, q>2 20 p 2 (c+4) 3 n 3c+4 log 5 n, m=└8n log q┘ and
β
=
1
27
p
n
1
+
(
3
c
/
2
)
log
n
log
q
q
m
.
12. The apparatus of claim 11 , where the encryption scheme supports n c additions and one multiplication in any order over a matrix ring p m×m .
13. A computer readable storage device tangibly embodying a program of instructions executable by a machine for performing operations, the operations comprising:
receiving a ciphertext C to be decrypted as information B in accordance with an encryption scheme that comprises a decrypt function; and
decrypting the ciphertext C in accordance with the decrypt function of the encryption scheme to obtain the information B,
where the encryption scheme utilizes at least one private key T, where the information B, the ciphertext C and the at least one private key T are matrices,
where the decrypt function receives as inputs the at least one private key T and the ciphertext C and outputs the information B in accordance with
B=T −1 ·(TCT t mod q)·(T t ) −1 mod p, where p is an integer, where q is an odd prime number.
14. The computer readable storage device of claim 13 , where Bε p m×m , Cε q m×m , and Tε q m×m , and, where n denotes a security parameter and m, q=poly(n), where Ψ β is an error distribution, where β is a Gaussian error parameter given by β=1/poly(n).
15. The computer readable storage device of claim 13 , where the encryption scheme is homomorphic and supports computing bilinear forms.
16. The computer readable storage device of claim 13 , where p=2 and the information B comprises a matrix of binary values.
17. The computer readable storage medium of claim 13 , where =c(n)>0, q>2 20 p 2 (c+4) 3 n 3c+4 log 5 n, m=└8n log q┘ and
β
=
1
27
p
n
1
+
(
3
c
/
2
)
log
n
log
q
q
m
.
18. The computer readable storage device of claim 17 , where the encryption scheme supports n c additions and one multiplication in any order over a matrix ring p m×m .
19. An apparatus comprising:
at least one storage medium configured to store a ciphertext C to be decrypted as information B in accordance with an encryption scheme that comprises a decrypt function; and
at least one processor configured to decrypt the ciphertext C in accordance with the decrypt function of the encryption scheme to obtain the information B,
where the encryption scheme utilizes at least one private key T, where the information B, the ciphertext C and the at least one private key T are matrices,
where the decrypt function receives as inputs the at least one private key T and the ciphertext C and outputs the information B in accordance with
B=T −1 ·(TCT t mod q)·(T t ) −1 mod p, where p is an integer, where q is an odd prime number.
20. The apparatus of claim 19 , where Bε p m×m , Cε q m×m and Tε q m×m , where n denotes a security parameter and m, q=poly (n), where Ψ β is an error distribution, where β is a Gaussian error parameter given by β=1/poly (n).
21. The apparatus of claim 19 , where the encryption scheme is homomorphic and supports computing bilinear forms.
22. The apparatus of claim 19 , where p=2 and the information B comprises a matrix of binary values.
23. The apparatus of claim 19 , where =c(n)>0, q>2 20 p 2 (c+4) 3 n 3c+4 log 5 n, m=└8n log q┘ and
β
=
1
27
p
n
1
+
(
3
c
/
2
)
log
n
log
q
q
m
.
24. The apparatus of claim 23 , where the encryption scheme supports n c additions and one multiplication in any order over a matrix ring p m×m .
25. A computer readable storage device tangibly embodying a program of instructions executable by a machine for performing operations, the operations comprising:
receiving information B to be encrypted as a ciphertext C in accordance with an encryption scheme that comprises an encrypt function and a decrypt function; and
encrypting the information B in accordance with the encrypt function of the encryption scheme to obtain the ciphertext C,
where the encryption scheme utilizes at least one public key A and at least one private key T corresponding to the at least one public key A, where the information B, the ciphertext C, the at least one public key A and the at least one private key T are matrices, where Bε p m×m , Cε q m×m , Aε q m×n and Tε q m×m , where n denotes a security parameter and m, q=poly (n), where q is an odd prime number, where p is an integer, where q>p,
where the encrypt function receives as inputs A and B and outputs the ciphertext C as C←AS+pX+B(mod q), where S is a random matrix and S q n×m , where X is an error matrix and X Ψ β (q) m×m , where Ψ β is an error distribution, where β is a Gaussian error parameter given by β=1/poly (n),
where the decrypt function receives as inputs T and C and outputs the information B in accordance with B=T −1 ·(TCT t mod q)·(T t ) −1 mod p, where the encryption scheme is homomorphic and supports computing bilinear forms.
26. A method, comprising:
receiving, by a computer, information B to be encrypted as a ciphertext C in accordance with an encryption scheme that comprises an encrypt function; and
encrypting, by the computer, the information B in accordance with the encrypt function of the encryption scheme to obtain the ciphertext C,
where the encryption scheme utilizes at least one public key A, where the information B, ciphertext C, and the at least one public key A are matrices,
where encrypt function receives as inputs the at least one public key A and the information B and outputs the ciphertext C as C←AS+pX+B(mod q), where S is a random matrix, where X is an error matrix, where p is an integer, where q is an odd prime number.
27. The method of claim 26 , where the encryption scheme is homomorphic and supports computing bilinear forms.
28. The method of claim 26 , where p=2 and the information B comprises a matrix of binary values.
29. A method, comprising:
receiving, by a computer, a ciphertext C to be decrypted as information B in accordance with an encryption scheme that comprises a decrypt function; and
decrypting, by the computer, the ciphertext C in accordance with the decrypt function of the encryption scheme to obtain the information B,
where the encryption scheme utilizes at least one private key T, where the information B, the ciphertext C and the at least one private key T are matrices,
where the decrypt function receives as inputs the at least one private key T and the ciphertext C and outputs the information B in accordance with
B=T −1 ·(TCT t mod q)·(T t ) −1 mod p, where p is an integer, where q is an odd prime number.
30. The method of claim 29 , where the encryption scheme is homomorphic and supports computing bilinear forms.
31. The method of claim 29 , where p=2 and the information B comprises a matrix of binary values.
32. A method, comprising:
receiving, by a computer, information B to be encrypted as a ciphertext C in accordance with an encryption scheme that comprises an encrypt function and a decrypt function; and
encrypting, by the computer, the information B in accordance with the encrypt function of the encryption scheme to obtain the ciphertext C,
where the encryption scheme utilizes at least one public key A and at least one private key T corresponding to the at least one public key A, where the information B, the ciphertext C, the at least one public key A and the at least one private key T are matrices, where Bε p m×m , Cε q m×m , Aε q m×n and Tε q m×m , where n denotes a security parameter and m, q=poly(n), where q is an odd prime number, where p is an integer, where q>p,
where the encrypt function receives as inputs A and B and outputs the ciphertext C as C←AS+pX+B(mod q), where S is a random matrix and S q n×m , where X is an error matrix and X Ψ β (q) m×m , where Ψ β is an error distribution, where β is a Gaussian error parameter given by β=1/poly(n),
where the decrypt function receives as inputs T and C and outputs the information B in accordance with B=T −1 ·(TCT t mod q)·(T t ) −1 mod p, where the encryption scheme is homomorphic and supports computing bilinear forms.