Secure computation system, secure computation device, secure computation method, and program
View Patent ↗Fisher's exact test is efficiently computed through secure computation. A computation range determination part determines i 0 , i 1 , x 0 , x 1 . A preliminary computation part computes f(x 0 ), . . . , f(x 1 ), and generates an array M=(f(x 0 ), . . . , f(x 1 )). A securing part secures the array M, and generates a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>). A batch-reading part generates a function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ).
1. A secure computation system comprising three or more secure computation devices, wherein the secure computation system generates a function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n, . . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy i 0 ≤i 1 and x 0 ≤x 1 ;
compute f(x 0 ), . . . , f(x 1 ), and generate an array M=(f(x 0 ), . . . , f(x 1 ));
secure the array M, and generate a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>);
execute following formulae, and generate the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ),
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
output the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 )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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n, . . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy and i 0 ≤i 1 and x 0 ≤x 1 ;
compute f(x 0 ), . . . , f(x 1 ), and generate an array M=(f(x 0 ), . . . , f(x 1 ));
secure the array M, and generate a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>);
execute following formulae, and generate the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ),
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
output the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n, . . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c) ≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy i 0 ≤i 1 and x 1 ≤x 1 by circuitry of each of the three or more secure computation devices;
computing f(x 0 ), . . . , f(x 1 ), and generating an array M=(f(x 0 ), . . . , f(x 1 )) 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(x 0 )>, . . . , <f(x 1 )>) 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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) by the circuitry of each of the three or more secure computation devices,
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
outputting the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n,. . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy and i 0 ≤i 1 and x 0 ≤x 1 ;
computing f(x 0 ), . . . , f(x 1 ), and generating an array M=(f(x 0 ), . . . , f(x 1 ));
securing the array M, and generating a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>);
executing following formulae, and generating the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ),
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
outputing the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
5. A secure computation system comprising three or more secure computation devices, wherein the secure computation system generates a function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) defined by a following equation:
log 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n,. . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy i 0 ≤i 1 and x 0 ≤x 1 ;
compute f(x 0 ), . . . , f(x 1 ), and generate an array M=(f(x 0 ), . . . , f(x 1 ));
secure the array M, and generate a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>);
execute following formulae, and generate the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ),
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
output the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) defined by a following equation:
log 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n, . . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1
determine i 0 , i 1 , x 0 and x 1 that satisfy and i 0 ≤i 1 and x 0 ≤x 1 ;
compute f(x 0 ), . . . , f(x 1 ), and generate an array M=(f(x 0 ), . . . , f(x 1 ));
secure the array M, and generate a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>); and
execute following formulae, and generate the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ),
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
output the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) defined by a following equation:
log 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n,. . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy and x 0 ≤x 1 by circuitry of each of the three or more secure computation devices;
computing f(x 0 ), . . . , f(x 1 ), and generating an array M=(f(x 0 ), . . . , f(x 1 )), 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(x 0 )>, . . . , <f(x 1 )>) by the circuitry of each of the secure computation devices; and
executing following formulae, and generating the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) by the circuitry of each of the secure computation devices,
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
outputting the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.
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(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ) for computing a secret text of a probability p i (i 0 ≤i≤i 1 ) defined by a following equation:
log 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 <α>, j 0 , . . . , j m−1 are relative positions from β, BatchRead(<α>; <β>; j 0 , . . . , j m−1 ) represents a function of generating a secure text (<α[β+j 0 mod n]>, . . . , <α[β+j m−1 mod n]>) having a size of m by batch-reading elements at positions β+j 0 mod n,. . . , β+j m−1 mod n from the secure text <α>, i 0 ≤max(-a, -d), min(b, c)≤i 1 , x 0 ≤min(a+i 0 , b-i 1 , c-i 1 , d+i 0 ), and max(n, a+i 1 , b-i 1 , c-i 1 , d+i 0 )≤x 1 ,
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 i 0 , i 1 , x 0 and x 1 that satisfy i 0 ≤i 1 and x 0 ≤x 1 ;
computing f(x 0 ), . . . , f(x 1 ), and generating an array M=(f(x 0 ), . . . , f(x 1 )), for a freely selected function f(x);
securing the array M, and generating a secure text array <M>=(<f(x 0 )>, . . . , <f(x 1 )>);
executing following formulae, and generating the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>) (i 0 ≤i≤i 1 ),
(< f ( a i 0 )>,< f ( a i 0 +1 )>, . . . ,< f ( a i 1 )>)←BatchRead(< M>;<a>;i 0 ,i 0 +1, . . . , i 1 ),
(< f ( b i 0 )>,< f ( b i 0 +1 )>, . . . ,< f ( b i 1 )>)←BatchRead(< M>;<b>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( c i 0 )>,< f ( c i 0 +1 )>, . . . ,< f ( c i 1 )>)←BatchRead(< M>;<c>;−i 0 ,−( i 0 +1, . . . ,− i 1 ),
(< f ( d i 0 )>,< f ( d i 0 +1 )>, . . . ,< f ( d i 1 )>)←BatchRead(< M>;<d>;i 0 ,i 0 +1, . . . , i 1 );
and
outputting the function value secure text (<f(a i )>, <f(b i )>, <f(c i )>, <f(d i )>.