Patent Publication Number: US-2021182062-A1

Title: Secure strong mapping computing systems, methods, secure computing apparatus and program

Description:
TECHNICAL FIELD 
     The present invention relates to techniques for computing mapping in secure computation. 
     BACKGROUND ART 
     A mapping protocol described in Non-Patent Literature 1 is known as a conventional technique for mapping computation. 
     Prior Art Literature 
     Non-Patent Literature 
     Non-Patent Literature 1: Koki Hamada, Dai Ikarashi, and Koji Chida, “A Batch Mapping Algorithm for Secure Function Evaluation”, The transactions of the Institute of Electronics, Information and Communication Engineers, Vol. J96-A, No. 4, pp. 157-165 
     SUMMARY OF THE INVENTION 
     Problems to be Solved by the Invention 
     The conventional mapping protocol, however, cannot detect outliers because a domain of definition is intervals (such as [1, 3]→1, [4, 8]→5, [9, 10]→2; there is no gap in the domain of definition). 
     The present invention is aimed at providing a secure strong mapping computing system, methods, a secure computing apparatus, and a program that can perform mapping computation while detecting outliers. 
     Means to Solve the Problems 
     A secure strong mapping computing system according to an aspect of the present invention is a secure joining computing system including a plurality of secure computing apparatuses, where F k  and F v  are arbitrary rings; [α] is a share generated by secret sharing of α, with α being an arbitrary vector or permutation; m and n are predetermined integers greater than or equal to 1; u is a predetermined value; r∈F k   m  is a predetermined vector with elements different from each other; and d∈F v   m  and x∈F k   n  are predetermined vectors. The plurality of secure computing apparatuses include: a plurality of first vector joining units that use a share [r] of the vector r and a share [x] of the vector x to generate a share [k] of a vector k ∈[F k ] 2m+n  which is generated by joining the vector r, the vector x, and the same vector as the vector r; a plurality of first permutation calculation units that use the share [k] to generate a share [σ] of a permutation σ for stable sorting of the vector k; a plurality of first vector generation units that use a share [d] of the vector d and u to generate a share [d′] of a vector d′, which is a vector generated by subtracting u from respective elements of the vector d; a plurality of second vector joining units that use the share [d′] to generate a share [v] of a vector v∈[F v ] 2m+n  which is generated by joining the vector d′, a 0-vector with a number of elements of n, and a vector −d′ which is a vector generated by inverting signs of respective elements of the vector d′; a plurality of first permutation application units that use the share [v] and the share [σ] to generate a share [σ(v)] of a vector σ(v) which is generated by application of the permutation σ to the vector v; a plurality of second vector generation units that use the share [σ(v)] to generate a share [σ(y)] of a vector σ(y), each element of which is a sum of the u and a sum of elements of the vector σ(v) up to an element corresponding to that element, the elements including the element corresponding to that element; a plurality of first inverse permutation application units that use the share [σ(y)] and the share [σ] to generate a share [σ −1 (σ(y))] of a vector σ −1 (σ(y)) which is generated by application of an inverse permutation σ −1  of the permutation σ to the vector σ(y); and a plurality of first vector extraction units that use the share [σ −1 (σ(y))] to obtain a share [y] of a vector y which is generated by extracting m+1th to m+nth elements of the vector σ −1 (σ(y)). 
     Effects of the Invention 
     Mapping computation can be performed while detecting outliers. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates a functional configuration of a secure strong mapping computing system and a secure joining system. 
         FIG. 2  illustrates a functional configuration of a secure computing apparatus for secure strong mapping computation. 
         FIG. 3  illustrates a processing procedure of a secure strong mapping computing method. 
         FIG. 4  illustrates a functional configuration of a secure computing apparatus of a secure joining system for performing left outer join. 
         FIG. 5  illustrates a processing procedure of a secure joining method for performing left outer join. 
         FIG. 6  illustrates a functional configuration of a secure computing apparatus of a secure joining system for performing right-left outer join. 
         FIG. 7  illustrates a processing procedure of a secure joining method for performing right outer join. 
         FIG. 8  illustrates a functional configuration of a secure computing apparatus of a secure joining system for performing full outer join. 
         FIG. 9  illustrates a processing procedure of a secure joining method for performing full outer join. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     Embodiments of the present invention are described below in detail. In the drawings, components having the same function are given the same reference characters and overlapping description is omitted. 
     [Secure Strong Mapping Computing System and Method] 
     Referring to  FIG. 1 , an exemplary configuration of a secure strong mapping computing system according to an embodiment is described. The secure strong mapping computing system includes N (≥2) secure computing apparatuses  1   1 , . . . ,  1   N . In this embodiment, the secure computing apparatuses  1   1 , . . . ,  1   N  are each connected to a communication network  2 . The communication network  2  is a circuit-switched or packet-switched communication network configured to allow communications between connected apparatuses, and can be the Internet, a local area network (LAN), a wide area network (WAN), and the like, for example. The apparatuses do not necessarily be capable of communicating online via the communication network  2 . For example, they may be configured such that information entered to the secure computing apparatuses  1   1 , . . . ,  1   N  is stored in a portable recording medium such as magnetic tape or a USB memory and the information is entered offline to the secure computing apparatuses  1   1 , . . . ,  1   N  from the portable recording medium. 
     Referring to  FIG. 2 , an exemplary configuration of a secure computing apparatus  1   n  (n=1, . . . , N) included in the secure strong mapping computing system is described. As shown in  FIG. 2 , the secure computing apparatus  1   n  of the secure strong mapping computing system includes a first vector joining unit  11   n , a first permutation calculation unit  12   n , a first vector generation unit  13   n , a second vector joining unit  14   n , a first permutation application unit  15   n , a second vector generation unit  16   n , a first inverse permutation application unit  17   n , and a first vector extraction unit  18   n , for example. 
     By the components of the secure computing apparatus  1   n  (1≤n≤N) performing processing at each step described later in cooperation with the components of other secure computing apparatus  1   n′  (n′=1, . . . , N; where n≠n′), a secure strong mapping computing method according to an embodiment is implemented. 
     The processing at each step is performed in secure computation. That is, the secure computing apparatus  1   n  performs the processing at each step without reconstructing a share, in other words, without knowing the content of the share. 
     The secure computing apparatus  1   n  is a special apparatus configured by loading of a special program into a well-known or dedicated computer having a central processing unit (CPU), main storage unit (random access memory: RAM), and the like, for example. The secure computing apparatus  1   n  executes various kinds of processing under control of the central processing unit, for example. Data input to the secure computing apparatus  1   n  and data resulting from processing are stored in the main storage unit, for example, and the data stored in the main storage unit is read into the central processing unit as necessary to be used for other processing. The components of the secure computing apparatus  1   n  may at least partially consist of hardware such as an integrated circuit. 
     For the following description, [α] is assumed to be a share generated by secret sharing of α, with α being an arbitrary vector or an arbitrary permutation. 
     Referring to  FIG. 3 , the processing procedure of the secure strong mapping computing method which is performed by the secure joining system in the embodiment is described. 
     The secure strong mapping computing system and method are for computing a vector y which is output when a mapping defined by a vector r ∈F k   m  corresponding to the domain of definition, a vector d∈F v   m  corresponding to a range, and an outlier u is applied to a vector x corresponding to input. m and n are predetermined integers greater than or equal to 1, the outlier u is a predetermined value, r∈F k   m  is a predetermined vector with elements different from each other, and d∈F v   m  and x∈F k   n  are predetermined vectors. 
     When r i  is the ith element of the vector r, d i  is the ith element of the vector d, x i  is the ith element of the vector x, and y i  is the ith element of the vector y, this mapping is a mapping that assumes y i =d when j with x i =r j  exists and assumes y i =u when j with x i =r j  does not exist. 
     For example, in the case of the vector r=(1, 3, 2), the vector d=(2, 5, 1), u=−1, and the vector x=(1, 0, 2, 5, 3), application of the mapping to the vector x=(1, 0, 2, 5, 3) gives a vector: the vector y=(2, −1, 1, −1, 5). 
     &lt;Step S 1 &gt; 
     A share [r] of the vector r and a share [x] of the vector x are input to the first vector joining units  11   1 , . . . ,  11   N . 
     The first vector joining units  11   1 , . . . ,  11   N  each generate a share [k] of a vector k∈[F k ] 2m+n  which is generated by joining the vector r, the vector x, and the same vector as the vector r (step S 1 ). 
     The generated share [k] is output to the first permutation calculation units  12   1 , . . . ,  12   N . 
     For example, assume that the vector r=(1, 3, 2) and the vector x=(1, 0, 2, 5, 3) hold. Then, the vector k=(1, 3, 2, 1, 0, 2, 5, 3, 1, 3, 2) is yielded. 
     &lt;Step S 2 &gt; 
     The share [k] is input to the first permutation calculation units  12   1 , . . . ,  12   N . 
     The first permutation calculation units  12   1 , . . . ,  12   N  each use the share [k] to generate a share [σ] of a permutation σ for stable sorting of the vector k (step S 2 ). 
     The share [σ] is output to the first vector generation units  13   1 , . . . ,  13   N . 
     For example, the permutation σ=(4, 0, 3, 8, 2, 5, 10, 1, 7, 9, 6) is yielded when the vector k=(1, 3, 2, 1, 0, 2, 5, 3, 1, 3, 2). 
     Generation of the share [σ] of the permutation σ for performing a stable sort can be implemented with the approach of Reference Literature 1, for example. 
     [Reference Literature 1] Dai Ikarashi, Koki Hamada, Ryo Kikuchi, and Koji Chida, “A Design and an Implementation of Super-high-speed Multi-party Sorting: The Day When Multi-party Computation Reaches Scripting Languages”, CSS2017, 2017 
     &lt;Step S 3 &gt; 
     A share [d] of the vector d and u are input to the first vector generation units  13   1 , . . . ,  13   N . 
     The first vector generation units  13   1 , . . . ,  13   N  each use the share [d] and u to generate a share [d′] of a vector d′, which is a vector generated by subtracting u from the respective elements of the vector d (step S 3 ). 
     The share [d′] is output to the second vector joining units  14   1 , . . . ,  14   N . 
     For example, the vector d′=(3, 6, 2) is yielded when the vector d=(2, 5, 1) and u=−1. 
     &lt;Step S 4 &gt; 
     The share [d′] is input to the second vector joining units  14   1 , . . . ,  14   N . 
     The second vector joining units  14   1 , . . . ,  14   N  each use the share [d′] to generate a share [v] of a vector v∈[F v ] 2m+n  which is generated by joining the vector d′, a 0-vector with a number of elements of n, and a vector −d′ which is a vector generated by inverting the signs of the respective elements of the vector d′ (step S 4 ). 
     The share [v] is output to the first permutation application units  15   1 , . . . ,  15   N . 
     For example, the vector v=(3, 6, 2, 0, 0, 0, 0, 0, −3, −6, −2) is yielded when the vector d′=(3, 6, 2) and n=5. 
     &lt;Step S 5 &gt; 
     The share [v] and the share [σ] are input to the first permutation application units  15   1 , . . . ,  15   N . 
     The first permutation application units  15   1 , . . . ,  15   N  each use the share [v] and the share [σ] to generate a share [σ(v)] of a vector σ(v) which is generated by application of the permutation σ to the vector v (step S 5 ). 
     The share [σ(v)] is output to the second vector generation units  16   1 , . . . ,  16   N . 
     For example, the vector σ(v)=(0, 3, 0, −3, 2, 0, −2, 6, 0, −6, 0) is yielded when the permutation σ=(4, 0, 3, 8, 2, 5, 10, 1, 7, 9, 6) and the vector v=(3, 6, 2, 0, 0, 0, 0, 0, −3, −6, −2). 
     &lt;Step S 6 &gt; 
     The share [σ(v)] is input to the second vector generation units  16   1 , . . . ,  16   N . 
     The second vector generation units  16   1 , . . . ,  16   N  each use the share [σ(v)] to generate a share [σ(y)] of a vector σ(y), each element of which is the sum of u and the sum of the elements of the vector σ(v) up to the element corresponding to that element, the elements including the element corresponding to that element (step S 6 ). In other words, the second vector generation units  16   1 , . . . ,  16   N  calculate the prefix-sum of the vector σ(v) with the initial value being u, as σ(y). When σ(v) i  is the ith element of σ(v) and σ(y) i  is the ith element of σ(y), σ(y) i =u+Σ j=1   i σ(v) j  is yielded. 
     The share [σ(y)] is output to the first inverse permutation application units  17   1 , . . . ,  17   N . 
     For example, the vector σ(y)=(−1, 2, 2, −1, 1, 1, −1, 5, 5, −1, −1) is yielded when the vector σ(v)=(0, 3, 0, −3, 2, 0, −2, 6, 0, −6, 0). 
     &lt;Step S 7 &gt; 
     The share [σ(y)] and the share [σ] are input to the first inverse permutation application units  17   1 , . . . ,  17   N . 
     The first inverse permutation application units  17   1 , . . . ,  17   N  each use the share [σ(y)] and the share [σ] to generate a share [σ −1 (σ(y))] of a vector σ −1 (σ(y)) which is generated by application of an inverse permutation σ −1  of the permutation σ to the vector σ(y) (step S 7 ). 
     The share [σ −1 (σ(y))] is output to the first vector extraction units  18   1 , . . . ,  18   N . 
     For example, the vector σ −1 (σ(y))=(2, 5, 1, 2, −1, 1, −1, 5, −1, −1, −1) is yielded when the permutation σ=(4, 0, 3, 8, 2, 5, 10, 1, 7, 9, 6) and the vector σ(y)=(−1, 2, 2, −1, 1, 1, −1, 5, 5, −1, −1). 
     &lt;Step S 8 &gt; 
     The share [σ −1 (σ(y))] is input to the first vector extraction units  18   1 , . . . ,  18   N . 
     The first vector extraction units  18   1 , . . . ,  18   N  each use the share [σ −1 (σ(y))] to obtain a share [y] of the vector y which is generated by extracting the m+1th to the m+nth elements of the vector σ −1 (σ(y)) (step S 8 ). 
     For example, the vector y=(2, −1, 1, −1, 5) is yielded when the vector σ −1 (σ(y))=(2, 5, 1, 2, −1, 1, −1, 5, −1, −1, −1). 
     The vector y=(2, −1, 1, −1, 5) represents a vector that is output when applying the mapping with the vector r=(1, 3, 2), the vector d=(2, 5, 1), u=−1, and the vector x=(1, 0, 2, 5, 3) to the vector x=(1, 0, 2, 5, 3). The first element “1”, the third element “2”, and the fifth element “3” of the vector x=(1, 0, 2, 5, 3) have been mapped to the first element “2”, the third element “1”, and the fifth element “5” of the vector y=(2, −1, 1, −1, 5), respectively, via the mapping. Also, the second element “0” and the fourth element “5” of the vector x=(1, 0, 2, 5, 3) have been mapped to the outlier “−1” via the mapping because they are values that do not exist in the elements of the vector r, which corresponds to the domain of definition. 
     In this manner, mapping computation can be performed while detecting outliers with the secure strong mapping computing system and method. 
     In the following, embodiments of the secure joining system and method using the secure strong mapping computing system and method are described. 
     [Secure Joining System and Method for Performing Left Outer Join] 
     Referring to  FIG. 1 , an exemplary configuration of a secure joining system according to an embodiment is described. This secure joining system and method performs so-called left outer join. Left outer join is discussed later. 
     The secure joining system includes N (≥2) secure computing apparatuses  1   1 , . . . ,  1   N  as with the secure strong mapping computing system. In this embodiment, the secure computing apparatuses  1   1 , . . . ,  1   N  are each connected to the communication network  2 . The communication network  2  is a circuit-switched or packet-switched communication network configured to allow communications between connected apparatuses, and can be the Internet, a local area network (LAN), a wide area network (WAN), and the like, for example. The apparatuses do not necessarily be capable of communicating online via the communication network  2 . For example, they may be configured such that information entered to the secure computing apparatuses  1   1 , . . . ,  1   N  is stored in a portable recording medium such as magnetic tape or a USB memory and the information is entered offline to the secure computing apparatuses  1   1 , . . . ,  1   N  from the portable recording medium. 
     Referring to  FIG. 4 , an exemplary configuration of a secure computing apparatus  1   n  (n=1, . . . , N) included in the secure joining system is described. As shown in  FIG. 4 , the secure computing apparatus  1   n  of the secure joining system includes the first vector joining unit  11   n , the first permutation calculation unit  12   n , the first vector generation unit  13   n , the second vector joining unit  14   n , the first permutation application unit  15   n , the second vector generation unit  16   n , the first inverse permutation application unit  17   n , the first vector extraction unit  18   n , a second permutation application unit  19   n , a third vector extraction unit  110   n , a second inverse permutation application unit  111   n , a second vector extraction unit  112   n , a modified second table generation unit  113   n , a third permutation application unit  114   n , a fourth vector generation unit  115   n , a shifting unit  116   n , a third inverse permutation application unit  117   n , a bit inversion unit  118   n , a third vector extraction unit  119   n , a modified first table generation unit  120   n , a first table joining unit  121   n , and a first table formatting unit  122   n , for example. 
     The first vector joining unit  11   n , the first permutation calculation unit  12   n , the first vector generation unit  13   n , the second vector joining unit  14   n , the first permutation application unit  15   n , the second vector generation unit  16   n , the first inverse permutation application unit  17   n , and the first vector extraction unit  18   n  of the secure computing apparatus  1   n , which are enclosed by dashed line in  FIG. 4 , can be said to be a portion corresponding to the secure strong mapping computing system. 
     By the components of the secure computing apparatus  1   n  (1≤n≤N) performing processing at each step described later in cooperation with the components of other secure computing apparatus  1   n′  (n′=1, . . . , N; where n≠n′), a secure joining method according to an embodiment is implemented. 
     The processing at each step is performed in secure computation. That is, the secure computing apparatus  1   n  performs the processing at each step without reconstructing a share, in other words, without knowing the content of the share. 
     The secure computing apparatus  1   n  is a special apparatus configured by loading of a special program into a well-known or dedicated computer having a central processing unit (CPU), main storage unit (random access memory: RAM), and the like, for example. The secure computing apparatus  1   n  executes various kinds of processing under control of the central processing unit, for example. Data input to the secure computing apparatus  1   n  and data resulting from processing are stored in the main storage unit, for example, and the data stored in the main storage unit is read into the central processing unit as necessary to be used for other processing. The components of the secure computing apparatus  1   n  may at least partially consist of hardware such as an integrated circuit. 
     Referring to  FIG. 5 , the processing procedure of the secure joining method which is performed by the secure joining system in the embodiment is described. 
     The secure joining system described below performs left outer join of a first table and a second table. In other words, the secure joining system described below joins records that are common to the first table and the second table with records that exist only in the first table while maintaining confidentiality. 
     Assume that m, n, L 1 , and L 2  are integers greater than or equal to 1. m, n, L 1 , and L 2  may be the same value or different values. 
     The first table has in records. Each one of the in records has one key and attribute values of L 1  attributes. Let k 1 ∈F k   m  be a vector of the keys of the first table. It is assumed that there are no overlapping keys in the first table. 
     The second table has n records. Each one of the n records has one key and attribute values of L 2  attributes. Let k 2 ∈F k   n  be a vector of the keys of the second table. It is assumed that overlapping keys are permitted in the second table. 
     For example, assume that the first table has three records and consists of a vector of keys, k 1 =(3, 5, 9), and a vector of the attribute values of one attribute v 1 , v 1 =(100, 19, 85). 
     Also assume that the second table has four records and consists of a vector of keys, k 2 =(3, 7, 9, 9), and a vector of the attribute values of one attribute v 2 , v 2 =(water, mix au lait, drug, water). 
     In a case where the first table contains the attribute values of multiple attributes, v 1  may be a vector which is a concatenation of the attribute values of the multiple attributes. For example, assume that the first table has two records and contains the attribute values of two attributes, where the vector of the attribute values of the first attribute is v 1,1 =(29, 169) and the vector of the attribute values of the second attribute is v 1,1 =(35, 175). In this case, v 1  may be the vector v 1 =((29, 35), (169, 175)), which is a concatenation of the attribute values of these two attributes. 
     Similarly, in a case where the second table contains the attribute values of multiple attributes, v 2  may be a vector which is a concatenation of the attribute values of the multiple attributes. 
     Since in general a vector with its elements being rings is also a ring, data formed by arranging the values of the respective attributes contained in a record can be considered to be a vector, that is, a ring. 
     First, with processing at the &lt;step S 1 &gt; to &lt;step S 8 &gt; of the secure strong mapping computing system and method described above, the vector y that is output when a mapping defined by r, d, and u is applied to x is calculated, where the vector corresponding to the domain of definition is the vector r=k 1 , the vector corresponding to the range is the vector d=v 1 , and the vector corresponding to input is the vector x=k 2 . This results in the attribute values of the attribute v 1  of the first table that correspond to the records of the second table. An attribute value corresponding to a record which is a record of the second table and which corresponds to a key that does not exist in the first table will be the outlier u. 
     As the processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; is similar to the processing of the processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; described in Section [Secure strong mapping computing system and method], overlapping description is not repeated here. 
     For example, in the case of the vector r=k 1 =(3, 5, 9), the vector d=v 1 =(100, 19, 85), u=−1, and x=k 2 =(3, 7, 9, 9), application of the mapping to the vector x=(3, 7, 9, 9) gives a vector: the vector y=(100, −1, 85, 85). Since the second element “7” of the vector x=k 2 =(3, 7, 9, 9) does not exist in the elements of the vector r=k 1 =(3, 5, 9), the second element of the vector y=(100, −1, 85, 85) is the outlier u=−1. In this manner, the vector y is calculated such that an attribute value corresponding to a record which is a record of the second table and which corresponds to a key that does not exist in the first table will be the outlier u. 
     &lt;Step S 9 &gt; 
     To the second permutation application units  19   1 , . . . ,  19   N , a share [g] of a vector g∈[F] 2m+n  which is generated by joining in elements each being 1, n elements each being 0, and in elements each being −1, and the share [σ] are input. Here, F is an arbitrary ring. 
     The second permutation application units  19   1 , . . . ,  19   N  each generate a share [σ(g)] of a vector σ(g) which is generated by application of the permutation σ to the vector g, using the share [g] of the vector g∈[F] 2m+n  which is generated by joining in elements each being 1, n elements each being 0, and in elements each being −1, and the share [σ] (step S 9 ). 
     The share [σ(g)] is output to the third vector generation units  110   1 , . . . ,  110   N . 
     For example, for example, g=(1, 1, 1, 0, 0, 0, 0, −1, −1, −1) and σ(g)=(1, 0, −1, 1, −1, 0, 1, 0, 0, −1) are yielded when m=3 and n=4 hold and the permutation σ is σ defined by the formula (1) below. 
     
       
         
           
             
               
                 
                   σ 
                   = 
                   
                     ( 
                     
                       
                         
                           3 
                         
                         
                           5 
                         
                         
                           9 
                         
                         
                           3 
                         
                         
                           7 
                         
                         
                           9 
                         
                         
                           9 
                         
                         
                           3 
                         
                         
                           5 
                         
                         
                           9 
                         
                       
                       
                         
                           3 
                         
                         
                           3 
                         
                         
                           3 
                         
                         
                           5 
                         
                         
                           5 
                         
                         
                           7 
                         
                         
                           9 
                         
                         
                           9 
                         
                         
                           9 
                         
                         
                           9 
                         
                       
                     
                     ) 
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
     Here, each sequence (i, j) T  of the permutation σ means that the ith element of the vector to which the permutation is applied is moved to the jth element. 
     &lt;Step S 10 &gt; 
     The share [σ(g)] is input to the third vector generation units  110   1 , . . . ,  110   N . 
     The third vector generation units  110   1 , . . . ,  110   N  each use the share [σ(g)] to generate a share [σ(g′)] of a vector σ(g′), each element of which is the sum of the elements of the vector σ(g) up to the element corresponding to that element, the elements including the element corresponding to that element (step S 10 ). In other words, the third vector generation units  110   1 , . . . ,  110   N  calculate the prefix-sum of σ(g) as σ(g′). When σ(g) i  is the ith element of σ(g) and σ(g′) i  is the ith element of σ(g′), σ(g′) i =Σ j=1   i σ(g) j  is yielded. 
     The share [σ(g′)] is output to the second inverse permutation application units  111   1 , . . . ,  111   N . 
     For example, σ(g′)=(1, 1, 0, 1, 0, 0, 1, 1, 1, 0) is yielded when σ(g)=(1, 0, −1, 1, −1, 0, 1, 0, 0, −1). 
     &lt;Step S 11 &gt; 
     The share [σ(g′)] and a share [g′] are input to the second inverse permutation application units  111   1 , . . . ,  111   N . 
     The second inverse permutation application units  111   1 , . . . ,  111   N  each use the share [σ(g′)] and the share [g′] to generate a share [g′] of a vector g′ which is generated by application of the inverse permutation σ −1  of the permutation σ to the vector σ(g′) (step S 11 ). 
     The share [g′] is output to the second vector extraction units  112   1 , . . . ,  112   N . 
     For example, g′=(1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0) is yielded when σ(g′)=(1, 1, 0, 1, 0, 0, 1, 1, 1, 0). 
     &lt;Step S 12 &gt; 
     The share [g′] is input to the second vector extraction units  112   1 , . . . ,  112   N . 
     The second vector extraction units  112   1 , . . . ,  112   N  each use the share [g′] to generate a share [f 1 ′] of a vector f 1 ′ which is generated by extracting the m+1th to m+nth elements of the vector g′ (step S 12 ). 
     The share [f 1 ′] is output to the modified second table generation units  113   1 , . . . ,  113   N . 
     For example, f 1 ′=(1, 0, 1, 1) is yielded when m=3, n=4, and g′=(1, 1, 1, 1, 0, 1, 1, 0, 0, 0). 
     &lt;Step S 13 &gt; 
     The share [f 1 ′] and the share [y] are input to the modified second table generation units  113   1 , . . . ,  113   N . 
     The modified second table generation units  113   1 , . . . ,  113   N  each use the share [f 1 ′] and the share [y] to generate a modified second table by joining the vector f 1 ′, the vector f 1 ′ if f 1 ′ i =0 with i=1, . . . , n, and a table having the ith element of the attribute of the second table as u v2 , and the vector y (step S 13 ). u v2  is a predetermined value. 
     The modified second table is output to the first table joining units  121   1 , . . . ,  121   N . 
     For example, in a case where the second table consists of the vector of keys, k 2 =(3, 7, 9, 9), and the vector of the attribute values of the one attribute v 2 , v 2 =(water, mix au lait, drug, water), with f 1 ′=(1, 0, 1, 1) and the vector (100, −1, 85, 85), the modified second table will be the table shown below. In the modified second table below, if f 1 ′ i =0 with i=1, . . . , n, the ith element of the key of the second table is turned into u=−1. 
     
       
         
           
               
            
               
                   
               
               
                 (A) 
               
            
           
           
               
               
               
               
               
            
               
                   
                 f1′ 
                 k 2   
                 v 1   
                 v 2   
               
               
                   
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 1 
                 3 
                 100 
                 water 
               
               
                   
                 0 
                 −1 
                 −1 
                 u v2   
               
               
                   
                 1 
                 9 
                 85 
                 drug 
               
               
                   
                 1 
                 9 
                 85 
                 water 
               
               
                   
                   
               
            
           
         
       
     
     &lt;Step S 14 &gt; 
     To the third permutation application units  114   1 , . . . ,  114   N , a share [e] of a vector e∈[F] 2m+n  which is generated by joining in elements each being 1, n elements each being 0, and in elements each being −1, and the share [σ] are input. 
     The third permutation application units  114   1 , . . . ,  114   N  each use the share [e] of the vector e∈[F] 2m+n  and the share [σ] to generate a share [σ(e)] of a vector σ(e) which is generated by application of the permutation σ to the vector e (step S 14 ). 
     The share [σ(e)] is output to the fourth vector generation units  115   1 , . . . ,  115   N . 
     For example, for example, g=(1, 1, 1, 0, 0, 0, 0, −1, −1, −1) and σ(g)=(1, 0, −1, 1, −1, 0, 1, 0, 0, −1) are yielded when m=3 and n=4 hold and the permutation σ is σ defined by the formula (1) above. 
     &lt;Step S 15 &gt; 
     The share [σ(e)] is input to the fourth vector generation units  115   1 , . . . ,  115   N . 
     The fourth vector generation units  115   1 , . . . ,  115   N  each use the share [σ(e)] to generate a share [σ(e′)] of a vector σ(e′), each element of which is the sum of the elements of the vector σ(e) up to the element corresponding to that element, the elements including the element corresponding to that element (step S 15 ). In other words, the fourth vector generation units  115   1 , . . . ,  115   N  calculate the prefix-sum of σ(e) as σ(e′). 
     The share [σ(e′)] is output to the shifting units  116   1 , . . . ,  116   N . 
     For example, σ(e′)=(1, 1, 0, 1, 0, 0, 1, 1, 1, 0) is yielded when σ(e)=(1, 0, −1, 1, −1, 0, 1, 0, 0, −1). 
     &lt;Step S 16 &gt; 
     The share [σ(e′)] is input to the shifting units  116   1 , . . . ,  116   N . 
     The shifting units  116   1 , . . . ,  116   N  each use the share [σ(e′)] to generate a share [σ(e″)] of a vector σ(e″) which is generated by shifting the elements of the vector σ(e) by one (step S 16 ). In the case of shifting the elements of the vector σ(e) each by one forward (to the left), the last element (the rightmost element) of the vector σ(e″) is set to 0, for example. Similarly, in the case of shifting the elements of the vector σ(e) each by one backward (to the right), the first element (the leftmost element) of the vector σ(e″) is set to 0, for example. 
     The share [σ(e″)] is output to the third inverse permutation application units  117   1 , . . . ,  117   N . 
     For example, the vector σ(e″)=(1, 0, 1, 0, 0, 1, 1, 1, 0, 0) is yielded when σ(e′)=(1, 1, 0, 1, 0, 0, 1, 1, 1, 0) and the elements are shifted forward (to the left) by one. 
     &lt;Step S 17 &gt; 
     The share [σ(e″)] and the share [σ] are input to the third inverse permutation application units  117   1 , . . . ,  117   N . 
     The third inverse permutation application units  117   1 , . . . ,  117   N  each use the share [σ(e″)] and the share [σ] to generate a share [e″] of a vector e″ which is generated by application of the inverse permutation σ −1  of the permutation σ to the vector σ(e″) (step S 17 ). 
     The share [e″] is output to the bit inversion units  118   1 , . . . ,  118   N . 
     For example, the vector e″=(1, 0, 1, 0, 1, 1, 0, 1, 0, 0) is yielded when the vector σ(e″)=(1, 0, 1, 0, 0, 1, 1, 1, 0, 0) holds and the permutation σ is σ defined by the formula (1) above. 
     &lt;Step S 18 &gt; 
     The share [e″] is input to the bit inversion units  118   1 , . . . ,  118   N . 
     The bit inversion units  118   1 , . . . ,  118   N  each use the share [e″] to generate a share [f] of a vector f which is generated by inverting 0 and 1 of the elements of the vector e″ (step S 18 ). 
     The share [f] is output to the third vector extraction units  119   1 , . . . ,  119   N . 
     For example, the vector f=(0, 1, 0, 1, 0, 0, 1, 0, 1, 1) is yielded when the vector e″=(1, 0, 1, 0, 1, 1, 0, 1, 0, 0). 
     &lt;Step S 19 &gt; 
     The share [f] is input to the third vector extraction units  119   1 , . . . ,  119   N . 
     The third vector extraction units  119   1 , . . . ,  119   N  each use the share [f] to generate a share [f′] of a vector f′ which is generated by extracting in elements of the vector f from the left (step S 19 ). 
     The share [f′] is output to the modified first table generation units  120   1 , . . . ,  120   N . 
     For example, the vector f′=(0, 1, 0) is yielded when the vector f=(0, 1, 0, 1, 0, 0, 1, 0, 1, 1). 
     The vector f′ represents the positions of records that exist only in the first table. For example, the vector f′=(0, 1, 0) means that the second record of the first table exists only in the first table and is absent in the second table. 
     &lt;Step S 20 &gt; 
     The share [f′], the share [r], and the share [d] are input to the modified first table generation units  120   1 , . . . ,  120   N . 
     The modified first table generation units  120   1 , . . . ,  120   N  each use the share [f′], the share [r], and the share [d] to generate a modified first table by joining the vector f′, the vector f′ having the ith element of the key of the first table as u k  if f′ i =0 with i=1, . . . , m, a table having the ith element of the attribute of the first table as u v1 , and a vector with elements being as a vector corresponding to the attribute of the second table, where f′ i  is the ith element of the vector f′, r i  is the ith element of the vector r, and u k  and u v1  are predetermined values (step S 20 ). 
     The modified first table is output to the first table joining units  121   1 , . . . ,  121   N . 
     For example, in a case where u k , u v1 =−1 and the vector f′=(0, 1, 0) hold, the first table has three records and consists of the vector of keys, k 1 =(3, 5, 9), and the vector of the attribute values of the one attribute v 1 , v 1 =(100, 19, 85), and r=k 1  and d=v 1  hold, the modified first table will be the table shown below. 
     
       
         
           
               
            
               
                   
               
               
                 (B) 
               
            
           
           
               
               
               
               
               
            
               
                   
                 f′ 
                 k 1   
                 v 1   
                 v 2   
               
               
                   
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 0 
                 −1 
                 −1 
                 u v2   
               
               
                   
                 1 
                 5 
                 19 
                 u v2   
               
               
                   
                 0 
                 9 
                 −1 
                 u v2   
               
               
                   
                   
               
            
           
         
       
     
     &lt;Step S 21 &gt; 
     The modified second table and the modified first table are input to the first table joining units  121   1 , . . . ,  121   N . 
     The first table joining units  121   1 , . . . ,  121   N  each generate a joined table by joining the modified second table and the modified first table (step S 21 ). 
     For example, when the modified second table is the one shown in (A) above and the modified first table is the one shown in (B) above, the joined table will be the table shown below. In the joined table below, a vector generated by joining the flag vector f 1 ′ and f is represented as f″. 
     
       
         
           
               
            
               
                   
               
               
                 (c) 
               
            
           
           
               
               
               
               
               
            
               
                   
                 f″ 
                 k 2   
                 v 1   
                 v 2   
               
               
                   
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 1 
                 3 
                 100  
                 water 
               
               
                   
                 0 
                 −1 
                 −1 
                 u v2   
               
               
                   
                 1 
                 9 
                 85 
                 drug  
               
               
                   
                 1 
                 9 
                 85 
                 water 
               
               
                   
                 0 
                 −1 
                 −1 
                 u v2   
               
               
                   
                 1 
                 5 
                 19 
                 u v2   
               
               
                   
                 0 
                 −1 
                 −1 
                 u v2   
               
               
                   
                   
               
            
           
         
       
     
     &lt;Step S 22 &gt; 
     The shares [f 1 ′] and [f′] are input to the first table formatting units  122   1 , . . . ,  122   N . 
     The first table formatting units  122   1 , . . . ,  122   N  each use the joined table and the shares [f 1 ′] and [f′] to generate a formatted joined table by extracting, from the joined table, records for which the elements of the vector f 1 ′ and the vector f′ (in other words, the elements of the vector f″ which is generated by joining the vector f 1 ′ and the vector f′) are 1 (step S 22 ). 
     For example, when the joined table is the joined table (C) above, the formatted joined table will be the table shown below. 
     
       
         
           
               
            
               
                   
               
               
                 (C) 
               
            
           
           
               
               
               
               
               
            
               
                   
                 f″ 
                 k 2   
                 v 1   
                 v 2   
               
               
                   
                   
               
            
           
           
               
               
               
               
               
            
               
                   
                 1 
                 3 
                 100 
                 water 
               
               
                   
                 1 
                 9 
                 85 
                 drug  
               
               
                   
                 1 
                 9 
                 85 
                 water 
               
               
                   
                 1 
                 5 
                 19 
                 u v2   
               
               
                   
                   
               
            
           
         
       
     
     Alternatively, the first table formatting units  122   1 , . . . ,  122   N  may generate the formatted joined table by sorting by the vector f″ which is generated by joining the vector f 1 ′ and the vector f′ and thereafter extracting the records for which the elements of the vector f″ are 1. In this case, the share [f″] of the vector f″ may be released. 
     This formatted joined table is a left outer join of the first table and the second table. 
     [Secure Joining System and Method for Performing Right Outer Join] 
     Referring to  FIG. 1 , an exemplary configuration of a secure joining system according to an embodiment is described. This secure joining system and method performs so-called right outer join. In other words, this secure joining system joins records that are common to the first table and the second table with records that exist only in the second table while maintaining confidentiality. 
     The secure joining system for performing right outer join is similar to the secure joining system for performing left outer join except that it includes a modified second table generation unit  123   n , instead of including the second permutation application unit  19   n , the third vector extraction unit  110   n , the second inverse permutation application unit  111   n , the second vector extraction unit  112   n , the modified second table generation unit  113   n , the third permutation application unit  114   n , the fourth vector generation unit  115   n , the shifting unit  116   n , the third inverse permutation application unit  117   n , the bit inversion unit  118   n , the third vector extraction unit  119   n , the modified first table generation unit  120   n , the first table joining unit  121   n , and the first table formatting unit  122   n . 
     The secure joining method for performing right outer join is similar to the secure joining method for performing left outer join except that it performs the processing at step S 23  instead of performing the processing at step S 9  to step S 22 . 
     In the following, differences from the secure joining system and method for performing left outer join are described. The same portions as those of the secure joining system and method for performing left outer join are not described again. 
     As shown in  FIG. 6 , the secure computing apparatus  1   n  of the secure joining system includes the first vector joining unit  11   n , the first permutation calculation unit  12   n , the first vector generation unit  13   n , the second vector joining unit  14   n , the first permutation application unit  15   n , the second vector generation unit  16   n , the first inverse permutation application unit  17   n , the first vector extraction unit  18   n , and the modified second table generation unit  123   n , for example. 
     The first vector joining unit  11   n , the first permutation calculation unit  12   n , the first vector generation unit  13   n , the second vector joining unit  14   n , the first permutation application unit  15   n , the second vector generation unit  16   n , the first inverse permutation application unit  17   n , and the first vector extraction unit  18   n  of the secure computing apparatus  1   n , which are enclosed by dashed line in  FIG. 6 , can be said to be a portion corresponding to the secure strong mapping computing system. 
     Referring to  FIG. 7 , the processing procedure of the secure joining method which is performed by the secure joining system in the embodiment is described. 
     As the processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; is similar to the processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; described in Section [Secure strong mapping computing system and method], overlapping description is not repeated here. 
     For example, in the case of the vector r=k 1 =(3, 5, 9), the vector d=v 1 =(100, 19, 85), u=−1, and x=k 2 =(3, 7, 9, 9), application of the mapping to the vector x=(3, 7, 9, 9) gives a vector: the vector y=(100, −1, 85, 85). Since the second element “7” of the vector x=k 2 =(3, 7, 9, 9) does not exist in the elements of the vector r=k 1 =(3, 5, 9), the second element of the vector y=(100, −1, 85, 85) is the outlier u=−1. In this manner, the vector y is calculated such that an attribute value corresponding to a record which is a record of the second table and which corresponds to a key that does not exist in the first table will be the outlier u. 
     &lt;Step S 23 &gt; 
     The share [y] is input to the modified second table generation units  123   1 , . . . ,  122   N . 
     The modified second table generation units  123   1 , . . . ,  122   N  each use the share [y] to generate a modified second table by joining the second table and the vector y (step S 23 ). 
     For example, in a case where the second table has four records and consists of the vector of keys, k 2 =(3, 7, 9, 9), and the vector of the attribute values of the one attribute v 2 , v 2 =(water, mix au lait, drug, water), with the vector y=(100, −1, 85, 85), the modified second table will be the table shown below. 
     
       
         
           
               
            
               
                   
               
               
                 (D) 
               
            
           
           
               
               
               
            
               
                 k 2   
                 v 1   
                 v 2   
               
               
                   
               
            
           
           
               
               
               
            
               
                 3 
                 100 
                 water 
               
               
                 7 
                 −1 
                 mix au lait 
               
               
                 9 
                 85 
                 drug 
               
               
                 9 
                 85 
                 water 
               
               
                   
               
            
           
         
       
     
     This modified second table is a right outer join of the first table and the second table. 
     [Secure Joining System and Method for Performing Full Outer Join] 
     Referring to  FIG. 8 , an exemplary configuration of a secure joining system according to an embodiment is described. This secure joining system and method performs so-called full outer join. In other words, this secure joining system joins records that are common to the first table and the second table, records that exist only in the first table, and records that exist only in the second table while maintaining confidentiality. 
     The secure joining system for performing full outer join is similar to the secure joining system for performing left outer join and the secure joining system for performing right outer join except that it includes a second table formatting unit  124   n  and a second table joining unit  125   n , instead of including the first table joining unit  121   n  and the first table formatting unit  122   n . 
     The secure joining method for performing full outer join is similar to the secure joining method for performing left outer join and the secure joining method for performing right outer join except that it performs the processing at steps S 24  and S 25  instead of performing the processing at step S 21  and step S 22 . 
     In the following, differences from the secure joining system and method for performing left outer join and the secure joining system and method for performing right outer join are described. The same portions as those of the secure joining system and method for performing left outer join and the secure joining system and method for performing right outer join are not described again. 
     As shown in  FIG. 8 , the secure computing apparatus  1   n  of the secure joining system includes the first vector joining unit  11   n , the first permutation calculation unit  12   n , the first vector generation unit  13   n , the second vector joining unit  14   n , the first permutation application unit  15   n , the second vector generation unit  16   n , the first inverse permutation application unit  17   n , the first vector extraction unit  18   n , the second permutation application unit  19   n , the third vector extraction unit  110   n , the second inverse permutation application unit  111   n , the second vector extraction unit  112   n , the modified second table generation unit  113   n , the third permutation application unit  114   n , the fourth vector generation unit  115   n , the shifting unit  116   n , the third inverse permutation application unit  117   n , the bit inversion unit  118   n , the third vector extraction unit  119   n , the modified first table generation unit  120   n , the first table joining unit  121   n , the first table formatting unit  122   n , the modified second table generation unit  123   n , the second table formatting unit  124   n , and the second table joining unit  125   n , for example. 
     The first vector joining unit  11   n , the first permutation calculation unit  12   n , the first vector generation unit  13   n , the second vector joining unit  14   n , the first permutation application unit  15   n , the second vector generation unit  16   n , the first inverse permutation application unit  17   n , and the first vector extraction unit  18   n  of the secure computing apparatus  1   n , which are enclosed by dashed line in  FIG. 8 , can be said to be a portion corresponding to the secure strong mapping computing system. 
     Referring to  FIG. 9 , the processing procedure of the secure joining method which is performed by the secure joining system in the embodiment is described. 
     First, processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; is performed. As the processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; is similar to the processing at &lt;step S 1 &gt; to &lt;step S 8 &gt; described in Section [Secure strong mapping computing system and method], overlapping description is not repeated here. 
     For example, in the case of the vector r=k 1 =(3, 5, 9), the vector d=v 1 =(100, 19, 85), u=−1, and x=k 2 =(3, 7, 9, 9), application of the mapping to the vector x=(3, 7, 9, 9) gives a vector: the vector y=(100, −1, 85, 85). Since the second element “7” of the vector x=k 2 =(3, 7, 9, 9) does not exist in the elements of the vector r=k 1 =(3, 5, 9), the second element of the vector y=(100, −1, 85, 85) is the outlier u=−1. In this manner, the vector y is calculated such that an attribute value corresponding to a record which is a record of the second table and which corresponds to a key that does not exist in the first table will be the outlier u. 
     Next, the processing at &lt;step S 23 &gt; is performed. As the processing at &lt;step S 23 &gt; is similar to the processing at &lt;step S 23 &gt; described in Section [Secure joining system and method for performing right outer join], overlapping description is not repeated here. 
     For example, in a case where the second table has four records and consists of the vector of keys, k 2 =(3, 7, 9, 9), and the vector of the attribute values of the one attribute v 2 , v 2 =(water, mix au lait, drug, water), with the vector y=(100, −1, 85, 85), the modified second table will be the table shown below. 
     
       
         
           
               
            
               
                   
               
               
                 (D) 
               
            
           
           
               
               
               
            
               
                 k 2   
                 v 1   
                 v 2   
               
               
                   
               
            
           
           
               
               
               
            
               
                 3 
                 100 
                 water 
               
               
                 7 
                 −1 
                 mix au lait 
               
               
                 9 
                 85 
                 drug 
               
               
                 9 
                 85 
                 water 
               
               
                   
               
            
           
         
       
     
     Next, processing at &lt;step S 9 &gt; to &lt;step S 20 &gt; is performed. As the processing at &lt;step S 9 &gt; to &lt;step S 20 &gt; is similar to the processing at &lt;step S 9 &gt; to &lt;step S 20 &gt; described in Section [Secure joining system and method for performing left outer join], overlapping description is not repeated here. 
     Next, processing at &lt;step S 24 &gt; and &lt;step S 25 &gt; is performed. 
     &lt;Step S 24 &gt; 
     The share [f′] is input to the second table formatting units  124   1 , . . . ,  124   N . 
     The second table formatting units  124   1 , . . . ,  124   N  each use the modified first table and the share [f′] to generate a formatted modified first table by extracting, from the modified first table, records for which the elements of the vector f′ are 1 (step S 24 ). 
     The formatted modified first table is output to the second table joining units  125   1 , . . . ,  125   N . 
     For example, when the modified first table is the table (B) above, the formatted modified first table will be the table shown below. 
     
       
         
           
               
               
               
               
               
             
               
                   
                   
               
             
            
               
                   
                 5 
                 19 
                 u v2   
                 (E) 
               
               
                   
                   
               
            
           
         
       
     
     &lt;Step S 25 &gt; 
     The modified second table and the formatted modified first table are input to the second table joining units  125   1 , . . . ,  125   N . 
     The second table joining units  125   1 , . . . ,  125   N  each generate a joined table by joining the modified second table and the formatted modified first table (step S 25 ). 
     For example, when the modified second table is the table (D) above and the formatted modified first table is the table (E) above, the joined table will be the table shown below. 
     
       
         
           
               
               
               
             
               
                   
               
               
                 k 2   
                 v 1   
                 v 2   
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
            
               
                 3 
                 100 
                 water 
               
               
                 7 
                 −1 
                 mix au lait 
               
               
                 9 
                 85 
                 drug 
               
               
                 9 
                 85 
                 water 
               
               
                 5 
                 19 
                 u v2   
               
               
                   
               
            
           
         
       
     
     This table is a full join of the first table and the second table. 
     MODIFICATIONS 
     While the embodiments of the present invention have been described, specific configurations are not limited to these embodiments, but design modifications and the like within a range not departing from the spirit of the invention are encompassed in the scope of the invention, of course. 
     For example, the attribute of a key may be a composite key of z attributes, where z is a positive integer greater than or equal to 2. In this case, the processing at step S 1  may be performed in the following manner, for example. 
     Assume r 0 , . . . , r z?1  instead of r. Assume x 0 , . . . , x z?1  instead of x. 
     In this case, the processing at step S 1  joins r i  and x i , then again with r i  to obtain k i  for each i (where i=0, . . . , z−1). Then, each k i  is turned into a bit representation by bit decomposition and joined horizontally. For example, when k 0 =(1, 2, 3, 1, 3, 0, 1, 1, 2, 3) T  and k 1 =(0, 0, 0, 0, 0, 1, 1, 0, 0, 0) T , bit decomposition of k 0  results in (k 0 ) 0 =(1, 0, 1, 1, 1, 0, 1, 1, 0, 1) T  and (k 0 ) 1 =(0, 1, 1, 0, 1, 0, 0, 0, 1,1) T . 
     Here, since k 0  assumes a value from 1 to 3, each element of k 0  can be represented in 2 bits. (k 0 ) 0  is the lower bit of k 0  upon bit decomposition, and (k 0 ) 1  is the upper bit of k 0  upon bit decomposition. Since k 1  is inherently a 1-bit number in this example, it does not require decomposition and k 1 =(k 1 ) 0  is assumed. Horizontal joining of (k 0 ) 0 , (k 0 ) 1 , and (k 1 ) 0  gives: 
     
       
         
           
             
               
                 ( 
                 
                   
                     
                       1. 
                     
                     
                       0. 
                     
                     
                       1. 
                     
                     
                       1. 
                     
                     
                       1. 
                     
                     
                       0. 
                     
                     
                       1 
                     
                   
                   
                     
                       0. 
                     
                     
                       1. 
                     
                     
                       1. 
                     
                     
                       0. 
                     
                     
                       1. 
                     
                     
                       0. 
                     
                     
                       0 
                     
                   
                   
                     
                       0. 
                     
                     
                       0. 
                     
                     
                       0. 
                     
                     
                       0. 
                     
                     
                       0. 
                     
                     
                       1. 
                     
                     
                       1 
                     
                   
                 
                 ) 
               
               T 
             
             . 
           
         
       
     
     Regarding such an arrangement as a matrix and regarding each row of this matrix as a bit representation of the keys of one record, a vector of bit representations of keys, (1, 2, 3, 1, 3, 4, 5, 1, 2, 3), is obtained. This vector can be k which is used at step S 2  and after. In this manner, a case with a composite key can also be addressed. 
     For a composite key, overlap of keys refers to whether keys overlap in terms of combination of the values of the all key attributes and it is assumed that mere overlapping of the values of individual attributes is not regarded as an overlap. For example, a combination of (1, 0) and (1, 1) is not an overlap. 
     The various processes described in the embodiments may be executed in parallel or separately depending on the processing ability of an apparatus executing the process or on any necessity, rather than being executed in time series in accordance with the described order. 
     [Program and Recording Medium] 
     When various types of processing functions in the apparatuses described above are implemented on a computer, the contents of processing function to be contained in each apparatus is written by a program. With this program executed on the computer, various types of processing functions in the above-described apparatuses are implemented on the computer. 
     This program in which the contents of processing are written can be recorded in a computer-readable recording medium. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disk, a magneto-optical recording medium, and a semiconductor memory. 
     Distribution of this program is implemented by sales, transfer, rental, and other transactions of a portable recording medium such as a DVD and a CD-ROM on which the program is recorded, for example. Furthermore, this program may be stored in a storage unit of a server computer and transferred from the server computer to other computers via a network so as to be distributed. 
     A computer which executes such program first stores the program recorded in a portable recording medium or transferred from a server computer once in a storage unit thereof, for example. When the processing is performed, the computer reads out the program stored in the storage unit thereof and performs processing in accordance with the program thus read out. As another execution form of this program, the computer may directly read out the program from a portable recording medium and perform processing in accordance with the program. Furthermore, each time the program is transferred to the computer from the server computer, the computer may sequentially perform processing in accordance with the received program. Alternatively, a configuration may be adopted in which the transfer of a program to the computer from the server computer is not performed and the above-described processing is executed by so-called application service provider (ASP)-type service by which the processing functions are implemented only by an instruction for execution thereof and result acquisition. It should be noted that a program in this form includes information which is provided for processing performed by electronic calculation equipment and which is equivalent to a program (such as data which is not a direct instruction to the computer but has a property specifying the processing performed by the computer). 
     In this form, the present apparatus is configured with a predetermined program executed on a computer. However, the present apparatus may be configured with at least part of these processing contents realized in a hardware manner.