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

Patent metadata

Field	Value
Publication number	US-12386948-B2
Application number	US-202118565091-A
Country	US
Kind code	B2
Filing date	Jun 4, 2021
Priority date	Jun 4, 2021
Publication date	Aug 12, 2025
Grant date	Aug 12, 2025

Abstract

A concealed operation result indicating concealed information of an Intersect operation result of X and Y is obtained while X={{x 0 , . . . , x n−1 }} and Y={{y 0 , . . . , y m−1 }} are concealed. A secure computation device obtains a sequence ([s], [M]) including [s] including n [B 0 ] and m [B 1 ] and [M] including [x 0 ], . . . , [x n−1 ] and [y 0 ], . . . , [y m−1 ], performs stable sorting on the sequence ([s], [M]) according to an order relationship of content represented by each of the elements M 0 , . . . , M n+m−1 to obtain a sequence ([s′], [M′]), obtain [eq q ] where eq q =T when M′ q =M′ q+1 and eq q =F otherwise and [seq q ] where seq q =T when s′ q =s′ q+1 and seq q =F otherwise, obtain [f q ] where f q =D 1 when eq q =T and seq q =F and f q =D 0 otherwise, and outputs [f q ] and [M′ q ]. Where, [α] is concealed information of α.

First claim

The invention claimed is:

1. A secure computation device that obtains a concealed operation result representing concealed information of an Intersect operation result between a first multiset X={{x 0 , . . . , x n−1 }} and a second multiset Y={{y 0 , . . . , y m−1 }} while concealing the first multiset X and the second multiset Y, the device comprising processing circuitry configured to:
(A) receive n first elements [x 0 ], . . . , [x n−1 ] and m second elements [y 0 ], . . . , [y m−1 ] as inputs, and obtain an input flagged sequence ([s], [M]) including a sequence [s]=([s 0 ], . . . , [s n−1 ], [s n ], . . . , [s n+m−1 ])=([B 0 ], . . . , [B 0 ], [B 1 ], . . . , [B 1 ]) including n first values [B 0 ] and m second values [B 1 ] and a sequence [M]=([M 0 ], . . . , [M n−1 ], [M n ], . . . , [M n+m−1 ])=([x 0 ], . . . , [x n−1 ], [y 0 ], . . . , [y m−1 ]) including first elements [x 0 ], . . . , [x n−1 ] and second elements [y 0 ], . . . , [y m−1 ] in which Bo and Bi are different from each other, each first value [s i ]=[B 0 ] is associated with each first element [M i ]=[x i ], and each second value [s j+n ]=[B 1 ] is associated with each second element [M j+n ]=[y j ], where n and m are positive integers, i=0, . . . , n−1, j=0, . . . , m−1, q=0, . . . , n+m−1, and [α] is concealed information of α;
(B) perform, by secure computation, stable sorting according to an order relation of content represented by each of elements M 0 , . . . , M n+m−1 corresponding to the sequence [M] for the input flagged sequence ([s], [M]) while maintaining a correspondence between [s q ] and [M q ], to obtain a sorted sequence ([s′], [M′]) including a sequence [s′]=([s′ 0 ], . . . , [s′ n+m−1 ]) of sorted values [s′ 0 ], . . . , [s′ n+m−1 ] and a sequence [M′]=([M′= 0 ], . . . , [M′ n+m−1 ]) of sorted elements [M′ 0 ], . . . , [M′ n+m−1 ];
(C) obtains obtain a first equality check result [eq q ] and a second equality check result [seq q ] by secure computation using the sorted sequence ([s′], [M′]), where eq q =T when M′q=M′ q+1 holds, eq q =F when M′q=M′ q+1 does not hold, eq n+m−1 =F, seq q =T when s′q=s′q+1 holds, seq q =F when s′q=s′q+1 does not hold, seq n+m−1 =F, and T and F are different from each other;
(D) obtain an output flag [f q ] by secure computation using the first equality check result [eq q ] and the second equality check result [seq q ], where, f q =D 1 when “eq q =T and seq q =F” holds, f q =Do when “eq q =T and seq q =F” does not hold, and Di and Do are different from each other; and
(E) output the concealed operation result including the output flag and the sorted element [M′ q ] of the sequence [M′] associated with each other.

2. The secure computation device according to claim 1 , wherein
(A) the processing circuitry is configured to obtain the input flagged sequence ([s], [M]) represented by:

(

[
s
]

,

[
M
]

)

=

(

[

s
0

]

[

M
0

]

⋮

⋮

[

s

n
-
1

]

[

M

n
-
1

]

[

s
n

]

[

M
n

]

⋮

⋮

[

s

n
+
m
-
1

]

[

M

n
+
m
-
1

]

)

=

(

[

B
0

]

[

x
0

]

⋮

⋮

[

B
0

Assignees

• Nippon Telegraph & Telephone

Inventors

• Sudo Hiroki
• Ikarashi Dai

Classifications

• G06F21/71

  to assure secure computing or processing of information · CPC title

• G06F2221/034

  Test or assess a computer or a system · CPC title

• H04L2209/046

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

• H04L9/008

  involving homomorphic encryption · CPC title

• H04L2209/46

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