# US 11,121,868 B2 · Secure computation system, secure computation device, secure computation method, and program

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 11,121,868 B2
- Document ID: US11121868B2
- Status: Granted
- Kind: B2
- Application number: 16/309,034
- Filed: 2017-06-30
- Published: 2019-07-25
- Granted: 2021-09-14
- Earliest claimed: 2016-07-06
- Assignees: Nippon Telegraph and Telephone Corporation
- Applicants: Nippon Telegraph and Telephone Corporation
- Inventors: Koki Hamada
- Web page: https://patentgrep.com/patent/US11121868B2

## CPC

- H04L 9/0861: {Generation of secret information including derivation or calculation of cryptographic keys or passwords}
- G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)}
- G06F 21/602: {Providing cryptographic facilities or services}
- G09C 1/00: Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system (cryptographic typewriters G09C3/00)
- H04L 9/0869: {involving random numbers or seeds}
- G06F 21/71: to assure secure computing or processing of information
- G06F 21/72: in cryptographic circuits
- H04L 63/0421: {Anonymous communication, i.e. the party's identifiers are hidden from the other party or parties, e.g. using an anonymizer}
- H04L 63/0428: {wherein the data content is protected, e.g. by encrypting or encapsulating the payload}
- H04L 2209/46: Secure multiparty computation, e.g. millionaire problem
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G09C: CIPHERING OR DECIPHERING APPARATUS FOR CRYPTOGRAPHIC OR OTHER PURPOSES INVOLVING THE NEED FOR SECRECY

## 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).

## Claims

### Claim 1

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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 2

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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 3

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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 4

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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 5

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:
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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 6

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:
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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 7

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:
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>, <b>, <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>, <b>, <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>;<b>;−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)>.

### Claim 8

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:
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>, <b>, <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>, <b>, <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>;<b>;−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)>.