Secure computation apparatus, secure computation system, secure computation method, and program
View Patent ↗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 α.
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
]
[
x
n
-
1
]
[
B
1
]
[
y
0
]
⋮
⋮
[
B
1
]
[
y
m
-
1
]
)
(B) the processing circuitry is configured to obtain the sorted sequence ([s′], [M′]) represented by:
(
[
s
′
]
,
[
M
′
]
)
=
(
[
s
0
′
]
[
M
0
′
]
⋮
⋮
[
s
n
+
m
-
1
′
]
[
M
n
+
m
-
1
′
]
)
a sequence of M′ 0 , . . . , M′ n+m−1 is a stable sorting result of a sequence of the elements M 0 , . . . , M n+m−1 according to an order relation of content represented by each of the elements M 0 , . . . , M n+m−1 , and
each sorted value [s′ q ] is an element [s r ] associated with an element [M r ] stably sorted into each sorted element [M′ q ] by secure computation, and r=0, . . . , n+m−1.
3. A secure computation system having the secure computation device according to claim 1 .
4. A secure computation method of 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 method comprising:
(A) an input flag adding step of receiving n first elements [x 0 ], . . . , [x n−1 ] and m second elements [y 0 ], . . . , [y m−1 ] as inputs, and obtaining 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 B 0 and B 1 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) a stable sorting step of performing 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 ] by secure computation, 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) an equality check step of obtaining 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) an output flag generation step of obtaining 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 =D 0 when “eq q =T and seq q =F” does not hold, and Di and Do are different from each other; and
(E) an output flag adding step of outputting the concealed operation result including the output flag [f q ] and the sorted element [M′ q ] of the sequence [M′] associated with each other.
5. 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 .