# US 2001/0024501 A1 · 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

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2001/0024501 A1
- Document ID: US20010024501A1
- Status: Published application
- Kind: A1
- Application number: 09/796,458
- Filed: 2001-03-02
- Published: 2001-09-27
- Earliest claimed: 2000-03-03
- Assignees: NEC Corporation
- Inventors: Jun Furukawa
- Web page: https://patentgrep.com/patent/US20010024501A1

## CPC

- H04L 9/3013: {involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 9/3218: {using proof of knowledge, e.g. Fiat-Shamir, GQ, Schnorr, ornon-interactive zero-knowledge proofs}
- H04L 9/3271: {using challenge-response}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

A shuffle with proof having a method for proof generating with a 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, the response-challenge value relation not dependent on the challenge value exists. The above relation retention true proves the condition under which the transformation is met. 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

### Claim 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; and wherein
(e) said shuffle information includes the manner of permuting the input encrypted message, variables used for permuting and random numbers.

### Claim 2

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.

### Claim 3 (depends on 1)

The method for shuffle with proof as defined in claim 1 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.

### Claim 4 (depends on 2)

The shuffle verifying method as defined in claim 2 wherein
said transformation information retention verifying step (a) verifies that a represented value represented by a challenge value with respect to the basis of said output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by a response with respect to the basis of said input message sequence; and wherein
said transformation condition verifying step (b) verifies, by said transformation condition commitment, that with regard to the input response and the challenge value, an identity holds 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.

### Claim 5 (depends on 3)

The method for shuffle with proof as defined in claim 3 wherein
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.

### Claim 6 (depends on 4)

The shuffle verifying method as defined in claim 4 wherein
said transformation condition verifying step (b) verifying by said transformation condition commitment that with regard to the input response, sub-response and the challenge value, an identity holds 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, and verifying the authenticity of said sub-response based on the sub-equation coefficients committed, the response and the challenge value.

### Claim 7 (depends on 1)

The method for shuffle with proof as defined in claim 1 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-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 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 the coefficients partly or entirely committed being regarded as said transformation condition commitment, and
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 response and 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.

### Claim 8 (depends on 2)

The shuffle verifying method as defined in claim 2 wherein
said transformation information retention verifying step (a) verifying that a represented value represented by challenge value with respect to the basis of said output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basisof input message sequence; and wherein
said transformation condition verifying step (b) comprehends a plurality of first and second transformation condition verifying steps either one or both thereof,
said first transformation condition verifying step verifying by said transformation condition commitment that with regard to the input response and the challenge value, an identity holds 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, and
said second verifying step verifying by said transformation condition commitment that with regard to the input response, sub-response and the challenge value, an identity holds as a polynomial of the response, sub-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, and also verifying the authenticity of said sub-response based on the sub-equation coefficients committed, response and the challenge value.

### Claim 9 (depends on 2)

The method for shuffle with proof as defined in claim 2 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.

### Claim 10 (depends on 2)

The shuffle verifying method as defined in claim 2 wherein
said transformation information retention verifying step (a) is made up of a plurality of transformation information retention verifying steps each of which verifies that a represented value represented by challenge value with respect to the basis of the output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence; and wherein
said transformation condition verifying step (b) includes a plurality of first and second transformation condition verifying steps, either one or both thereof,
said first verifying step verifying by said transformation condition commitment that with regard to an input response and the challenge value, an identity holds 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, and
said second verifying step verifying by said transformation condition commitment that with regard to the input response, sub-response and the challenge value an identity holds 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, and verifying the authenticity of said sub-response from the sub-equation coefficients committed, the response and the challenge value.

### Claim 11 (depends on 3, 5)

The method for shuffle with proof as defined in claim 3 or 5 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.

### Claim 12 (depends on 3, 5)

The method for shuffle with proof as defined in claim 3 or 5 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.

### Claim 13 (depends on 7, 9)

The method for shuffle with proof as defined in claim 7 or 9, 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.

### Claim 14

An input message sequence generating method comprising:
generating a portion of an input message sequence to be input to a device for shuffle with proof, as value that is pseudo random numbers or as values obtained by transforming a public key and an input encrypted message sequence by pseudo random numbers, and
inputting said input message sequence to the device for shuffle with proof.

### Claim 15 (depends on 14)

The input message sequence generating method as defined in claim 14 wherein the input message sequence, the public key and the pseudo random numbers are combined together into an input message sequence.

### Claim 16 (depends on 14)

The input message sequence generating method as defined in claim 14 in which the input encrypted message sequence is transformed by a public key sequence and output a proof text proving the authenticity of the public key sequence, wherein
said public key sequence is a plurality of public keys corresponding to a same secret key, generated by cooperation of provers owning the secret key in a scattered state, with a set of specified element of each of said public keys being pseudo random numbers generated by an input including an input message sequence.

### Claim 17 (depends on 14)

The input message sequence generating method as defined in claim 14 wherein
the set of specified generators of each of said plural public keys corresponding to the same secret key generated by cooperation of provers owning the secret key in a scattered state generates a public key sequence as pseudo random numbers generated by inputting the input message sequence, encrypts each input plain text with each public key constituting the sequence, proves that encryption is by the respective public keys and generates the input message sequence by combining the input encrypted message sequence and the public key.

### Claim 18

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.

### Claim 19

An apparatus for shuffle with proof in which input message sequence, which is including a plurality of input encrypted messages and one or more publ ic 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.

### Claim 20

A shuffle verification apparatus which (a) receives inputs, and in which (b) the result of verification, i.e., acceptance or non-acceptance is output;
said 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 said encrypted messages and re-encryption by said public key or keys, and a shuffle proof text,
(a2) said output encrypted message sequence output from said device for shuffle with proof, and
(a3) a shuffle proof text output from said device for shuffle with proof, said shuffle proof text including the transformation information retention commitment pertinent to retention of the transformation information from said input message sequence to said output encrypted message, a transformation condition commitment pertinent to a condition to be met by said transformation, and the response,
said apparatus comprising:
(c) a transformation information retention verifying unit for testifying retention of the transformation information on transformation from said input message sequence to said output encrypted message sequence based on said 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 said input message sequence to said output encrypted message sequence based on said transformation condition commitment, said response and the challenge value; wherein
(e) acceptance is output as the result of the shuffle verification if the verification by said transformation information retention verifying unit and the transformation condition verifying unit are both accepted and non-acceptance is output otherwise.

### Claim 21 (depends on 19)

The apparatus for shuffle with proof as defined in claim 19 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 bemet 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.

### Claim 22 (depends on 20)

The shuffle verification apparatus as defined in claim 20 wherein
said transformation information retention verifying unit includes means for verifying that a represented value represented by a challenge value with respect to the basis of the output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence;
said transformation condition verifying unit includes means for verifying by said transformation condition commitment that with respect to an input response and the challenge value, an identity holds 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.

### Claim 23 (depends on 21)

The apparatus for shuffle with proof as defined in claim 21 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.

### Claim 24 (depends on 22)

The shuffle verification apparatus as defined in claim 22 wherein
said transformation condition verification unit verifies by said transformation condition commitment that with respect to the input response, sub-response and the challenge value, an identity holds as a polynomial of the response, sub-response and the challenge value, said polynomial stating the condition to be met by the transformation from said input message sequence to said output encrypted message sequence, to verify the authenticity of said sub-response based on the committed sub-equation coefficients, the response and the challenge value.

### Claim 25 (depends on 19)

The apparatus for shuffle with proof as defined in claim 19 wherein
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; and
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.

### Claim 26 (depends on 20)

The shuffle verification apparatus as defined in claim 20 wherein
said transformation information retention verification unit verifies that a represented value represented by a challenge value with respect to the basis of said output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence; and wherein
said transformation condition verifying unit is present in a plurality of numbers including first and second verifying units,
said first transformation condition verifying unit verifying by said transformation condition commitment that with respect to the input response and the challenge value, an identity holds 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, and
said second verifying unit verifying by said transformation condition commitment that with respect to the input response, sub-response and the challenge value, an identity holds 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, and also verifying the authenticity of said sub-response from the sub-equation coefficients committed, the response and the challenge value.

### Claim 27 (depends on 19)

The apparatus for shuffle with proof as defined in claim 19 wherein
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; and wherein
said transformation condition commitment generating unit is present in a plural i ty 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; and
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 plural I ty 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.

### Claim 28 (depends on 20)

The shuffle verification apparatus as defined in claim 20 wherein
said transformation information retention verifying unit is present in a plurality of numbers, each of which verifies that a represented value represented by a challenge value with respect to the basis of the output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence;
said transformation condition verifying unit is present in a plurality of numbers comprising one or both of first and second verifying units,
said first transformation condition verifying unit verifying by said transformation condition commitment that with respect to an input response and the challenge value, an identity holds 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, and
said second transformation condition verifying unit verifying by said transformation condition commitment that with respect to the input response, sub-response and the challenge value, an identity holds 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, and verifying the authenticity of said sub-response from the sub-equation coefficients committed, the response and the challenge value.

### Claim 29 (depends on 21, 23)

The apparatus for shuffle with proof as defined in claim 21 or 23 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.

### Claim 30 (depends on 21, 23)

The apparatus for shuffle with proof as defined in claim 21 or 23 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.

### Claim 31 (depends on 25, 27)

The apparatus for shuffle with proof as defined in claim 25 or 27, 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.

### Claim 32 (depends on 19)

The input message sequence generating apparatus as defined in claim 19 wherein
a portion of an input message sequence input to a device for shuffle with proof, as value that is pseudo random numbers or as values resulting from transformation applied to the public key and the input encrypted message sequence by the pseudo random numbers.

### Claim 33 (depends on 32)

The input message sequence generating apparatus as defined in claim 32 wherein the input encrypted message sequence, the public key and the pseudo random numbers are combined together into an input message sequence.

### Claim 34 (depends on 32)

The input message sequence generating apparatus as defined in claim 32 in which an input encrypted message sequence is transformed by a public key sequence and output a proof text proving the authenticity of the public key sequence, wherein
said public key sequence is a plurality of public keys corresponding to the same secret key, generated by cooperation of provers owning the secret key in a scattered state, with a set of specified generators of each of public key being pseudo random numbers generated by an input including an input message sequence.

### Claim 35 (depends on 32)

The input message sequence generating apparatus as defined in claim 32 wherein
the set of specified generators of each of plural public keys corresponding to the same secret key generated by cooperation of provers owning the secret key in the scattered state generates a public key sequence as pseudo random numbers generated by inputting the input message sequence, encrypts each input plain text with each public key constituting the public key sequence, proves that the encryption is by the respective public keys and generates the input message sequence by combining the input encrypted message sequence and the public key.

### Claim 36

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.

### Claim 37

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.

### Claim 38

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 transformat ion, 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.

### Claim 39 (depends on 37)

The machine readable program as defined in claim 37, to perform the processing comprising:
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.

### Claim 40 (depends on 38)

The machine readable program as defined in claim 38, to perform the processing comprising:
said transformation information retention verifying processing verifying that a represented value represented by a challenge value with respect to the basis of output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence; and
said transformation condition verifying processing verifying by said transformation condition commitment that with regard to an input response and the challenge value an identity holds 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.

### Claim 41 (depends on 37)

The machine readable program as defined in claim 37, to perform the processing comprising:
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.

### Claim 42 (depends on 40)

The machine readable program as defined in claim 40, to perform the processing comprising:
said transformation condition verification processing verifying by said transformation condition commitment, that with regard to the input response, sub-response and the challenge value, an identity holds 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, to verify the authenticity of said sub-response from sub-equation coefficients committed, the response and the challenge value.

### Claim 43 (depends on 37)

The machine readable program as defined in claim 37, to perform the processing comprising:
said transformation information retention commitment generating processing generating 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 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.

### Claim 44 (depends on 38)

The machine readable program as defined in claim 38, to perform the processing comprising:
said transformation information retention verification processing verifying that a represented value represented by a challenge value with respect to the basis of said output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence; and
said transformation condition verifying processing being made up of a plurality of transformation condition verifying processings including first and second ones thereof
said first verifying processing verifying by said transformation condition commitment, that with regard to the input response and the challenge value, an identity holds 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, and
said second verifying processing verifying by said transformation condition commitment that with regard to the input response, sub-response and the challenge value, an identity holds 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, and also verifying the authenticity of said sub-response based on the sub-equation coefficients committed, the response and the challenge value.

### Claim 45 (depends on 37)

The machine readable program as defined in claim 37, to perform the processing comprising:
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 bemet 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.

### Claim 46 (depends on 38)

The machine readable program as defined in claim 38, to perform the processing comprising:
said transformation information retention verifying processing, comprehending a plurality of transformation information retention verifying processings, each of which verifies that a represented value represented by a challenge value with respect to the basis of the output encrypted message sequence and the transformation information retention commitment is equal to a represented value represented by the response with respect to the basis of the input message sequence;
said transformation condition verifying processing including a plurality of, first and second, transformation condition verifying processings
the first transformation condition verifying processing verifying by said transformation condition commitment that with regard to an input response and the challenge value, an identity holds 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, and
the second transformation condition verifying processing verifying by said transformation condition commitment that with regard to the input response, sub-response and the challenge value, an identity holds 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, and
verifying the authenticity of said sub-response based on the sub-equation coefficients committed, the response and the challenge value.

### Claim 47 (depends on 39, 41)

The machine readable program as defined in claim 39 or 41, to perform the processing for generating the transformation condition commitment;
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 respective of the challenge value, where each component of the response is made up of a polynomial of the challenge value.

### Claim 48 (depends on 39, 41)

The machine readable program as an apparatus for shuffle with proof, as defined in claim 39 or 41, to perform the processing for generating the transformation condition commitment;
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.

### Claim 49 (depends on 43, 45)

The machine readable program as defined in claim 43 or 45, to perform the processing for generating the transformation condition commitment;
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.

### Claim 50 (depends on 37)

The machine readable program as defined in claim 37, to perform the processing for generating an input message sequence to be input to the apparatus for shuffle with proof, in which
a portion of an input message sequence input to a device for shuffle with proof, as value that is pseudo random numbers or as values resulting from transformation applied to the public key and the input encrypted message sequence by the pseudo random numbers.

### Claim 51 (depends on 50)

The machine readable program for allowing a computer, as an apparatus as defined in claim 50, to perform the processing of combining an input message sequence, public key and the pseudo random numbers together into an input message sequence.

### Claim 52 (depends on 50)

The machine readable program as defined in claim 50, to perform the processing of transforming an input encrypted message sequence by a public key sequence and output a proof text proving the authenticity of the public key sequence,
said public key sequence being made up of a plurality of public keys corresponding to the same secret key, generated by cooperation of provers owning the secret key in a scattered state, with a set of specified generators of each public key being pseudo random numbers generated by an input including an input message sequence.

### Claim 53 (depends on 50)

The machine readable program as defined in claim 50, to perform the processing comprising:
a set of specified generators of each of plural public keys corresponding to the same secret key generated by cooperation of provers owning the secret key in scattered state generating a public key sequence as pseudo random numbers generated by inputting an input including an input message sequence,
encrypting each input plain text with each public key constituting the public key sequence,
proving that the encryption is by the respective public keys, and
generating the input message sequence by combining the input encrypted message sequence and the public keys.

### Claim 54

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.
