INFORMATION PROCESSING APPARATUS, SIGNATURE GENERATION APPARATUS, INFORMATION PROCESSING METHOD, SIGNATURE GENERATION METHOD, AND PROGRAM

• US 20140192981A1
• Filed: 08/17/2012
• Published: 07/10/2014
• Est. Priority Date: 08/29/2011
• Status: Active Grant

• Current Assignee: Sony Corporation (Sony Group Corp.)
• Original Assignee: Sony Corporation (Sony Group Corp.)
• Inventors: Hiwatari, Harunaga, Sakumoto, Koichi, Shirai, Taizo
• Granted Patent: US 9,276,735 B2
• Time in Patent Office: Days
• US Class Current: 380/46
• CPC Class Codes: 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
• CPC Class Codes: H04L 9/3093 involving Lattices or polynomial equations, e.g. NTRU scheme
• CPC Class Codes: H04L 9/3247 involving digital signatures

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ, a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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

1-19. -19. (canceled)

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

22. 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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

24. 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.

25. 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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply unit configured to supply the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

27. 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.

28. 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.

29. 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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a signature key s that is an element of a set Kⁿ; 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=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a step of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a signature key s that is an element of a set K^r% and

a step of supplying the digital signature to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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), . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a vector s that is an element of a set Kⁿ;

a message supply function of supplying the message to a verifier storing the pair of multi-order multivariate polynomials F and vectors y=(y₁, . . . , y_m)=(f₁(s), . . . , f_m(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.

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=(f₁, . . . , f_m) defined in a ring K, the pair of random numbers, and a signature key s that is an element of a set Kⁿ; 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=(f₁(s), . . . , f_m(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.