Information processing technique for pattern matching

Patent metadata

Field	Value
Publication number	US-9596083-B2
Application number	US-201514697573-A
Country	US
Kind code	B2
Filing date	Apr 27, 2015
Priority date	May 2, 2014
Publication date	Mar 14, 2017
Grant date	Mar 14, 2017

Abstract

A matching method includes: generating a first numerical vector; generating a second numerical vector by squaring each component of the first numerical vector and a third numerical vector by cubing each component of the first numerical vector; generating first to third polynomials by executing polynomial transformation of the first to third numerical vectors; encrypting the first to third polynomials by a homomorphic encryption scheme; executing a predetermined operation while keeping data used in the predetermined operation encrypted, by using fourth to sixth polynomials obtained by the polynomial transformation and the homomorphic encryption of fourth to sixth numerical vectors, wherein the fourth numerical vector is generated by numerically vectorizing second text, the fifth numerical vector is generated by squaring each component of the fourth numerical vector, and the sixth numerical vector is generated by cubing each component of the fourth numerical vector; and decrypting a result of the predetermined operation.

First claim

What is claimed is:

1. A matching method, comprising:
first generating, by a system that includes a plurality of computers, a first numerical vector by numerically vectorizing first text stored in a first data storage unit;
second generating, by the system, a second numerical vector by squaring each component of the first numerical vector and a third numerical vector by cubing each component of the first numerical vector;
third generating, by the system, a first polynomial by executing a polynomial transformation of the first numerical vector, a second polynomial by executing the polynomial transformation of the second numerical vector, and a third polynomial by executing the polynomial transformation of the third numerical vector;
encrypting, by the system, the first polynomial, the second polynomial and the third polynomial by a homomorphic encryption scheme capable of operating polynomials;
executing, by the system, an operation in which a distance between the first text and second text in pattern matching becomes 0 when the first text coincides with a part of the second text, when the first text that includes a special character representing any character coincides with the part of the second text, and when the first text coincides with the part of the second text that includes the special character, while keeping data used in the operation encrypted, by using the encrypted first polynomial, the encrypted second polynomial, the encrypted third polynomial, a fourth polynomial obtained by the polynomial transformation and the homomorphic encryption of a fourth numerical vector, a fifth polynomial obtained by the polynomial transformation and the homomorphic encryption of a fifth numerical vector, and a sixth polynomial obtained by the polynomial transformation and the homomorphic encryption of a sixth numerical vector, wherein the fourth numerical vector is generated by numerically vectorizing the second text, the fifth numerical vector is generated by squaring each component of the fourth numerical vector, the sixth numerical vector is generated by cubing each component of the fourth numerical vector, and the fourth polynomial, the fifth polynomial and the sixth polynomial are stored in a second data storage unit;
decrypting, by the system, a result of the operation; and
determining, by the system and based on the decrypted result, whether the first text exists in the second text.

2. The matching method as set forth in claim 1 , wherein the determining comprises identifying a component whose value is 0 in a vector included in the decrypted result.

3. The matching method as set forth in claim 1 , wherein the polynomial transformation to obtain the fourth to sixth polynomials differs from the polynomial transformation to obtain the first to third polynomials.

4. An information processing system, comprising:
a first information processing apparatus accessible to a first data storage unit that stores first text; and
a second information processing apparatus, and
wherein the first information processing apparatus comprises:
a first memory; and
a first processor coupled to the first memory and configured to:
generate a first numerical vector by numerically vectorizing the first text stored in the first data storage unit;
generate a second numerical vector by squaring each component of the first numerical vector and a third numerical vector by cubing each component of the first numerical vector;
generate a first polynomial by executing a polynomial transformation of the first numerical vector, a second polynomial by executing the polynomial transformation of the second numerical vector, and a third polynomial by executing the polynomial transformation of the third numerical vector;
encrypt the first polynomial, the second polynomial and the third polynomial by a homomorphic encryption scheme capable of operating polynomials; and
transmit the encrypted first polynomial, the encrypted second polynomial, and the encrypted third polynomial to the second information processing apparatus,
the second information processing apparatus comprises:
a second memory; and
a second processor coupled to the second memory and configured to:
receive the encrypted first polynomial, the encrypted second polynomial, and the encrypted third polynomial from the first information processing apparatus;
execute an operation in which a distance between the first text and second text in pattern matching becomes 0 when the first text coincides with a part of the second text, when the first text that includes a special character representing any character coincides with the part of the second text, and when the first text coincides with the part of the second text that includes the special character, while keeping data used in the operation encrypted, by using the encrypted first polynomial, the encrypted second polynomial, the encrypted third polynomial, a fourth polynomial obtained by the polynomial transformation and the homomorphic encryption of a fourth numerical vector, a fifth polynomial obtained by the polynomial transformation and the homomorphic encryption of a fifth numerical vector, and a sixth polynomial obtained by the polynomial transformation and the homomorphic encryption of a sixth numerical vector, wherein the fourth numerical vector is generated by numerically vectorizing the second text, the fifth numerical vector is generated by squaring each component of the fourth numerical vector, the sixth numerical vector is generated by cubing each component of the fourth numerical vector, and the fourth polynomial, the fifth polynomial and the sixth polynomial are stored in a second data storage unit;
transmit a result of the operation, and
the first processor is configured to:
receive the result of the operation;
decrypt the result of the operation; and
determine, based on the decrypted result, whether the first text exists in the second text.

5. A computer-readable, non-transitory storage medium storing a program that causes a computer to execute a process, the process comprising:
receiving a first polynomial obtained by a polynomial transformation and homomorphic encryption of a first numerical vector, a second polynomial obtained by the polynomial transformation and the homomorphic encryption of a second numerical vector, and a third polynomial obtained by the polynomial transformation and the homomorphic encryption of a third numerical vector, wherein the first numerical vector is generated by numerically vectorizing first text, the second numerical vector is generated by squaring each component of the first numerical vector, the third numerical vector is generated by cubing each component of the first numerical vector;
executing an operation in which a distance between the first text and second text in pattern matching becomes 0 when the first text coincides with a part of the second text, when the first text that includes a special character representing any character coincides with the part of the second text, and when the first text coincides with the part of the second text that includes the special character, while keeping data used in the operation encrypted, by using the first polynomial, the second polynomial, the third polynomial, a fourth polynomial obtained by the polynomial transformation and the homomorphic encryption of a fourth numerical vector, a fifth polynomial obtained by the polynomial transformation and the homomorphic encryption of a fifth numerical vector, and a sixth polynomial obtained by the polynomial transformation and the homomorphic encryption of a sixth numerical vector, wherein the fourth numerical vector is generated by numerically vectorizing the second text, the fifth numerical vector is generated by squaring each component of the fourth numerical vector, the sixth numerical vec

Assignees

• Fujitsu Ltd

Inventors

• Yasuda Masaya
• Shimoyama Takeshi
• Kogure Jun

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/3093 Primary

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