US-12619433-B2 - Secret calculation system, apparatus, method and program

US12619433B2US 12619433 B2US12619433 B2US 12619433B2US-12619433-B2

Abstract

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.

Inventors

Ryo Kikuchi
Dai Ikarashi
Hiroki Sudo

Assignees

NTT, INC.

Dates

Publication Date: 20260505
Application Date: 20210708

Claims (14)

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.

Description

CROSS-REFERENCE TO RELATED APPLICATION The present application is based on PCT filing PCT/JP2021/025770, filed Jul. 8, 2021, the entire contents of which are incorporated herein by reference. TECHNICAL FIELD The present invention relates to a technology for performing a database operation while keeping data secret. BACKGROUND ART In order to handle data safely, technologies called secure computation in which analysis is performed in a state in which encryption is performed have been studied. Among them, encrypted database processing is considered in order to efficiently perform extraction of data that satisfies conditions, calculation of a total value, and the like in a state in which encryption is performed. A group by operation that is a type of database (DB) processing is grouping processing in which a table is used as an input, grouping is performed for each value of a designated column, and in some cases, a statistical value for each group is calculated and output in a table format. Non Patent Literature 1 proposes a method of performing a group by operation in a state in which encryption is performed. An input/output considered here is a table obtained by encrypting a normal table for each element. On the other hand, in a case where database processing is performed in a state in which encryption is performed, it is conceivable that a flag indicating whether a certain record is an original output is added to the input/output unlike a normal table. As data in which [·] is encrypted with k→ set as a vector of a key, v→ set as a vector of a value, and f→ set as a vector of a flag, FIG. 15(a) illustrates an example of a normal unencrypted table, FIG. 15(b) illustrates an example of an encrypted table in Non Patent Literature 1, and FIG. 15(c) illustrates an example of a table to which flags are added. In FIG. 15, “?” indicates that some value is inserted. In a case where the flag is 0, the value of the record is ignored, and thus the value of “?” is any value. CITATION LIST Non Patent Literature Non Patent Literature 1: Ryo Kikuchi, Koki Hamada, Dai Ikarashi, Gen Takahashi, Katsumi Takahashi, “Oudanteki dousen bunseki wo himitsu keisan de yattemiyou (Secure cross-sector customer-flow invention)” In SCIS, 2020. SUMMARY OF INVENTION Technical Problem In a case where the table to which the flags are added illustrated in FIG. 7(c) is input, an algorithm proposed in Non Patent Literature 1 does not function. This is because, in addition to the different input formats, it has been conventionally assumed that all records are meaningful values, and thus, for example, performing processing while skipping a record that is not used is not possible, and a value of “?” to be ignored affects the final result, and accordingly, the original result cannot be obtained. An object of the present invention is to provide a secure computation system, device, method, and program that perform a group by max operation or a group by min operation on a table to which a flag is added. Solution to Problem A secure computation system according to an aspect of this invention is a secure computation system including a plurality of secure computation devices in which m is a number of records and is an integer of 1 or more, k→ is a vector of a key k→=(k1, . . . , km), v→ is a vector of a value v→=(v1, . . . , vm), f→ is a vector of a flag f→=(f1, . . . , fm), [α] is a ciphertext of α with α set as any value or any vector, and a predetermined operation using α as a ciphertext is possible, in which the plurality of secure computation devices includes a plurality of first calculation units that 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 plurality of second calculation units that generates a ciphertext [e′→] of a vector e′→ including ei (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=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 plurality of third calculation units that generates a ciphertext [x→] of a vector x→ including xi(i=1, . . . , m) as an element by generating a ciphertext [xi] of xi 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′→], and a plurality of fou