US 11,121,868 B2Granted

Secure computation system, secure computation device, secure computation method, and program

AssigneeNippon Telegraph and Telephone Corporation

InventorKoki Hamada

Life of this patent

Estimating the term…

Abstract

Fisher's exact test is efficiently computed through secure computation. A computation range determination part determines i0, i1, x0, x1. A preliminary computation part computes f(x0), . . . , f(x1), and generates an array M=(f(x0), . . . , f(x1)). A securing part secures the array M, and generates a secure text array <M>=(<f(x0)>, . . . , <f(x1)>). A batch-reading part generates a function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1).

Claims8

Dependent claims

A secure computation system comprising three or more secure computation devices, wherein the secure computation system generates a function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1) for computing a secret text of a probability pi (i0≤i≤i1) defined by a following equation:

p
i
=
f
⁡
(
a
+
b
)
⁢
f
⁡
(
c
+
d
)
⁢
f
⁡
(
a
+
c
)
⁢
f
⁡
(
b
+
d
)
f
⁡
(
a
+
b
+
c
+
d
)
⁢
f
⁡
(
a
i
)
⁢
f
⁡
(
b
i
)
⁢
f
⁡
(
c
i
)
⁢
f
⁡
(
d
i
)
,
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d> are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n-1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n, . . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
each of the three or more secure computation devices comprises circuitry configured to:
receive, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determine i0, i1, x0 and x1 that satisfy i0≤i1 and x0≤x1;
compute f(x0), . . . , f(x1), and generate an array M=(f(x0), . . . , f(x1));
secure the array M, and generate a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
execute following formulae, and generate the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
output the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

86 more elements

A secure computation device configured to operate in a secure computation system comprising three or more secure computation devices, wherein the secure computation device generates a function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1) for computing a secret text of a probability pi (i0≤i≤i1)defined by a following equation:

p
i
=
f
⁡
(
a
+
b
)
⁢
f
⁡
(
c
+
d
)
⁢
f
⁡
(
a
+
c
)
⁢
f
⁡
(
b
+
d
)
f
⁡
(
a
+
b
+
c
+
d
)
⁢
f
⁡
(
a
i
)
⁢
f
⁡
(
b
i
)
⁢
f
⁡
(
c
i
)
⁢
f
⁡
(
d
i
)
,
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n−1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n, . . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
the secure computation device comprises circuitry configured to:
receive, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determine i0, i1, x0 and x1 that satisfy and i0≤i1 and x0≤x1;
compute f(x0), . . . , f(x1), and generate an array M=(f(x0), . . . , f(x1));
secure the array M, and generate a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
execute following formulae, and generate the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
output the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

86 more elements

A secure computation method executed by a secure computation system comprising three or more secure computation devices, wherein the secure computation method generates a function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1) for computing a secret text of a probability pi (i0≤i≤i1) defined by a following equation:

p
i
=
f
⁡
(
a
+
b
)
⁢
f
⁡
(
c
+
d
)
⁢
f
⁡
(
a
+
c
)
⁢
f
⁡
(
b
+
d
)
f
⁡
(
a
+
b
+
c
+
d
)
⁢
f
⁡
(
a
i
)
⁢
f
⁡
(
b
i
)
⁢
f
⁡
(
c
i
)
⁢
f
⁡
(
d
i
)
,
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n-1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n, . . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c) ≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
the secure computation method comprising, by each of the three or more secure computation devices:
receive, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determining i0, i1, x0 and x1 that satisfy i0≤i1 and x1≤x1 by circuitry of each of the three or more secure computation devices;
computing f(x0), . . . , f(x1), and generating an array M=(f(x0), . . . , f(x1)) by the circuitry of each of the three or more secure computation devices;
securing the array M, and generating a secure text array <M>=(<f(x0)>, . . . , <f(x1)>) by the circuitry of each of the three or more secure computation devices;
and
executing following formulae, and generating the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1) by the circuitry of each of the three or more secure computation devices,
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
outputting the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

87 more elements

A non-transitory computer readable medium including computer executable instructions that make a secure computation device, configured to operate in a secure computation system comprising three or more secure computation devices, perform a method, wherein the method generates a function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1) for computing a secret text of a probability pi (i0≤i≤i1) defined by a following equation:

p
i
=
f
⁡
(
a
+
b
)
⁢
f
⁡
(
c
+
d
)
⁢
f
⁡
(
a
+
c
)
⁢
f
⁡
(
b
+
d
)
f
⁡
(
a
+
b
+
c
+
d
)
⁢
f
⁡
(
a
i
)
⁢
f
⁡
(
b
i
)
⁢
f
⁡
(
c
i
)
⁢
f
⁡
(
d
i
)
,
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n−1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n,. . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
the method comprising:
receiving, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determining i0, i1, x0 and x1 that satisfy and i0≤i1 and x0≤x1;
computing f(x0), . . . , f(x1), and generating an array M=(f(x0), . . . , f(x1));
securing the array M, and generating a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
executing following formulae, and generating the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
outputing the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

86 more elements

log pi=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(ai)−f(bi)−f(ci)−f(di),
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n−1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n,. . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
each of the secure computation devices comprises circuitry configured to:
receive, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determine i0, i1, x0 and x1 that satisfy i0≤i1 and x0≤x1;
compute f(x0), . . . , f(x1), and generate an array M=(f(x0), . . . , f(x1));
secure the array M, and generate a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
execute following formulae, and generate the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
output the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

13 more elements

log pi=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(ai)−f(bi)−f(ci)−f(di),
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n−1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n, . . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
the secure computation device comprises circuitry configured to:
receive, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determine i0, i1, x0 and x1
determine i0, i1, x0 and x1 that satisfy and i0≤i1 and x0≤x1;
compute f(x0), . . . , f(x1), and generate an array M=(f(x0), . . . , f(x1));
secure the array M, and generate a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
and
execute following formulae, and generate the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
output the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

15 more elements

log pi=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(ai)−f(bi)−f(ci)−f(di),
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n−1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n,. . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
the secure computation method comprising by each of the three or more secure computation devices:
receiving, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determining i0, i1, x0 and x1 that satisfy and x0≤x1 by circuitry of each of the three or more secure computation devices;
computing f(x0), . . . , f(x1), and generating an array M=(f(x0), . . . , f(x1)), for a freely selected function f(x) by the circuitry of each of the secure computation devices;
securing the array M, and generating a secure text array <M>=(<f(x0)>, . . . , <f(x1)>) by the circuitry of each of the secure computation devices;
and
executing following formulae, and generating the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1) by the circuitry of each of the secure computation devices,
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
outputting the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

14 more elements

log pi=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(ai)−f(bi)−f(ci)−f(di),
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d>are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n−1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n,. . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
the method comprising:
receiving, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determining i0, i1, x0 and x1 that satisfy i0≤i1 and x0≤x1;
computing f(x0), . . . , f(x1), and generating an array M=(f(x0), . . . , f(x1)), for a freely selected function f(x);
securing the array M, and generating a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
executing following formulae, and generating the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
outputting the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

13 more elements

Dependencies are inferred from the claim text.

Facts

Application: 16/309,034Filed 30 Jun 2017
Priority: JP JP2016-1340896 Jul 2016
Published: US 2019/0229904 A125 Jul 2019
Granted: 14 Sep 2021
Term ends: Not estimatedThe source records don’t support an estimate.

Classification13 codes

H04L 9/0861
Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords: generation of secret information…
G06F 17/18
Complex mathematical operations: for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression…
G06F 21/602
Protecting data: providing cryptographic facilities or services
G09C 1/00
Apparatus or methods whereby a given sequence of signs

Family

US 2019/0229904 A1Pre-grant publication · published 25 Jul 2019
US 11,121,868 B2This patent

From the US filing history. Foreign family members aren’t listed.

Timeline

Citations

Open elsewhere

Building an agent or pulling many patents? Use the API or MCP server instead of scraping pages. Get an API key

patentgrep

Loading patent…

Abstract

p
i
=
f
⁡
(
a
+
b
)
⁢
f
⁡
(
c
+
d
)
⁢
f
⁡
(
a
+
c
)
⁢
f
⁡
(
b
+
d
)
f
⁡
(
a
+
b
+
c
+
d
)
⁢
f
⁡
(
a
i
)
⁢
f
⁡
(
b
i
)
⁢
f
⁡
(
c
i
)
⁢
f
⁡
(
d
i
)
,
wherein f(x):=x!, a, b, c, and d are non-negative integers, a is a frequency on a first row and a first column in a 2×2 contingency table, b is a frequency on the first row and a second column in the contingency table, c is a frequency on a second row and the first column in the contingency table, d is a frequency on the second row and the second column in the contingency table, <a>, , <c>, and <d> are secure text pieces of respective frequencies a, b, c, and d, <α>=(<α[0]>, <α[1]>, . . . , <α[n-1]>) is a secure text array having a size of n, <β>is a secret text of a position in the secure text array <α>, j0, . . . , jm−1 are relative positions from β, BatchRead(<α>;
<β>;
j0, . . . , jm−1) represents a function of generating a secure text (<α[β+j0mod n]>, . . . , <α[β+jm−1 mod n]>) having a size of m by batch-reading elements at positions β+j0 mod n, . . . , β+jm−1 mod n from the secure text <α>, i0≤max(-a, -d), min(b, c)≤i1, x0≤min(a+i0, b-i1, c-i1, d+i0), and max(n, a+i1, b-i1, c-i1, d+i0)≤x1,
each of the three or more secure computation devices comprises circuitry configured to:
receive, over a network, an input of the secure texts (<a>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices;
determine i0, i1, x0 and x1 that satisfy i0≤i1 and x0≤x1;
compute f(x0), . . . , f(x1), and generate an array M=(f(x0), . . . , f(x1));
secure the array M, and generate a secure text array <M>=(<f(x0)>, . . . , <f(x1)>);
execute following formulae, and generate the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>) (i0≤i≤i1),
(<f(ai0)>,<f(ai0+1)>, . . . ,<f(ai1)>)←BatchRead(<M>;<a>;i0,i0+1, . . . ,i1),
(<f(bi0)>,<f(bi0+1)>, . . . ,<f(bi1)>)←BatchRead(<M>;;−i0,−(i0+1, . . . ,−i1),
(<f(ci0)>,<f(ci0+1)>, . . . ,<f(ci1)>)←BatchRead(<M>;<c>;−i0,−(i0+1, . . . ,−i1),
(<f(di0)>,<f(di0+1)>, . . . ,<f(di1)>)←BatchRead(<M>;<d>;i0,i0+1, . . . ,i1);
and
output the function value secure text (<f(ai)>, <f(bi)>, <f(ci)>, <f(di)>.

86 more elements

Facts

Application

16/309,034Filed 30 Jun 2017

Priority

JP JP2016-1340896 Jul 2016

Published

US 2019/0229904 A125 Jul 2019

Granted

14 Sep 2021

Term ends

Not estimatedThe source records don’t support an estimate.

Classification13 codes

H04L 9/0861
Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords: generation of secret information…
G06F 17/18
Complex mathematical operations: for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression…
G06F 21/602
Protecting data: providing cryptographic facilities or services
G09C 1/00
Apparatus or methods whereby a given sequence of signs