Device for performing arithmetic operations of multivariate polynomials, control method, and program

Patent metadata

Field	Value
Publication number	US-9672007-B2
Application number	US-201314366129-A
Country	US
Kind code	B2
Filing date	Feb 15, 2013
Priority date	Mar 2, 2012
Publication date	Jun 6, 2017
Grant date	Jun 6, 2017

Abstract

Provided is an arithmetic operation device including a plurality of shift registers each constituted by first to (N+1) th registers and a control unit configured to cause the shift registers to move stored values. The control unit causes the stored values to be output from a predetermined pair of registers constituting the first shift register while causing the stored values to move so that all combinations of a pair of stored values selectable from the stored values are output, and causes the stored values to be output from a predetermined pair of registers constituting the other shift register while causing the stored values to move.

First claim

The invention claimed is:

1. An arithmetic operation device, comprising:
a plurality of shift registers each constituted by first to (N+1) th registers and configured to move a stored value from an (n+1) th register to an n th register, wherein (n=1 to N); and
a control unit configured to cause a first shift register, in which the first to (N+1) th registers respectively store stored values x 1 , . . . , x N , and c, to move the stored values, and to cause a second shift register in which the first to (N+1) th registers respectively store stored values x N ′, . . . , x 1 ′, and c′, to move the stored values in a same cycle as the first shift register, wherein c is a determined number, and c′ is a determined number,
wherein the control unit is further configured to output the stored values from a first determined pair of registers constituting the first shift register while moving the stored values so that all combinations of a pair of stored values selectable from the stored values x 1 , . . . , x N , and c are output, wherein the first determined pair of registers of the first shift register are the first register and the second register, and
output the stored values from second determined pair of registers constituting the second shift register while moving the stored values so that all combinations of a pair of stored values selectable from the stored values x N ′, . . . , x 1 ′, and c′ are output, wherein the second determined pair of registers of the second shift register are the corresponding first register and the corresponding (N+1) th register.

2. The arithmetic operation device according to claim 1 , further comprising:
a variable multiplication unit configured to multiply two stored values output from each of the plurality of shift registers;
a selection unit configured to select one from output results from the variable multiplication unit;
a coefficient multiplication unit configured to multiply the output value of the selection unit by a determined coefficient;
a first summing unit configured to add up all output values of the coefficient multiplication unit relating to the stored values output from the first shift register; and
a second summing unit configured to add up all output values of the coefficient multiplication unit relating to the stored values output from the second shift register.

3. The arithmetic operation device according to claim 1 , wherein, based on a combination of a first control process in which the stored values stored in the second to (N+1) th registers are moved while a stored value stored in the first register is maintained in at least one of the plurality of shift registers and a second control process in which all stored values stored in the first to (N+1) th registers are moved in the at least one of the plurality of shift registers, the control unit is further configured to control the plurality of shift registers so that all combinations of the pair of stored values are output.

4. An arithmetic operation device, comprising:
a plurality of shift registers each constituted by first to (N+1) th registers and configured to move a stored value from an (n+1) th register to an n th register, wherein (n=1 to N); and
a control unit configured to cause a first shift register, in which the first to (N+1) th registers respectively store stored values x 1 , . . . , x N , and c, to move the stored values, to cause a second shift register in which the first to (N+1) th registers respectively store stored values x N ′, . . . , x 1 ′, and c′ to move the stored values in a same cycle as the first shift register, and to cause a third shift register in which the first to (N+1) th registers respectively store stored values x N ″, . . . , x 1 ″, and c″ to move the stored values in a same cycle as the second shift register, wherein c is a determined number, c′ is a determined number and c″ is a determined number,
wherein the control unit
is further configured to output the stored values from a first determined pair of registers constituting the first shift register while moving the stored values to move so that all combinations of a pair of stored values selectable from the stored values x 1 , . . . , x N , and c are output, wherein the first determined pair of registers of the first shift register are the first register and the second register, and
output the stored values from a second and a third determined pair of registers constituting the second and third shift registers respectively while moving the stored values so that all combinations of a pair of stored values selectable from the stored values x N ′, . . . , x 1 ′, and c′ and all combinations of a pair of stored values selectable from the stored values x N ″, . . . , x 1 ″, and c″, wherein the second and the third determined pair of registers in the second shift register and the third shift register respectively, are the corresponding first register and the corresponding (N+1) th register.

5. The arithmetic operation device according to claim 4 , further comprising:
a variable multiplication unit configured to multiply two stored values output from each of the plurality of shift registers;
an addition unit configured to add an output value of the variable multiplication unit based on a first stored value output from the second shift register and a second stored value output from the third shift register to an output value of the variable multiplication unit based on a second stored value output from the second shift register and a first stored value output from the third shift register;
a selection unit configured to select one from output results from the variable multiplication unit and the addition unit;
a coefficient multiplication unit configured to multiply the output value of the selection unit by a determined coefficient;
a first summing unit configured to add up all output values of the coefficient multiplication unit related to the stored values output from the first shift register; and
a second summing unit configured to add up output values of the coefficient multiplication unit related to the stored values output from the second shift register and the third shift register.

6. The arithmetic operation device according to claim 4 , wherein, based on a combination of a first control process in which the stored values stored in the second to (N+1) th registers are moved while a stored value stored in the first register is maintained in at least one of the plurality of shift registers and a second control process in which all stored values stored in the first to (N+1) th registers are moved in at least one of the plurality of shift registers, the control unit is configured to control the plurality of shift registers so that all combinations of the pairs of stored values are output.

7. A control method, comprising:
moving stored values of, among a plurality of shift registers each constituted by first to (N+1) th registers and capable of moving a stored value from an (n+1) th register to an n th register, a first shift register in which the first to (N+1) th registers respectively store stored values x 1 , . . . , x N , and c and moving stored values of a second shift register in which the first to (N+1) th registers respectively store stored values x N ′, . . . , x 1 ′, and c′, in a same cycle as the first shift register, wherein (n=1 to N), wherein c is a determined number, and c′ is a determined number;
outputting the stored values from a first determined pair of registers constituting the first shift register while the stored values are moved so that all combinations of a pair of stored values selectable from the stored values x 1 , . . . , x N , and c are output, wherein the first determined pair of registers of the first shift register are the first

Assignees

• Sony Corp

Inventors

• Hiwatari Harunaga
• Akishita Toru

Classifications

• G06F7/552

  Powers or roots {, e.g. Pythagorean sums} · CPC title

• G06F5/01 Primary

  for shifting, e.g. justifying, scaling, normalising {(digital stores in which the information is moved stepwise, e.g. shift-registers G11C19/00; digital stores in which the information circulates G11C21/00)} · CPC title

• H04L9/3247

  involving digital signatures · CPC title

• H04L9/3093

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

• H04L9/3221

  interactive zero-knowledge proofs · CPC title