IP Library › Granted Patent US 11,200,346

Granted Patent B2

US 11,200,346 · App. 16/313,233 · Granted Dec 14, 2021

Secure computation for reading multiple elements from a secure text array

Inventor: Koki Hamada (Musashino, JP)

Assignee: NIPPON TELEGRAPH AND TELEPHONE CORPORATION

G06F21/72 G09C1/00

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 11,200,346
App. No.: 16/313,233
Granted: Dec 14, 2021
Kind: B2

External Links

USPTO Patent Center↗ Full Patent PDF↗

Abstract

Multiple elements are efficiently read from a secured array. A secure text array <a>=(<a[0]>, . . . , <a[n−1]>) where an array a=(a[0], . . . , a[n−1]) having a size of n is secured, secure text <x> of an integer x that is equal to or higher than 0 and less than n, and in integers i 0 , . . . , i m-1 that are equal to or higher than 0 and less than n are input into an input part 11 . A secure shift part 12 secure-shifts the secure text array <a> by <x> to obtain a secure text array <a′>=(<a′[0]>, . . . , <a′[n−1]>) where an array a′=(a′[0], . . . , a′[n−1]) obtained by shifting leftward the array a by x is secured. An array generation part 13 generates a secure text array =(<a′[i 0 ]>, . . . , <a′[i m-1 ]>) from the secure text array <a′>.

Claims (55)

1. A secure computation system comprising three or more secure computation devices for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+i 0 , . . . , x+i m-1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

wherein x denotes an absolute position of the element to be read out in the array a, i 0 , . . . , i m-1 denote relative positions of the elements to be read out from x in the array a, x is an integer that is equal to or higher than 0 and less than n, and i 0 , . . . , i m-1 are integers that are equal to or higher than 0 and less than n,

each of the three or more secure computation devices comprises circuitry configured to:

receive, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text integers i 0 , . . . , i m-1 , wherein the secure text array <a> is obtained by securing the array a=(a[0], a[1], . . . , a[n−1]), having a size of n, by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

obtain a secure text array <a′>=(<a′[0]>, . . . , <a′[n−1]>) using the secure text array <a> and the secure text <x>, wherein the secure text array <a′> is obtained by securing an array a′=(a′[0], . . . , a′[n−1]) by secret sharing, and the array a′ is obtained by shifting leftward the array a by x; and

generate a secure text array =(<a′[i 0 ]>, . . . , <a′[i m-1 ]>) from the secure text array <a′>,

wherein each of the three or more secure computation devices is configured to act upon a divided portion of the secure text array <a>, the secure text <x>, and the secure text array , such that the original values of a, x, and b are concealed from each of the three or more secure computation devices.

2. A secure computation system comprising three or more secure computation devices for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+0, . . . , x+m−1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

wherein x denotes an absolute position of the element to be read out in the array a, m denotes a count of elements to be read out from x, x is an integer that is equal to or higher than 0 and less than n, and m is a natural number,

each of the three or more secure computation devices comprises circuitry configured to:

receive, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text natural number m, wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]) having a size of n, by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

generate a secure text array =(<a′[0]>, . . . , <a′[m−1]>) from the secure text array <a′>,

3. A secure computation device included in a secure computation system comprising three or more secure computation devices for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+i 0 , . . . , x+i m-1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

each of the three or more secure computation devices comprises circuitry configured to:

receive, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text integers i 0 , . . . , i m-1 , wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]), having a size of n, by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

generate a secure text array =(<a′[i 0 ]>, . . . , <a′[i m-1 ]>) from the secure text array <a′>,

4. A secure computation device included in a secure computation system comprising three or more secure computation devices for generating a secure text array which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+0, . . . , x+m−1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

each of the three or more secure computation devices comprises circuitry configured to:

receive, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text natural number m, wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]), having a size of n, by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

generate a secure text array =(<a′[0]>, . . . , <a′[m−1]>) from the secure text array <a′>.

5. A secure computation method for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+i 0 , . . . , x+i m-1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

the secure computation method comprising:

receiving, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text integers i 0 , . . . , i m-1 , wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]) having a size of n by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, by circuitry of each of three or more secure computation devices, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

obtaining a secure text array <a′>=(<a′[0]>, . . . , <a′[n−1]>) using the secure text array <a> and the secure text <x>, wherein the secure text array <a′> is obtained by securing an array a′=(a′[0], . . . , a′[n−1]) by secret sharing, and the array a′ is obtained by shifting leftward the array a by x, by the circuitry of each of the three or more secure computation devices; and

generating a secure text array =(<a′[i 0 ]>, . . . , <a′[i m-1 ]>) from the secure text array <a′> by the circuitry of each of the three or more secure computation devices,

wherein each of the three or more secure computation devices is configured to act upon a divided portion of the secure text array <a>, and the secure text <x>, and the secure text array , such that the original values of a, x, and b are concealed from each of the three or more secure computation devices.

6. A secure computation method for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+0, . . . , x+m−1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

the secure computation method comprising:

receiving, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text natural number m, wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]), having a size of n, by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, by circuitry of each of three or more secure computation devices, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

obtaining a secure text array <a′>=(<a′[0]>, . . . , <a′[n−1]>) using the secure text array <a> and the secure text <x>, wherein the secure text array <a′> is obtained by securing an array a′=(a′[0], . . . , a∝[n−1]) by secret sharing, and the array a′ is obtained by shifting leftward the array a by x, by the circuitry of each of the three or more secure computation devices; and

generating a secure text array =(<a′[0]>, . . . , <a′[m−1]>) from the secure text array <a′> by the circuitry of each of the three or more secure computation devices,

7. A non-transitory computer readable medium including computer executable instructions that make a secure computation device perform a method for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+i 0 , . . . , x+i m-1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

the method comprising:

receiving, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text integers i 0 , . . . , i m-1 , wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]), having a size of n, by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

generating a secure text array =(<a′[i 0 ]>, . . . , <a′[i m-1 ]>) from the secure text array <a′>,

8. A non-transitory computer readable medium including computer executable instructions that make a secure computation device perform a method for generating a secure text array , which represents plain text array “b” in concealed form, having m elements by reading out elements whose positions are x+0, . . . , x+m−1 from a secure text array <a>, which represents plain text array “a” in concealed form, having n elements while concealing x,

the method comprising,

receiving, over a network, a secret share of the secure text array <a>=(<a[0]>, . . . , <a[n−1]>), a secret share of a secure text <x>, and the plain text natural number m, wherein the secure text array <a> is obtained by securing the array a=(a[0], . . . , a[n−1]) having a size of n by secret sharing, and the secure text <x> is obtained by securing an integer x by secret sharing, wherein secret sharing is a process in which an entire original plain text data is concealed from each of a plurality of devices by dividing the entire original plain text data into fragments which are shared among the plurality of devices;

generating a secure text array =(<a′[0]>, . . . , <a′[m−1]>) from the secure text array <a′>,

Assignments (1)

ASSIGNMENT OF ASSIGNOR'S INTEREST Recorded Dec 26, 2018

From: HAMADA, KOKI

To: NIPPON TELEGRAPH AND TELEPHONE CORPORATION

Reel/Frame 047852/0140 →

Priority Claims (1)

JP JP2016-134090 · Jul 6, 2016 · national

Continuity (1)

Related Publication 20190163933A1 · May 30, 2019