Secret hash table construction system, reference system, methods for the same

Patent metadata

Field	Value
Publication number	US-12333039-B2
Application number	US-202017792145-A
Country	US
Kind code	B2
Filing date	Jan 16, 2020
Priority date	Jan 16, 2020
Publication date	Jun 17, 2025
Grant date	Jun 17, 2025

Abstract

A server determines an array [[addr]] indicating a storage destination of each piece of data, generates an array of concealed values, and connects the generated array to the array [[addr]] to determine an array [[addr′]]. The server generates a sort permutation [[σ 1 ]] for the array, applies the sort permutation [[σ 1 ]] to the array [[addr′]], and converts the array [[addr′]] into an array with a sequence composed of first Z elements set to [[i]] followed by α i elements set to [[B]]. The server generates a sort permutation [[σ 2 ]] for the converted array [[addr′]], generates dummy data, imparts the generated dummy data to the concealed data sequence, applies the sort permutations [[σ 1 ]] and [[σ 2 ]] to the data array imparted with the dummy data, and generates, as a secret hash table, a data sequence obtained by deleting the last N pieces of data from the sorted data array.

First claim

The invention claimed is:

1. A secret hash table construction system including a plurality of servers and constructing a secret hash table by a coordination protocol of the plurality of servers by using secure computation, wherein
the secret hash table has a data structure configured to have B address values and storing a maximum of Z pieces of data for each of the B address values, and
each of the plurality of servers comprises processing circuitry configured to implement:
a storage destination array calculation unit configured to determine, for a concealed data sequence ((A)), a pseudo-random function value ((addr i )) by using a key ((k i )) of each piece of data of the concealed data sequence ((A)) as input of a pseudo-random function and a secret key ((s)) as a secret key of the pseudo-random function, to determine an array ((addr)) indicating a storage destination of each piece of the data;
a concealed value array connection unit configured to generate an array ((addr dummy )) of concealed values and connect the generated array ((addr dummy )) to the array ((addr)) to determine an array ((addr′))←((addr))∥((addr dummy ));
a sort permutation generation application unit configured to generate a sort permutation ((σ 1 )) for the array ((addr′)) by using values included in the array ((addr′)) as keys and apply the sort permutation ((σ 1 )) to the array ((addr′));
a conversion unit configured to convert the array ((addr′)) into an array with a sequence composed of first Z elements set to ((i)) followed by α i elements set to ((B)), α i being the number of i included in the array ((addr′));
a sort permutation generation unit configured to generate a sort permutation ((σ 2 )) for the converted array ((addr′)) by using values included in the converted array ((addr′)) as keys; and
a table generation unit configured to generate dummy data ((empty)) for a concealed data sequence ((˜A)) corresponding to the concealed data sequence ((A)), impart the generated dummy data ((empty)) to the concealed data sequence ((˜A)), apply the sort permutations ((σ 1 )) and ((σ 2 )) to the data array imparted with the dummy data, and generate, as a secret hash table, a data sequence obtained by deleting the last N pieces of data from the sorted data array.

2. A reference system for referring to a secret hash table constructed by the secret hash table construction system according to claim 1 ,
the reference system including a plurality of servers and referring to the secret hash table by a coordination protocol of the plurality of servers by using secure computation, wherein
each of the plurality of servers comprises processing circuitry configured to implement:
a data sequence acquisition unit configured to use a concealed key value ((k)) of data to be referred to as input of a pseudo-random function PRF and use the secret key ((s)) to generate an address value ((t))←PRF(((k)), ((s))) corresponding to the concealed key value ((k)), restore an address value t from the address value ((t)), and acquire a data sequence ((A t )) corresponding to the address value;
a comparison result acquisition unit configured to compare key values included in the data sequence ((A t )) and the concealed key value ((k)) and calculate an array ((E)) composed of the results of the comparison; and
an inner product calculation unit configured to calculate an inner product of the data sequence ((A t )) and the array ((E)).

3. The secret hash table construction system according to claim 1 , wherein
the secret hash table construction system constructs two secret hash tables having a data structure configured to have B address values and store a maximum of Z pieces of data for each of the B address values, and
the table generation unit generates dummy data ((empty)) for the concealed data sequence ((˜A)) corresponding to the concealed data sequence ((A)), imparts the generated dummy data ((empty)) to the concealed data sequence ((˜A)), applies the sort permutations ((σ 1 )) and ((σ 2 )) to the data array imparted with the dummy data, generates, as a first secret hash table, a data sequence obtained by deleting the last N pieces of data from the sorted data array, and controls each of the units to construct a second secret hash table for a data sequence ((B)) composed of the last N pieces of data of the sorted data array, by using a second secret key ((s 2 )) instead of the secret key ((s)).

4. A secret hash table construction system including a plurality of servers and constructing a secret hash table by a coordination protocol of the plurality of servers by using secure computation, wherein
the secret hash table has a data structure configured to have B address values and store a maximum of Z pieces of data for each of the B address values, and
each of the plurality of servers comprises processing circuitry configured to implement:
a storage destination array calculation unit configured to determine, for a concealed data sequence ((A)), a pseudo-random function value ((addr 0 i )) by using a key ((k i )) of each piece of data of the concealed data sequence ((A)) as input of a pseudo-random function and a secret key ((s 0 )) as a secret key of the pseudo-random function, to determine an array ((addr 0 )) indicating a storage destination of each piece of the data, and further configured to determine, for the concealed data sequence ((A)), a pseudo-random function value ((addr 1 i )) by using the key ((k i )) of each piece of the data of the concealed data sequence ((A)) as input of the pseudo-random function and a secret key ((s 1 )) as a secret key of the pseudo-random function, to determine an array ((addr 1 )) indicating a storage destination of each piece of the data;
a concealed value array generation unit configured to generate arrays ((addr 0 dummy )) and ((addr 1 dummy )) of concealed values;
a tag imparting unit configured to impart tags (( 1 )), . . . , ((N+BZ)) to an array ((A′)) obtained by connecting B×Z pieces of dummy data to the concealed data sequence ((A));
an array creation unit configured to create an array ((T))=(((t 1 )), . . . , ((t N+BZ ))), where ((t i ))=(((i)), ((addr 0 i )), ((addr 1 i )), ((d))), (i)) is each of the tags, ((addr 0 i )) and ((addr 1 i )) are i-th elements of the arrays ((addr 0 )) and ((addr 1 )), respectively, and ((d)) is a concealed value indicating whether data is dummy data;
a sort unit configured to repeat the following processing (i) to (ix) Z times,
(i) newly generating a secret random permutation for the array ((T)) and applying the new secret random permutation to the array ((T)),
(ii) generating a sort permutation using an element ((addr 0 i )) of the array ((addr 0 )) as a key value and applying the generated sort permutation to the array ((T)),
(iii) creating, for a sorted array ((T′)), a secret array ((M)) obtained by marking data located at the beginning for each address value,
(iv) creating a sort permutation for the array ((M)) and applying the created sort permutation to ((T′)),
(v) separating the last B pieces of data from ((T′)), retaining the B pieces of data as an array ((L 0 j )), and retaining the array shortened by B as ((T″)),
(vi) sorting ((T″)) by using ((addr 1 i )) as a key value, creating, for the sorted array, a secret array obtained by marking the data located at the beginning for each address value, creating a sort permutation for the created array, and applying the created sort permutation to ((T″)),
(vii) separating the last B pieces of data from ((T″)) and retaining the B pieces of data as an array ((L 1 j )),
(viii) comparing respective elements of the arrays ((L 0 j )) and (L 1 j )) in order from the beginning and exchanging elements when dummy data is present in B 0 j , and
(ix) connecting ((L 1 j )) to the array ((T″)), setting the connected arr

Assignees

• Nippon Telegraph & Telephone

Inventors

• Ichikawa Atsunori
• Hamada Koki
• Kikuchi Ryo

Classifications

• G06F12/1018

  involving hashing techniques, e.g. inverted page tables · CPC title

• H04L9/0894

  Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage · CPC title

• G06F21/14

  against software analysis or reverse engineering, e.g. by obfuscation · CPC title

• H04L2209/08

  Randomization, e.g. dummy operations or using noise · CPC title

• G06F16/9014

  hash tables · CPC title