IP Library › Granted Patent US 12,189,594
Granted Patent B2
US 12,189,594 · App. 18/255,928 · Granted Jan 7, 2025

Secret hash table construction apparatus, secret hash table construction system, secret hash table construction method and program

Inventor: Atsunori Ichikawa (Tokyo, JP)
Assignee: NIPPON TELEGRAPH AND TELEPHONE CORPORATION
G06F16/2255G06F21/602
View Patent ↗
Loading inventors, assignments & file history…
Monitor This Case
Get email alerts when status or documents change.
Order Certified Copies
Most orders are placed with the USPTO same day — all within 24 business hours.
Order via The Patent Place →
Pre-filled with this patent's details
Quick Facts
Patent No.
US 12,189,594
App. No.
18/255,928
Granted
Jan 7, 2025
Kind
B2
Abstract

A secret hash table construction apparatus constructs a secret hash table capable of storing up to Z items of data in B kinds of address values by secret computation from a real data stream including items of data each having a key and a flag indicating whether or not the data is dummy data. The secret hash table construction apparatus executes generating a first array in which a storage destination data array is connected with another storage destination data array as dummy data; generating a second array in which the real data stream is connected with a dummy data stream; sorting each of the first and second arrays based on a ranking operations; extracting address values of lower ranks to generate a third array; and sorting the second array using a fourth array, and outputting BZ elements in the sorted second array as the secret hash table.

Claims (34)

1. A secret hash table construction apparatus for constructing a secret hash table capable of storing up to a maximum of Z items of data in each of B kinds of address values by secret computation from a real data stream including a plurality of items of data each having a key and a flag indicating whether or not the data is dummy data, the secret hash table construction apparatus comprising:

a memory; and

a processor configured to execute

generating a first array in which a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value with respect to each item of data of the real data stream is connected with a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value as dummy data;

generating a second array in which the real data stream is connected with a dummy data stream;

sorting each of the first array and the second array based on the first address value and the flag in the first array, performing a ranking operation on a same item of data with respect to the first address value of the sorted first array, and sorting each of the first array and the second array based on the ranking;

sorting each of the first array and the second array based on the second address value and the flag in the first array and performing a ranking operation on a same item of data with respect to the second address value of the sorted first array;

extracting an address value of a lower rank among the first address value and the second address value in the first array, and generating a third array including the extracted address value and a flag; and

sorting the second array using a fourth array obtained by comparing each element of a rank array computed from an address value in the third array with Z, and outputting B*Z elements in the sorted second array as the secret hash table.

2. The secret hash table construction apparatus according to claim 1 , wherein the processor generates the secret hash table without performing sorting other than sorting based on the fourth array with respect to the second array in which the real data array is connected with the dummy data array by using a tag array including tags each indicating each item of data in the real data array and each item of data in the dummy data array.

3. The secret hash table construction apparatus according to claim 1 , wherein the processor computes two address values from a key value of an access object, acquires 2Z items of data corresponding to the two address values from the secret hash table, and returns data having a same key value as the key value among the 2Z items of data.

4. The secret hash table construction apparatus according to claim 1 , wherein the processor computes two address values from a key value to be deleted, acquires 2Z items of data corresponding to the two address values from the secret hash table, and deletes data having a same key value as the key value among the 2Z items of data.

5. The secret hash table construction apparatus according to claim 1 , wherein the processor sorts all data items in the secret hash table based on flags of the data, and acquires a predetermined number of items of data at top of the secret hash table as the real data stream.

6. A secret hash table construction system for constructing a secret hash table capable of storing up to a maximum of Z items of data in each of B kinds of address values by secret computation from a real data stream including a plurality of items of data each having a key and a flag indicating whether or not the data is dummy data, the secret hash table construction system comprising a computing unit which:

generating a first array in which a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value with respect to each item of data of the real data stream is connected with a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value as dummy data;

generating a second array in which the real data stream is connected with a dummy data stream;

sorting each of the first array and the second array based on the first address value and the flag in the first array, performing a ranking operation on a same item of data with respect to the first address value of the sorted first array, and sorting each of the first array and the second array based on the ranking;

sorting each of the first array and the second array based on the second address value and the flag in the first array and performing a ranking operation on a same item of data with respect to the second address value of the sorted first array;

extracting an address value of a lower rank among the first address value and the second address value in the first array, and generating a third array including the extracted address value and a flag; and

sorting the second array using a fourth array obtained by comparing each element of a rank array computed from an address value in the third array with Z, and outputting B*Z elements in the sorted second array as the secret hash table.

7. A secret hash table construction method executed by a secret hash table construction system for constructing a secret hash table capable of storing up to a maximum of Z items of data in each of B kinds of address values by secret computation from a real data stream including a plurality of items of data each having a key and a flag indicating whether or not the data is dummy data, the secret hash table construction method comprising:

generating a first array in which a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value with respect to each item of data of the real data stream is connected with a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value as dummy data;

generating a second array in which the real data stream is connected with a dummy data stream;

sorting each of the first array and the second array based on the first address value and the flag in the first array, performing a ranking operation on a same item of data with respect to the first address value of the sorted first array, and sorting each of the first array and the second array based on the ranking;

sorting each of the first array and the second array based on the second address value and the flag in the first array and performing a ranking operation on a same item of data with respect to the second address value of the sorted first array;

extracting an address value of a lower rank among the first address value and the second address value in the first array, and generating a third array including the extracted address value and a flag; and

sorting the second array using a fourth array obtained by comparing each element of a rank array computed from an address value in the third array with Z, and outputting B*Z elements in the sorted second array as the secret hash table.

8. A non-transitory computer-readable recording medium having computer-readable instructions stored thereon, which when executed, cause a computer to perform a secret hash table construction method executed by a secret hash table construction system for constructing a secret hash table capable of storing up to a maximum of Z items of data in each of B kinds of address values by secret computation from a real data stream including a plurality of items of data each having a key and a flag indicating whether or not the data is dummy data, the secret hash table construction method comprising:

generating a first array in which a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value with respect to each item of data of the real data stream is connected with a storage destination data array including a first address value and a second address value, a flag, and a rank for each address value as dummy data;

generating a second array in which the real data stream is connected with a dummy data stream;

sorting each of the first array and the second array based on the first address value and the flag in the first array, performing a ranking operation on a same item of data with respect to the first address value of the sorted first array, and sorting each of the first array and the second array based on the ranking;

sorting each of the first array and the second array based on the second address value and the flag in the first array and performing a ranking operation on a same item of data with respect to the second address value of the sorted first array;

extracting an address value of a lower rank among the first address value and the second address value in the first array, and generating a third array including the extracted address value and a flag; and

sorting the second array using a fourth array obtained by comparing each element of a rank array computed from an address value in the third array with Z, and outputting B*Z elements in the sorted second array as the secret hash table.

Assignments (2)
CHANGE OF NAME Recorded Aug 15, 2025
From: NIPPON TELEGRAPH AND TELEPHONE CORPORATION
To: NTT, INC.
Reel/Frame 072491/0021 →
ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Jun 5, 2023
From: ICHIKAWA, ATSUNORI
To: NIPPON TELEGRAPH AND TELEPHONE CORPORATION
Reel/Frame 063852/0959 →
Continuity (1)
Related Publication 20240028576A1 · Jan 25, 2024
References Cited (16)
US 20050240943A1 · Smith · 2005 [cited by examiner]
US 20090254572A1 · Redlich · 2009 [cited by examiner]
US 20140304505A1 · Dawson · 2014 [cited by examiner]
US 20190147770A1 · Yoshino · 2019 [cited by examiner]
US 20230039723A1 · Ichikawa · 2023 [cited by examiner]
Asharov et al.: “OptORAMa: Optimal Oblivious RAM”, Journal of the ACM, vol. 70, No. 1, Article 4. Publication date: Dec. 2022 (Year: 2022). [cited by examiner]
Chan et al.: “Perfectly Secure Oblivious Parallel RAM”, The University of Hong Kong (Year: 2018). [cited by examiner]
Kushilevitz et al.: “Sub-logarithmic Distributed Oblivious RAM with Small Block Size”, arXiv.org e-Print archive as arXiv:1802.05145 [cs.CR] (Year: 2018). [cited by examiner]
Atsunori Ichikawa et al., “Optimal Secret Hash in 3-Party Computation and Oblivious RAM with Sublogarithmic Efficiency”, 2020 Symposium on Cryptography and Information Security (SCIS), Proceedings (2020). [cited by applicant]
T-H.H.Chan et al., “Oblivious hashing revisited, and applications to asymptotically efficient ORAM and OPRAM”, Cryptology ePrint Archive, Report 2017/924, 2017. [cited by applicant]
K. Chida et al., “High-throughput secure AES computation”, In WAHC@CCS 2018, pp. 13-24, 2018. [cited by applicant]
K. Chida et al., “An efficient secure threeparty sorting protocol with an honest majority”, CryptologyePrint Archive, Report 2019/695 (2019), https://eprint.iacr.org/2019/695. [cited by applicant]
O. Goldreich et al., “Software protection and simulation on oblivious RAMs”, J. ACM, 43(3):1-44, Nov. 1993. [cited by applicant]
M. Ito et al., “Secret sharing schemes realizing general access structures”, Proceedings of the IEEE Global Telecommunication Conference, Globecom 87, pp. 99-102, 1987. [cited by applicant]
A. Shamir, “How to share a secret”, Commun. ACM, vol. 22, No. 11, pp. 612-613, 1979. [cited by applicant]
Naoto Kiribuchi et al., “MEVAL3: A Library for Programmable Secret Computation”, Symposium on Cryptography and Information Security (SCIS), 2018. [cited by applicant]