Granted Patent B2

US 12,512,973 · App. 17/791,547 · Granted Dec 30, 2025

Inventors: Koki Hamada (Musashino, JP); Ryo Kikuchi (Musashino, JP)

Assignee: NTT, Inc.

H04L9/0861G06F7/544

Abstract

Claims (30)

1 . A secure maximum value computation apparatus for a set of secret values X={((x 1 )), ((x 2 )), . . . , ((x n ))} where n is a positive integer, the secure maximum value computation apparatus comprising:

output circuitry configured to output ((x 1 )) and ((1)) as a maximum secret value ((y)) and a flag ((z(x 1 ))), respectively, when n=1;

comparison circuitry configured to compute comparison results of which is larger with respect to a predetermined order for every pairs {((x i )), ((x j ))}⊂X of elements of the set of secret values X, where 1≤i≤j≤n;

flag computation circuitry configured to compute whether all comparison results related to each of the ((x i ))s are “large” for each of the ((x i ))s to set a computed value as a flag ((z(x i ))); and

maximum value computation circuitry configured to use the ((z(x i ))) to compute a maximum value ((y)), wherein

in a case that a function LE(x i , x j ) outputs ((1)) when x i x j and outputs ((0)) when x j >x j , the comparison circuitry performs computations of LE(x i , x j ) for every (i, j)s (i,jϵ[l, n], i<j) to set computation results ((c i, j ))s as the comparison results,

a and b are inputs, and

in a case that a function EQ(((a)), ((b))) outputs ((1)) when a=b and outputs ((0)) when a≠b, the flag computation circuitry:

performs computations of 1−((c j, i ) for every (i, j)s (i, j∈[1, n], i>j) to set computation results as ((c i, j ))s, and

performs a computation of ((z(x j )))←EQ(Σ i≠j ((c i, j )), n−1) for each i to set a computation result as a flag ((z(x i ))).

2 . The secure maximum value computation apparatus according to claim 1 , wherein the maximum value computation circuitry computes Σ i∈[1, n] ((x i ))×((z(x i )))) to set a computation result as the maximum value ((y)).

3 . The secure maximum value computation apparatus according to claim 1 , wherein the flag computation performs computations of 1−((c j, i )) for every (i, j)s (i, j∈[1, n], i>j) to set computation results as (c i, j ))s and performs a computation of Π i≠j ((c i, j )) for each i to set a computation result as a flag ((z(x i ))).

4 . A secure maximum value computation apparatus for a set of secret values X={((x 1 )), ((x 2 )), . . . , ((x n ))}, wherein n is positive integer, the secure maximum value computation apparatus comprising:

output circuitry configured to output ((x 1 )) and ((1)) as a maximum value ((y)) and a flag ((z(x 1 ))), respectively, when n=1;

flag computation circuitry configured to compute whether all comparison results related to each of the ((x i ))s are “large” for each of the ((x i )) s to set a computed value as a flag ((Z(X i )));

comparison circuitry configured to compute comparison results of which is larger with respect to a predetermined order for every pairs {((x i )), ((x j ))}⊂X of elements of the set of secret values X, where 1≤i≤j≤n;

maximum value computation circuitry configured to use the ((z(x i ))) to compute a maximum value ((y)); and

dividing circuitry configured to divide X into two or more subsets, wherein;

the secure maximum value computation apparatus is configured to perform processing on each of the two or more subsets to compute a secret value of a maximum value and a flag corresponding to each of the two or more subsets and perform processing on a set of maximum values corresponding to the two or more subsets to compute a maximum value ((y)) and the flag for each of the two or more subsets; and

flag computation circuitry configured to compute a flag obtained by multiplying the flag computed for each of the two or more subsets with each other.

5 . A secure maximum value computation apparatus for a set of secret values X={((x 1 ), ((x 2 )), . . . , ((x n ))}, wherein n is a positive integer, the secure maximum value computation apparatus comprising:

output circuitry configured to output ((x 1 )) and ((1)) as a maximum secret value ((y)) and a flag ((z(x 1 ))), respectively, when n=1 holds;

comparison circuitry configured to compute comparison results of which is larger with respect to a predetermined order for every pairs {((x i )), ((x j ))}⊂X of elements of the set of secret values X, where 1≤i≤j≤n;

flag computation circuitry configured to compute whether all comparison results related to each of the ((x i ))s are “large” for each of the ((x i ))s to set a computed value as a flag ((z(x i )));

maximum value computation circuitry configured to use the ((z(x i ))) to compute a maximum value ((y)); and

dividing circuitry configured to divide X into two or more subsets, wherein

the secure maximum value computation apparatus performs processing on each of the two or more subsets to compute a secret value of a maximum value and a flag corresponding to each of the two or more subsets, and

the secure maximum value computation apparatus further includes processing circuitry configured to

perform processing on a set of maximum values corresponding to the two or more) subsets to compute the maximum value ((y)) and the flag for each of the two or more subsets; and

compute a flag by multiplying the flag computed for each of the two or more subsets with each other.

Assignments (2)

Continuity (1)

References Cited (16)