# US 2014/0192981 A1 · Information processing apparatus, signature generation apparatus, information processing method, signature generation method, and program

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

- Number: US 2014/0192981 A1
- Document ID: US20140192981A1
- Status: Published application
- Kind: A1
- Application number: 14/239,931
- Filed: 2012-08-17
- Published: 2014-07-10
- Earliest claimed: 2011-08-29
- Assignees: Sony Corporation
- Inventors: Harunaga Hiwatari; Koichi Sakumoto; Taizo Shirai
- Web page: https://patentgrep.com/patent/US20140192981A1

## CPC

- H04L 9/0816: {Key establishment, i.e. cryptographic processes or cryptographic protocols whereby a shared secret becomes available to two or more parties, for subsequent use}
- H04L 9/3093: {involving Lattices or polynomial equations, e.g. NTRU scheme}
- H04L 9/3247: {involving digital signatures}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

## Abstract

Provided is an information processing apparatus including a random number generation unit configured to generate a pair of random numbers from a seed, a message generation unit configured to generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn, a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)), and a response supply unit configured to supply the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns.

## Claims

### Claim at position 1

1-19. (canceled)

### Claim 20

An information processing apparatus comprising:
a random number generation unit configured to generate a pair of random numbers from a seed;
a message generation unit configured to generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a response supply unit configured to supply the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information,
wherein the message generation unit stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers, and
wherein the response supply unit regenerates the same random numbers or the same intermediate variables used as the response information based on the seed stored in the storage apparatus.

### Claim 21

An information processing apparatus comprising:
a random number generation unit configured to generate a pair of random numbers from a seed;
a message generation unit configured to generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a response supply unit configured to supply the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information,
wherein the message generation unit stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers,
wherein the message generation unit generates the messages of N times (where N≧2),
wherein the message supply unit supplies the verifier with the messages of the N times with interactivity of one time,
wherein the response supply unit supplies the verifier with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time,
wherein the message generation unit generates one hash value from the messages of the N times,
wherein the message supply unit supplies the verifier with the hash value instead of the messages of the N times, and
wherein the message generation unit stores the generated messages in the storage apparatus and calculates the hash value by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the messages stored in the storage apparatus and a process of erasing the messages stored in the storage apparatus when a sum size of the messages stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 22 (depends on 21)

The information processing apparatus according to claim 21, wherein the response supply unit regenerates the same random numbers or the same intermediate variables used as the response information based on the seed stored in the storage apparatus.

### Claim 23

An information processing apparatus comprising:
a random number generation unit configured to generate a pair of random numbers from a seed;
a message generation unit configured to generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation unit configured to generate third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply unit configured to supply the third information to the verifier; and
a response supply unit configured to supply the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein the message generation unit stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers, and
wherein the response supply unit regenerates the random numbers or the intermediate variables used as the response information based on the seed stored in the storage apparatus.

### Claim 24 (depends on 23)

The information processing apparatus according to claim 23, wherein the intermediate information generation unit regenerates the random numbers or the intermediate variables used at a time of the generation of the third information based on the seed stored in the storage apparatus.

### Claim 25 (depends on 24)

The information processing apparatus according to claim 24, wherein the intermediate information generation unit sequentially erases the random numbers becoming unnecessary in course of generating the third information and the intermediate variables generated from the random numbers.

### Claim 26

An information processing apparatus comprising:
a random number generation unit configured to generate a pair of random numbers from a seed;
a message generation unit configured to generate a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation unit configured to generate third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply unit configured to supply the third information to the verifier; and
a response supply unit configured to supply the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein the message generation unit stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers,
wherein the message generation unit generates the messages of N times (where N≧2),
wherein the message supply unit supplies the verifier with the messages of the N times with interactivity of one time,
wherein the intermediate information generation unit generates the third information of the N times based on the first information selected by the verifier for each of the messages of the N times and the second information of the N times obtained at the time of the generation of the messages,
wherein the intermediate information supply unit supplies the verifier with the third information of the N times with interactivity of one time,
wherein the response supply unit supplies the verifier with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time,
wherein the message generation unit generates one hash value from the messages of the N times,
wherein the message supply unit supplies the verifier with the hash value instead of the messages of the N times, and
wherein the message generation unit stores the generated messages in the storage apparatus and calculates the hash value by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the messages stored in the storage apparatus and a process of erasing the messages stored in the storage apparatus when a sum size of the messages stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 27 (depends on 26)

The information processing apparatus according to claim 26, wherein the intermediate information generation unit regenerates the random numbers or the intermediate variables used at a time of the generation of the third information based on the seed stored in the storage apparatus.

### Claim 28 (depends on 27)

The information processing apparatus according to claim 27, wherein the intermediate information generation unit sequentially erases the random numbers becoming unnecessary in course of generating the third information and the intermediate variables generated from the random numbers.

### Claim 29 (depends on 26)

The information processing apparatus according to claim 26, wherein the response supply unit regenerates the random numbers or the intermediate variables used as the response information based on the seed stored in the storage apparatus.

### Claim 30

A signature generation apparatus comprising:
a random number generation unit configured to generate a pair of random numbers from a seed;
a signature generation unit configured to generate a digital signature for a document M based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a signature key s that is an element of a set Kn; and
a signature supply unit configured to supply the digital signature to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(f1(s), . . . , fm(s)),
wherein the signature generation unit stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the digital signature and intermediate variables generated from the random numbers,
wherein the signature generation unit generates the digital signatures of N times (where N≧2),
wherein the signature supply unit supplies the verifier with the digital signatures of the N times with interactivity of one time,
wherein the signature generation unit generates one hash value from messages of the N times,
wherein the signature supply unit supplies the hash value to the verifier instead of the digital signatures of the N times, and
wherein the signature generation unit stores the generated digital signatures in the storage apparatus and calculates the hash value by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the digital signatures stored in the storage apparatus and a process of erasing the digital signatures stored in the storage apparatus when a sum size of the digital signatures stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 31

An information processing method comprising:
a step of generating a pair of random numbers from a seed;
a step of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a step of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information,
wherein, in the step of generating the message, the seed is stored in a storage apparatus and a process of sequentially erasing the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers is executed, and
wherein, in the step of supplying the response information, the same random numbers or the same intermediate variables used as the response information are regenerated based on the seed stored in the storage apparatus.

### Claim 32

An information processing method comprising:
a step of generating a pair of random numbers from a seed;
a step of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a step of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information,
wherein, in the step of generating the message, the seed is stored in a storage apparatus and a process of sequentially erasing the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers is executed,
wherein, in the step of generating the message, the messages of N times (where N≧2) are generated,
wherein, in the step of supplying the message, the messages of the N times are supplied to the verifier with interactivity of one time,
wherein, in the step of supplying the response information, the verifier is supplied with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time,
wherein, in the step of generating the message, one hash value is generated from the messages of the N times,
wherein, in the step of supplying the message, the hash value is supplied to the verifier instead of the messages of the N times, and
wherein, in the step of generating the message, the generated messages are stored in the storage apparatus and the hash value is calculated by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the messages stored in the storage apparatus and a process of erasing the messages stored in the storage apparatus when a sum size of the messages stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 33

An information processing method comprising:
a step of generating a pair of random numbers from a seed;
a step of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a step of generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
a step of supplying the third information to the verifier; and
a step of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein, in the step of generating the message, the seed is stored in a storage apparatus and a process of sequentially erasing the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers is executed, and
wherein, in the step of supplying the response information, the random numbers or the intermediate variables used as the response information are regenerated based on the seed stored in the storage apparatus.

### Claim 34

An information processing method comprising:
a step of generating a pair of random numbers from a seed;
a step of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
a step of generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
a step of supplying the third information to the verifier; and
a step of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein, in the step of generating the message, the seed is stored in a storage apparatus and a process of sequentially erasing the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers is executed,
wherein, in the step of generating the message, the messages of N times (where N≧2) are generated,
wherein, in the step of supplying the message, the verifier is supplied with the messages of the N times with interactivity of one time,
wherein, in the step of generating intermediate information, the third information of the N times is generated based on the first information selected by the verifier for each of the messages of the N times and the second information of the N times obtained at the time of the generation of the messages,
wherein, in the step of generating intermediate information, the verifier is supplied with the third information of the N times with interactivity of one time,
wherein, in the step of supplying the response information, the verifier is supplied with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time,
wherein, in the step of generating the message, one hash value is generated from the messages of the N times,
wherein, in the step of supplying the message, the hash value is supplied to the verifier instead of the messages of the N times, and
wherein, in the step of generating the message, the generated messages are stored in the storage apparatus and the hash value is calculated by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the messages stored in the storage apparatus and a process of erasing the messages stored in the storage apparatus when a sum size of the messages stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 35

A signature generation method comprising:
a step of generating a pair of random numbers from a seed;
a step of generating a digital signature for a document M based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a signature key s that is an element of a set Kr% and
a step of supplying the digital signature to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(f1(s), . . . , fm(s)),
wherein, in the step of generating the digital signature, the seed is stored in a storage apparatus and a process of sequentially erasing the random numbers becoming unnecessary in course of generating the digital signature and intermediate variables generated from the random numbers is executed,
wherein, in the step of generating the digital signature, the digital signatures of N times (where N≧2) are generated,
wherein, in the step of supplying the digital signature, the verifier is supplied with the digital signatures of the N times with interactivity of one time,
wherein, in the step of generating the digital signature, one hash value is generated from messages of the N times,
wherein, in the step of supplying the digital signature, the hash value is supplied to the verifier instead of the digital signatures of the N times, and
wherein, in the step of generating the digital signature, the generated digital signatures are stored in the storage apparatus and the hash value is calculated by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the digital signatures stored in the storage apparatus and a process of erasing the digital signatures stored in the storage apparatus when a sum size of the digital signatures stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 36

A non-transitory computer readable medium including computer executable instructions causing a computer to realize:
a random number generation function of generating a pair of random numbers from a seed;
a message generation function of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a response supply function of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information,
wherein the message generation function stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers, and
wherein the response supply function regenerates the same random numbers or the same intermediate variables used as the response information based on the seed stored in the storage apparatus.

### Claim 37

A non-transitory computer readable medium including computer executable instructions causing a computer to realize:
a random number generation function of generating a pair of random numbers from a seed;
a message generation function of generating a message based on a pair of multi-order multivariate polynomials F=(f), . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s)); and
a response supply function of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧3) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys and the response information,
wherein the message generation function stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers,
wherein the message generation function generates the messages of N times (where N≧2),
wherein the message supply function supplies the verifier with the messages of the N times with interactivity of one time,
wherein the response supply function supplies the verifier with the response information of the N times corresponding to the verification patterns selected by the verifier for the messages of the N times, with interactivity of one time,
wherein the message generation function generates one hash value from the messages of the N times,
wherein the message supply function supplies the verifier with the hash value instead of the messages of the N times, and
wherein the message generation function stores the generated messages in the storage apparatus and calculates the hash value by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the messages stored in the storage apparatus and a process of erasing the messages stored in the storage apparatus when a sum size of the messages stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 38

A non-transitory computer readable medium including computer executable instructions causing a computer to realize:
a random number generation function of generating a pair of random numbers from a seed;
a message generation function of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation function of generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply function of supplying the third information to the verifier; and
a response supply function of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein the message generation function stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers, and
wherein the response supply function regenerates the random numbers or the intermediate variables used as the response information based on the seed stored in the storage apparatus.

### Claim 39

A non-transitory computer readable medium including computer executable instructions causing a computer to realize:
a random number generation function of generating a pair of random numbers from a seed;
a message generation function of generating a message based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kn;
a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y1, . . . , ym)=(f1(s), . . . , fm(s));
an intermediate information generation function of generating third information based on first information randomly selected by the verifier and second information obtained at a time of generation of the message;
an intermediate information supply function of supplying the third information to the verifier; and
a response supply function of supplying the verifier with response information corresponding to a verification pattern selected by the verifier from among k (where k≧2) verification patterns,
wherein the vector s is a secret key,
wherein the pair of multi-order multivariate polynomials F and the vectors y are public keys,
wherein the response information is information selected from among the pair of random numbers and the message according to the verification pattern,
wherein the message is information obtained by executing calculation prepared in advance for the verification pattern corresponding to the response information based on the public keys, the first information, the third information, and the response information,
wherein the message generation function stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the message and intermediate variables generated from the random numbers,
wherein the message generation function generates the messages of N times (where N≧2),
wherein the message supply function supplies the verifier with the messages of the N times with interactivity of one time,
wherein the intermediate information generation function generates the third information of the N times based on the first information selected by the verifier for each of the messages of the N times and the second information of the N times obtained at the time of the generation of the messages,
wherein the intermediate information supply function supplies the verifier with the third information of the N times with interactivity of one time,
wherein the response supply function supplies the verifier with the response information of the N times corresponding to the verification patterns selected by the verifier for each of the messages of the N times, with interactivity of one time,
wherein the message generation function generates one hash value from the messages of the N times,
wherein the message supply function supplies the verifier with the hash value instead of the messages of the N times, and
wherein the message generation function stores the generated messages in the storage apparatus and calculates the hash value by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the messages stored in the storage apparatus and a process of erasing the messages stored in the storage apparatus when a sum size of the messages stored in the storage apparatus is greater than a block unit of the hash function.

### Claim 40

A non-transitory computer readable medium including computer executable instructions causing a computer to realize:
a random number generation function of generating a pair of random numbers from a seed;
a signature generation function of generating a digital signature for a document M based on a pair of multi-order multivariate polynomials F=(f1, . . . , fm) defined in a ring K, the pair of random numbers, and a signature key s that is an element of a set Kn; and
a signature supply function of supplying the digital signature to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(f1(s), . . . , fm(s)),
wherein the signature generation function stores the seed in a storage apparatus and sequentially erases the random numbers becoming unnecessary in course of generating the digital signature and intermediate variables generated from the random numbers,
wherein the signature generation function generates the digital signatures of N times (where N≧2),
wherein the signature supply function supplies the verifier with the digital signatures of the N times with interactivity of one time,
wherein the signature generation function generates one hash value from messages of the N times,
wherein the signature supply function supplies the hash value to the verifier instead of the digital signatures of the N times, and
wherein the signature generation function stores the generated digital signatures in the storage apparatus and calculates the hash value by sequentially executing a process of calculating an intermediate value calculated by a hash function during calculation of the hash value based on the digital signatures stored in the storage apparatus and a process of erasing the digital signatures stored in the storage apparatus when a sum size of the digital signatures stored in the storage apparatus is greater than a block unit of the hash function.