Efficient homomorphic encryption scheme for bilinear forms

Patent metadata

Field	Value
Publication number	US-9252954-B2
Application number	US-201414511507-A
Country	US
Kind code	B2
Filing date	Oct 10, 2014
Priority date	Mar 30, 2010
Publication date	Feb 2, 2016
Grant date	Feb 2, 2016

Abstract

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.

First claim

What is claimed is:

1. 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 use an encryption scheme that is homomorphic and supports computing bilinear forms, the at least one processor configured to encrypt 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; and
wherein the at least one processor is further configured to output the ciphertext C, to send the outputted ciphertext over a network to a remote computer which uses the outputted ciphertext in one or more homomorphic operations, and to receive a result of the one or more homomorphic operations from the remote computer, and wherein the at least one processor is further configured to perform decryption of the result of the one or more homomorphic operations received from the remote computer to create plaintext.

2. The apparatus 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 apparatus of claim 1 , where p=2 and the information B comprises a matrix of binary values.

4. The apparatus 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

.

5. The apparatus of claim 4 , where the encryption scheme supports n c additions and one multiplication in any order over a matrix ring p m×m .

6. 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
using, by the computer, an encryption scheme that is homomorphic and supports computing bilinear forms at least by 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;
outputting by the computer the ciphertext C, sending the outputted ciphertext over a network to a remote computer which uses the outputted ciphertext in one or more homomorphic operations, receiving a result of the one or more homomorphic operations from the remote computer, and decrypting the result of the one or more homomorphic operations received from the remote computer to create plaintext.

7. The method of claim 6 , 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).

8. The method of claim 6 , where p=2 and the information B comprises a matrix of binary values.

Assignees

• IBM

Inventors

• Halevi Shai
• Gentry Craig B
• Vaikuntanathan Vinod

Classifications

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L2209/24

  Key scheduling, i.e. generating round keys or sub-keys for block encryption · CPC title

• H04L9/30 Primary

  Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy · CPC title

• H04L9/0861

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title