Secret calculation system, apparatus, method and program

Patent metadata

Field	Value
Publication number	US-12412487-B2
Application number	US-202118574762-A
Country	US
Kind code	B2
Filing date	Jul 8, 2021
Priority date	Jul 8, 2021
Publication date	Sep 9, 2025
Grant date	Sep 9, 2025

Abstract

A secure computation device 1 n of a secure computation system according to an aspect of this invention 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 , a fifth calculation unit 15 n , a sixth calculation unit 16 n , a seventh calculation unit 17 n , and an output unit 18 n . By calculation being performed in cooperation of these, a group by count operation can be performed on a table to which a flag is added.

First claim

The invention claimed is:

1. A secure computation system comprising 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 → =(k 1 , . . . , k m ), f → is a vector of a flag f → =(f 1 , . . . , f m ), [α] is a ciphertext of α with α set as any value or any vector, and a predetermined operation using α as a ciphertext is possible,
wherein the plurality of secure computation devices comprises processing circuitry configured to:
generate a ciphertext [f′ → ] and a ciphertext [k′ → ] of a vector f′ → and a vector k′ → obtained by sorting the vector f → and the vector k → , respectively, with a vector obtained by concatenating negative of the vector f → and the vector k → set as a key, using a ciphertext [f → ] of the vector f → and a ciphertext [k → ] of the vector k → ;
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 =1 and k′ i ≠k′ i+1 or f′ i =1 and f 1+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 [m′] of m′ with a result obtained by subtracting a number of records having a flag of 0 from the m set as m′, using at least the m;
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 i when an element e i =0 is satisfied, the element e i being an element of the vector e → , and a value of m′ 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′ → ];
obtain a ciphertext [x′ → ], a ciphertext [k″ → ], and a ciphertext [e″ → ] of a vector x′ → , a vector k″ → , and a 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′ → ];
generate a ciphertext [c → ] of a vector c → including c i (i=1, . . . , m) as an element by generating a ciphertext [c i ] of c i that is a value obtained by subtracting an element x′ i−1 from an element x′ i of the vector x′ → with a ciphertext [x′ 1 ] of an element x′ 1 of the vector x′ → set as a ciphertext [c 1 ] and with i=2, . . . , m set, using the ciphertext [x″ → ]; and
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″ → ].

2. The secure computation system according to claim 1 ,
wherein the processing circuitry further configured to output the ciphertext [k″ → ], the ciphertext [c → ], and the ciphertext [e′″ → ].

3. The secure computation system according to claim 1 ,
wherein the processing circuitry further configured to output a result obtained by deleting an element corresponding to an element indicating a dummy record among elements e i ′″ of a vector e′″ → from the ciphertext [k″ → ] and the ciphertext [c → ], using the ciphertext [k″ → ], the ciphertext [c → ], and the ciphertext [e′″ → ].

4. A secure computation device of the secure computation system according to claim 1 .

5. A secure computation method in which m is a number of records and is an integer of 1 or more, k → is a vector of a key k → =(k 1 , . . . , k m ), f → is a vector of a flag f → =(f 1 , . . . , f m ), [α] is a ciphertext of α with α set as any value or any vector, and a predetermined operation using α 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′ → ] and a ciphertext [k′ → ] of a vector f′ → and a vector k′ → obtained by sorting the vector f → and the vector k → , respectively, with a vector obtained by concatenating negative of the vector f → and the vector k → set as a key, using a ciphertext [f → ] of the vector f → and a ciphertext [k → ] of the vector k → ;
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, . . . , 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 third calculation step in which a plurality of third calculation units generates a ciphertext [m′] of m′ with a result obtained by subtracting a number of records having a flag of 0 from the m set as m′, using at least the m;
a fourth calculation step in which a plurality of fourth 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 i when an element e i =0 is satisfied, the element e i being an element of the vector e → , and a value of m′ when an element e i =1 is satisfied, the element ei being an element of the vector e → , with i=1, . . . , m set, using the ciphertext [e′ → ];
a fifth calculation step in which a plurality of fifth calculation units obtains a ciphertext [x′ → ], a ciphertext [k″ → ], and a ciphertext [e″ → ] of a vector x′ → , a vector k″ → , and a 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′ → ];
a sixth calculation step in which a plurality of sixth calculation units generates a ciphertext [c → ] of a vector c → including c i (i=1, . . . , m) as an element by generating a ciphertext [c i ] of c i that is a value obtained by subtracting an element x′ i−1 from an element x′ i of the vector x′ → with a ciphertext [x′ 1 ] of an element x′ 1 of the vector x′ → set as a ciphertext [c 1 ] and with i=2, . . . , m set, using the ciphertext [x′ → ]; and
a seventh calculation step in which a plurality of seventh 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″ → ].

6. 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 5 .

Assignees

• Nippon Telegraph & Telephone

Inventors

• Kikuchi Ryo
• Ikarashi Dai
• Sudo Hiroki

Classifications

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• H04L9/008

  involving homomorphic encryption · CPC title

• H04L9/085

  Secret sharing or secret splitting, e.g. threshold schemes · CPC title

• H04L2209/46

  Secure multiparty computation, e.g. millionaire problem · CPC title

• G06F21/602

  Providing cryptographic facilities or services · CPC title