SOLVING LATTICE PROBLEMS USING ANNEALING

• US 20200133995A1
• Filed: 10/31/2018
• Published: 04/30/2020
• Est. Priority Date: 10/31/2018
• Status: Active Grant

• Current Assignee: Fujitsu Limited
• Original Assignee: Fujitsu Limited
• Inventors: MANDAL, Avradip, ROY, Arnab, MONTGOMERY, Hart
• Granted Patent: US 11,080,365 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06N 20/10 using kernel methods, e.g. support vector machines [SVM]
• CPC Class Codes: G06N 3/08 Learning methods
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme

Abstract

According to an aspect of an embodiment, operations may include obtaining a basis “A” that defines a lattice in an m-dimensional space. The operations may further include obtaining a target vector “y” that defines a particular location in the m-dimensional space. In addition, the operations may include generating an Ising model connection weight matrix “W” by multiplying a transposition of “A” (“A^T”) by “A”. Moreover, the operations may include generating an Ising model bias vector “b” by multiplying a transposition of “y” (“y^T”) by “A”. The operations may further include providing “W” and “b” to an annealing system configured to solve problems written according to the Ising model. Additionally, the operations may include obtaining an output from the annealing system that represents an output vector “x” of a particular point included in the lattice that is the closest point in the lattice to the particular location defined by “y”.

Claims

1. A method comprising:

obtaining a basis “

A”

that defines a lattice in an m-dimensional space, the lattice including a plurality of points in the m-dimensional space, the basis “

A”

being a matrix of “

n”

number of linearly independent vectors in which each respective vector has “

m”

elements that define a location in the m-dimensional space and in which each respective point of the lattice is defined with respect to a linear combination of the vectors of the basis;

obtaining a target vector “

y”

that defines a particular location in the m-dimensional space;

generating an Ising model connection weight matrix “

W”

by multiplying a transposition of “

A”

(“

A^T”

) by “

A”

;

generating an Ising model bias vector “

b”

by multiplying a transposition of “

y”

(“

y^T”

) by “

A”

;

providing “

W” and

“

b”

to an annealing system configured to solve problems written according to the Ising model;

obtaining an output from the annealing system that represents an output vector “

x”

of a particular point included in the lattice in which the particular point is the closest point in the lattice to the particular location defined by “

y”

; and

using “

x”

to obtain a solution to a closest vector problem that is defined by finding which point in the lattice is closest to the particular location as defined by “

y”

.

2. The method of claim 1, further comprising:

obtaining “

A”

from an initial basis “

AI”

in which “

AI”

defines another lattice in the m-dimensional space in which “

A”

is the same as “

AI”

except with the elements of a specific vector “

i”

of “

AI”

being doubled in “

A”

;

obtaining the target vector “

y”

from “

AI”

by using the specific vector “

i”

as the target vector “

i”

;

determining a distance between the target vector “

y” and

the output vector “

x” and

using the distance between the target vector “

y” and

the output vector “

x”

in determining a solution to a shortest vector problem that is defined by finding which point in the other lattice has the shortest vector.

3. The method of claim 2, further comprising:

repeating the operations of claim 2 for every vector of the initial basis “

AI”

to obtain a plurality of distances between each target vector “

y” and

its corresponding output vector “

x”

; and

using a particular output vector “

x”

that corresponds to the shortest distance of the plurality of distances as the solution to the shortest vector problem.

4. The method of claim 2, further comprising solving a compute and forward problem using the solution to the shortest vector problem.

5. The method of claim 1, further comprising converting values of “

W” and

“

b”

into binary format to allow for input of “

W” and

“

b”

to the annealing system

6. The method of claim 5, further comprising determining a number of bits for “

W” and

“

b”

based on a determinant of the lattice.

7. The method of claim 6, further comprising determining the determinant by determining the determinant of “

A”

.

8. The method of claim 1, further comprising testing whether a particular learning with error based cryptography system is secure using “

x”

.

9. One or more non-transitory computer-readable storage media configured to store instructions that, in response to being executed, cause a system to perform operations, the operations comprising:

obtaining a basis “

A”

that defines a lattice in an m-dimensional space, the lattice including a plurality of points in the m-dimensional space, the basis “

A”

being a matrix of “

n”

number of linearly independent vectors in which each respective vector has “

m”

elements that define a location in the m-dimensional space and in which each respective point of the lattice is defined with respect to a linear combination of the vectors of the basis;

obtaining a target vector “

y”

that defines a particular location in the m-dimensional space;

generating an Ising model connection weight matrix “

W”

by multiplying a transposition of “

A”

(“

A^T”

) by “

A”

;

generating an Ising model bias vector “

b”

by multiplying a transposition of “

y”

(“

y^T”

) by “

A”

;

providing “

W” and

“

b”

to an annealing system configured to solve problems written according to the Ising model;

obtaining an output from the annealing system that represents an output vector “

x”

of a particular point included in the lattice in which the particular point is the closest point in the lattice to the particular location defined by “

y”

; and

using “

x”

to obtain a solution to a closest vector problem that is defined by finding which point in the lattice is closest to the particular location as defined by “

y”

.

10. The one or more non-transitory computer-readable storage media of claim 9, wherein the operations further comprise:

obtaining “

A”

from an initial basis “

AI”

in which “

AI”

defines another lattice in the m-dimensional space in which “

A”

is the same as “

AI”

except with the elements of a specific vector “

i”

of “

AI”

being doubled in “

A”

;

obtaining the target vector “

y”

from “

AI”

by using the specific vector “

i”

as the target vector “

i”

;

determining a distance between the target vector “

y” and

the output vector “

x” and

using the distance between the target vector “

y” and

the output vector “

x”

in determining a solution to a shortest vector problem that is defined by finding which point in the other lattice has the shortest vector.

11. The one or more non-transitory computer-readable storage media of claim 10, wherein the operations further comprise:

repeating the operations of claim 10 for every vector of the initial basis “

AI”

to obtain a plurality of distances between each target vector “

y” and

its corresponding output vector “

x”

; and

using a particular output vector “

x”

that corresponds to the shortest distance of the plurality of distances as the solution to the shortest vector problem.

12. The one or more non-transitory computer-readable storage media of claim 10, wherein the operations further comprise solving a compute and forward problem using the solution to the shortest vector problem.

13. The one or more non-transitory computer-readable storage media of claim 9, wherein the operations further comprise converting values of “

W” and

“

b”

into binary format to allow for input of “

W” and

“

b”

to the annealing system

14. The one or more non-transitory computer-readable storage media of claim 13, wherein the operations further comprise determining a number of bits for “

W” and

“

b”

based on a determinant of the lattice.

15. The one or more non-transitory computer-readable storage media of claim 9, wherein the operations further comprise testing whether a particular learning with error based cryptography system is secure using “

x”

.

16. A system comprising:

one or more computer-readable storage media configured to store instructions; and

one or more processors communicatively coupled to the one or more computer-readable storage media and configured to, in response to execution of the instructions, cause the system to perform operations, the operations comprising;

obtaining a basis “

A”

that defines a lattice in an m-dimensional space, the lattice including a plurality of points in the m-dimensional space, the basis “

A”

being a matrix of “

n”

number of linearly independent vectors in which each respective vector has “

m”

elements that define a location in the m-dimensional space and in which each respective point of the lattice is defined with respect to a linear combination of the vectors of the basis;

obtaining a target vector “

y”

that defines a particular location in the m-dimensional space;

generating an Ising model connection weight matrix “

W”

by multiplying a transposition of “

A”

(“

A^T”

) by “

A”

;

generating an Ising model bias vector “

b”

by multiplying a transposition of “

y”

(“

y^T”

) by “

A”

;

providing “

W” and

“

b”

to an annealing system configured to solve problems written according to the Ising model;

obtaining an output from the annealing system that represents an output vector “

x”

of a particular point included in the lattice in which the particular point is the closest point in the lattice to the particular location defined by “

y”

; and

using “

x”

to obtain a solution to a closest vector problem that is defined by finding which point in the lattice is closest to the particular location as defined by “

y”

.

17. The system of claim 16, wherein the operations further comprise:

obtaining “

A”

from an initial basis “

AI”

in which “

AI”

defines another lattice in the m-dimensional space in which “

A”

is the same as “

AI”

except with the elements of a specific vector “

i”

of “

AI”

being doubled in “

A”

;

obtaining the target vector “

y”

from “

AI”

by using the specific vector “

i”

as the target vector “

i”

;

determining a distance between the target vector “

y” and

the output vector “

x” and

using the distance between the target vector “

y” and

the output vector “

x”

in determining a solution to a shortest vector problem that is defined by finding which point in the other lattice has the shortest vector.

18. The system of claim 17, wherein the operations further comprise:

repeating the operations of claim 17 for every vector of the initial basis “

AI”

to obtain a plurality of distances between each target vector “

y” and

its corresponding output vector “

x”

; and

using a particular output vector “

x”

that corresponds to the shortest distance of the plurality of distances as the solution to the shortest vector problem.

19. The system of claim 17, wherein the operations further comprise solving a compute and forward problem using the solution to the shortest vector problem.

20. The system of claim 16, wherein the operations further comprise converting values of “

W” and

“

b”

into binary format to allow for input of “

W” and

“

b”

to the annealing system