Secret maximum value calculation apparatus, method and program

Patent metadata

Field	Value
Publication number	US-12512973-B2
Application number	US-202017791547-A
Country	US
Kind code	B2
Filing date	Jan 17, 2020
Priority date	Jan 17, 2020
Publication date	Dec 30, 2025
Grant date	Dec 30, 2025

Abstract

A secure maximum value computation apparatus, assuming that a set X={[[x 1 ]], [[x 2 ]], . . . , [[x n ]]}, includes an output unit 1 that outputs [[x 1 ]] and [[1]] as a maximum secret value [[y]] and a flag [[z(x 1 )]], respectively, when n=1 holds, a comparison unit 2 that computes a comparison result of which is larger with respect to a predetermined order for each pair {[[x i ]], [[x j ]]}⊂X of elements of the X, a flag computation unit 3 that computes 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 a maximum value computation unit 4 that uses the [[z(x i )]] to computes a maximum value [[y]].

First claim

The invention claimed is:

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.

Assignees

• Ntt Inc

Inventors

• Hamada Koki
• Kikuchi Ryo

Classifications

• G06F7/544

  for evaluating functions by calculation {(G06F7/4824 takes precedence)} · CPC title

• H04L2209/46

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

• H04L9/0861 Primary

  Generation of secret information including derivation or calculation of cryptographic keys or passwords · CPC title

• H04L9/085 Primary

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