Secret calculation system, apparatus, method and program
A secure computation device 1 n of the secure computation system includes a first calculation unit 11 n , a second calculation unit 12 n , a third calculation unit 13 n , a fourth calculation unit 14 n , and an output unit 15 n . By calculation being performed in cooperation of these, a group by max operation or a group by min operation can be performed on a table to which a flag is added.
1 . A secure computation system for performing a group-by database operation on an encrypted table having a plurality of records indicated by flags, the system comprising:
a plurality of secure computation devices, wherein
m is a number of records of the encrypted table and is an integer of 1 or more, k → is a vector of a key k → =(k 1 , . . . , k m ), v → is a vector of a value v → =(v 1 , . . . , v m ), f → is a vector of the flags f → =(f 1 , . . . , f m ), [α] is a ciphertext of α with α set as any value or any vector, and a predetermined operation using a as a ciphertext is possible, and
the plurality of secure computation devices include processing circuitry configured to:
generate a ciphertext [f′ → ], a ciphertext [k′ → ], and a ciphertext [v′ → ] of a vector f′ → , a vector k′ → , and a vector v′ → obtained by sorting the vector f → , the vector k → , and the vector v → , respectively, with a vector obtained by concatenating negative of the vector f → , the vector k → , and the vector v → set as a key, using a ciphertext [f → ] of the vector f → , a ciphertext [k → ] of the vector k → , and a ciphertext [v → ] of the vector v → ;
generate a ciphertext [e′ → ] of a vector e′ → including e i (i=1, . . . , m) as an element by generating a ciphertext [e′ m ] of e′ m such that e′ i =0 is satisfied when f′ i =I and k′ i ≠k′ i+1 , or f′ i =1 and f′ i+1 =0 are satisfied or otherwise e′ i =1 is satisfied, and e′ m =0 is satisfied when f′ m =1 is satisfied or otherwise e′ m =1 is satisfied, with i=1, . . . , m−1 set, using the ciphertext [f′ → ] and the ciphertext [k′ → ];
generate a ciphertext [x → ] of a vector x → including x i (i=1, . . . , m) as an element by generating a ciphertext [x i ] of x i having a value of v′ i when an element e′ i =0 is satisfied, the element e′ i being an element of the vector e′ → , and a value of 0 when an element e′ i =1 is satisfied, the element e′ i being an element of the vector e′ → , with i=1, . . . , m set, using the ciphertext [e′ → ] and the ciphertext [v′ → ];
calculate a ciphertext [e′″ → ] of a vector e′″ → including a value obtained by subtracting each element of the vector e′ → from 1, using the ciphertext [e′ → ]; and
output a result of the group-by database operation based on the ciphertext [k′ → ], the ciphertext [x → ], and the ciphertext [e′″ → ].
2 . The secure computation system according to claim 1 , wherein the processing circuitry configured to generate a ciphertext [x′ → ], a ciphertext [k″ → ], and a ciphertext [e″ → ] of a vector x′ → , the vector k″ → , and the vector e″ → obtained by sorting the vector x → , the vector k′ → , and the vector e′ → , respectively, with the vector e′ → set as a key, using the ciphertext [e′ → ], the ciphertext [x → ], and the ciphertext [k′ → ], and calculates a ciphertext [e′″ → ] of a vector e′″ → including a value obtained by subtracting each element of the vector e″ → from 1, using the ciphertext [e″ → ].
3 . The secure computation system according to claim 2 , wherein the processing circuitry is further configured to output the ciphertext [k′ → ] or the ciphertext [k″ → ], the ciphertext [x → ] or the ciphertext [x′ → ], and the ciphertext [e′″ → ].
4 . The secure computation system according to claim 3 , wherein the processing circuitry is configured to not output a ciphertext corresponding a dummy record.
5 . The secure computation system according to claim 1 , wherein each of the flags indicates whether or not a corresponding one of the plurality of records is a dummy record.
6 . A secure computation system for performing a group-by database operation on an enc ted table having a plurality of records indicated by flags, the system comprising:
a plurality of secure computation devices, wherein
m is a number of records of the encrypted table and is an integer of 1 or more, k → is a vector of a key k → =(k 1 , . . . , k m ), v → is a vector of a value v → =(v 1 , . . . , v m ), f → is a vector of the flags f → =(f 1 , . . . , f m ), [α] is a ciphertext of α with α set as any value or any vector, and a predetermined operation using a as a ciphertext is possible, and
the plurality of secure computation devices include processing circuitry configured to:
generate a ciphertext [f′ → ], a ciphertext [k′ → ], and a ciphertext [v′ → ] of a vector f → , a vector k′ → , and a vector v′ → obtained by sorting the vector f → , the vector k → , and the vector v → , respectively, with a vector obtained by concatenating negative of the vector f → , the vector k → , and the vector v → set as a key, using a ciphertext [f → ] of the vector f → , a ciphertext [k → ] of the vector k → , and a ciphertext [v → ] of the vector v → ;
generate a ciphertext [g′ → ] of a vector g′ → including g i (i=1, . . . , m) as an element by generating a ciphertext [g 1 ] of g 1 such that g i =0 is satisfied when f′ i =1 and k′ i ≠k′ i+1 or f′ i =1 and f′ i+1 =0 are satisfied or otherwise g i =1 is satisfied, and g i =1 is satisfied when f′ 1 =0 is satisfied or otherwise g 1 =0 is satisfied, with i=1, . . . , m−1 set, using the ciphertext [f′ → ] and the ciphertext [k′ → ];
generate a ciphertext [x′ → ] of a vector x → including x i (i=1, . . . , m) as an element by generating a ciphertext [x i ] of x i having a value of v′ i when an element g i =0 is satisfied, the element g i being an element of the vector g → , and a value of 0 when an element g i =1 is satisfied, the element g i being an element of the vector g → , with i=1, . . . , m set, using the ciphertext [g → ] and the ciphertext [v′ → ];
calculate a ciphertext [g′ → ] of a vector g′ → including a value obtained by subtracting each element of the vector g → from 1, using the ciphertext [g → ]; and
output a result of the group-by database operation based on the ciphertext [k′ → ], the ciphertext [x → ], and the ciphertext [g′ → ].
7 . The secure computation system according to claim 6 , wherein the processing circuitry configured to generate a ciphertext [x′ → ], a ciphertext [k″ → ], and a ciphertext [g′ → ] of a vector x′ → , the vector k″ → , and the vector g′ → obtained by sorting the vector x → , the vector k′ → , and the vector g → , respectively, with the vector g → set as a key, using the ciphertext [g → ], the ciphertext [x → ], and the ciphertext [k′ → ], and calculates a ciphertext [g″ → ] of a vector g″ → including a value obtained by subtracting each element of the vector g′ → from 1, using the ciphertext [g′ → ].
8 . The secure computation system according to claim 7 , wherein the processing circuitry is further configured to output the ciphertext [k′ → ] or the ciphertext [k″ → ], the ciphertext [x → ] or the ciphertext [x′ → ], and the ciphertext [g′ → ] or the ciphertext [g″ → ].
9 . The secure computation system according to claim 8 , wherein the processing circuitry is configured to not output a ciphertext corresponding a dummy record.
10 . The secure computation system according to claim 6 , wherein each of the flags indicates whether or not a corresponding one of the plurality of records is a dummy record.
11 . A secure computation device of the secure computation system according to claim 1 .
12 . A secure computation method for performing a group-by database operation on an encrypted table having a plurality of records indicated by flags, in which m is a number of records of the encrypted table and is an integer of 1 or more, k → is a vector of a key k → =(k 1 , . . . , k m ), v → is a vector of a value v → =(v 1 , . . . v m ), f → is a vector of the flags f → =(f 1 , . . . , f m ), [α] is a ciphertext of α with α set as any value or any vector, and a predetermined operation using a as a ciphertext is possible, the secure computation method comprising:
a first calculation step in which a plurality of first calculation units generates a ciphertext [f′ → ], a ciphertext [k′ → ], and a ciphertext [v′ → ] of a vector f′ → , a vector k′ → , and a vector v′ → obtained by sorting the vector f → , the vector k → , and the vector v → , respectively, with a vector obtained by concatenating negative of the vector f → , the vector k → , and the vector v → set as a key, using a ciphertext [f → ] of the vector f → , a ciphertext [k → ] of the vector k → , and a ciphertext [v → ] of the vector v → ;
a second calculation step in which a plurality of second calculation units generates a ciphertext [e′ → ] of a vector e′ → including e i (i=1, . . . , in) as an element by generating a ciphertext [e′ m ] of e′ m ˜such that e′ i =0 is satisfied when f′ i =1 and k′ i ≠k′ i+1 or f′ i =1 and f′ i+1 =0 are satisfied or otherwise e′ i =1 is satisfied, and e′ m =0 is satisfied when f′ m =1 is satisfied or otherwise e′ m =1 is satisfied, with i=1, . . . , m−1 set, using the ciphertext [f′ → ] and the ciphertext [k′ → ];
a third calculation step in which a plurality of third calculation units generates a ciphertext [x → ] of a vector x → including x i (i=1, . . . , m) as an element by generating a ciphertext [x i ] of x i having a value of v′ i when an element e′ i =0 is satisfied, the element e′ i being an element of the vector e′ → , and a value of 0 when an element e′ i =1 is satisfied, the element e′ i being an element of the vector e′ → , with i=1, . . . , m set, using the ciphertext [e′ → ] and the ciphertext [v′ → ];
a fourth calculation step in which a plurality of fourth calculation units calculates a ciphertext [e′″ → ] of a vector e′″ → including a value obtained by subtracting each element of the vector e′ → from 1, using the ciphertext [e′ → ]; and
an output step in which a plurality of output units output a result of the group-by database operation based on the ciphertext [k′ → ], the ciphertext [x → ], and the ciphertext [e′″ → ].
13 . A non-transitory computer readable medium that stores a program for causing a computer to function as each step of the secure computation method according to claim 12 .
14 . The secure computation method according to claim 12 , wherein each of the flags indicates whether or not a corresponding one of the plurality of records is a dummy record.