Patent Publication Number: US-2022224516-A1

Title: Secure division system, secure computation apparatus, secure division method, and program

Description:
TECHNICAL FIELD 
     This invention relates to an applied encryption technology, and more particularly relates to a technology for efficiently performing division without revealing input and output values. 
     BACKGROUND ART 
     Methods of obtaining specific operation results without restoring encrypted numerical values include a method called secure computation (e.g., see NPL 1). With the method described in NPL 1, encryption that involves sharing fragments of numerical values between three secure computation apparatuses is performed and the three secure computation apparatuses perform cooperative computation, thereby enabling the results of addition/subtraction, constant addition, multiplication, constant multiplication, logical operations (negation, logical product, logical sum, exclusive OR) and data format conversion (integers, binary numbers) to be held is a shared state, that is, in an encrypted state, between the three secure computation apparatuses, without restoring the numerical values. 
     In the case of performing division without revealing input and output values, there are methods of realizing Goldschmidt division by secure computation (e.g., see NPL 2). 
     CITATION LIST 
     Non Patent Literature 
     
         
         [NPL 1] Koji CHIDA, Koki HAMADA, Dai IGARASHI &amp; Katsumi TAKAHASHI, “A Three-party Secure Function Evaluation with Lightweight Verifiability Revisited”, CSS, 2010. 
         [NPL 2] Dan BOGDANOV, Margus NIITSOO, Tomas TOFT &amp; Jan WILLEMSON, “High-performance secure multi-party computation for data mining applications”, International Journal of Information Security, Vol. 11, No. 6, pp. 403-418, 2012. 
       
    
     SUMMARY OF THE INVENTION 
     Technical Problem 
     However, in the case of realizing Goldschmidt division by secure computation, it is necessary to use multiplication of fixed-point numbers. With secure computation, there is a problem in that multiplication of fixed-point numbers involves a large number of processing stages, that is, a high communication frequency. 
     With the foregoing technical problem in view, an object of this invention is to realize division with a small number of processing stages that does not use multiplication of fixed-point numbers. 
     Means for Solving the Problem 
     In order to solve the above problem, a secure division system according to one aspect of this invention is a secure division system including a plurality of secure computation apparatuses and for obtaining a secret value representing a result of dividing N by D using a secret value [N] of N and a secret value [D] of D, where R is an integer not less than 3, L 0  and L 1  are non-negative integers, N is a real number not less than 0 and less than R L1 , D is a natural number, N −L0 , . . . , N L1−1  are values of respective digits from an L 0 th digit after the decimal point to an L 1 th digit of an integer part in R notation of N, and j is each integer from L 1 −1 to −L 0 , each secure computation apparatus including an initialization unit configured to set a secret value [P L1 ] of a partial remainder P L1  to 0, a parallel comparison unit configured to compute secret values [E 1 ], . . . , [E R−1 ] of comparison results E 1 , . . . , E R−1  of comparing a secret value [n] of a partial divisor n=P j+1 R+N j  with [D]×g for each integer g not less than 1 and less than R in parallel, and an update unit configured to compute a secret value [Q j ] of a quotient Q j  and a secret value [P j ] of a partial remainder P j  that satisfy n=DQ j +P j  using the secret values [E 1 ], . . . , [E R−1 ] of the comparison results E 1 , . . . , E R−1 . 
     Effects of the Invention 
     According to this invention, division is realized without using multiplication of fixed-point numbers, thus enabling division to be realized with a small number of processing stages. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a diagram illustrating a functional configuration of a secure division system. 
         FIG. 2  is a diagram illustrating a functional configuration of a secure computation apparatus. 
         FIG. 3  is a diagram illustrating a processing procedure of a secure division method. 
         FIG. 4  is a diagram illustrating a functional configuration of a computer. 
     
    
    
     DESCRIPTION OF EMBODIMENTS 
     Firstly, the notation method and a definition of terminology in this specification will be described. 
     &lt;Notation Method&gt; 
     A value obtained by securing a given value a through encryption, secret sharing or the like will be called a secret value of a, and will be notated as [a]. In the case of the value a being secured through secret sharing, a set of fragments of secret sharing that are held by secure computation apparatuses will be referenced by [a]. 
     [a,b] (square brackets) in the definition range of variables represents a closed interval, and (a,b) (round brackets) represents an open interval. For example, i∈[a,b] represents i taking a value not less than a and not more than b. Also, i∈[a,b) represents i taking a value not less than a and less than b. 
     &lt;Addition, Subtraction, Multiplication&gt; 
     Addition, subtraction and multiplication operations on a secure sentence compute secret values [c 1 ], [c 2 ] and [c 3 ] of the respective computation results c 1 , c 2  and c 3  of a+b, a−b and ab, with secret values [a] and [b] of the two values a and b as inputs. Execution of these operations is respectively described as in the following formulas. 
     
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         c 
                         1 
                       
                       ] 
                     
                     ← 
                     
                       Add 
                       ⁡ 
                       
                         ( 
                         
                           
                             [ 
                             a 
                             ] 
                           
                           , 
                           
                             [ 
                             b 
                             ] 
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       [ 
                       
                         c 
                         2 
                       
                       ] 
                     
                     ← 
                     
                       Sub 
                       ⁡ 
                       
                         ( 
                         
                           
                             [ 
                             a 
                             ] 
                           
                           , 
                           
                             [ 
                             b 
                             ] 
                           
                         
                         ) 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       [ 
                       
                         c 
                         3 
                       
                       ] 
                     
                     ← 
                     
                       Mul 
                       ⁡ 
                       
                         ( 
                         
                           
                             [ 
                             a 
                             ] 
                           
                           , 
                           
                             [ 
                             b 
                             ] 
                           
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     1 
                   
                   ] 
                 
               
             
           
         
       
     
     If there is no risk of misunderstanding, Add([a],[b]), Sub([a],[b]) and Mul([a],[b]) may be respectively abbreviated to [a]+[b], [a]−[b] and [a]×[b]. 
     &lt;Comparison&gt; 
     A comparison operation computes a secret value [c] of a Boolean value c∈{0,1}, with secret values [a] and [b] of the two values a and b as inputs, where alb. The Boolean value takes 1 when true and 0 when false. Execution of this operation is described as in the following formula. 
     
       
         
           
             
               
                 
                   
                     [ 
                     c 
                     ] 
                   
                   ← 
                   
                     ( 
                     
                       
                         [ 
                         a 
                         ] 
                       
                       ⁢ 
                       
                         ≤ 
                         ? 
                       
                       ⁢ 
                       
                         [ 
                         b 
                         ] 
                       
                     
                     ) 
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ] 
                 
               
             
           
         
       
     
     Hereinafter, embodiments of this invention will be described in detail. Note that, in the drawings, constituent elements having the same function will be given the same numerals, and redundant description thereof will be omitted. 
     Embodiments 
     A secure division system of an embodiment computes and outputs secret values [Q −L0 ], . . . , [Q L1−1 ] of values Q −L0 , . . . , Q L1−1  of respective digits from an L 0 th digit after the decimal point to an L 1 th digit of an integer part in R notation of N/D, with a secret value [N] of a dividend N and a secret value [D] of a divisor D as inputs. Here, R is an integer not less than 3, L 0  and L 1  are non-negative integers, N is a real number not less than 0 and less than R L1 , and D is a natural number. Note that [N −L0 ], . . . , [N −L0+1 ], . . . , [N L1−2 ], [N L1−1 ] that are used throughout the embodiment are secret values of N −L0 , N −L0+1 , . . . , N L1−2 , N L1−1  representing R decomposition of N such as in the following formula. 
     
       
         
           
             
               
                 
                   
                     
                       N 
                       
                         - 
                         
                           L 
                           0 
                         
                       
                     
                     , 
                     
                       N 
                       
                         
                           - 
                           
                             L 
                             0 
                           
                         
                         + 
                         1 
                       
                     
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       N 
                       
                         
                           L 
                           1 
                         
                         - 
                         2 
                       
                     
                     , 
                     
                       N 
                       
                         L 
                         
                           1 
                           - 
                           1 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         s 
                         . 
                         t 
                         . 
                         
                             
                         
                         ⁢ 
                         N 
                       
                       = 
                       
                         
                           
                             ∑ 
                             
                               j 
                               ∈ 
                               
                                 [ 
                                 
                                   
                                     - 
                                     
                                       L 
                                       0 
                                     
                                   
                                   , 
                                   
                                     L 
                                     1 
                                   
                                 
                                 ) 
                               
                             
                           
                           ⁢ 
                           
                             
                               N 
                               j 
                             
                             ⁢ 
                             
                               R 
                               j 
                             
                           
                         
                         + 
                         r 
                       
                     
                     , 
                     
                       0 
                       ≤ 
                       r 
                       &lt; 
                       
                         R 
                         
                           - 
                           
                             L 
                             0 
                           
                         
                       
                     
                     , 
                     
                       
                         N 
                         j 
                       
                       ∈ 
                       
                         [ 
                         
                           0 
                           , 
                           R 
                         
                         ) 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     3 
                   
                   ] 
                 
               
             
           
         
       
     
     An example configuration of the secure division system of the embodiment will be described, with reference to  FIG. 1 . A secure division system  100  includes, for example, K (≥2) secure computation apparatuses  1   1 , . . . ,  1   K , as shown in  FIG. 1 . In the present embodiment, the secure computation apparatuses  1   1 , . . . ,  1   K  are each connected to a communication network  9 . The communication network  9  is a circuit switching or packet switching communication network configured such that connected apparatuses can communicate with each other, and the Internet, a LAN (Local Area Network), a WAN (Wide Area Network) or other such networks can be used, for example. Note that it is not necessarily required for the apparatuses to be able to communicate online via the communication network  9 . For example, a configuration may be adopted in which information to be input to the secure computation apparatuses  1   1 , . . . ,  1   K  is stored on a portable recording medium such as magnetic tape or a USB memory, and is input offline to the secure computation apparatuses  1   1 , . . . ,  1   K  from the portable recording medium. 
     An example configuration of a secure computation apparatus  1   k  (k=1, . . . , K) included in the secure division system  100  of the embodiment will be described, with reference to  FIG. 2 . The secure computation apparatus  1   k  includes, for example, an input unit  11 , an initialization unit  12 , a parallel comparison unit  13 , an update unit  14 , an iterative control unit  15  and an output unit  16 , as shown in  FIG. 2 . A secure division method of the present embodiment is realized by this secure computation apparatus  1   k  (k=1, . . . , K) performing the processing of steps described later in cooperation with another secure computation apparatus  1   k . (k′=1, . . . , K, where k≠k′). 
     The secure computation apparatus  1   k  is a special apparatus constituted by a special program being loaded on a known or dedicated computer having a central processing unit (CPU), a main storage device (RAM: Random Access Memory) and other such constituent elements. The secure computation apparatus  1   k  executes various processing under the control of the central processing unit, for example. Data input to the secure computation apparatus  1   k  and data obtained by the various processing is, for example, stored on the main storage device, and the data stored on the main storage device is read out to the central processing unit as needed and utilized in other processing. At least some of the processing units of the secure computation apparatus  1   k  may be constituted by hardware such as an integrated circuit. 
     A processing procedure of the secure division method that is executed by the secure division system  100  of the embodiment will be described, with reference to  FIG. 3 . 
     In step S 11 , the secret value [N] of the dividend N and the secret value [D] of the divisor D are input to the input unit  11  of each secure computation apparatus  1   k . Secret values [N −L0 ], . . . , [N L1−1 ] of N −L0  N −L0+1 , . . . , N L1−2 , N L1−1  representing R decomposition of the dividend N may be input to the input unit  11 , instead of the secret value [N] of the dividend N. In the case where the secret value [N] of the dividend N is input to the input unit  11 , the input unit  11  generates the secret values [N −L0 ], . . . , [N L1−1 ] of N −L0 , N −L0+1 , . . . , N L1−2 , N L1−1  representing R decomposition of the dividend N from the secret value [N] of the dividend N. The input unit  11  outputs the secret values [N −L0 ], . . . , [N L1−1 ] of N −L0 , N −L0+1 , . . . , N L1−2 , N L1−1  representing R decomposition of the dividend N and the secret value [D] of the divisor D to the parallel comparison unit  13 . 
     In step S 12 , the initialization unit  12  of each secure computation apparatus  1   k  initializes a secret value [P L1 ] of a partial remainder P L1  to [P L1 ]=0. Also, an index j of iterative processing is initialized to j=L 1 −1. The initialization unit  12  outputs the secret value [P L1 ] of the partial remainder P L1  to the parallel comparison unit  13 . Also, the index j is output to the iterative control unit  15 . 
     In step S 13 , the parallel comparison unit  13  of each secure computation apparatus  1   k  computes a secret value [E g ] (g∈[1,R)) of a result of comparing a secret value [n] of a partial devisor n where n=P j+1 R+N j  with each [D]×g where g∈[1,R) in parallel. Specifically, the parallel comparison unit  13  computes the secret value [E g ] of the comparison result E g  for each integer g not less than 1 and less than R by the following formula. The parallel comparison unit  13  outputs the secret values [E 1 ], . . . , [E R−1 ] of the comparison results E 1 , . . . , E R−1  to the update unit  14 . 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       E 
                       g 
                     
                     ] 
                   
                   = 
                   
                     
                       
                         ( 
                         
                           
                             
                               [ 
                               D 
                               ] 
                             
                             × 
                             g 
                           
                           ⁢ 
                           
                             ≤ 
                             ? 
                           
                           ⁢ 
                           
                             [ 
                             n 
                             ] 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       for 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       g 
                     
                     ∈ 
                     
                       [ 
                       
                         1 
                         , 
                         R 
                       
                       ) 
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     4 
                   
                   ] 
                 
               
             
           
         
       
     
     In step S 14 , the update unit  14  of each secure computation apparatus  1   k  computes a secret value [Q j ] of a quotient Q j  and a secret value [P j ] of a partial remainder P j , using the secret values [E 1 ], . . . , [E R−1 ] of the comparison results E 1 , . . . , E R−1 . Note that Q j  and P j  satisfy n=DQ j +P j , Q j ∈[0,R) and P j ∈[0,R). Specifically, the update unit  14  computes the secret value [Q j ] of the quotient Q j  and the secret value [P j ] of the partial remainder P j  by the following formula. The update unit  14  outputs the secret value [Q j ] of the quotient Q j  and the secret value [P j ] of the partial remainder P j  to the output unit  16 . 
     
       
         
           
             
               
                 
                   
                     
                       [ 
                       
                         Q 
                         j 
                       
                       ] 
                     
                     := 
                     
                       
                         [ 
                         
                           E 
                           1 
                         
                         ] 
                       
                       + 
                       … 
                       + 
                       
                         [ 
                         
                           E 
                           
                             R 
                             - 
                             1 
                           
                         
                         ] 
                       
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       [ 
                       
                         P 
                         j 
                       
                       ] 
                     
                     := 
                     
                       
                         [ 
                         n 
                         ] 
                       
                       - 
                       
                         
                           [ 
                           D 
                           ] 
                         
                         × 
                         
                           [ 
                           
                             Q 
                             j 
                           
                           ] 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     5 
                   
                   ] 
                 
               
             
           
         
       
     
     In step S 15 - 1 , the iterative control unit  15  of each secure computation unit  1   k  determines whether j is not more than −L 0 , that is, the truth of j≤−L 0 . If j≤−L 0  is false, that is, if j&gt;−L 0 , the processing is advanced to step S 15 - 2 . If j≤−L 0  is true, the processing is advanced to step S 16 . In step S 15 - 2 , the iterative control unit  15  of each secure computation apparatus  1   k  decrements j, that is, computes j=j−1, and returns the processing to step S 13 . In other words, the iterative control unit  15  performs control for repeatedly executing the parallel comparison unit  13  and the update unit  14  for each j where j=L 1 −1, . . . , −L 0 . 
     In step S 16 , the output unit  16  of each secure computation apparatus  1   k  outputs the secret values [Q −L0 ], . . . , [Q L1−1 ] of the quotients Q −L0 , . . . , Q L1−1 . 
     An algorithm that is executed in the abovementioned embodiment is shown below. 
     
       
         
           
             
               
                 
                   
                     
                       1. 
                       ⁢ 
                       
                           
                       
                       [ 
                       
                         P 
                         
                           L 
                           1 
                         
                       
                       ] 
                     
                     = 
                     0 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       2. 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       for 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       j 
                     
                     = 
                     
                       
                         
                           
                             L 
                             
                               1 
                               - 
                               1 
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           to 
                         
                         ⁢ 
                         
                             
                         
                         - 
                         
                           
                             L 
                             0 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               do 
                               ⁢ 
                               
                                 
 
                               
                               ( 
                               a 
                               ) 
                             
                             ⁢ 
                             
                                 
                             
                             [ 
                             n 
                             ] 
                           
                         
                       
                       := 
                       
                         
                           
                             [ 
                             
                               P 
                               
                                 j 
                                 + 
                                 1 
                               
                             
                             ] 
                           
                           × 
                           R 
                         
                         + 
                         
                           [ 
                           
                             N 
                             j 
                           
                           ] 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         ( 
                         b 
                         ) 
                       
                       ⁢ 
                       
                           
                       
                       [ 
                       
                         E 
                         g 
                       
                       ] 
                     
                     = 
                     
                       
                         
                           ( 
                           
                             
                               
                                 [ 
                                 D 
                                 ] 
                               
                               × 
                               g 
                             
                             ⁢ 
                             
                               ≤ 
                               ? 
                             
                             ⁢ 
                             
                               [ 
                               n 
                               ] 
                             
                           
                           ) 
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         for 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         g 
                       
                       ∈ 
                       
                         [ 
                         
                           1 
                           , 
                           R 
                         
                         ) 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         
                           ( 
                           c 
                           ) 
                         
                         ⁢ 
                         
                             
                         
                         [ 
                         
                           Q 
                           j 
                         
                         ] 
                       
                       := 
                       
                         
                           [ 
                           
                             E 
                             1 
                           
                           ] 
                         
                         + 
                         … 
                         + 
                         
                           [ 
                           
                             E 
                             
                               R 
                               - 
                               1 
                             
                           
                           ] 
                         
                       
                     
                     , 
                     
                       
                         [ 
                         
                           P 
                           j 
                         
                         ] 
                       
                       := 
                       
                         
                           [ 
                           n 
                           ] 
                         
                         - 
                         
                           
                             [ 
                             D 
                             ] 
                           
                           × 
                           
                             [ 
                             
                               Q 
                               j 
                             
                             ] 
                           
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Math 
                     . 
                     
                         
                     
                     ⁢ 
                     6 
                   
                   ] 
                 
               
             
           
         
       
     
     With the configuration of the abovementioned embodiment, division can be realized by comparison of L 0 +L 1  stages. Since one division requires a small number of stages, execution time is shortened, particularly when repeatedly executing division in series. 
     The case where R=2 in the abovementioned embodiment is equivalent to computing division in bit units. Division that is computed in bit units requires a large number of stages of comparison. In the abovementioned embodiment, even though the number of comparisons increases by approximately (R−1)/(log 2 R) times compared with division that is computed in bit units, the number of stages can be reduced by approximately 1/(log 2 R) times. 
     Although embodiments of this invention have been described above, the specific configuration is not limited to these embodiments, and appropriate design modifications or other such changes that do not depart from the spirit of this invention are intended to be included in the invention. The various types of processing described in the embodiments may be executed not only chronologically in the order of description but in parallel or individually according to the processing capacity of the apparatus that executes the processing or as needed. 
     [Program, Recording Medium] 
     In the case where the various types of processing functions in the apparatuses described in the abovementioned embodiments are executed by a computer, the processing contents of the functions that would be provided in the respective apparatuses will be described with a program. By loading this program on a storage unit  1020  of the computer shown in  FIG. 4  and operating a control unit  1010 , an input unit  1030 , an output unit  1040  and other such constituent elements, the various types of processing functions of the abovementioned apparatuses will be realized on the computer. 
     This program describing the processing contents can be recorded on a computer-readable recording medium. The computer-readable recording medium may, for example, be a magnetic recording device, an optical disc, a magneto-optical recording medium, a semiconductor memory or other such medium. 
     Also, distribution of this program is carried out by a portable recording medium such as DVD, CD-ROM or other such medium on which the program is recorded being sold, transferred, rented and the like. Furthermore, a configuration may also be adopted in which this program is distributed by storing the program on a storage device of a server computer, and transferring the program to other computers from the server computer via a network. 
     The computer that executes such a program first initially stores the program recorded on the portable recording medium or the program transferred from the server computer on a storage device thereof, for example. At the time of executing processing, this computer reads the program stored on the storage device thereof, and executes processing in accordance with the read program. Also, as other execution modes of this program, a configuration may be adopted in which the computer reads the program directly from the portable recording medium and executes processing in accordance with the read program, and, furthermore, whenever a program is transferred to this computer from the server computer, sequentially executes processing in accordance with the received program. Also, a configuration may be adopted in which the abovementioned processing is executed by a so-called ASP (Application Service Provider) service that realizes the processing functions with only an execution instruction and result acquisition from the server computer, without a program being transferred to the computer. Note that a computer program in the present embodiment is assumed to include any information that is to be processed by an electronic computer equivalent to a computer program (data, etc. that is not a direct set of instructions given to a computer but has the quality of defining processing by a computer). 
     Also, in this embodiment, the apparatus is configured by executing a prescribed program on a computer, but at least part of the processing contents thereof may be realized in a hardware manner.