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

Abstract

Fisher's exact test is efficiently computed through secure computation. A computation range determination part determines i.sub.0, i.sub.1, x.sub.0, x.sub.1. A preliminary computation part computes f(x.sub.0), . . . , f(x.sub.1), and generates an array M=(f(x.sub.0), . . . , f(x.sub.1)). A securing part secures the array M, and generates a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>). A batch-reading part generates a function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1).

Claims

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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation: $p_{i} = \frac{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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n, . . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.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>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices; determine i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1; compute f(x.sub.0), . . . , f(x.sub.1), and generate an array M=(f(x.sub.0), . . . , f(x.sub.1)); secure the array M, and generate a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>); execute following formulae, and generate the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1),
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and output the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1)defined by a following equation: $p_{i} = \frac{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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n, . . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.1, 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 i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy and i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1; compute f(x.sub.0), . . . , f(x.sub.1), and generate an array M=(f(x.sub.0), . . . , f(x.sub.1)); secure the array M, and generate a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>); execute following formulae, and generate the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1),
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and output the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation: $p_{i} = \frac{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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n, . . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c) ≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.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>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices; determining i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy i.sub.0≤i.sub.1 and x.sub.1≤x.sub.1 by circuitry of each of the three or more secure computation devices; computing f(x.sub.0), . . . , f(x.sub.1), and generating an array M=(f(x.sub.0), . . . , f(x.sub.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.sub.0)>, . . . , <f(x.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) by the circuitry of each of the three or more secure computation devices,
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and outputting the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation: $p_{i} = \frac{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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n,. . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.1, 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 i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy and i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1; computing f(x.sub.0), . . . , f(x.sub.1), and generating an array M=(f(x.sub.0), . . . , f(x.sub.1)); securing the array M, and generating a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>); executing following formulae, and generating the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1),
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and outputing the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation:
log p.sub.i=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(a.sub.i)−f(b.sub.i)−f(c.sub.i)−f(d.sub.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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n,. . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.1, 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 i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1; compute f(x.sub.0), . . . , f(x.sub.1), and generate an array M=(f(x.sub.0), . . . , f(x.sub.1)); secure the array M, and generate a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>); execute following formulae, and generate the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1),
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and output the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation:
log p.sub.i=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(a.sub.i)−f(b.sub.i)−f(c.sub.i)−f(d.sub.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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n, . . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.1, 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 i.sub.0, i.sub.1, x.sub.0 and x.sub.1 determine i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy and i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1; compute f(x.sub.0), . . . , f(x.sub.1), and generate an array M=(f(x.sub.0), . . . , f(x.sub.1)); secure the array M, and generate a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>); and execute following formulae, and generate the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1),
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and output the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation:
log p.sub.i=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(a.sub.i)−f(b.sub.i)−f(c.sub.i)−f(d.sub.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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n,. . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.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>, , <c>, <d>), wherein the original respective frequencies a, b, c and d are concealed from each of the secret computation devices; determining i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy and x.sub.0≤x.sub.1 by circuitry of each of the three or more secure computation devices; computing f(x.sub.0), . . . , f(x.sub.1), and generating an array M=(f(x.sub.0), . . . , f(x.sub.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.sub.0)>, . . . , <f(x.sub.1)>) by the circuitry of each of the secure computation devices; and executing following formulae, and generating the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) by the circuitry of each of the secure computation devices,
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and outputting the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.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.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1) for computing a secret text of a probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by a following equation:
log p.sub.i=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(a.sub.i)−f(b.sub.i)−f(c.sub.i)−f(d.sub.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 <α>, j.sub.0, . . . , j.sub.m−1 are relative positions from β, BatchRead(<α>; <β>; j.sub.0, . . . , j.sub.m−1) represents a function of generating a secure text (<α[β+j.sub.0mod n]>, . . . , <α[β+j.sub.m−1 mod n]>) having a size of m by batch-reading elements at positions β+j.sub.0 mod n,. . . , β+j.sub.m−1 mod n from the secure text <α>, i.sub.0≤max(-a, -d), min(b, c)≤i.sub.1, x.sub.0≤min(a+i.sub.0, b-i.sub.1, c-i.sub.1, d+i.sub.0), and max(n, a+i.sub.1, b-i.sub.1, c-i.sub.1, d+i.sub.0)≤x.sub.1, 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 i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1; computing f(x.sub.0), . . . , f(x.sub.1), and generating an array M=(f(x.sub.0), . . . , f(x.sub.1)), for a freely selected function f(x); securing the array M, and generating a secure text array <M>=(<f(x.sub.0)>, . . . , <f(x.sub.1)>); executing following formulae, and generating the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i.sub.0≤i≤i.sub.1),
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1); and outputting the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a diagram exemplifying a functional configuration of a secure computation system;

(2) FIG. 2 is a diagram exemplifying a functional configuration of a secure computation device; and

(3) FIG. 3 is a diagram exemplifying processing procedures of a secure computation method.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(4) Prior to description of embodiments, notations in this Description and the definitions of terms used in this Description are described.

Notation

(5) A value secured by applying encryption or secret sharing to a certain value “a” is called the secure text of “a” and is represented as <a>. Meanwhile, “a” is called the plain text of <a>. In a case where the securing is secret sharing, a set of the secret sharing fragments held by the individual parties according to <a>is referred to.

Secure Shift

(6) A process of adopting, as inputs, secure text array <a>=(<a[0]>, <a[1]>, . . . , <a[n−1]>) having a size of n, and secure text <d>having a shift amount of d, and of computing a secure text array <a′>=(<a[d]>, <a[d+1]>, . . . , <a[n−1]>, <a[0]>, <a[d−1]>) with <a>being shifted leftward by d, is called secure shift, and is described by the following formula.
<a′>←Shift(<a>,<d>)

(7) A method of achieving the secure shift is described in the following reference document 1.

(8) [Reference Document 1] Koki Hamada, Naoto Kiribuchi, and Dai Ikarashi, “A round-efficient pattern matching algorithm for secure multi-party computation”, Computer Security Symposium 2014, vol. 2014, pp. 674-681, October 2014

Batch-Reading Algorithm

(9) A batch-reading algorithm adopts, as inputs, secure text array <a>=(<a[0]>, <a[1]>, . . . , <a[n−1]>) having a size of n, secure text <x>of a natural number x representing a position, and m plain text pieces j.sub.0, j.sub.1, . . . , j.sub.m−1 representing a relative position from x, and obtains m secure text pieces =(<a[x+j.sub.0 mod n]>, <a[x+j.sub.1 mod n]>, . . . , <a[x+j.sub.m−1 mod n]>) without disclosing the values of x and a[0], a[1], . . . , a[n−1]. Hereinafter, the batch-reading algorithm is described by the following formula.
←BatchRead(<a>;<x>;j.sub.0,j.sub.1, . . . ,j.sub.m−1)

(10) The batch-reading algorithm can be more efficiently executed by implementation as follows using the secure shift as described above. Note that the batch-reading algorithm applicable to the present invention is not limited thereto. Any algorithm capable of achieving the input and output described above is applicable. First, secure text array <a>=(<a[0]>, <a[1]>, . . . , <a[n−1]>) having a size of n, secure text <x> of an integer x that is equal to or higher than 0 and less than n, and m plain text pieces j.sub.0, . . . , j.sub.m−1 representing a relative position from x are input. Next, <a′>=(<a′[0]>, <a′[1]>, . . . , <a′[n−1]>), where array <a> is shifted leftward by <x>, is obtained by <a′>←Shift(<a>,<x>). It is then assumed that <b[k]>=<a′[j.sub.k]>(0≤k<m), a secure text array =(<b[0]>, <b[1]>, . . . , <b[m−1]>)=(<a′[j.sub.0]>, <a′[j.sub.1]>, . . . , <a′[j.sub.m−1]>) is generated.

(11) Hereinafter, embodiments of the present invention are described in detail. In the diagrams, configuration parts having the same functions are assigned the same numerals, and redundant description thereof is omitted.

First Embodiment

(12) A secure computation system of a first embodiment comprises n (≥3) secure computation devices 1.sub.1, . . . , 1.sub.n, as exemplified in FIG. 1. In this embodiment, the secure computation devices 1.sub.1, . . . , 1.sub.n are each connected to a communication network 2. The communication network 2 is a communication network that is of a circuit switching scheme or a packet switching scheme and is configured to allow the secure computation devices 1.sub.1, . . . , 1.sub.nto communicate with each other. For example, the Internet, a LAN (Local Area Network), a WAN (Wide Area Network) or the like may be used. Each device is not necessarily capable of communicating online via the communication network 2. For example, it may be configured such that information to be input into the secure computation devices 1.sub.i(i∈{1, . . . , n}) may be stored in a portable recording medium, such as magnetic tape or a USB memory, and input may be performed offline from the portable recording medium.

(13) As exemplified in FIG. 2, the secure computation device 1 includes an input part 11, a computation range determination part 12, a preliminary computation part 13, a securing part 14, a batch-reading part 15, and an output part 16. The secure computation device 1 performs the process of each step exemplified in FIG. 3, thereby achieving a secure computation method of the first embodiment.

(14) The secure computation device 1 is, for example, a special device configured to include a publicly known or dedicated computer which includes a central processing unit (CPU) and a main memory (RAM: Random Access Memory) and the like and into which a special program has been read. The secure computation device 1 executes each process under control by the central processing unit, for example. Data input into the secure computation device 1 and data obtained by each process are stored in the main memory, for example. The data stored in the main memory is read into the central processing unit as required, and is used for another process. At least some of the processing parts of the secure computation device 1 may be configured by hardware, such as an integrated circuit.

(15) Referring to FIG. 3, the processing procedures of the secure computation method of the first embodiment are described.

(16) In step S11, a secure text (<a>, , <c>, <d>) of a combination of frequencies (a, b, c, d) in a 2×2 contingency table is input into the input part 11. Here, the 2×2 contingency table is defined by the following formulae, and a, b, c and d are non-negative integers.

(17) TABLE-US-00002 Subtotal due With event 1 Without event 1 to event 2 With event 2 a b n.sub.1• Without event 2 c d n.sub.2• Subtotal due to n•.sub.1 n•.sub.2 n event 1

(18) In step S12, the computation range determination part 12 determines values i.sub.0, i.sub.1, x.sub.0 and x.sub.1 that satisfy i.sub.0≤i.sub.1 and x.sub.0≤x.sub.1. Here, it is determined that i.sub.0=−n, i.sub.1=n, x.sub.0=−n, and x.sub.1=2n. The values x.sub.0 and x.sub.1 are transmitted to the preliminary computation part 13. The values i.sub.0 and i.sub.1 are transmitted to the batch-reading part 15.

(19) In step S13, as for the function f(x), the preliminary computation part 13 computes f(x.sub.0), f(x.sub.0+1), . . . , f(x.sub.1), and generates an array M=(f(x.sub.0), f(x.sub.0+1), . . . , f(x.sub.1)). In the first embodiment, to compute the probability p.sub.i (i.sub.0≤i≤i.sub.1) defined by the following equation, the function f(x) is defined as f(x):=x!.

(20) $p_{i} = \frac{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})}$

(21) In step S14, the securing part 14 generates a secure text array <M>=(<f(x.sub.0)>, <f(x.sub.0+1)>, . . . , <f(x.sub.1)>) where the array M is secured. The secure text array <M> is transmitted to the batch-reading part 15.

(22) In step S15, the batch-reading part 15 executes the following formulae, and generates a function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) (i=i.sub.0, . . . , i.sub.1).
(<f(a.sub.i.sub.0)>,<f(a.sub.i.sub.0.sub.+1)>, . . . ,<f(a.sub.i.sub.1)>)←BatchRead(<M>;<a>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),
(<f(b.sub.i.sub.0)>,<f(b.sub.i.sub.0.sub.+1)>, . . . ,<f(b.sub.i.sub.1)>)←BatchRead(<M>;;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(c.sub.i.sub.0)>,<f(c.sub.i.sub.0.sub.+1)>, . . . ,<f(c.sub.i.sub.1)>)←BatchRead(<M>;<c>;−i.sub.0,−(i.sub.0+1, . . . ,−i.sub.1),
(<f(d.sub.i.sub.0)>,<f(d.sub.i.sub.0.sub.+1)>, . . . ,<f(d.sub.i.sub.1)>)←BatchRead(<M>;<d>;i.sub.0,i.sub.0+1, . . . ,i.sub.1),

(23) In step S16, the function value secure text (<f(a.sub.i)>, <f(b.sub.i)>, <f(c.sub.i)>, <f(d.sub.i)>) is output from the output part 16.

Second Embodiment

(24) Referring to FIG. 3, the processing procedures of the secure computation method of a second embodiment are described. Hereinafter, differences from the first embodiment described above are mainly described.

(25) In step S13, as for the function f(x), the preliminary computation part 13 computes f(x.sub.0), f(x.sub.0+1), . . . , f(x.sub.1), and generates an array M=(f(x.sub.0), f(x.sub.0+1), . . . , f(x.sub.1)). In the second embodiment, the probabilities log p.sub.i (i.sub.0≤i≤i.sub.1) defined by the following equation are computed and then the probabilities p.sub.i=exp(log p.sub.i) are computed, the function f(x) is defined as f(x):=log(x!).
log p.sub.i=f(a+b)+f(c+d)+f(a+c)+f(b+d)−f(a+b+c+d)−f(a.sub.i)−f(b.sub.i)−f(c.sub.i)−f(d.sub.i)

(26) The point of the present invention is to utilize the fact that the differences of inputs a.sub.i0, a.sub.i0+1, . . . , a.sub.i1 of function values f(a.sub.i0), f(a.sub.i0+1), . . . , f(a.sub.i1) are information allowed to be disclosed, to achieve computation of function value secure text <f(a.sub.i0)>, <f(a.sub.i0+1)>, . . . , <f(a.sub.i> efficiently, using the batch-reading algorithm.

(27) By such a configuration, according to the secure computation technology of the present invention, multiple table references are collectively executed, thereby allowing Fisher's exact test to be efficiently computed. The computation amount of batch reading from an array having a size of n is O(n). Consequently, provided that 1+i.sub.1−i.sub.0=K and 1+x.sub.1−x.sub.0=L, the entire computation amount is improved from O(KL) to O(L).

(28) The embodiments of the present invention have thus been described above. However, the specific configuration is not limited to that in these embodiments. Even if the design is appropriately changed in a range without departing from the spirit of the present invention, it is a matter of course that the configuration is included in the present invention. The various processes described in the embodiments can be executed in a time-series manner according to the order of the description. Alternatively, such execution may be performed in parallel or individually, in conformity with the processing capability of the device that executes the processes, or as required.

Program and Recording Medium

(29) In the cases where the various processing functions in each device described in the embodiments are implemented with a computer, the processing content of the functions that each device should have is described as a program. The program is executed by the computer, thereby achieving the various processing functions in each device described above on the computer.

(30) The program that describes the processing content can be preliminarily recorded in a computer-readable recording medium. The computer-readable recording medium may be, for example, any computer-readable recording medium, such as a magnetic recording device, an optical disk, a magneto-optical recording medium, or a semiconductor memory.

(31) The program is distributed by, for example, selling, transferring, or lending a portable recording medium, such as DVD or CD-ROM, where the program is recorded. Alternatively, a configuration may be adopted where the program may be preliminarily stored in a storing device of a server computer, and the program may be transferred from the server computer to another computer via a network, thereby distributing the program.

(32) For example, the computer for executing such a program, first, stores the program recorded in a portable recording medium or transferred from a server computer, temporarily in its storing device. At the time of executing the process, the computer reads the program recorded in its recording medium, and executes the processes according to the read program.

(33) According to another execution mode of this program, the computer may directly read the program from the portable recording medium, and execute the processes according to the program. Further alternatively, every time the program is transferred to the computer from the server computer, the computer may successively execute the process according to the received program. Another configuration may be adopted that executes the processes described above through a service of what is called an ASP (Application Service Provider) type according to which the program is not transferred from the server computer to the computer concerned, and the processing function is achieved only by an execution instruction therefor and acquisition of the result. The program according to the embodiments include information that is provided for the processes by the computer and conforms to the program (data and the like that are not direct instructions to the computer but have characteristics defining the processes of the computer).

(34) According to the embodiments, this device is thus configured by executing a predetermined program on the computer. Alternatively, at least a part of the processing content may be achieved as hardware.

INDUSTRIAL APPLICABILITY

(35) The secure computation technology of the present invention is applicable to, for example, execution of Fisher's exact test through secure computation with genome information being kept secure, in genome wide association study that deals with sensitive information.

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

Assignee

Inventors

Cpc classification

Classification Explorer

G09C1/00

PHYSICS

Classification Explorer

H04L63/0428

ELECTRICITY

Classification Explorer

H04L63/0421

ELECTRICITY

Classification Explorer

G06F21/71

PHYSICS

Classification Explorer

H04L9/0861

ELECTRICITY

Classification Explorer

H04L2209/46

ELECTRICITY

Classification Explorer

H04L9/0869

ELECTRICITY

Classification Explorer

G06F17/18

PHYSICS

Classification Explorer

G06F21/72

PHYSICS

Classification Explorer

G06F21/602

PHYSICS

International classification

Classification Explorer

H04L9/08

ELECTRICITY

Classification Explorer

G06F17/18

PHYSICS

Classification Explorer

G09C1/00

PHYSICS

Classification Explorer

G06F21/60

PHYSICS

Abstract

Claims

Description