Granted Patent B2

US 12,333,273 · App. 17/279,096 · Granted Jun 17, 2025

Inventor: Dai Ikarashi (Musashino, JP)

Assignee: NIPPON TELEGRAPH AND TELEPHONE CORPORATION

G06F7/544G06F5/01H04L9/085

Abstract

Claims (31)

1. A secure cryptographic right shift computation system comprising m secure computation apparatuses that perform a distributed secure computation by taking an input of a distributed value [a] of a value “a” and a shift amount “b,” and calculating a distributed value [a>>b] of a value obtained by shifting the value “a” by “b” bits toward right,

wherein [⋅] is a distributed value obtained by distributing a value “⋅” by first secret sharing, <⋅> is a distributed value obtained by distributing the value “⋅” by additive secret sharing among the m secure computation apparatuses, {⋅} is a distributed value obtained by distributing a bit expression of the value “⋅” among the m secure devices “⋅,” the distributed value [⋅] and the distributed value <⋅> can be mutually converted, “a” is an arbitrary value, “b” is a shift amount, “m” is a distribution number of three or more, “u” is an integer of log m or more, “l” is a bit number of the value “a,” and >> is a right shift operator, and

wherein the secure computation apparatuses are interconnected by a network to cooperate in calculating the distributed value, and each include processing circuitry configured to:

calculate a distributed value [a′]=[2 u a] by using the distributed value [a];

convert the distributed value [a′] into a distributed value <a′>=<a′> 0 , . . . , <a′> m−1 of the additive secret sharing;

generate, for each integer i of 0 or more and less than m, a distributed value <s>=<s> 0 , . . . , <s> m−1 by calculating <s> i =<a′> i >>b+u;

convert the distributed value <s> into a distributed value [s] of the first secret sharing;

convert lower u bits of a share <a′> i of the distributed value <a′> into a distributed value {a′ i mod 2 u } of a bit expression for each integer i of 0 or more and less than m;

calculate lower u bits of −Σ i<m {a′ i mod 2 u } to obtain as a distributed value {q} of a bit expression by using the distributed value {a′ i mod 2 u };

convert the distributed value {q} into a distributed value [q] of the first secret sharing; and

calculate [s]−[2 l−(b+u) q]+1 to obtain as the distributed value [a>>b] by using the distributed values [s] and [q].

2. The cryptographic secure right shift computation system according to claim 1 ,

wherein the processing circuitry is further configured to:

convert lower b+u bits of the share <a′> i into a distributed value {a′ iR }={a′ i mod 2b+u} of a bit expression for each integer i of 0 or more and less than m; and

calculate a distributed value {z}=Σ i<m {a′ iR }+{q} of a bit expression by using the distributed values {a′ iR } and {q}, and obtains a bit sequence of a (b+u)-th bit and after of the distributed value {z} as a distributed value {z Q },

wherein:

the processing circuitry converts the distributed values {q} and {z Q } into distributed values [q] and [z Q ] of the first secret sharing; and

the processing circuitry calculates [s]−[2 l−(b+u) q]+[z Q ] to obtain as the distributed value [a>>b] by using the distributed values [s], [q], and [z Q ].

3. A secure computation apparatus included in the cryptographic secure right shift computation system according to claim 1 .

4. A non-transitory computer-readable recording medium on which a program recorded thereon for causing a computer to function as the cryptographic secure computation apparatus according to claim 3 .

5. A cryptographic secure right shift computation method executed by a secure right shift computation system that includes m secure computation apparatuses that perform a distributed secure computation by taking an input of a distributed value [a] of a value “a” and a shift amount “b,” and calculating a distributed value [a>>b] of a value obtained by shifting the value “a” by “b” bits toward right,

wherein [⋅] is a distributed value obtained by distributing a value “⋅” by first secret sharing among the m secure computation apparatuses, <⋅> is a distributed value obtained by distributing the value “⋅” by additive secret sharing among the m secure computation apparatuses, {⋅} is a distributed value obtained by distributing a bit expression of the value “⋅,” among the m secure computation apparatuses “⋅” the distributed value and the distributed value <⋅> can be mutually converted, “a” is an arbitrary value, “b” is a shift amount, “m” is a distribution number of three or more, “u” is an integer of log m or more, “l” is a bit number of the value “a,” and >> is a right shift operator, and

wherein the secure right shift computation method comprising, by processing circuitry of each of the secure computation apparatuses which are interconnected by a network to cooperate in calculating the distributed value::

calculating, a distributed value [a′]=[ 2 u a] by using the distributed value [a];

converting, the distributed value [a′] into a distributed value <a′>=<a′> 0 , . . . <a′> m−1 of the additive secret sharing;

generating, for each integer i of 0 or more and less than m, a distributed value <s>=<s> 0 , . . . , <s> m−1 by calculating <s> i =<a′> i >>b+u;

converting, the distributed value <s> into a distributed value [s] of the first secret sharing;

converting, lower u bits of a share <a′> i of the distributed value <a′> into a distributed value {a′ i mod 2 u } of a bit expression for each integer i of 0 or more and less than m;

calculating, lower u bits of −Σ i<m {a′ i mod 2 u } to obtain as a distributed value {q} of a bit expression by using the distributed value {a′ i mod 2 u };

converting, the distributed value {q} into a distributed value [q] of the first secret sharing; and

calculating, [s]−[ 2 l−(b+u) q]+1 to obtain as the distributed value [a>>b] by using the distributed values [s] and [q].

Assignments (2)

Priority Claims (1)

Continuity (1)

References Cited (12)