Secure computation apparatus, secure computation system, secure computation method, and program

Patent metadata

Field	Value
Publication number	US-12475237-B2
Application number	US-202118566678-A
Country	US
Kind code	B2
Filing date	Jun 8, 2021
Priority date	Jun 8, 2021
Publication date	Nov 18, 2025
Grant date	Nov 18, 2025

Abstract

By using [x 0,0 ], . . . , [x 0,r(0)-1 ], . . . , [x L-1,0 ], . . . , [x L-1,r(L-1)-1 ] obtained by concealing L sets X 0 ={x 0,0 , . . . , x 0,r(0)-1 }, . . . , X L-1 ={x L-1,0 , . . . , x L-1,r(L-1)-1 }, [c 0 ], . . . , [c m-1 ] obtained by concealing the number c p of elements representing k p among x 0,0 , . . . , x 0,r(0)-1 , . . . , x L-1,0 , . . . , x L-1,r(L-1)-1 for p=0, . . . , m−1 are obtained, [eq 0 ], . . . , [eq m-1 ] obtained by concealing eq p =T when c p is L and eq p =F when c p is not L for p=0, . . . , m−1 are obtained, and a data structure including [k p ] and [eq p ] associated with each other is output as a concealed operation result of a product set of X 0 , . . . , X L-1 .

First claim

The invention claimed is:

1 . A secure computation device that obtains a concealed operation result representing concealed information of a product set of L sets X 0 , . . . , X L-1 while concealing sets X 0 ={x 0,0 , . . . , X 0,r(0)-1 }, . . . , X L-1 ={X L-1,0 , . . . , X L-1,r (L-1)-1 }, L being an integer of 2 or greater, i=0, . . . , L−1, r(i) being an integer of 1 or greater, j(i)=0, . . . , r(i)-1, m being an integer of 1 or greater, k 0 , . . . , k m-1 being pieces of key information different from each other, p=0, . . . , m−1, and [α] being concealed information of α, the secure computation device comprising processing circuitry configured to:
(A) obtain count results [c 0 ], . . . , [c m-1 ] through secure computation by using concealed elements [x 0,0 ], . . . , [X 0,r(0)-1 ], . . . , [X L-1,0 ], . . . , [X L-1,r(L-1)-1 ] where each element x i,j(i) represents any one of the key information k 0 , . . . , k m-1 , and a number of elements representing key information k p among elements X 0,0 , . . . , X 0,r(0)-1 , . . . , X L-1,0 , . . . , X L-1,r(L-1)-1 iS C p ;
(B) obtain equality check results [eq 0 ], . . . , [eq m-1 ] through the secure computation by using count results [c 0 ], . . . , [C m-1 ], where eq p =T when c p is L, eq p =F when c p is not L, and T and F are different from each other; and
(C) output the concealed operation result including concealed key information [k p ] and a equality check result [eq p ] associated with each other,

wherein the processing circuitry is configured to further obtain concealed key information [k 0 ], . . . , [k m-1 ] through the secure computation by using the concealed elements [x 0,0 ], . . . , [X 0,r(0)-1 ], . . . , [X L-1,0 ], . . . , [X L-1,r(L-1)-1 ].

2 . The secure computation device according to claim 1 , wherein
n is an integer greater than m, (A) the processing circuitry is configured to obtain sequences ([f], [k], [c]), where a sequence [f] is a sequence including m valid flags [f 0 ], . . . , [f m-1 ] and n-m dummy flags [f m ], . . . , [f n-1 ], where f 0 , . . . , f m-1 are B 1 , f m , . . . , f n-1 are B 0 , and B 1 and B 0 are different from each other, a sequence [k] is a sequence including m pieces of concealed key information [k 0 ], . . . , [k m-1 ] and n-m pieces of dummy information [k m ], . . . , [k n-1 ], a sequence [c] is a sequence including m count results [c 0 ], . . . , [c m-1 ] and n-m pieces of dummy information [c m ], . . . , [C n-1 ], for p=0, . . . , m−1, a valid flag [f p ], a concealed key information [k p ], and a count result [c p ] are associated with each other, and for q=m, . . . , n−1, a dummy flag [f q ], a dummy information [k q ], and a dummy information [c q ] are associated with each other, (B) the processing circuitry is configured to obtain equality check results [eq 0 ], . . . , [eq m-1 ] and dummy information [eq m ], . . . , [eq n-1 ] through the secure computation by using the sequences ([f], [k], [c]), and (C) the processing circuitry is configured to output the concealed operation result including the concealed key information [k p ] and the equality check result [eq p ] associated with each other for p=0, . . . , m−1, and the dummy information [k q ] and a dummy information [eq q ] associated with each other for q=m, . . . , n−1.

3 . The secure computation device according to claim 1 , wherein L is an integer of 3 or greater.

4 . A secure computation system comprising the secure computation device according to claim 1 .

5 . A secure computation method by a secure computation device that obtains a concealed operation result representing concealed information of a product set of L sets X 0 , . . . , X L-1 while concealing sets X 0 ={x 0,0 , . . . , X 0,r(0)-1 }, . . . , X L-1 ={X L-1,0 , . . . , X L-1,r(L-1)-1 }, L being an integer of 2 or greater, i=0, . . . , L−1, r(i) being an integer of 1 or greater, j(i)=0, . . . , r(i)-1, m being an integer of 1 or greater, k 0 , . . . , k m-1 are pieces of key information different from each other, p=0, . . . , m−1, and [α] being concealed information of a, the secure computation method comprising:
(A) a counting step of obtaining count results [c 0 ], . . . , [c m-1 ] through secure computation by using concealed elements [x 0,0 ], . . . , [x 0,r(0)-1 ], . . . , [X L-1,0 ], . . . , [X L-1,r(L-1)-1 ] where each element X i,j(i) represents any one of the key information k 0 , . . . , k m-1 , and a number of elements representing key information k p among elements X 0,0 , . . . , X 0,r(0)-1 , . . . , X L-1,0 , . . . , X L-1,r(L-1)-1 iS C p ;
(B) an equality check step of obtaining equality check results [eq 0 ], . . . , [eq m-1 ] through the secure computation by using count results [c 0 ], . . . , [C m-1 ], where eq p =T when c p is L, eq p =F when c p is not L, and T and Fare different from each other; and
(C) an output flag adding step of outputting the concealed operation result including concealed key information [k p ] and a equality check result [eq p ] associated with each other,
wherein the method further comprises obtaining concealed key information [k 0 ], . . . , [k m-1 ], through the secure computation by using the concealed elements [X 0,0 ], . . . , [X 0,r(0)-1 ], . . . , [X L-1,0 ], . . . , [X L-1,r (L-1)-1].

6 . A non-transitory computer-readable recording medium storing a program for causing a computer to function as the secure computation device according to claim 1 .

Assignees

• Ntt Inc

Inventors

• Sudo Hiroki
• Ikarashi Dai

Classifications

• H04L2209/046

  of operations, operands or results of the operations · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• H04L9/008

  involving homomorphic encryption · CPC title

• G06F21/602 Primary

  Providing cryptographic facilities or services · CPC title

• H04L9/085 Primary

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title