Cryptographic processing method and cryptographic processing device

Patent metadata

Field	Value
Publication number	US-9871652-B2
Application number	US-201514831179-A
Country	US
Kind code	B2
Filing date	Aug 20, 2015
Priority date	Oct 10, 2014
Publication date	Jan 16, 2018
Grant date	Jan 16, 2018

Abstract

A computer generates a third encrypted polynomial that corresponds to a result of encrypting a third polynomial by use of a result of multiplying a first encrypted polynomial by a second encrypted polynomial, and outputs cryptographic information that represents the third encrypted polynomial. The first encrypted polynomial is a polynomial obtained by encrypting a first polynomial that corresponds to a first vector, and the second encrypted polynomial is a polynomial obtained by encrypting a second polynomial that corresponds to a second vector. The third polynomial includes a first term that has a coefficient based on an inner product of the first vector and the second vector and a second term other than the first term, in which a coefficient of the second term is masked.

First claim

What is claimed is:

1. A cryptographic processing method comprising:
generating a third encrypted polynomial that corresponds to a result of encrypting a third polynomial by a computer, by use of a result of multiplying a first encrypted polynomial obtained by encrypting a first polynomial that corresponds to a first vector by a second encrypted polynomial obtained by encrypting a second polynomial that corresponds to a second vector, the third polynomial including a first term that has a coefficient based on an inner product of the first vector and the second vector and a second term other than the first term, wherein the computer masks a coefficient of the second term by performing cryptographic masking on the result of multiplying the first encrypted polynomial by the second encrypted polynomial; and
outputting cryptographic information that represents the third encrypted polynomial.

2. The cryptographic processing method according to claim 1 , wherein
coefficients in one or more terms including the second term from among a plurality of terms included in the third polynomial are masked by random numbers.

3. The cryptographic processing method according to claim 1 , wherein
the first encrypted polynomial and the second encrypted polynomial are generated by a homomorphic encryption of lattice dimension n, and by use of a dimension d of the first vector and an integer k not less than 0, a degree of the first term is represented by an integer one less than a remainder obtained by dividing d+k+1 by n.

4. The cryptographic processing method according to claim 3 , wherein
the computer sends the cryptographic information to a decryption device, the third polynomial corresponds to a result of decrypting the third encrypted polynomial, the integer k is an integer not less than 1, and the decryption device obtains the coefficient of the first term included in the third polynomial by use of the integer k, the lattice dimension n and the dimension d.

5. The cryptographic processing method according to claim 1 , wherein
the coefficient based on the inner product represents the dissimilarity or similarity between the first vector and the second vector.

6. A cryptographic processing device comprising:
a memory; and
a processor coupled to the memory and that generates a third encrypted polynomial that corresponds to a result of encrypting a third polynomial by use of a result of multiplying a first encrypted polynomial obtained by encrypting a first polynomial that corresponds to a first vector by a second encrypted polynomial obtained by encrypting a second polynomial that corresponds to a second vector, the third polynomial including a first term that has a coefficient based on an inner product of the first vector and the second vector and a second term other than the first term, wherein the processor masks a coefficient of the second term by performing cryptographic masking on the result of multiplying the first encrypted polynomial by the second encrypted polynomial; and
a communication interface coupled to the memory and the processor and that outputs cryptographic information that represents the third encrypted polynomial.

7. The cryptographic processing device according to claim 6 , wherein
coefficients in one or more terms from among a plurality of terms included in the third polynomial are masked by random numbers.

8. The cryptographic processing device according to claim 6 , wherein
the first encrypted polynomial and the second encrypted polynomial are generated by a homomorphic encryption of lattice dimension n, and by use of a dimension d of the first vector and an integer k not less than 0, a degree of the first term is represented by an integer one less than a remainder obtained by dividing d+k+1 by n.

9. The cryptographic processing device according to claim 8 , wherein
the output interface sends the cryptographic information to a decryption device, the third polynomial corresponds to a result of decrypting the third encrypted polynomial, the integer k is an integer not less than 1, and the decryption device obtains the coefficient of the first term included in the third polynomial by use of the integer k, the lattice dimension n and the dimension d.

10. The cryptographic processing device according to claim 6 , wherein
the coefficient based on the inner product represents the dissimilarity or similarity between the first vector and the second vector.

11. A non-transitory computer-readable recording medium having stored therein a cryptographic processing program that causes a computer to execute a process comprising:
generating a third encrypted polynomial that corresponds to a result of encrypting a third polynomial by use of a result of multiplying a first encrypted polynomial obtained by encrypting a first polynomial that corresponds to a first vector by a second encrypted polynomial obtained by encrypting a second polynomial that corresponds to a second vector, the third polynomial including a first term that has a coefficient based on an inner product of the first vector and the second vector and a second term other than the first term, wherein the computer masks a coefficient of the second term by performing cryptographic masking on the result of multiplying the first encrypted polynomial by the second encrypted polynomial; and
outputting cryptographic information that represents the third encrypted polynomial.

12. The non-transitory computer-readable recording medium according to claim 11 , wherein
coefficients in one or more terms from among a plurality of terms included in the third polynomial are masked by random numbers.

13. The non-transitory computer-readable recording medium according to claim 11 , wherein
the first encrypted polynomial and the second encrypted polynomial are generated by a homomorphic encryption of lattice dimension n, and by use of a dimension d of the first vector and an integer k not less than 0, a degree of the first term is represented by an integer one less than a remainder obtained by dividing d+k+1 by n.

14. The non-transitory computer-readable recording medium according to claim 13 , wherein
the computer sends the cryptographic information to a decryption device, the third polynomial corresponds to a result of decrypting the third encrypted polynomial, the integer k is an integer not less than 1, and the decryption device obtains the coefficient of the first term included in the third polynomial by use of the integer k, the lattice dimension n and the dimension d.

15. The non-transitory computer-readable recording medium according to claim 11 , wherein
the coefficient based on the inner product represents the dissimilarity or similarity between the first vector and the second vector.

Assignees

• Fujitsu Ltd

Inventors

• Morikawa Ikuya
• Yasuda Masaya

Classifications

• G09C1/00

  Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00) · CPC title

• H04L9/008 Primary

  involving homomorphic encryption · CPC title