Nondecreasing sequence determining device, method and program

A nondecreasing sequence determining device, comprising:

• a sorting part taking inputs of m sets P0, . . . , Pm−1 and sorting elements of a set Pi in ascending order for i=0, . . . , m−1 to generate a vector ti,i−1 and a vector bi,i+1;
• a concealing part generating an encrypted text <t′i,i+1> in which a vector is concealed and generating an encrypted text <b′i,i+1> in which a vector is concealed, wherein, in the vector t′i,i+1, t′i,i+1[k]=1 is set if λ that satisfies ti,i+1[λ]k exists for k=0, . . . , n−1 and λ=0, . . . , m−1, otherwise, t′i,i+1[k]=0 is set, and in the vector b′i,i+1, b′i,i+1[k]=1 is set if λ that satisfies bi,i+1[λ]=k exists, otherwise b′i,i+1[k]=0 is set, where each of elements of the sets P0, . . . , PM−1 is greater than 0 or equal to 0 and less than n;
• a merging part merging secret texts <t′0,1>, <t′m−1,m> to generate a secret text <t′0,m> and merging secret texts <b′0,1>, to generate a secret text <b′0,m> by repeating a process of merging secret texts (<t′i,j>, <b′i,j>) and (<t′j,k>, <b′j,k>) that satisfy 0≦i<j<k≦m to generate a secret text (<t′i,k>, <b′i,k>);
• and
• a determining part calculating <t′0,m[0]><t′0,m[1]> . . . <t′0,m[m−1]> by using the secret text <t′0,m> and outputting the result of the calculation as the result of determination;
• wherein the merging part comprises:
• a first stable-sorting part alternately arranging elements of secret texts <b′i,j> and <t′j,k> to generate a secret text <a> and stable-sorting a secret text (<(0,1)n>, <a>, <(0, . . . , 2n−1)>) by using <a> as a key to generate a secret text (f<f>, <a′>, <p>);
• a first key-reveal-sorting part calculating <a[h]>×<f′[h]>×<f ′[h+1]>+<f′[h]>×<f′[h−1]>) for h=0, . . . , n−1 to generate a secret text <m> and key-reveal sorting the secret text <m> by using a secret text <p> to generate a secret text <m′>;
• a second stable-sorting part alternately breaking down elements of the secret text <m> to generate secret texts <m0> and <m1>, stably sorting (<t′i,j>, <(0, . . . , n−1)>) by using <t′i,j> as a key to generate a secret text (<t″0>, <p0>), stably sorting the secret text <m0> by using <b′i,j> as a key to generate a secret text <m″0>, stably sorting (<b′i,k>, <(0, . . . , n−1)>) by using <b′i,k> as a key to generate a secret text (<b″1>, <p1>), and stably sorting the secret text <m1> by using <t′j,k> as a key to generate a secret text <m″1>;
• and
• a second key-reveal-sorting part generating a secret text <t″> that is the product of a secret text <t″0> and a secret text <m″0>, and a secret text <b″> that is the product of a secret text <b″1> and a secret text <m″1>, key-reveal sorting the secret text <t″> by using a secret text <p0> as a key to generate a secret text <t′i,k>, and key-reveal sorting the secret text <b″> by using a secret text <p1> as a key to generate a secret text <b′i,k>,
• where (0, 1)n is a vector being composed of 0s and 1s and having a length of 2n and  denotes the negation of .

A nondecreasing sequence determining method comprising:

• a sorting step of taking, by a sorting part, inputs of m sets P0, . . . , Pm−1 and sorting elements of a set Pi in ascending order for i=0, . . . , m−1 to generate a vector ti,i+1 and a vector bi,i−1;
• a merging step of merging, by a merging part, vectors t0,1, . . . , tm-1,m to generate a vector and merging vectors b0,1, . . . ,bm−1,m to generate a vector b0,m by repeating a process of merging vectors (ti,j, bi,j) and vectors (tj,k, bj,k) that satisfy 0≦i<j<k≦m to generate vectors (ti,k, bi,k);
• and
• a determining step of outputting, by a determining part, a result of determination that indicates the absence of a nondecreasing sequence if the length of the vector t0,m is 0 and outputting a result of determination that indicates the presence of a nondecreasing sequence if the length of the vector to,n, is greater than or equal to 1;
• wherein the merging step comprises:
• a stable-sorting step of coupling, by a stable-sorting part, a vector bi,j with a vector tj,k and stably sorting elements of a resulting vector to generate a vector e;
• a searching step of searching, by a searching part, the vector e for every set of (λ, x, y) in which e[λ] is bij[x] and e[λ+1] is tj,k[y] and generating a set X including all of found x and a set Y including all of found y;
• and
• an extracting step of sorting, by an extracting part, elements ti,j[x] (x∈X) of a vector ti,j in ascending order to generate a vector ti,k and sorting elements bj,k[y] (y∈Y) of a vector bj,k in ascending order to generate a vector bi,k.

A nondecreasing sequence determining method comprising:

• a sorting step of taking, by a sorting part, inputs of m sets P0, . . . , Pm−1 and sorting elements of a set Pi in ascending order for i=0, m−1 to generate a vector ti,i+1 and a vector bi,i+1;
• a concealing step of generating, by a concealing part, an encrypted text <t′i,i+1> in which a vector t′i,i+1 is concealed and generating an encrypted text <b′i,i+1> in which a vector b′i,i+1 is concealed, wherein, in the vector t′i,i+1, t′i,i+1[k]=1 is set if λ, that satisfies ti,i,+1[λ]k exists for k=0, . . . , n−1 and λ=0, . . . , m−1, otherwise, t′i,i,+1[k]=0 is set, and in the vector b′i,i+1, b′i,i+1[k]=1 is set if λ that satisfies bi,i,+1[λ]=k exists, otherwise b′i,i+1[k]=0 is set, where each of elements of the sets P0, . . . , PM−1 is greater than 0 or equal to 0 and less than n;
• a merging step of merging, by a merging part, secret texts <t′0,1>, . . . , <t′m−1,m> to generate a secret text <t0,m> and merging secret texts <b′0,1<, . . . , <b′m−1,m>, to generate a secret text <b′0,m> by repeating a process of merging secret texts (<t′i,j>,<b′i,j>) and (<t′j,k>, <b′j,k>) that satisfy 0≦i<j<k≦m to generate a secret text (<t′i,k>, <b′i,k>);
• and
• a determining step of calculating, by a determining part, <t′0,m[0]><t′0,m[1]> . . . <t′0,m[m−1]> by using the secret text <t′0,m> and outputting the result of the calculation as the result of determination;
• wherein the merging step comprises:
• a first stable-sorting step of alternately arranging, by a first stable-sorting part, elements of secret texts <b′i,j> and <t′j,k> to generate a secret text <a> and stably sorting a secret text (<(0,1)n>, <a>, <(0, . . . , 2n−1)>) by using <a> as a key to generate a secret text (<f′>, <a′>, <p>);
• a first key-reveal-sorting step of calculating, by a first key-reveal-sorting part, <a[h]>×(<f′[h]>×<f′[h+1]>+<f′[h]>×<f′[h−1]>) for h=0, . . . , n−1 to generate a secret text <m> and key-reveal sorting the secret text <m> by using a secret text <p> to generate a secret text <m′>;
• a second stable-sorting step of alternately breaking down, by a second stable-sorting part, elements of the secret text <m> to generate secret texts <m0> and <m1>, stably sorting (<t′i,j>, <(0, . . . , n−1)> by using <t′i,j> as a key to generate a secret text (<t″0>, <p0>), stably sorting the secret text <m0> by using <b′i,j> as a key to generate a secret text <m″0>, stably sorting (<b′j,k>, <(0, . . . , n−1)>) by using <b′j,k> as a key to generate a secret text (<b″1>, <p1>), and stably sorting the secret text <m1> by using <t′j,k> as a key to generate a secret text <m″1>, and
• a second key-reveal-sorting step of generating, by a second key-reveal-sorting part, a secret text <t″> that is the product of a secret text <t″0> and a secret text <m″0>, and a secret text <b″> that is the product of a secret text <b″1> and a secret text <m″1>, key-reveal sorting the secret text <t″> by using a secret text <p0> as a key to generate a secret text <t′i,k>, and key-reveal sorting the secret text <b″> by using a secret text <p1> as a key to generate a secret text <b′i,k>,
• where (0, 1)n is a vector being composed of 0s and 1s and having a length of 2n and denotes the negation of .