Patent Publication Number: US-10333697-B2

Title: Nondecreasing sequence determining device, method and program

Description:
TECHNICAL FIELD 
     The present invention relates to an applied cipher technique and, in particular, to a method for determining whether a nondecreasing sequence exists without revealing input data. 
     BACKGROUND ART 
     There is a method, called secure computation, for obtaining computational results without decrypting encrypted numerical values (see Non-patent literature 1, for example). In the method in Non-patent Literature 1, encryption is performed that distributes pieces of a numerical value are distributed among three secure computers and the three secure computers cooperate to perform a computation, thereby enabling the result of an addition, subtraction, addition by a constant, multiplication, multiplication by a constant, or logical operation (negation, AND, OR, or exclusive-OR) or data format conversion (integer, binary) to be held in such a manner that the result is distributed among the three secure computers without reconstructing the numerical value, that is, with the result being kept encrypted. 
     One method of accomplishing pattern matching of character sequences on secure computation is a method described in Non-patent literature 2. In the method in Non-patent literature 2, pattern matching is accomplished by evaluating a nondeterministic finite automaton represented by a pattern character by character in an input text. 
     PRIOR ART LITERATURE 
     Non-Patent Literature 
     
         
         Non-patent literature 1: Koji Chida, Koki Hamada, Dai Ikarashi, Katsumi Takahashi: “A three-party secure function evaluation with lightweight verifiability revisited”, CSS, 2010 
         Non-patent literature 2: Hiroki Harada, Hirohito Sasakawa, Hiroki Arimura, Jun Sakuma, “A Polynomial Time/Space Algorithm for Oblivious Regular Expression Matching Algorithm”, SCIS, pp. 1-8, 2014 
       
    
     SUMMARY OF THE INVENTION 
     Problems to be Solved by the Invention 
     However, the existing technique in Non-patent literature 2 requires Ω(n) rounds of multiplications, where n is the length of an input text in pattern matching. A process for determining whether a text matches a pattern after positions of partial character strings in the pattern are identified in pattern matching can be abstracted to the problem of determining whether a nondecreasing sequence can be created by selecting elements one by one from each set of a sequence of sets. 
     An object of the present invention is to efficiently determine whether a nondecreasing sequence exists by selecting elements one by one from each set of a sequence of sets. 
     Means to Solve the Problem 
     To solve the problem described above, a nondecreasing sequence determining device according to the present invention comprises: a sorting part taking inputs of m sets P 0 , . . . , P m-1  and sorting elements of a set P i  in ascending order for i=0, . . . , m−1 to generate a vector t i,i+1  and a vector b i,i+1 ; a merging part merging vectors t 0,1 , . . . , t m-1,m  to generate a vector t 0,m  and merging vectors b 0,1 , . . . , b m-1,m  to generate a vector b 0,m  by repeating a process of merging vectors (t i,j , b i,j ) and vectors (t j,k , b i,k ) that satisfy 0≤i&lt;j&lt;k≤m to generate vectors (t j,k , b j,k ); and a determining part outputting a result of determination that indicates the absence of a nondecreasing sequence if the length of the vector t 0,m  is 0 and outputting a result of determination that indicates the presence of a nondecreasing sequence if the length of the vector t 0,m  is greater than or equal to 1. The merging part comprises: a stable-sorting part coupling a vector b i,j  with a vector t j,k  and stably sorting elements of a resulting vector to generate a vector e; a searching part searching the vector e for every set of (λ, x, y) in which e[λ] is b i,j [x] and e[λ+1] is t j,k [y] and generating a set X including all of found x and a set Y including all of found y; and an extracting part sorting elements t i,j [x] (x∈X) of a vector t i,j  in ascending order to generate a vector t i,k  and sorting elements b j,k [y] (y∈Y) of a vector b j,k  in ascending order to generate a vector b i,k . 
     Effects of the Invention 
     The nondecreasing sequence determining technique according to the present invention determines in O(log m) rounds whether a nondecreasing sequence exists by selecting elements one by one from each of m sets. Accordingly, whether a nondecreasing sequence exists can be efficiently determined. This enables efficient pattern matching for texts. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a diagram illustrating a functional configuration of a nondecreasing sequence determining device according to a first embodiment; 
         FIG. 2  is a diagram illustrating a process flow of a nondecreasing sequence determining method according to the first embodiment; 
         FIG. 3  is a diagram illustrating a functional configuration of a nondecreasing sequence determining device according to a third embodiment; and 
         FIG. 4  is a diagram illustrating a process flow of a nondecreasing sequence determining method according to the third embodiment. 
     
    
    
     DETAILED DESCRIPTION OF THE EMBODIMENTS 
     Before describing embodiments, notation and the definitions of terms used herein will be given. 
     Notation 
     A value “a” concealed by encryption or secret sharing is referred to as a secret text of “a” and denoted as &lt;a&gt;. If secret sharing is used for concealment, a set of pieces of a shared secret held by secure computing devices is referred to by &lt;a&gt;. 
     The i-th row of a matrix X is denoted by X[i]. The i-th element of a vector u is denoted by u[i]. A whole matrix of resulting from concealing the elements of a matrix X is denoted by &lt;X&gt; and is referred to as a secret text of X. A whole vector resulting from concealing the elements of a vector “u” is denoted by &lt;u&gt; and referred to as a secret text of “u”.
 
┌●┐  [Formula 1]
 
is the ceiling function and means the smallest integer greater than or equal to ●.
 
└●┘  [Formula 2]
 
is the floor function and means the greatest integer smaller than or equal to ●.
 
     ● T  denotes the transpose of ●. 
     &lt;Addition, Subtraction, Multiplication&gt; 
     Addition, subtraction and multiplication take inputs of secret texts &lt;a&gt;, &lt;b&gt; of two values a, b and yield secret texts &lt;c 1 &gt;, &lt;c 2 &gt; and &lt;c 3 &gt;, respectively, as the results of the computations, a+b, a−b, and ab, respectively. The executions of the operations are written as follows:
 
&lt; c   1 &gt;←Add(&lt; a&gt;,&lt;b &gt;),
 
&lt; c   2 &gt;←Sub(&lt; a&gt;,&lt;b &gt;),
 
&lt; c   3 &gt;←Mul(&lt; a&gt;,&lt;b &gt;)  [Formula 3]
 
     Note that when there is no risk of misunderstanding, Add (&lt;a&gt;, &lt;b&gt;), Sub (&lt;a&gt;, &lt;b&gt;) and Mul (&lt;a&gt;, &lt;b&gt;) are simply denoted as &lt;a&gt;+&lt;b&gt;, &lt;a&gt;−&lt;b&gt; and &lt;a&gt;×&lt;b&gt;, respectively. 
     &lt;Logical Operations&gt; 
     Logical OR, logical AND, and negation operations take inputs of secret texts &lt;a&gt;, &lt;b&gt; of two values a, b∈{0, 1} and yield secret texts &lt;c 1 &gt;, &lt;c 2 &gt; and &lt;c 3 &gt;, respectively, of the results c 1 , c 2 , and c 3  of logical OR of “a” and “b”, logical AND of “a” and “b” and negation of “a”, respectively. The executions of the operations are written as follows:
 
&lt; c   1   &gt;←&lt;a&gt;     &lt;b&gt;,  
 
&lt; c   2   &gt;←&lt;a&gt;     &lt;b&gt;,  
 
&lt; c   3   &lt;←     &lt;a&gt;   [Formula 4]
 
     The logical operations are accomplished by computations of the following formulas:
 
&lt; c   1   &gt;←&lt;a&gt;+&lt;b&gt;−&lt;a&gt;×&lt;b&gt;,  
 
&lt; c   2   &gt;←&lt;a&gt;×&lt;b&gt;,  
 
&lt; c   3 &gt;←1−&lt; a&gt;   [Formula 5]
 
     &lt;Sort Operation&gt; 
     Sort is an operation that sorts elements of a vector in ascending order and outputs the resulting vector. The vector k′=(k′[0], . . . , k′[n−1]) output for an input vector k=(k[0], . . . , k[n−1]) is a vector resulting from sorting of the elements of k that satisfy k′[0]≤ . . . ≤k′[n−1]. 
     Stable sort is an operation which preserves the original order of elements having the same value, if present, in the sort operation. Elements of vectors k and k′ satisfy k′[π s (i)]=k[i] for a given bijection π s {0, . . . , n−1}→{0, . . . , n−1} and the following formula holds in the stable sort.
 
π s ( i )&lt;π s ( j ) ( k [ i ]&lt; k [ j ]) ( k [ i ]= k [ j ]   i&lt;j )  [Formula 6]
 
     A stable sort operation in secret computation dealt with in the following description takes inputs of a plurality of vectors and, in accordance with sorting of the elements of a vector used as a key, sorts the elements of another vector. Specifically, a stable sort operation takes inputs of a vector k having a size n used as the key in the stable sort and secret texts &lt;k&gt;, &lt;a (0) &gt;, . . . , &lt;a (λ−1) &gt; of a number λ, (1≤λ) of vectors a (0) , . . . , a (λ−1)  having the size n and calculates secret texts &lt;b (0) &gt;, . . . , &lt;b (λ−1) &gt; of vectors b (0) , . . . , b (λ−1)  in which the elements of each vector a (0) , . . . , a (λ−1)  are sorted in accordance with the order of the elements of the vector k sorted by the stable sort.
 
&lt; b   (0)   &gt;, . . . ,&lt;b   (λ−1) &gt;←StableSort(&lt; a   (0)   &gt;, . . . ,&lt;a   (λ−1)   &gt;;&lt;k &gt;)  [Formula 7]
 
     Key reveal sort is processing in which a key is revealed in a stable sort operation. The processing is more efficient than processing performed with the key being concealed and, if the configuration of values included in the key is known, there is no risk of unnecessarily revealing information. The execution of the operation is written as follows.
 
&lt; b   (0)   &gt;, . . . ,&lt;b   (λ−1) &gt;←RevealSort(&lt; a   (0)   &gt;, . . . ,&lt;a   (λ−1)   &gt;;&lt;k &gt;)  [Formula 8]
 
     Concealment, reconstruction, addition, subtraction and multiplication may be accomplished by using methods described in Non-Patent Literature 1. Stable sort and key reveal sort may be accomplished by using a method described in Koki Hamada, Dai Ikarashi, Koji Chida, and Katsumi Takahashi, “Oblivious radix sort: An efficient sorting algorithm for practical secure multi-party computation”, IACR Cryptology ePrint Archive, vol. 2014, p. 121, 2014 (Reference literature 1)”. 
     &lt;Nondecreasing Sequences&gt; 
     The nondecreasing sequence determining technique is a method for determining whether a vector p that is a nondecreasing sequence having a size m form sets P 0 , P 1 , . . . , P m-1  (where p[i]∈P i (0≤i&lt;m) and p[0]≤p[1]≤ . . . ≤p[m−1]). 
     For example, assume that sets P 0 , P 1 , . . . , P 4  are as follows. 
     P 0 ={0, 3, 7, 8, 10} 
     P 1 ={2, 5, 8, 9} 
     P 2 ={2, 4, 8} 
     P 3 ={0, 4, 7, 9} 
     P 4 ={0, 6, 7} 
     For example, the vector P 0 ={0, 8, 2, 4, 6} satisfies p 0 [i]∈P i (0≤i&lt;m) but does not satisfy p 0 [0]≤p 0 [1]≤p 0 [2]≤p 0 [3]≤p 0 [4] because p 0 [1]&gt;p 0 [2], and therefore the vector p 0  is not a nondecreasing sequence. 
     On the other hand, for example, the vector p 1 =(0, 2, 4, 4, 6) satisfies p 1 [i]∈P i (0≤i&lt;m) and also satisfies p 1 [0]≤p 1 [1]≤p 1 [2]≤p 1 [3]≤p 1 [4] and therefore the vector p 1  is a nondecreasing sequence. 
     Embodiments of the present invention will be described below in detail. Note that components that has like functions are given like reference numerals in drawings and repeated description of the components will be omitted. 
     First Embodiment 
     As illustrated in  FIG. 1 , a nondecreasing sequence determining device  1  according to a first embodiment comprises a sorting part  10 , a merging part  20  and a determining part  30 . The merging part  20  comprises a stable-sorting part  21 , a searching part  22  and an extracting part  23 , for example. 
     The nondecreasing sequence determining device  1  is a special device configured by installing a special program into a well-known or dedicated computer comprising a central processing unit (CPU), a random access memory (RAM) and other components. The nondecreasing sequence determining device  1  executes processes under the control of the CPU, for example. Data input into the nondecreasing sequence determining device  1  and data obtained through the processes are stored in the RAM and the data stored in the RAM is read and used in other processes as needed, for example. 
     A nondecreasing sequence determining method according to the first embodiment will be described below with reference to  FIG. 2 . 
     The nondecreasing sequence determining method according to the first embodiment takes inputs of m sets P 0 , . . . , P m-1  and returns 1 if a vector p that is a nondecreasing sequence having a size m exists or returns 0 if not. 
     At step S 10 , the sorting part  10  sorts the elements of a set P i , where i=0, . . . , m−1, in ascending order to generate vectors t i,i+1  and b i,i+1 . Specifically, the sorting part  10  sorts the elements of a set P 0  in ascending order to generate vectors t 0,1  and b 0,1 , sorts the elements of a set P 1  in ascending order to generate vectors t 1,2  and b 1,2 , and sorts the elements of a set P m-1  in ascending order to generate vectors t m-1,m  and b m-1,m . 
     At step S 20   a , the merging part  20  selects vectors (t i,j , b i,j ) and (t j,k , b j,k ), merges the vectors (t i,j , b i,j ) and (t j,k , b j,k ) by a process from step S 21  to step S 23  to generate vectors (t i,k , b i,k ). By recursively performing the process, the merging part  20  merges vectors t 0,1 , . . . , t m-1 , . . . , t m-1,m  to generate a vector t 0,m  and merges vectors b 0,1 , . . . , b m-1,m  to generate a vector b 0,m . 
     At step S 21 , the stable-sorting part  21  couples the vector b i,j  and vector t j,k  together and stably sorts the elements in ascending order to generate a vector e. 
     At step S 22 , the searching part  22  searches the vector e for every set (λ, x, y) in which e[λ] is b i,j [x] and e[λ+1] is t j,k [y] and generates a set X that includes all of found x and a set Y that includes all of found y. 
     At step S 23 , the extracting part  23  sorts t i,j [x] (x∈X) in ascending order to generate a vector t i,k  and sorts b j,k [y] (y∈Y) to generate a vector b i,k . 
     At step S 20   b , the merging part  20  determines whether all of the vectors t 0,1 , . . . , t m-1,m  and vectors b 0,1 , . . . , b m-1,m  have been merged. In other words, the merging part  20  determines whether vectors (t 0,m,  b 0,m ) have been generated. If the merge has not been completed, the process returns to step S 20   a . If merge has been completed, the process proceeds to step S 30 . 
     At step S 30 , if the length of a vector t 0,m  is 0, the determining part  30  outputs 0 indicating the absence of a nondecreasing sequence. If the length of a vector t 0,m  is greater than or equal to 1, the determining part  30  outputs 1 indicating the presence of a nondecreasing sequence. 
     An example will be used to show that the presence of a nondecreasing sequence can be determined by the method described above. 
     Assume that sets P 0 , P 1 , . . . , P 4  are as follows. 
     P 0 −{0, 3, 7, 8, 10} 
     P 1 ={2, 5, 8, 9} 
     P 2 ={2, 4, 8} 
     P 3 ={0, 4, 7, 9} 
     P 4 ={0, 6, 7} 
     Since a nondecreasing sequence is p[i]∈P i (0≤i&lt;m) and p i [0]≤p 1 [1]≤p 1 [2]≤p 1 [3]≤p 1 [4], there are nondecreasing sequences such as (0, 2, 2, 4, 6), (0, 2, 2, 4, 7), (0, 2, 4, 4, 6), (0, 2, 4, 4, 7) and (0, 2, 4, 7, 7), for example, in sets P 0 , P 1 , . . . , P 4 . 
     At step S 10 , the following vectors t 0,1 , . . . , t 4,5  and b 0,1 , . . . , b 4,5  are generated. 
     t 0,1 =b 0,1 =(0, 3, 7, 8, 10) 
     t 1,2 =b 1,2 =(2, 5, 8, 9) 
     t 2,3 =b 2,3 =(2, 4, 8) 
     t 3,4 =b 3,4 =(0, 4, 7, 9) 
     t 4,5 =b 3,4 =(0, 6, 7) 
     At step S 20   a , i=0, j=1, and k=2 are set and vectors (t 0,1 , b 0,1 ) and (t 1,2 , b, 1,2 ) are selected and merged by performing steps S 21  to S 23  described below to generate vectors (t 0,2 , b 0,2 ). 
     At step  21 , the following vector e is generated from the vectors b 0,1  and t 1,2 . 
     e=(0, 2, 3, 5, 7, 8, 8, 9, 10) 
     =(b 0,1 [0], t 1,2 [0], b 0,1 [1], t 1,2 [1], b 0,1 [2], b 0,1 [3], t 1,2 [2], t 1,2 [3], b 0,1 [4]) 
     At step S 22 , the following sets of (λ, x, y) are found. 
     (λ=0,x=0,y=0), 
     (λ=2,x=1,y=1), 
     (λ=5,x=3,y=2) 
     Therefore, set λ={0, 1, 31} and set Y={0, 1, 2}. 
     At step S 23 , the following vectors (t 0,2 , b 0,2 ) are generated. 
     t 0,2 =(t 0,1 [0], t 0,1 [1], t 0,1 [3])=(0, 3, 8) 
     b 0,2 =(b 1,2 [0], b 1,2 [1], b 1,2 [2])=(2, 5, 8) 
     At step S 20   b , vectors t 0,5  and b 0,5  do not exist and therefore the process returns to step S 20   a.    
     In the second round of step S 20   a , i−2, j−3 and k−4 are set, vectors (t 2,3 , b 2,3 ) and (t 3,4 , b 3,4 ) are selected and merged vectors (t 2,4 , b, 2,4 ) are generated in the same way as described above. 
     The vector b 2,3 =(2, 4, 8) and the vector t 3,4 =(0, 4, 7, 9) are coupled together and stable sort is performed to generate the following vector e. 
     e=(0, 2, 4, 4, 7, 8 9) 
     =(t 3,4 [0], b 2,3 [0], b 2,3 [1], t 3,4 [1], t 3,4 [2], b 2,3 [2], t 3,4 [3]) 
     Then, (λ=2,x=1,y=1) and (λ=5,x=2,y=3) are found and therefore X=(1,2) and Y=(1, 3). Accordingly, the vectors (t 2,4 , b 2,4 ) are as follows. 
     t 2,4 =(t 2,3 [1], t 2,3 [2])=(4, 8) 
     b 2,4 =(b 3,4 [1], b 3,4 [3])=(4, 9) 
     In the third round of step S 20   a , i=2, j=4 and k=5 are set, vectors (t 2,4 , b 2,4 ) and (t 4,5 , b 4,5 ) are selected and merged vectors (t 2,5 , b 2,5 ) is generated in the same way as described above. 
     The vector b 2,4 −(4, 9) and the vector t 4,5 −(0, 6, 7) are coupled together and stable sort is performed to generate the following vector e. 
     e=(0, 4, 6, 7, 9) 
     =(t 4,5 [0], b 2,4 [0], t 4,5 [1], t 4,5 [2], b 2,4 [1]) 
     Then, (λ=1, x=0, y=1) is found and therefore X=(0) and Y=(1). Accordingly, the vectors (t 2,5 , b 2,5 ) are as follows. 
     t 2,5 =(t 2,4 [0])=(4) 
     b 2,5 =(b 4,5 [1])=(6) 
     In the fourth round of step S 20   a , i=0, j=2 and k=5 are set, vectors (t 0,2 , b 0,2 ) and (t 2,5 , b 2,5 ) are selected and merged vectors (t 0,5 , b 0,5 ) are generated in the same way as described above. 
     The vector b 0,2 =(2, 5, 8) and the vector t 2,5 =(4) are coupled together and stable sort is performed to generate the following vector e. 
     e=(2, 4, 5, 8) 
     =(b 0,2 [0], t 2,5 [0], b 0,2 [1], b 0,2 [2]) 
     Then, (λ=0, x=0, y=0) is found and therefore X=(0) and Y=(0). Accordingly, the vector (t 0,5 , b 0,5 ) is as follows. 
     t 0,5 =(t 0,2 [0])=(0) 
     b 0,5 =(b 2,5 [0])=(6) 
     At step S 20   b , since vectors t 0,5  and b 0,5  exist, the process proceeds to step S 30 . 
     At step S 30 , since the length of t 0,5  is not 0, 1 indicating the presence of a nondecreasing sequence is output as the result of determination. 
     Second Embodiment 
     In a nondecreasing sequence determining device according to a second embodiment, a merging part  20  sets i, j, and k such that the following formula is satisfied, and vectors (t i,j , b i,j ) and vectors (t i,k , b i,k ) are selected for generating vectors (t i,k , b i,k ). 
     
       
         
           
             
               
                 
                   j 
                   = 
                   
                     ⌊ 
                     
                       
                         i 
                         + 
                         k 
                       
                       2 
                     
                     ⌋ 
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     9 
                   
                   ] 
                 
               
             
           
         
       
     
     By configuring as described above, the merging part  20  can obtain vectors (t 0,m , b 0,m ) with a recursive procedure in
 
┌log 2   m┐   [Formula 10]
 
rounds.
 
     Third Embodiment 
     A third embodiment is a method of determining whether a nondecreasing sequence exists by using secure computation. In the third embodiment, each iteration of a recursive procedure can be accomplished in O(1) rounds of computations and therefore the whole process can be accomplished in O(log m) rounds. 
     As illustrated in  FIG. 3 , a nondecreasing sequence determining device  2  according to the third embodiment comprises a sorting part  10 , a concealing part  40 , a merging part  50 , and a determining part  60 . The merging part  50  comprises a first stable-sorting part  51 , a first key-reveal-sorting part  52 , a second stable-sorting part  53  and a second key-reveal-sorting part  54 , for example. 
     A nondecreasing sequence determining method according to the third embodiment will be described below with reference to  FIG. 4 . The following description focuses on differences from the first embodiment described above. 
     At step S 40 , the concealing part  40  determines that each of the elements of a set P i , where i=0, . . . , m−1, is greater than or equal to 0 and less than n, and converts a vector to a vector to generate an encrypted text &lt;t′ i,i+1 &gt; in which the vector t i,i,+1  is concealed in accordance with the following formula. 
     
       
         
           
             
               
                 
                   
                     
                       t 
                       
                         i 
                         , 
                         
                           i 
                           + 
                           1 
                         
                       
                       ′ 
                     
                     ⁡ 
                     
                       [ 
                       k 
                       ] 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ∃ 
                                   
                                     λ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       s 
                                       . 
                                       t 
                                       . 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         
                                           t 
                                           
                                             i 
                                             , 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                         
                                         ⁡ 
                                         
                                           [ 
                                           λ 
                                           ] 
                                         
                                       
                                     
                                   
                                 
                               
                               = 
                               k 
                             
                             , 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     11 
                   
                   ] 
                 
               
             
           
         
       
     
     Similarly, the concealing part  40  converts a vector b i,i+1  to a vector b′ i,i+1  to generate an encrypted text &lt;b′ i,i+1 &gt; in which the vector b i,i,+1  is concealed in accordance with the following formula. 
     
       
         
           
             
               
                 
                   
                     
                       b 
                       
                         i 
                         , 
                         
                           i 
                           + 
                           1 
                         
                       
                       ′ 
                     
                     ⁡ 
                     
                       [ 
                       k 
                       ] 
                     
                   
                   = 
                   
                     { 
                     
                       
                         
                           1 
                         
                         
                           
                             
                               
                                 if 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   ∃ 
                                   
                                     λ 
                                     ⁢ 
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       s 
                                       . 
                                       t 
                                       . 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         
                                           b 
                                           
                                             i 
                                             , 
                                             
                                               i 
                                               + 
                                               1 
                                             
                                           
                                         
                                         ⁡ 
                                         
                                           [ 
                                           λ 
                                           ] 
                                         
                                       
                                     
                                   
                                 
                               
                               = 
                               k 
                             
                             , 
                           
                         
                       
                       
                         
                           0 
                         
                         
                           otherwise 
                         
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     12 
                   
                   ] 
                 
               
             
           
         
       
     
     Examples of vectors t′ i,i,+1  and b′ i,i+1  are given below. For example, assume that sets P 0 , P 1 , . . . , P 4  are as follows. 
     P 0 ={0, 3, 7, 8, 10} 
     P 1 ={2, 5, 8, 9} 
     P 2 ={2, 4, 8} 
     P 3 ={0, 4, 7, 9} 
     P 4 ={0, 6, 7} 
     Let n=12, then vectors t′ i,i,+1  and by b′ i,i,+1  are as follows. 
     t′ 0,1 =b′ 0,1 =(1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0), 
     t′ 1,2 =b′ 1,2 =(0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0, 0), 
     t′ 2,3 =b′ 2,3 =(0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0), 
     t′ 3,4 =b′ 3,4 =(1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0), 
     t′ 4,5 =b′ 4,5 =(1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0) 
     At step S 50   a , the merging part  50  selects a secret text (&lt;t′ i,j &gt;, &lt;b i,j &gt;) and a secret text (&lt;t′ j,k &gt;, &lt;b′ j,k &gt;) that satisfy 0≤i&lt;j&lt;k≤m and merges the secret text (&lt;t′ i,j &gt;, &lt;b′ i,j ) and the secret text (&lt;t′ j,k &gt;, &lt;b′ j,k &gt;) together by the process from step S 51  to step S 54  to generate a secret text (&lt;t′ j,k &gt;, &lt;b′ j,k &gt;). By recursively performing the process, the merging part  50  merges secret texts &lt;t′ 0,1 &gt;, . . . , &lt;t′ m-1,m &gt; to generate a secret text &lt;t′ 0,m &gt; and merges secret texts &lt;b′ 0,1 &gt;, . . . , &lt;b′ m-1,m &gt; to generate a secret text &lt;b′ 0,m &gt;. 
     At step S 51 , the first stable-sorting part  51  alternately arranges elements of a secret text &lt;b′ i,j &gt; and elements of secret text &lt;t′ j,k &gt; to generate a secret text &lt;a&gt;. Specifically, the first stable-sorting part  51  generates a secret text &lt;a&gt; for h=0, . . . , n−1 in accordance with the following formula.
 
&lt; a [2 h ]&gt;←&lt; b′   i,j [2 h ]&gt;,
 
&lt; a [2 h+ 1]&gt;←&lt; t′   j,k [2 h+ 1]&gt;  [Formula 13]
 
     The first stable-sorting part  51  then generates a secret text (&lt;f′&gt;, &lt;a′&gt;, &lt;p&gt;) by stably sorting (&lt;(0, 1) n &gt;, &lt;a&gt;, &lt;(0, . . . , 2n−1)&gt;) using  &lt;a&gt; as a key, where (0, 1) n  is a vector that is composed of 0s and 1s and has a length of 2n. Specifically, the stable-sorting part  51  performs stable sort written as follows. 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           
                             ( 
                             
                               
                                 〈 
                                 
                                   f 
                                   ′ 
                                 
                                 〉 
                               
                               , 
                               
                                 〈 
                                 
                                   a 
                                   ′ 
                                 
                                 〉 
                               
                               , 
                               
                                 〈 
                                 p 
                                 〉 
                               
                             
                             ) 
                           
                           ← 
                           
                             StableSort 
                             ( 
                             
                               
                                 〈 
                                 
                                   0 
                                   , 
                                   1 
                                 
                                 ) 
                               
                               n 
                             
                             〉 
                           
                         
                         , 
                         
                           〈 
                           a 
                           〉 
                         
                         , 
                         
                           
                             〈 
                             
                               ( 
                               
                                 0 
                                 , 
                                 … 
                                 ⁢ 
                                 
                                     
                                 
                                 , 
                                 
                                   
                                     2 
                                     ⁢ 
                                     n 
                                   
                                   - 
                                   1 
                                 
                               
                               ) 
                             
                             〉 
                           
                           ; 
                           
                             ⫬ 
                             
                               〈 
                               a 
                               〉 
                             
                           
                         
                       
                       ) 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     where 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         ( 
                         
                           0 
                           , 
                           1 
                         
                         ) 
                       
                       n 
                     
                   
                   = 
                   
                     
                       ( 
                       
                         
                           0 
                           , 
                           1 
                           , 
                           0 
                           , 
                           1 
                         
                         , 
                         … 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           0 
                           , 
                           1 
                         
                       
                       ) 
                     
                     
                       ︷ 
                       
                         2 
                         ⁢ 
                         n 
                       
                     
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     14 
                   
                   ] 
                 
               
             
           
         
       
     
     At step S 52 , the first key-reveal-sorting part  52  generates a secret text &lt;m&gt; for h=0, . . . , n−1 in accordance with the following formula.
 
&lt; m [ h ]&gt;
 
←&lt; a [ h ]&gt;×( &lt; f ′[ h ]&gt;×&lt; f ′[ h+ 1]&gt;+&lt; f ′[ h ]&gt;× &lt; f ′[ h− 1]&gt;)  [Formula 15]
 
     The first key-reveal-sorting part  52  then generates a secret text &lt;m′&gt; by key-reveal sorting the secret text &lt;m&gt; using a secret text &lt;p&gt; as a key. Specifically, the first key-reveal-sorting part  52  performs key-reveal sort written as follows.
 
&lt; m ′&gt;←RevealSort(&lt; m&gt;;&lt;p &gt;)  [Formula 16]
 
     At step S 53 , the second stable-sorting part  53  alternately breaks down the elements of the secret text &lt;m′&gt; to generate secret texts &lt;m 0 &gt;, &lt;m 1 &gt;. Specifically, the second stable-sorting part  53  generates secret texts &lt;m 0 &gt;, &lt;m 1 &gt; for h=0, . . . , n−1 in accordance with the following formula.
 
&lt; m   0 [ h ]&gt;←&lt; m ′[2 h ]&gt;,
 
&lt; m   1 [ h ]&gt;←&lt; m ′[2 h+ 1]&gt;  [Formula 17]
 
     The second stable-sorting part  53  then generates a secret text (&lt;t″ 0 &gt;, &lt;p 0 &gt;) by stably sorting (&lt;t′ i,j &gt;, &lt;(0, . . . , n−1)]&gt; using  &lt;t′ i, j &gt; as a key, generates a secret text &lt;m″ 0 &gt; by stably sorting the secret text &lt;m 0 &gt; using  &lt;b′ i,j &gt; as a key, generates a secret text (&lt;b″ 1 &gt;, &lt;p 1 &gt;) by stably sorting (&lt;b′ j,k &gt;, &lt;(0, . . . , n−1)&gt;) using  &lt;b′ j,k &gt; as a key, and generates a secret text &lt;m″ 1 &gt; by stably sorting the secret text &lt;m 1 &gt; using  &lt;t′ j,k &gt; as a key. Specifically, the second stable-sorting part  53  performs the four stable sort operations given below.
 
(&lt; t″   0   &gt;,&lt;p   0 &gt;)←StableSort(&lt; t′   i,j &gt;,&lt;(0, . . . , n− 1)&gt;; &lt; t′   i,j &gt;),
 
&lt; m″   0 &gt;←StableSort(&lt; m   0   &gt;;     b′   i,j &gt;),
 
(&lt; b″   1   &gt;,&lt;p   1 &gt;)←StableSort(&lt; b′   j,k &gt;,&lt;(0, . . . , n− 1)&gt;; &lt; b′   j,k &gt;),
 
&lt; m″   1 &gt;←StableSort(&lt; m   1   &gt;;     &lt;t′   j,k &gt;)  [Formula 18]
 
     At step S 54 , the second key-reveal-sorting part  54  generates secret texts &lt;t″&gt;, &lt;b″&gt; in accordance with the following formula.
 
&lt; t″&gt;←&lt;t″   0   &gt;×&lt;m″   0 &gt;,
 
&lt; b″&gt;←&lt;b″   1   &gt;×&lt;m″   1 &gt;  [Formula 19]
 
     The second key-reveal-sorting part  54  then generates a secret text &lt;t′ j,k &gt; by key-reveal sorting the secret text &lt;t″&gt; using a secret text &lt;p 0 &gt; as a key and generates a secret text &lt;b′ j,k &gt; by key reveal sorting the secret text &lt;b″&gt; using a secret text &lt;p 1 &gt; as a key. Specifically, the second key-reveal-sorting part  54  performs the two key reveal sort operations given below.
 
&lt; t ′&gt;←RevealSort(&lt; t″&gt;;&lt;p   0 &gt;),
 
&lt; b ′&gt;←RevealSort(&lt; b″&gt;;&lt;p   1 &gt;)  [Formula 20]
 
     At step S 50   b , the merging part  50  determines whether all of the secret texts &lt;t′ 0,1 &gt;, . . . , &lt;t′ m-1,m &gt; and the secret texts &lt;b′ 0,1 &gt;, . . . , &lt;b′ m-1,m &gt; have been merged. In other words, the merging part  50  determines whether secret texts (&lt;t′ 0,m &gt;, &lt;b′ 0,m &gt;) have been generated. If the merge has not been completed, the process returns to step S 50   a . If the merge has been completed, the process proceeds to step S 60 . 
     At step S 60 , the determining part  60  computes &lt;t′ 0,m [0]&gt; &lt;t′ 0,m [1]&gt;  . . .  &lt;t′ 0,m [m−1]&gt; by using the secret text &lt;t′ 0,m &gt; and outputs the result as the result of the determination. 
     The idea of the second embodiment described previously may be applied to the merging part  50  of the third embodiment and the merging part  50  may be configured to set i, j and k so as to satisfy the formula given below and select a secret text (&lt;t′ i,j &gt;, &lt;b′ i,j &gt;) and a secret text (&lt;t′ i,k &gt;, &lt;b′ j,k &gt;). 
     
       
         
           
             
               
                 
                   j 
                   = 
                   
                     ⌊ 
                     
                       
                         i 
                         + 
                         k 
                       
                       2 
                     
                     ⌋ 
                   
                 
               
               
                 
                   [ 
                   
                     Formula 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     21 
                   
                   ] 
                 
               
             
           
         
       
     
     Effects of the Invention 
     The nondecreasing sequence determining technique according to the present invention determines whether a nondecreasing sequence exists or not by selecting values one by one from each of m sets in only O(log m) rounds of recursive procedure. Especially when the determination performed using secure computation, the whole processing can be accomplished only O(log m) rounds because each iteration of the recursive procedure can be accomplished in O(1) rounds of computation. 
     Key Points of the Invention 
     In the present invention, when determination is made as to whether a nondecreasing sequence exits by selecting values one by one from each of m sets, a set of nondecreasing sequences is recursively constructed by divide and conquer to determine whether a nondecreasing sequence exists in O(log m) rounds. In the divide and conquer, computations are performed by keeping only sets of good-natured nondecreasing sequences that can be efficiently computed, rather than keeping all nondecreasing sequences, thereby accomplishing merge of sets of nondecreasing sequences by secure computation in O(1) rounds. Consequently, the whole computations can be accomplished by O(log m) rounds of secure computation. 
     It would be understood that the present invention is not limited to the embodiments described above and modifications can be made without departing from the spirit of the present invention. The operations described above may be performed not only in time sequence as is written but also in parallel or individually, depending on the throughput of the devices that perform the processes or requirements. 
     [Program and Recording Media] 
     If the processing functions of the devices described above are implemented by a computer, processing of the function that each device needs to include is described in a program. The program is executed on the computer to implement the processing functions described above on the computer. 
     The program describing the processing can be recorded on a computer-readable recording medium. The computer-readable recording medium may be any medium such as a magnetic recording device, an optical disc, a magneto-optical recording medium, and a semiconductor memory, for example. 
     The program may be distributed, for example, by selling, transferring, or lending portable recording media on which the program is recorded, such as DVDs or CD-ROMs. The program may be stored on a storage device of a server computer and transferred from the server computer to other computers over a network, thereby distributing the program. 
     A computer that executes the program first stores the program recorded on a portable recording medium or the program transferred from a server computer into a storage device of the computer. When the computer executes the processes, the computer reads the program stored in the storage device of the computer and executes the processes according to the read program. In another mode of execution of the program, the computer may read the program directly from a portable recording medium and may execute the processes according to the program or may execute the processes according to the program each time the program is transferred from the server computer to the computer. Alternatively, the processes may be executed using a so-called ASP (Application Service Provider) service in which the program is not transferred from a server computer to the computer but processing functions are implemented only by instructions to execute the program and acquisition of the results of the execution. It should be noted that the program in this mode comprises information that is made available for use in processing by an electronic computer and is equivalent to a program (such as data that is not direct commands to the computer but has the nature of defining processing performed by the computer). 
     While a given program is executed on a computer to configure the present device in this mode, at least part of the processes may be implemented by hardware.