Method and apparatus for shuffle with proof, method and apparatus for shuffle verification, method and apparatus for generating input message sequence and program for same

Abstract

A shuffle with proof having a method for proof generating with small computational resources proportionate to the number of input encrypted messages and a corresponding method for verification. Shuffle is represented by a generalized transformation. Combining a proof that the transformation information is retained and a proof of a condition under which the transformation is met constitute the proof for shuffle. The two proofs are short proportional to the number of input encrypted messages. Transformation information retention is proved in such a manner that, since the response is generated from challenge value in dependency upon transformation, the condition under which the transformation is met is reflected in the response-challenge value relation. If the condition under which the transformation corresponding to the shuffle is selected as the condition for proof, the two proofs may constitute the proof for shuffle.

Claims

What is claimed is:

1. A method for shuffle with proof in which an input message sequence, which is comprised of encrypted messages and one or more public-keys, and shuffle information are input, and in which an encrypted output message sequence obtained by processing permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text as a proof text for said processing, are output, the method comprising:

(a) a transformation information retention commitment generating step of generating an output encrypted message sequence from an input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating step of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating step of generating a response from said shuffle information and challenge value;

wherein:

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text;

(e) said shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers; and

wherein:

said transformation information retention commitment generating step (a) generates said output encrypted message sequence and the transformation information retention commitment as represented values which represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating step (b) generates coefficients of an identity, as a polynomial of responses and challenge values, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, said transformation condition commitment being coefficients of said identity or said coefficients partly or entirely committed;

said response generating step (c) generating said response from said shuffle information and the challenge values;

said representation associating the represented value with respect to the basis, it being computationally difficult to compute the representation of the given value with respect to the randomly given basis;

said challenge values being plural components decided at random after determining the input message sequence, output encrypted message sequence and the commitments in their entirety, or plural components output by a challenge value generating function receiving inputs of the input message sequence, the output encrypted message sequence and the entire commitments,

said challenge value generating function outputting plural components from a given input and being such a function that it is computationally difficult to find the input from the output or to determine an input taking the relation between output components into account; and

wherein

said identity at said transformation condition commitment generating step connotes the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

2. A method for shuffle with proof in which an input message sequence, which is comprised of encrypted messages and one or more public-keys, and shuffle information are input, and in which an encrypted output message sequence obtained by processing permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text as a proof text for said processing, are output, the method comprising:

(a) a transformation information retention commitment generating step of generating an output encrypted message sequence from an input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating step of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating step of generating a response from said shuffle information and challenge value;

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text; and

(e) said shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers;

wherein

said transformation information retention commitment generating step (a) generates said output encrypted message sequence and the transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating step (b) generates coefficients of an identity, as a polynomial of responses and challenge values, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, said transformation condition commitment being coefficients of said identity or said coefficients partly or entirely committed;

said response generating step (c) generating said response from said shuffle information and the challenge values;

said representation associating the represented value with respect to the basis, it being computationally difficult to compute the representation of the given value with respect to the randomly given basis;

said challenge values being plural components decided at random after determining the input message sequence, output encrypted message sequence and the commitments in their entirety, or plural components output by a challenge value generating function receiving inputs of the input message sequence, the output encrypted message sequence and the entire commitments,

said challenge value generating function outputting plural components from a given input and being such a function that it is computationally difficult to find the input from the output or to determine an input taking the relation between output components into account; and

wherein:

said identity at said transformation condition commitment generating step connotes the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

3. A method for shuffle with proof in which an input message sequence, which is comprised of encrypted messages and one or more public-keys, and shuffle information are input, and in which an encrypted output message sequence obtained by processing permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text as a proof text for said processing, are output, the method comprising:

(a) a transformation information retention commitment generating step of generating an output encrypted message sequence from an input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating step of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating step of generating a response from said shuffle information and challenge value;

wherein

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text; and

wherein

(e) said shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers;

said transformation information retention commitment generating step (a) generates said output encrypted message sequence and the transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of the variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating step (b) including a plurality of first and second transformation condition commitment generating steps either one or both thereof,

said first transformation condition commitment generating step generating coefficients of an identity polynomial of responses and challenge values, stating the condition to be met by the transformation from said input message sequence to said to said output encrypted message sequence from the shuffle information, with the coefficients of said identity or the coefficients partly or entirely committed being regarded as said transformation condition commitment,

said second transformation condition commitment generating step generating coefficients of an identity, as a polynomial of the response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information, and also generating the coefficients of said identity or those coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed as transformation condition commitment;

said response generating step (c) generating said response and a plurality of sub-responses responsive to said transformation condition commitment generating processing;

said shuffle proving text comprehending a plurality of said transformation condition commitments, sub-responses associated with these commitments, said response and said transformation information retention commitment; and

wherein

a plurality of identities at said transformation condition commitment generating step or steps include two, first and second, identities, i.e.:

the first identity connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value; and

the second identity connoting the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value where each component of the response is made up of a polynomial of the challenge value.

4. An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of said encrypted message and re-encryption by said public key and a shuffle proof text are output, said apparatus comprising:

(a) a transformation information retention commitment generating unit for generating the output encrypted message sequences from said input message sequence and for generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment";

(c) a response generating unit for generating a response from said shuffle information and challenge value;

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text;

wherein:

said transformation information retention commitment generating unit includes means for generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating unit generating coefficients of an identity, as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information and outputting the coefficients of said identity, or partly or entirely of said coefficients committed, as said transformation condition commitment;

said response generating unit including means for generating said response from challenge value,

said challenge value being either plural components determined at random after the shuffle information, said input message sequence, the output encrypted message sequence and the commitment are determined in their entirety, or plural components output by a challenge value generating function fed as inputs with said input message sequence, output encrypted message sequence and with the entire commitments; and

wherein:

said identity at said transformation condition commitment generating step connotes the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

5. An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of said encrypted message and re-encryption by said public key and a shuffle proof text are output, said apparatus comprising:

(a) a transformation retention commitment generating unit for generating the output encrypted message sequences from said input message sequence and for generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating unit for generating a response from said shuffle information and challenge value;

wherein

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text;

said transformation information retention commitment generating unit includes means for generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating unit generating coefficients of an identity, as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information and outputting the coefficients of said identity, or partly or entirely of said coefficients committed, as said transformation condition commitment;

said response generating unit including means for generating said response from challenge value,

said challenge value being either plural components determined at random after the shuffle information, said input message sequence, the output encrypted message sequence and the commitment are determined in their entirety, or plural components output by a challenge value generating function fed as inputs with said input message sequence, output encrypted message sequence and with the entire commitments; and

said identity at said transformation condition commitment generating step connotes the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

6. An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of said encrypted message and re-encryption by said public key and a shuffle proof text are output, said apparatus comprising:

(a) a transformation information retention commitment generating unit for generating the output encrypted message sequences from said input message and for generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating unit for generating a response from said shuffle information and challenge value;

wherein

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text;

said transformation information retention commitment generating unit includes means for generating said output encrypted message sequence and the transformation information retention commitment as represented values which is represented by representing-tuple with respect to a basis, where representing index-tuple is comprised of the variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating unit being present in a plurality of numbers including one or both of first and second transformation condition commitment generating units;

said first transformation condition commitment generating unit generating coefficients of an identity, as a polynomial of the response and challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, with the coefficients of said identity or the coefficients partly or entirely committed being regarded as said transformation condition commitment;

said second transformation condition commitment generating unit generating coefficients of an identity, as a polynomial of the response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information, and also generating the coefficients of said identity or these coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed as a transformation condition commitment;

said response generating unit generating said response and a plurality of sub-responses responsive to said response and the plurality of said transformation condition commitment generating units;

said shuffle proving text comprehending a plurality of said transformation condition commitments, sub-responses associated with said commitments, said response and said transformation information retention commitment;

wherein

a plurality of identities at said transformation condition commitment generating unit include two, first and second, identities:

said first identity connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value; and

said second identity connoting that the cubic sum of certain terms of said polynomial and the cubic sum of certain generators of said challenge value are equal to each other irrespective of the challenge value.

7. A storage medium storing a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output message sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text;

said transformation information retention commitment generating processing generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment processing generating coefficients of an identity, as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information and outputting the coefficients of said identity or said coefficients partly or entirely committed, as said transformation condition commitment; and

said response generating processing generating said response from plural components determined at random after the shuffle information, said input message sequence, the output encrypted message sequence and the commitment are determined in their entirety, or from challenge value which is plural components output by a challenge value generating function fed as inputs with said input message sequence, output encrypted message sequence and the entire commitments;

said identity at said transformation condition commitment generating processing connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

8. A storage medium storing a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output messages sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text;

said transformation information retention commitment generating processing generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment processing generating coefficients of an identity, as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information and outputting the coefficients of said identity or said coefficients partly or entirely committed, as said transformation condition commitment; and

said response generating processing generating said response from plural components determined at random after the shuffle information, said input message sequence, the output encrypted message sequence and the commitment are determined in their entirety, or from challenge value which is plural components output by a challenge value generating function fed as inputs with said input message sequence, output encrypted message sequence and the entire commitments;

said identity at said transformation condition commitment generating processing connoting the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

9. A storage medium storing a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output messages sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text;

said transformation information retention commitment generating processing generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating processing being performed in a plurality of numbers including first and second processings, either one or both thereof,

the first transformation condition commitment generating processing generating coefficients of an identity as a polynomial of responses and challenge values, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, with the coefficients of said identity or these coefficients partly or entirely committed being said transformation condition commitment; and

the second transformation condition commitment generating processing generating coefficients of an identity, as a polynomial of the response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information, and also generating the coefficients of said identity or these coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed, as transformation condition commitment;

said response generating processing generating said response and a plurality of sub-responses according to said response and said plurality of transformation condition commitment generating processings; and

outputting a plurality of said transformation condition commitments, sub-response associated with these commitments, said response and said transformation information retention commitment, as said shuffle proving text

a plurality of identities at said transformation condition commitment generating processings including two identities:

i.e., a first that is an identity connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value, and

a second identity connoting the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value where each component of the response is made up of a polynomial of the challenge value.

10. A method for shuffle with proof in which an input message sequence, which is comprised of encrypted messages and one or more public-keys, and shuffle information are input, and in which an encrypted output message sequence obtained by processing permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text as a proof text for said processing, are output, the method comprising:

(a) a transformation information retention commitment generating step of generating an output encrypted message sequence from an input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating step of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating step of generating a response from said shuffle information and challenge value;

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text; and

(e) said shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers;

wherein:

said transformation information retention commitment generating step (a) generates said output encrypted message sequence and the transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating step (b) generates coefficients of an identity, as a polynomial of responses and challenge values, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, said transformation condition commitment being coefficients of said identity or said coefficients partly or entirely committed;

said response generating step (c) generating said response from said shuffle information and the challenge values;

said representation associating the represented value with respect to the basis, it being computationally difficult to compute the representation of the given value with respect to the randomly given basis;

said challenge values being plural components decided at random after determining the input message sequence, output encrypted message sequence and the commitments in their entirety, or plural components output by a challenge value generating function receiving inputs of the input message sequence, the output encrypted message sequence and the entire commitments;

said challenge value generating function outputting plural components from a given input and being such a function that it is computationally difficult to find the input from the output or to determine an input taking the relation between output components into account:

said transformation condition commitment generating step (b) generates coefficients of an identity, as a polynomial of said response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information, and generating, as transformation condition commitments, the coefficients of said identity or those coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed;

said sub-response being not used in the transformation information retention verification processing in the shuffle verification, said sub-response being a polynomial of the response and the challenge value, with the coefficients of said polynomial being sub-equation coefficients;

said response generating step generating two responses, that is response and sub-response, using the shuffle information from said challenge value;

said shuffle proof text comprehending said transformation information retention commitment, transformation condition commitment, said response and the sub-response; and

said identity at said transformation condition commitment generating step connotes the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

11. A method for shuffle with proof in which an input message sequence, which is comprised of encrypted messages and one or more public-keys, and shuffle information are input, and in which an encrypted output message sequence obtained by processing permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text as a proof text for said processing, are output, the method comprising:

(a) a transformation information retention commitment generating step of generating an output encrypted message sequence from an input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating step of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating step of generating a response from said shuffle information and challenge value;

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text; and

(e) said shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers;

wherein:

said transformation information retention commitment generating step (a) generates said output encrypted message sequence and the transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating step (b) generates coefficients of an identity, as a polynomial of responses and challenge values, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, said transformation condition commitment being coefficients of said identity or said coefficients partly or entirely committed;

said response generating step (c) generating said response from said shuffle information and the challenge values;

said representation associating the represented value with respect to the basis, it being computationally difficult to compute the representation of the given value with respect to the randomly given basis;

said challenge values being plural components decided at random after determining the input message sequence, output encrypted message sequence and the commitments in their entirety, or plural components output by a challenge value generating function receiving inputs of the input message sequence, the output encrypted message sequence and the entire commitments;

said challenge value generating function outputting plural components from a given input and being such a function that it is computationally difficult to find the input from the output or to determine an input taking the relation between output components into account:

said transformation condition commitment generating step (b) generates coefficients of an identity, as a polynomial of said response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information, and generating, as transformation condition commitments, the coefficients of said identity or those coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed;

said sub-response being not used in the transformation information retention verification processing in the shuffle verification, said sub-response being a polynomial of the response and the challenge value, with the coefficients of said polynomial being sub-equation coefficients;

said response generating step generating two responses, that is response and sub-response, using the shuffle information from said challenge value;

said shuffle proof text comprehending said transformation information retention commitment, transformation condition commitment, said response and the sub-response; and

said identity at said transformation condition commitment generating step connotes the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

12. A shuffle verifying method in which an input message sequence, an output encrypted message sequence and a shuffle proof text are input, and a result of verification indicating acceptance or non-acceptance is output, the method comprising:

(a) a transformation information retention verifying step of verifying the retention of the transformation information on transformation from an input message sequence to an output encrypted message sequence from the input message sequence, output encrypted message sequence, transformation information retention commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, a response and challenge value; and

(b) a transformation condition verifying step of verifying the condition to be met by transformation from said input message sequence to said output encrypted message sequence, by the transformation condition commitment pertinent to the condition to be met by said transformation, said response and the challenge value; wherein

(c) acceptance is output as the result of the shuffle verification if both the verification of the transformation information retention verifying step and the verification of the transformation condition verifying step are accepted, and non-acceptance is output otherwise;

wherein:

said transformation information retention commitment generating step (a) comprehends a plurality of transformation information retention commitment generating steps each of which generates said output encrypted message sequence and the transformation information retention commitment as represented values represented by variables used for re-encryption, values used for permutation and random numbers, with respect to the basis of said input message sequence,

said transformation information retention commitment generating steps omitting, at second and subsequent steps thereof, generation of outputs of the second and subsequent transformation information retention commitment generating processing operations common to that of the first transformation information retention commitment generating step; and

wherein:

said transformation condition commitment generating step (b) comprehends a plurality of first and second transformation condition commitment generating steps, either one or both thereof;

said first transformation condition commitment generating step generating coefficients of an identity as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, and setting the coefficients of said identity or those coefficients partly or entirely committed as said transformation condition commitment; and

said second transforming condition commitment generating step generating coefficients of an identity as a polynomial of the response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, and generating the coefficients of said identity or those coefficients partly or entirely committed and the sub-equation coefficients or these coefficients partly or entirely committed, as said transformation condition commitment;

said response generating step (c) generating a plurality of responses responsive to said transformation information retention commitment generating steps and generating a plurality of sub-responses responsive to said transformation information retention commitment generating steps;

said shuffle proof text including said responses, a plurality of transformation information retention commitments, a plurality of transformation condition commitments and corresponding sub-responses;

wherein:

a plurality of identities at said transformation condition commitment generating step or steps include two, first and second, identities, i.e.:

the first identity connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value; and

the second identity connoting the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value where each component of the response is made up of a polynomial of the challenge value.

13. An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of said encrypted message and re-encryption by said public key and a shuffle proof text are output, said apparatus comprising:

(a) a transformation information retention commitment generating unit for generating the output encrypted message sequences from said input message sequence and for generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating unit for generating a response from said shuffle information and challenge value;

wherein

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text;

wherein:

said transformation information retention commitment generating unit includes means for generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating unit generating coefficients of an identity, as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information and outputting the coefficients of said identity, or partly or entirely of said coefficients committed, as said transformation condition commitment;

said response generating unit including means for generating said response from challenge value;

said challenge value being either plural components determined at random after the shuffle information, said input message sequence, the output encrypted message sequence and the commitment are determined in their entirety, or plural components output by a challenge value generating function fed as inputs with said input message sequence, output encrypted message sequence and with the entire commitments;

wherein

said transformation condition commitment generating unit includes means for stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence, and for generating coefficients of an identity as a polynomial of said response, said sub-response and the challenge value from said shuffle; and

means for generating the coefficients of said identity or said coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed, as transformation condition commitment;

said sub-response is a polynomial of the response and the challenge value, the coefficients of said polynomial being sub-equation coefficients;

said response generating unit including means for generating two responses, that is response and sub-response, from said challenge value, using the shuffle information;

said shuffle proof text being made up of said transformation information retention commitment, said transformation condition commitment, said response and the sub-response; and

said identity at said transformation condition commitment generating step connotes the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

14. An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of said encrypted message and re-encryption by said public key and a shuffle proof text are output, said apparatus comprising:

(a) a transformation information retention commitment generating unit for generating the output encrypted message sequences from said input message sequence and for generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating unit for generating a response from said shuffle information and challenge value;

wherein

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text; said transformation information retention commitment generating unit includes means for generating said output encrypted message sequence and said transformation information retention commitment as represented values which is represented by representing index-tuple with respect to a basis, where representing index-tuple is comprised of variables used for re-encryption, values corresponding to the permutation and random numbers and basis is the input message sequence;

said transformation condition commitment generating unit generating coefficients of an identity, as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle information and outputting the coefficients of said identity, or partly or entirely of said coefficients committed, as said transformation condition commitment;

said response generating unit including means for generating said response from challenge value,

said challenge value being either plural components determined at random after the shuffle information, said input message sequence, the output encrypted message sequence and the commitment are determined in their entirety, or plural components output by a challenge value generating function fed as inputs with said input message sequence, output encrypted message sequence and with the entire commitments;

wherein

said transformation condition commitment generating unit includes means for stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence, and for generating coefficients of an identity as a polynomial of said response, said sub-response and the challenge value from said shuffle; and

means for generating the coefficients of said identity or said coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed, as transformation condition commitment;

said sub-response is a polynomial of the response and the challenge value, the coefficients of said polynomial being sub-equation coefficients;

said response generating unit including means for generating two responses, that is response and sub-response, from said challenge value, using the shuffle information;

said shuffle proof text being made up of said transformation information retention commitment, said transformation condition commitment, said response and the sub-response; and

said identity at said transformation condition commitment generating step connotes the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

15. An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of said encrypted message and re-encryption by said public key and a shuffle proof text are output, said apparatus comprising:

(a) a transformation information retention commitment generating unit for generating the output encrypted message sequences from said input message sequence and for generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) a response generating unit for generating a response from said shuffle information and challenge value;

wherein

(d) said transformation information retention commitment, said transformation condition commitment and the response are output as said shuffle proof text;

said transformation information retention commitment generating unit is present in a plurality of numbers, each of which generates said output encrypted message sequence and the transformation information retention commitment in terms of represented values represented by variables used for re-encryption, values corresponding to permutation and random numbers, with respect to the basis of said input message sequence;

said transformation information retention commitment generating unit omitting generation of outputs of the second and subsequent transformation information retention commitment generating processing operation common to that of a first transformation information retention commitment generating unit;

said transformation condition commitment generating unit is present in a plurality of numbers comprising first and second transformation condition commitment generating units;

said first transformation condition commitment generating unit generating coefficients of an identity as a polynomial of the response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, and setting the coefficients of said identity or said coefficients partly or entirely committed as said transformation condition commitment;

said second transformation condition commitment generating unit generating coefficients of an identity as a polynomial of the response, sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, and generating the coefficients of said identity or said coefficients partly or entirely committed and the sub-equation coefficients or these coefficients partly or entirely committed, as said transformation condition commitment;

said response generating unit generating a plurality of responses responsive to outputs of said plurality of transformation information retention commitment generating units and generating a plurality of corresponding sub-responses responsive to outputs of said plurality of transformation condition commitment generating units;

said shuffle proof text including said responses, a plurality of transformation information retention commitments, a plurality of transformation condition commitments and corresponding sub-responses; and

wherein

a plurality of identities at said transformation condition commitment generating unit include two, first and second, identities:

said first identity connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value; and

said second identity connoting that the cubic sum of certain terms of said polynomial and the cubic sum of certain generators of said challenge value are equal to each other irrespective of the challenge value.

16. A storage medium storing a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output message sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text;

said transformation condition commitment generating processing generating coefficients of an identity, as a polynomial of said response, said sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle; and

generating the coefficients of said identity or said coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed, as a transformation condition commitment;

said sub-response being a polynomial of the response and the challenge value, with the coefficients of said polynomial being sub-equation coefficients;

said response generating processing generating two responses, i.e., response and sub-response, from said challenge value, using the shuffle information; and

outputting said transformation information retention commitment, said transformation condition commitment, said response and the sub-response as said shuffle proof text; and

said identity at said transformation condition commitment generating processing connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

17. A storage medium storing a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output message sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text;

said transformation condition commitment generating processing generating coefficients of an identity, as a polynomial of said response, said sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from said shuffle; and

generating the coefficients of said identity or said coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed, as a transformation condition commitment;

said sub-response being a polynomial of the response and the challenge value, with the coefficients of said polynomial being sub-equation coefficients;

said response generating processing generating two responses, i.e., response and sub-response, from said challenge value, using the shuffle information; and

outputting said transformation information retention commitment, said transformation condition commitment, said response and the sub-response as said shuffle proof text; and

said identity at said transformation condition commitment generating processing connoting the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

18. A storage medium storing a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output message sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text;

said transformation information retention commitment generating processing comprehending a plurality of transformation information retention commitment generating processings each of which generates represented values represented by said output encrypted message sequence and the transformation information retention commitment with variables used for re-encryption, values used for permutation and random numbers, with respect to the basis of said input message sequence, said transformation information retention commitment generating processing omitting generation of outputs of the second and subsequent transformation information retention commitment generating processings common to that of the first transformation information retention commitment generating processing; and

said transformation condition commitment generating step comprehending a plurality of, first and second, transformation information retention commitment generating processings,

the first transformation condition commitment generating processing generating coefficients of an identity as a polynomial of the response and the challenge value stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, and setting the coefficients of said identity or said coefficients partly or entirely committed as said transformation condition commitment, and

the second transformation condition commitment generating processing generating coefficients of an identity as a polynomial of the response, the sub-response and the challenge value, stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence from the shuffle information, and generating the coefficients of said identity or the coefficients partly or entirely committed and the sub-equation coefficients or these coefficients partly or entirely committed, as said transformation condition commitment;

said response generating processing generating a plurality of responses according to said transformation information retention commitment generating processings and generating a plurality of corresponding sub-responses according to said transformation information commitment generating processings;

said shuffle proof text including said responses, a plurality of transformation information retention commitments, a plurality of transformation condition commitments and corresponding sub-responses;

a plurality of identities at said transformation condition commitment generating processings including two identities:

i.e., a first that is an identity connoting the relation that the square sum of certain terms of said polynomial and the square sum of certain elements of said challenge value are equal to each other irrespective of the challenge value, where each component of the response is made up of a polynomial of the challenge value, and

a second identity connoting the relation that the cubic sum of certain terms of said polynomial and the cubic sum of certain elements of said challenge value are equal to each other irrespective of the challenge value where each component of the response is made up of a polynomial of the challenge value.

Description

FIELD OF THE INVENTION

This invention relates to a technique for shuffle for guaranteeing the presence of one-to-one correspondence between input and output encrypted messages, such as is used in constructing an anonymous communication path, as the one-to-one correspondence is kept confidential, and to a technique of verifying the shuffle.

BACKGROUND OF THE INVENTION

Background Art (1)

As for the background art for shuffle with proof, reference is had to e.g., the JP Patent Kokai JP-A-08-263575 (publication 1). FIG. 1 shows the structure described in this publication 1. Meanwhile, in the drawings of the present application, confluent arrows indicate that the information corresponding to the originating point of the arrows are all collected and sent to a location corresponding to the points of the respective arrows, whilst diverging arrows indicate that all or part of the information at the originating points of the arrows are sent to a location corresponding to the points of the arrows. On the other hand, broken lines indicate that these depend on the input message generating method used.

In FIG. 1, 160 pseudo output encrypted messages 103 represent commitment for zero-knowledge proving. Challenge values are generated from the input/output encrypted messages and the commitment, whilst the response (reply) represents designation of the mapping, responsive to bit values of the challenge values, from the input encrypted message or the output encrypted message, indicated by solid or arrows, to the pseudo output encrypted message.

Referring to FIG. 1, there is introduced a technique of permuting (re-arranging) plural ElGamal input cipher-texts 100 followed by re-encryption and for outputting the re-encrypted cipher-texts. This technique is termed "shuffle". For guaranteeing that this processing is authentic, the above publication introduces the following technique: That is, secret random numbers for permuting and re-encryption are made to be different each time and an operation similar to the shuffle is repeated a number of times equal to the number of safe variables (about 160) to output pseudo output encrypted messages so as to be used as commitment for proving the authenticity. As challenge values 105, Hash values of the commitments and the input/output encrypted messages are output.

The bit sequences of these challenge values are read sequentially from the upper side and designation of permutation (mapping representing the permutation) from the encrypted input message for the bit "0" and that from the encrypted output message for the bit "1" and the re-encryption (the random number used in re-encryption) is made into the response 106.

The aforementioned commitment, challenge values and response are output as a proof text of the shuffling. The method for designating the relation of correspondence responsive to the bit values of the Hash values is termed a Cut and Choose method.

Background Art (2)

As another prior-art technique, reference is had to "A mix-network on permutation networks", termed[Publication 2], publicized by Abe in Paper of Asiacrypt' 99 (LNCS 1716 258-273 Springer 1999), herein termed the Publication 2. In this Publication 2, permutation of a pair of encrypted input message is repeated to realize the permutation of plural encrypted input messages, in their entirety, as shown for example in FIG. 2. In this Publication 2, permutation of a pair of encrypted input message is repeated to realize the permutation of plural encrypted input messages, in their entirety, as shown for example in FIG. 2. By constructing the proving of the permutations of the respective encrypted input messages by a method other than the cut-and-choose method, the shuffling with proof may be improved in efficiency when the number of the encrypted input messages is smaller than a preset number. That is, the sequence of the encrypted input messages is re-arranged (permuted) in its entirety by permutation of individual encrypted input messages. Although the proving of the individual permutations is efficient, it is necessary to provide a large number of permutations.

SUMMARY OF THE DISCLOSURE

The above-described background arts suffer from the following deficiencies:

In the background art (1), shuffling needs to be performed a number of times corresponding to the safety variable (about 160) for commitment generation. Each shuffling is in need of computation which consume large amount of computational resource involving modular exponentiation twice as many as the number of re-encrypted input messages.

On the other hand, verification is in need of computation which consume large amount of computational resource involving modular exponentiation twice as many as the number of re-encrypted input messages.

Moreover, in the background art (2), the commitment of permutation of a pair of encrypted input messages and its proof is in need of a sum total of 16 modular-exponentiation computations.

The computational resources per permutation is small as compared to the computational resources per two encrypted input messages of the background art (1) (=320), permutation of paired encrypted input messages is retained to be performed a number of times which enables permutation of any sort of the entire encrypted input messages, this number being n logn-n+1, where n is the number of encrypted input messages.

So, the computational resources is increased with the increasing number of the encrypted input messages.

It is therefore an object of the present invention to provide a method and a system in which the required computational resources for proving can be diminished without dependency on the number of encrypted input messages, and a program product.

It is another object of the present invention to provide a method and a system for reducing the required computational resources for verification as in the case of proving. Other objects, advantages and features of the present invention will be apparent from the entire disclosure including the following description.

According to a first aspect of the invention, there is provided a method for shuffle with proof in which an input message sequence which is comprised of encrypted messages and one or more public-keys, and shuffle information are input, and in which an encrypted output message sequence obtained by processing permutation of the encrypted messages and re-encryption by the public key or keys, and a shuffle proof text as a proof text for the processing, are output.

The method comprises:

(a) a transformation information retention commitment generating step of generating an output encrypted message sequence from an input message sequence and generating a commitment pertinent to retention of the transformation information from the input message sequence to the output encrypted message sequence, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating step of generating a commitment pertinent to a condition to be met by the transformation, termed as "transformation condition commitment"; and

(c) a response generating step of generating a response from the shuffle information and challenge value;

wherein

(d) the transformation information retention commitment, the transformation condition commitment and the response are output as the shuffle proof text; and

wherein

(e) the shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers.

According to a second aspect of the invention, there is provided a shuffle verifying method in which an input message sequence, an output encrypted message sequence and a shuffle proof text are input, and a result of verification indicating acceptance or non-acceptance is output.

The method comprises:

(a) a transformation information retention verifying step of verifying the retention of the transformation information on transformation from an input message sequence to an output encrypted message sequence from the input message sequence, output encrypted message sequence, transformation information retention commitment pertinent to retention of the transformation information from the input message sequence to the output encrypted message sequence, a response and challenge value; and

(b) a transformation condition verifying step of verifying the condition to be met by transformation from the input message sequence to the output encrypted message sequence, by the transformation condition commitment pertinent to the condition to be met by the transformation, the response and the challenge value; wherein

(c) acceptance is output as the result of the shuffle verification if both the verification of the transformation information retention verifying step and the verification of the transformation condition verifying step are accepted, and non-acceptance is output otherwise.

According to a third aspect of the invention, there is provided an apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information including the manner of permuting the input encrypted messages, variables used for re-encryption and random numbers is input, and an output encrypted message sequence obtained on permutation of the encrypted message and re-encryption by the public key and a shuffle proof text are output.

The apparatus comprises:

(a) a transformation information retention commitment generating unit for generating the output encrypted message sequences from the input message sequence and for generating a commitment pertinent to retention of the transformation information from the input message sequence to the output encrypted message sequences, termed as "transformation information retention commitment";

(b) a transformation condition commitment generating unit for generating a commitment pertinent to a condition to be met by the transformation, termed as "transformation condition commitment"; and

(c) a response generating unit for generating a response from the shuffle information and challenge value;

wherein

(d) the transformation information retention commitment, the transformation condition commitment and the response are output as the shuffle proof text.

According to a fourth aspect, there is provided a shuffle verification apparatus which (a) receives inputs, and in which (b) the result of verification, i.e., acceptance or non-acceptance is output;

the inputs (a) comprising:

(a1) an input message sequence, made up of a plurality of encrypted messages and one or more public keys, input to a device for shuffle with proof, which is fed with the input message sequence and a shuffle information as input, and which outputs an encrypted output message sequence obtained on permutation of the encrypted messages and re-encryption by the public key or keys, and a shuffle proof text,

(a2) the output encrypted message sequence output from the device for shuffle with proof, and

(a3) a shuffle proof text output from the device for shuffle with proof, the shuffle proof text including the transformation information retention commitment pertinent to retention of the transformation information from the input message sequence to the output encrypted message, a transformation condition commitment pertinent to a condition to be met by the transformation, and the response.

The apparatus further comprises:

(c) a transformation information retention verifying unit for testifying retention of the transformation information on transformation from the input message sequence to the output encrypted message sequence based on the input message sequence, output encrypted message sequence, transformation information retention commitment, response and challenge value; and

(d) a transformation condition verifying unit for verifying the condition to be met by transformation from the input message sequence to the output encrypted message sequence based on the transformation condition commitment, the response and the challenge value;

wherein

(e) acceptance is output as the result of the shuffle verification if the verification by the transformation information retention verifying unit and the transformation condition verifying unit are both accepted and non-acceptance is output otherwise.

According to a fifth aspect of the present invention, there is provided an input message sequence generating method. The method generates an input message sequence, input to a device for shuffle with proof, in such a manner that a portion of the generated input message sequence is in the form of numerical values corresponding to the public key and the input encrypted message sequence transformed by the pseudo random numbers. According to the present invention, the input encrypted message sequence; public key and the pseudo random numbers may be combined into one input message sequence.

According to a sixth aspect, there is provided a machine readable program so formulated that a computer, as a shuffle apparatus, in which an input message sequence, which is including a plurality of input encrypted messages and one or more public keys, and the shuffle information, including the manner of permuting the input encrypted message, variables used for re-encryption and random numbers, are input, and in which an encrypted output message sequence obtained on permutation of said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text, are output, is caused to perform the processing comprising:

(a) transformation information retention commitment generating processing of generating said output encrypted message sequences from said input message sequence and generating a commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequences, termed as "transformation information retention commitment";

(b) transformation condition commitment generating processing of generating a commitment pertinent to a condition to be met by said transformation, termed as "transformation condition commitment"; and

(c) response generating processing of generating a response from said shuffle information and challenge value; and

(d) processing of outputting said transformation information retention commitment, transformation condition commitment and said response as said shuffle proof text.

According to a seventh aspect, there is provided a machine readable program so formulated that a computer, as a shuffle verifying apparatus, in which an input message sequence, an output encrypted message sequence output by a device for shuffle verifying with proof, the transformation information retention commitment, output from a device for shuffle with proof, pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, a transformation condition commitment, pertinent to the condition to be met by said transformation, and a shuffle proof text including a response, are input, and a result of verification indicating acceptance or non-acceptance is output, to perform the processing comprising:

(a) transformation information retention verifying processing of verifying the retention of the transformation information from said input message sequence to said output encrypted message sequence from the input message sequence, output encrypted message sequence, transformation information retention commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message sequence, a response and challenge value;

(b) transformation condition verifying processing of verifying the condition to be met by transformation from said input message sequence to said output encrypted message sequence from the transformation condition commitment pertinent to the condition to be met by said transformation, said response and the challenge value; and (c) processing of outputting acceptance as the result of the shuffle verification if both the verification of the transformation information retention verifying processing and the verification of the transformation condition verifying processing are accepted, and of outputting non-acceptance if otherwise.

According to a eighth aspect, there is provided a method for generating a public key sequence with proof comprising:

generating a public key sequence having a pseudo random number sequence uniquely determined from a given input as generators, having a public key, corresponding to the same secret key, as generators, and

generating a proof text proving the correspondence to the same secret key;

wherein the generations of said public key sequence and the proof text are performed in cooperation by provers owning the secret key in a scattered fashion.

According to a ninth aspect, there is provided an apparatus for generating a public key sequence with proof wherein a public key sequence having a pseudo random number sequence uniquely determined from a given input as generators, corresponding to the same secret key and having the public key as the element, and a proof text proving the correspondence to the same secret key are generated in cooperation by provers owning the secret key in a scattered fashion.

According to a tenth aspect, there is provided a machine readable program for allowing a computer to perform the processings of:

generating a public key sequence having a pseudo random number sequence uniquely determined from a given input as generators, said public key sequence corresponding to the same secret key and having a public key as element, and generating a proof text proving the correspondence to the same secret key by cooperation of provers owning the secret key in a scattered fashion.

In the following, the basic concept of the invention will be explained.

According to the present invention, the proof that the shuffle is represented by a sort of more general transformation and the information on this transformation is retained, and the proof for the condition to be met by the transformation are combined together to constitute the proof for shuffle.

These two proofs are each simpler than the proof of the conventional shuffle such that the computational resources is diminished without dependency on the number of the input encrypted messages. This asset is not lost in the proof of the shuffle consisting in the combination of the two proofs.

The proof that the information on transformation is retained is acquired by generating a response from the challenge value, after generation of the output encrypted message sequence and the transformation information retention commitment, depending upon the aforementioned transformation and upon the random numbers used in generating the transformation information retention commitment.

Since the transformation is reflected on the relation between the response and the challenge value, the relation, in terms of equation(s), to be met, based on the condition met by the transformation, by the response and the challenge value exists without dependency on the challenge value. This relation (equation) is committed to prove the condition to be met by the transformation.

If the condition to be met by the transformation representing the shuffle is selected as the condition to be met by the transformation to be proved, the proof of the shuffle can be constituted by the two proofs.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 shows the structure of the prior-art technique 1.

FIG. 2 shows the structure of the prior-art technique 2.

FIG. 3 shows information input/output between the structure of a device for shuffle with proof and a shuffle verifying device in an Embodiment of the present invention.

FIG. 4 shows details of the device for shuffle with proof of Embodiment 1 of the present invention.

FIG. 5 shows details of the shuffle verifying device of Embodiment 1 of the present invention.

FIG. 6 shows details of the device for shuffle with proof of Embodiment 2 of the present invention.

FIG. 7 shows details of the shuffle verifying device of Embodiment 2 of the present invention.

FIG. 8 shows details of the device for shuffle with proof of Embodiment 3 of the present invention.

FIG. 9 shows details of the shuffle verifying device of the Embodiment 3 of the present invention.

FIG. 10 shows details of the device for shuffle with proof of Embodiment 4 of the present invention.

FIG. 11 shows details of the shuffle verifying device of the Embodiment 4 of the present invention.

FIG. 12 shows details of an input message sequence-generating device of Embodiment 5 of the present invention.

FIG. 13 shows details of an input message sequence-generating device of Embodiment 6 of the present invention.

FIG. 14 shows details of a pre-processing device in the Embodiment 6 of the present invention.

FIG. 15 shows details of an input message sequence-generating device of Embodiment 7 of the present invention.

FIG. 16 shows details of an input message sequence-generating device of the Embodiment 7 of the present invention.

FIG. 17 shows details of the device for shuffle with proof of the Embodiment 7 of the present invention.

FIG. 18 shows details of the shuffle verifying device of the Embodiment 7 of the present invention.

FIG. 19 shows details of a device for shuffle with proof in the Embodiments 6 and 7 of the present invention.

FIG. 20 shows details of a device for shuffle in the Embodiments 6 and 7 of the present invention.

PREFERRED EMBODIMENTS OF THE INVENTION

For clarifying the above and other objects, features and advantages of the present invention, preferred embodiments of the present invention are now explained in detail with reference to the drawings.

First, the matter, which forms the premises underlying the present invention, is explained. The encryption method used in the present invention is a method belonging to the public key crypt-system which also belongs to a probabilistic crypto-system, such as ElGamal crypto-system.

In the method for shuffle with proof, according to the present invention, a prover performing the shuffle with proof cannot falsify or disguise the proof message for shuffling unless all of the formulators of the encrypted input messages divulge the secret variables used for creating the encrypted input messages to the prover. By using the input message sequence generating method according to the present invention, in combination, it is similarly possible to prevent falsification or disguise of the proof message even if the formulators of the encrypted input messages would act in collusion with the prover.

The method for shuffle with proof, according to the present invention, is comprised of a transformation information retention (holding) commitment generating processing, for generating the transformation information retention commitment, a transformation condition commitment processing for generating the transformation condition commitment, and a response generating processing for generating the response and sub-response. The proof text (verifying text) is made up of the commitment generated by the above three sort of processings and the response (response and sub-response).

The method for shuffle and verification according to the present invention is comprised of a transformation information retention verification processing for verifying the retention of the transformation information from the input message sequence, encrypted output message sequence, transformation information retention commitment and the response, and a transformation condition verification processing for verifying the condition satisfied by the transformation from the transformation condition commitment, response and the sub-response.

[Transformation Information Retention Commitment Generating Processing]

The transformation information retention commitment generating processing, forming the method for shuffle with proving is now explained.

The transformation information retention commitment generating processing performs transformation corresponding to shuffle from the input message sequence to generate an encrypted output message sequence, while performing general transformation using random numbers to generate a transformation information retention commitment.

If any other component than the encrypted input message sequence and the public key is contained in the input message sequence, this component transformed in association with the shuffle is also regarded as the transformation information retention commitment.

If plural responses are to be generated, general transformation by different random numbers is executed a number of times to generate a number of sets of the transformation information retention commitments.

In this transformation, the output encrypted message sequence and the transformation information retention commitment can be generated as a representation of the variables and random numbers used for re-encryption and values associated with the permutation with respect to a basis comprised of the input message sequence.

This representation associates the basis with a represented value, and the method needs to be such as to render the computation of the representation from the basis and the value of representation difficult with respect to the computational resources. For this representation method, modular exponentiation may be used.

For example, let the encrypted input message sequence g[i, ┌]; i=1, . . . , n; ┌=0, . . . , l,

the public key being g[i, ┌]; i=n+1, . . . , n+m; ┌=0, . . . , l,

other components of the input message sequence being g[i, ┌]; i=1, . . . , n+m; ┌=l+1, . . . , l′,

random numbers associated with general transformation, referred to below as the information hiding factor, being A[μ, j]; μ=1, . . . , n+m, j=n+1, . . . , n+m′,

the variable for re-encryption being A[i, j]; i=n+1, . . . , n+m, j=1, . . . , n,

the variable for transformation corresponding to permutation being A[i, j]; i, j=1, . . . , n, and

output encrypted message sequence being g"[i, ┌]; i=1, . . . , n; ┌=1, . . . , l,

it is possible to generate an output encrypted message sequence g"[i, ┌]; i=1, . . . , n; ┌=1, . . . , l as

g"[i, ┌]=
##CHR1##
_j=n+1^n+mg[j, ┌]^{A[j, i]}/F*_p i=1, . . . , n ┌=1, . . . , l,

the transformation information retention commitment as g"[i, ┌]=
##CHR2##
_j=n+1^n+mg[j, ┌]^{A[j, i]}/F*_p i=n+1, . . . , n+m′ ┌=1, . . . , l, and

the transformation information retention commitment, in case g[i, ┌]; i=1, . . . , n+m; ┌=l+1, . . . , l′ is included in the input message sequence, as g"[i, ┌]=
##CHR3##
_j=n+1^n+mg[j, ┌]^{A[j, i]}/F*_p i=1, . . . , n+m′ ┌=l+1, . . . , l′.

The above can collectively be represented by g"[i, ┌]=
##CHR4##
_j=1^n+mg[j, ┌]^{A[j, i]}/F*_p i=1, . . . , n+m′ ┌=1, . . . , l′.

Here, g"[i, ┌]; i=1, . . . , n+m; ┌=1, . . . , l is termed as "output message sequence", where g"[μ, ┌]; μ=1, . . . , n+m′; ┌=1, . . . , l′ is the represented value, A[μ, ν]; μ=1, . . . , n+m; ν=1, . . . , n+m′ is the representation and g[μ, ┌]; μ=1, . . . , n+m; ┌=1, . . . , l′ is the basis.

If plural sets of the transformation information retention commitments are to be generated depending on the number of the responses, plural different A[μ, j]; μ=1, . . . , n+m, j=n+1, . . . , n+m′ are provided and generated.

The fact that a prover is able to generate the transformation information retention commitment, input message sequence, and response corresponding to the output encrypted message sequence and challenge value, in such a manner as to satisfy the verification formulas, presents a proof that the knowledge of transformation from the input message sequence to the output encrypted message sequences is possessed.

[Transformation Condition Commitment Generating Processing]

The processing for generating the transformation condition commitments forming the shuffle method with proving is now explained.

The condition met by the transformation from the input message sequence to the output message sequence and the transformation information retention commitment is reflected on the relation between the response and the challenge value. So, there exists the relation (correlative equation) between the response and the challenge value, which holds without dependency on the challenge value. The transformation condition commitment is the commitment of this relation, which serves for representing the condition met by the transformation.

If plural responses are to be generated, the difference in the knowledge-hiding factor is reflected in the relation. For example, it is possible that this relation is determined as an identity as a polynomial of the responses and challenge values and the coefficients are committed. Alternatively, certain terms of the polynomial may be regarded as sub-responses, and coefficients of the sub-response may be committed to serve as transformation condition commitments. It is sufficient if a response and a sub-response are generated after determination of the challenge values.

The respective components of the response are polynomials of challenge values. The embodiments employ identities intending the relation that the square sums of certain terms of certain polynomials and square sums of certain components of the challenge values become equal to each other without dependency on (i.e., irrespective of) the challenge values, or identities intending the relation that the cubic sums of certain terms of certain polynomials and cubic sums of certain components of the challenge values become equal to each other without dependency on the challenge values.

The corresponding identities used in the embodiments are those which intend the relation

Σ_i=1ⁿ(Σ_j=1ⁿA[i, j]c[j])²=Σ_i=1ⁿc[i]²/F_q

or the relation

Σ_i=1ⁿ(Σ_j=1ⁿA[i, j]c[j])³=Σ_i=1ⁿc[i]³/F_q

using the challenge values c[i] and the response r[i].

Meanwhile,

Σ_j=1ⁿA[i, j]c[j]/F_qi=1, . . . , n

is a portion of a polynomial

Σ_j=1^n+m′A[i, j]c[j]/F_qi=1, . . . , n

of the challenge value forming r[i].

For example, these relations reflect the properties that A[i, j ]; i, j=0, . . . , n in the variables A[μ, ν]; μ=0, . . . , n+m; ν=0, . . . , n+m′ defining the transformation from the input message sequence to the output encrypted message sequences and to the transformation information retention commitment is an orthonormal matrix or a quasi-permutation matrix.

The "permutation matrix" is such a square matrix in each column and in each row of which only one nonzero element exists which is of a value of 1. A matrix, which is simultaneously an orthonormal matrix and a sub-permuted matrix, is a permutation matrix.

The "quasi-permutation matrix" is the above-mentioned permutation matrix, whose element equal to "1" is replaced by one of cubic roots of 1. It is also possible to replace the respective components by different cubic roots of 1. In such case, the transformation corresponding to the permutation matrix corresponds to the shuffle. That is, the transformation can be proved to be the shuffle by proving the condition met by the transformation by the transformation condition commitment generating processing.

Examples of the identities intending the above relation include

Σ_i=1ⁿr[i]r[i]+Σ_μ=1^n+mρ′[μ]r[μ]/F_q=Σ_i=1ⁿc[i]c[i]+Σ_μ=1^n+m′&#x 3c6;[μ]c[μ]/F_q

and

Σ_i=1ⁿr[i]r[i]r[i]+ρ"r′+Σ_μ=1^n+mρ′[μ]r[μ]/F_q=Σ_i=1ⁿr[i]r[i]r[i]+ρ"(λ[0]+Σi=1ⁿλ[i]r[i]r[i])+Σ_μ=1^n+mρ′[μ]r[μ]/F_q=Σ_i=1ⁿc[i]c[i]c[i]+Σ_i=1ⁿψ[i]c[i]c[i ]+Σ_μ=1^n+m′φ[μ]c[μ]/F_q.


Here, the coefficients of the identity ρ", ρ′[i], φ[μ], ψ[i] need to be determined so that the relation corresponding to the conditions to be met by the transformation.

There are also occasions wherein sub-equation coefficients λ[μ]; μ=0, . . . , n are committed, with a portion of the identity

r′=λ[0]+Σ_i=1ⁿλ[i]r[i]r[i]/F_q

as a sub-response.

As transformation condition commitments, coefficients of identities or those coefficients partly or entirely committed, and sub-equation coefficients or these coefficients partly or entirely committed, are generated, are generated. In an embodiment, a portion of an identity is committed to

v, v^φ[0]/F*_p

for example, and the sub-equation coefficients are committed to

u, u^λ[μ]/F*_p μ=0, . . . , n


Committing the coefficients of the identity and using the sub-response are effective for diminishing the information for a verifier to identify the shuffle from the response and the commitment.

[Response Generating Processing]

The response generating processing of constructing the shuffle method with proving is hereinafter explained.

In the response generating processing, the transformation information retention commitment, transformation condition commitment, an input message sequence and an output encrypted message sequences are input to a challenge value generating function (unit) to acquire a challenge value.

It is noted that the "challenge value generating function" is such a function in which it is computationally difficult to find input from an output or to determine input with the relation among different output components in mind. This assures that a challenge value has been generated after determination of the input, commitment and the output, without taking the intention of the prover into account.

If the challenge value generating function is not used, the challenge value is acquired by arbitrary selection by a verifier after the input, output and the commitment have been shown.

From the challenge value, the response or the sub-response, reflecting the shuffle method and the information-hiding factor is generated.

If plural responses and sub-responses are generated, the respective responses need to reflect different information hiding factors.

For example, it suffices to generate an response such that the value having represented by the challenge value with respect to the basis comprising of the output encrypted message sequences and the transformation information retention commitment will be equal to the value having represented by the response value with respect to the basis comprising of the input message sequence.

For example, the response r[μ]; μ=1, n+m is generated such as

r[μ]=Σ_ν=1^n+m′A[μ, ν]c[ν]/F_qμ=1, . . . , n+m

with sub-response,

r′=λ[0]+Σ_i=1ⁿλ[i]r[i]r[i]/F_q,

using the challenge value c[μ]; μ=1, . . . , n+m′.
[Transformation Information Retention Verification Processing]

The transformation information retention verification processing, forming the shuffle verification method, is hereinafter explained.

It is verified that the relation among the input message sequence, output encrypted message sequences and the transformation information retention commitment is reflected by the relation between the response and the challenge value. For example, it is confirmed that there exists the relationship between the response and the challenge value such that a represented value represented by the challenge value with respect to the basis of the output encrypted message sequences and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of an input message sequence.

For example, it is confirmed that the challenge value c[i]; i=1, . . . , n+m′ and the response r[i]; i=1, . . . , n+m satisfy the relation:


##CHR5##
_i=1^n+mg[i, ┌]^r[i]/F*_p┌=1, . . . , l′.


The same value of the challenge value as that used in formulating a proof message is used. This is possible because, in using a challenge value generating function, an input to the challenge value generating function exists in the proof message, input message sequence and the output encrypted message sequence.

[Transformation Condition Verification Processing]

The transformation condition verification processing, forming the shuffle verification method, is now explained.

From the transformation condition commitment, it is verified that the challenge value and the response meet the relation reflecting the condition met by the transformation.

For example, the response and the challenge value or the response, challenge value and the sub-response is substituted into an identity connoting the condition to be met by the transformation to confirm that the identity holds. In case where there is a sub-response, the authenticity of the sub-response is also confirmed based on the committed response, sub-response and sub-equation coefficients.

For coefficients, e.g., ρ", ρ′[μ], φ[μ], ψ[i], as the transformation condition commitment, the challenge value c[i]; i=1, . . . , n+m′ and the response r[i]; i=1, . . . , n+m are confirmed from the fact that the identity

Σ_i=1ⁿr[i]r[i]+Σ_μ=1^n+mρ′[μ]r[μ]=Σ_i=1ⁿc[i]c[i]+Σ_μ=1^n+m′φ[μ]c [μ]/F_q

or the identity

Σ_i=1ⁿr[i]r[i]r[i]+ρ"r′+Σ_μ=1^n+mρ′[μ]r[μ]/F_q=Σ_i=1ⁿr[i]r[i]r[i]+ρ"(λ[0]+Σi=1ⁿλ[i]r[i]r[i])+Σ_μ=1^n+mρ′[μ]r[μ]/F_q=Σ_i=1ⁿc[i]c[i]c[i]+Σ_i=1ⁿψ[i]c[i]c[i ]+Σ_μ=1^n+m′φ[μ]c[μ]/F_q

hold, while the authenticity of the sub-response is confirmed from the fact that the equation of verification

u^r′=u[0]
##CHR6##
_i=1ⁿu[i]^r[l]r[l]/F*_p

holds.

If the coefficients of the identity are partially committed, it is confirmed that, instead,

v^{Σ_i=1ⁿr[i]r[i]+Σ_μ=1^n+mρ′[μ]r[μ]}/F*_p=v^{Σ_i=1ⁿc[i]c[i]+Σ_μ=1^{n+m 32;}φ[μ]c[μ]}/F*_p

or

v^{Σ_i=1ⁿr[i]r[i]r[i]+ρ"r′+Σ_μ=1^n+mρ′[μ]r[μ]}/F*_p=v^{Σ_i=1ⁿr[i]r[i]r[i]+ρ"(λ[0]+Σ_i=1ⁿλ[i]r[i]r[i])+Σ_μ=1^n+mρ′[μ]r[μ]}/F*_p=v^{Σ_i=1ⁿc[i]c[i]c[i]+Σ<sub>i=1ⁿψ[i]c[i]c[i]+Σμ=1^n+m′φ[μ]c[μ]}/F*p

holds. In the above equations, [^] denotes exponential processing.
[Input Message Sequence Generating Method]

In the shuffle method with proving, according to the present invention, the transformation from the input message sequence to the output encrypted message sequences and the transformation information retention commitment needs to be reflected in the relation between the response and the challenge value. To this end, the response that can be generated given a challenge value needs to be limited. However, if the prover knows the generating information of the input encrypted message, there is a risk that this limitation be violated. The method to obstruct this risk is the input message sequence (string) generating method.

The input message sequence generating method according to the present invention generates pseudo random numbers to transform the input message sequence, or the pseudo random number is added to the input message sequence to generate an input message sequence which cannot be determined even by the formulator of the input encrypted message.

[Input Message Sequence Generating Method (1)]

Pseudo random numbers are generated and added to the encrypted input message sequence and to the public key to serve as an encrypted input message sequence. The pseudo random numbers are determined from a preset input to assure reproducibility.

For example, if the encrypted input message sequence is g[i, ┌]; i=1, . . . , n; ┌=0, . . . , l and the public key is g[i, ┌]; i=n+1, . . . , n+m; ┌=0, . . . , l, pseudo random numbers of (n+m) ×(l′-l), where l′-l≧1, are generated from the preset input such that

g[i, ┌]; i=1, . . . , n+m; ┌=l+1, . . . , l′

whilst the input message sequence is set to

g[i, ┌]i=1, . . . , n+m; ┌=1, . . . , l′.

[Input Message Sequence Generating Method (2)]

The respective encrypted messages, forming an encrypted input message sequence, and the public key, are re-encrypted by respective public keys forming a public key sequence generated from the input message sequence and the public key as inputs, and are combined together to form an input message sequence.

The "public key sequence" are prepared by uniquely generating a number of pseudo random numbers from an input which is the same as the number of the public keys forming the public key sequence so that the any of the random numbers represents certain element of the respective public keys.

For example, if the public key sequence is g′[i, ┌]; i=1, . . . , n+m; ┌=1, . . . , l, the input encrypted message sequence is η[i, ┌]; i=1, . . . , n; ┌=0, . . . , l, and the public key is η[i, ┌]; i=n+1, . . . , n+m; ┌=0, . . . , l, an input message sequence g[i, ┌]; i=1, . . . , n+m; ┌=l+1, . . . , l is represented by g[i, ┌]=η[i, ┌]g′[i, ┌]^s[l]/F*p using an optional positive integer s[i]; i=1, . . . , n+m which is apparent for a verifier. As s[i], e.g., s[n+m]=0, s[j]=1; j=1, . . . , n+m-1 is selected.

[Input Message Sequence Generating Method (3)]

Each input plain message (text) is encrypted using each associated public key forming a public key sequence, and proof is made of the fact that this public key has been used for encryption.

The encrypted message, which has received this proof, and the public key, are combined to an input message sequence.

If, for example, the public key sequence is g′[i, ┌]; i=1, . . . , n+m; ┌=0, 1, and the plain text is m[i]; i=1, . . . , n; ┌=0, 1, the input encrypted message

η[i, 0]=g′[i, 0]^s[i]/F*pi=1, . . . , n


η[i, 1]=m[i]g′[i, 1]^s[l]/F*pi=1, . . . n

is generated, at the same time as the knowledge of s[i] such that

η[i, 0]=g′[i, 0]^s[l]/F*p

is proved to give a proof message encrypted using g′[i, 0].

From the encrypted message for which the proof error message is verified, the input message sequence is made into

g[i, ┌]=η[i, ┌]i=1, . . . , n; ┌=0, 1


g[i, ┌]=g′[i, ┌]i=n+1, . . . , n+m; ┌=0, 1.

[Method for Generating Public Key Sequence with Proof]

From a given input, a pseudo random number sequence is uniquely generated, and plural public keys which includes values created by a given procedure from respective random numbers as components and which have the same secret key are generated in a plurality of numbers in association with the respective random numbers. Simultaneously, a proof message that all the public keys have the same secret key is produced.

If the secret key is owned discretely by plural persons, each person prepares the public key sequence with each secret key and combines them together to generate a public key sequence.

For example, a pseudo random number generator Hash (*) is accorded and an output is prepared from an input *. An output is fed to input. This process is repeated to generate a pseudo random number recursively. A number of public keys g′[i, ┌]; i=1, . . . , n+m; ┌=0, . . , l, having, as generators, each value of a number sequence g′[i, 0]; i=1, . . . , n+m made up of n+m generators obtained on removing 0 and 1 from a number sequence resulting from raising respective generators of the number sequence to the k'th power, and having the same secret key, are generated in association with the respective random numbers.

If the secret key is x[┌]; ┌=1, . . . , l, the public key sequence may be represented by

g′[i, 0]=g′[i, 0]


g′[i, ┌]=g′[i, 0]^x[┌]/F*pi=1, . . . , n+m; ┌=1, . . . , l.


A proof message that the above public key sequence has correctly been generated is generated.

If the secret key is owned in scattered state, each person creates a public key sequence corresponding to the discrete secret key, and the respective public key sequences are finally combined together to create a public key sequence associated with the secret key.

DETAILED DESCRIPTION OF THE EMBODIMENTS

Referring to the drawings, the present invention is explained with reference to Examples employing the ElGamal cipher-texts. In the drawings, abbreviations are used. For example, "retention commit" is the transformation information retention commitment, "condition commit" is the transformation condition commitment, "identity commit" is the commitment of the identity coefficients, "sub-response commit" is the commitment of the coefficients of the sub-response, "retention processing" is the processing for generating the transformation information retention commitment, "condition processing" is the processing for generating the transformation condition commitment, "response processing" is the processing for generating the response, "retention verification processing" is the transformation information retention verification processing, and "condition verification processing" is the transformation condition verification processing.

FIG. 3 shows input/output in the embodiment of the present invention for the shuffle device and a shuffle verification device.

In a preferred embodiment of the present invention, shown in FIG. 3, an input message sequence 300, made up of plural input message sequences 322 and the public key 323, a shuffle matrix 304, made up of a shuffle matrix 307, determining the permuting method, a re-encryption secret random number 305, as a variable for re-encryption, and an information hiding factor 306 as random numbers for generating the transformation information retention commitment, and a shuffle information 303, comprehending element (generator) coefficients 308 as seeds of coefficients of the identity, quasi-equation coefficients 309 as coefficients of the equation determining sub-response 319 as part of the identity and various constants for generating the transformation condition commitment made up of coefficients basis 310 for committing the coefficients, are input to a shuffle device with proof 312, and an output encrypted message sequence 313 and a shuffle proof message 314 are issued as output.

The shuffle proof message 314 comprehends a transformation condition commitment 316, including coefficients of the identity, committed coefficients of the identity and committed coefficients of the sub-response, a transformation information retention commitment 315, a response 317 and a sub-response 318.

The input message sequence 300, output encrypted message sequence 313 and the shuffle proof message 314 are input to a shuffle verification device 319, which then outputs the result of verification 322 in the form of acceptance or non-acceptance.

The shuffle device with proof is unable to falsify the shuffle proof message if and only if the prover is unaware of the input encrypted message generating information. The method added for inhibiting this falsification under any condition is the input message sequence generating method. Three sorts of the input message sequence generating methods are hereinafter explained along with the method for generating the public key sequence with proof used in two of these three input message sequence-generating methods.

In the following, the matter to be premised as a presupposition in common for the shuffle method with proof, an input message sequence generating method and an individual public key sequence generating method with proof, is explained in order.

First, the ElGamal domain parameters are explained.

These variables are two prime numbers (generators) p, q satisfying the relation

p=kq+1

where k is an integer.
[Challenge Value Generating Function and Basis Generating Function]

The challenge value generating function and basis generating function are explained. These are

Hash[μ; μ=0, . . . , n](*), Hash′[μ; μ=0, . . . , n](*).


The Greek letter μ, as suffix of each function, is a value from 0 to μ. If an argument[*] is input, (n+1) element vector is output.

An output of the challenge value generating function is (n+1) integers other than 1 and 0 not larger than q, whilst an output of the basis generating function is (n+1) integers other than 1 and 0 not larger than p, and is an integer which is the generator (element) of F*p of orders q (generator of the sub-group whose order being q of the multiplication group of orders p-1).

These functions are those for which the argument cannot be determined by number-theoretically intending the relation between input and output and between different components of the output.

As an illustrative method for constructing the basis generating function, one Hash function Hash (*) outputting |p| bits is provided to compute

Hash (*)

with the computed result being input to the argument of the Hash function to derive the computed results. This operation is repeated to recursively generate the number sequence h[0], h[1], h[2], . . . to find number sequence h[0]^k, h[1]^k, h[2]^k, . . . by raising each numerical value to the k'th power. Among these, (n+1) generators other than 1, 0 are sequentially selected.

As for the challenge value generating function, a number sequence is found using the Hash function outputting |q| bits and, among the generators of this sequence, those which are other than 1, 0 are selected. I</sub>