WO2025074851A1 - Information processing method, information processing system, and program - Google Patents

Abstract

The present disclosure pertains to an information processing method and an information processing system that enable the realization of a post quantum and highly secure practical digital signature, and also pertains to a program. The present invention sets s∈R_q as a secret key, sets F(s) comprising multi-order multivariate polynomials that form a Ring-MQ (multivariate quadratic) function as a public key, generates a digital signature on the basis of the secret key, and verifies whether the digital signature is normal by means of the public key. The present invention can be applied to a digital signature system.

Description

Information processing method, information processing system, and program

This disclosure relates to an information processing method, an information processing system, and a program, and in particular to an information processing method, an information processing system, and a program that enable the realization of practical electronic signatures that are highly secure and quantum-resistant.

With the rapid development of information processing and communication technologies, documents, both public and private, are being digitized at a rapid pace. As a result, electronic signatures are being used to safely manage electronic documents.

Electronic signatures are used to identify the creator of an electronic document. For this reason, if an electronic signature is forged by a malicious third party, there is a risk that the electronic document may be forged, so a high level of security is required.

In order to increase the security of electronic signatures, signature methods have been proposed that make use of difficult mathematical problems that do not have efficient algorithms that computers can solve, such as the prime factorization problem or the discrete logarithm problem, which pose a high degree of computational complexity.

However, when quantum computers are put into practical use, these mathematical problems will be able to be solved quickly enough for practical purposes, meaning that current electronic signature methods will no longer be able to provide sufficient security.

In response, a digital signature method has been proposed that uses multi-order, multivariate problems as quantum-resistant problems that differ from problems that can be solved by quantum computers, such as the prime factorization problem and the discrete logarithm problem (see Patent Document 1).

JP 2012-098690 A

However, electronic signature methods that use multi-order multivariate problems, such as the technology described in Patent Document 1, can improve quantum resistance, but they are known to increase the data size of the electronic signature and slow down the calculation speed, making them impractical.

For this reason, electronic signature methods that use problems other than multi-order, multivariate problems continue to be adopted, even though they are aware that quantum resistance will be compromised.

This disclosure has been made in light of these circumstances, and in particular makes it possible to realize practical electronic signatures that are quantum-resistant and highly secure.

An information processing method according to one aspect of the present disclosure is an information processing method including the steps of setting _s∈Rq as a private key, setting F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function as a public key, generating a digital signature based on the private key, and verifying whether the digital signature is authentic using the public key.

An information processing system and program according to one aspect of the present disclosure is an information processing system including a key generation unit that sets _s∈Rq as a private key and sets F(s) consisting of a multi-degree multivariate polynomial that forms a Ring-MQ (Multivariate Quadratic) function as a public key, an electronic signature generation unit that generates an electronic signature based on the private key, and an electronic signature verification unit that verifies whether the electronic signature is genuine using the public key, and a program that causes a computer to function as the key generation unit, the electronic signature generation unit, and the electronic signature verification unit.

In one aspect of the present disclosure, _s∈Rq is set as a private key, F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function is set as a public key, a digital signature is generated based on the private key, and whether or not the digital signature is authentic is verified using the public key.

FIG. 1 is a diagram illustrating an overview of the present disclosure. FIG. 11 is a diagram for explaining a Ring-MQ function calculation process. 3 is a flowchart illustrating the Ring-MQ function calculation process of FIG. 2; FIG. 2 is a diagram illustrating an example of an authentication protocol configuration used in the electronic signature system of the present disclosure. 5 is a diagram illustrating an example of the configuration of the prover side information processing device in FIG. 4; FIG. 5 is a diagram illustrating an example of the configuration of the verifier side information processing device in FIG. 4. 5 is a flowchart illustrating an authentication information verification process according to the authentication protocol of FIG. 4. 1 is a diagram for explaining partial cost _MPC that depends on the communication volume of the MPC protocol used in the electronic signature method, and a soundness error. FIG. 2 is a diagram illustrating the signature length of a digital signature for each digital signature method. 2 shows an example of the configuration of a general-purpose computer.

Below, a preferred embodiment of the present disclosure will be described in detail with reference to the attached drawings. Note that in this specification and drawings, components having substantially the same functional configurations are designated by the same reference numerals to avoid redundant description.

Hereinafter, an embodiment of the present technology will be described in the following order.
1. Overview of the Disclosure 2. Preferred Embodiments 3. Examples of Implementation by Software

<<1. Overview of the Disclosure>>
<Common electronic signature methods>
In particular, the present disclosure is directed to realizing a practical electronic signature that is quantum-resistant and highly secure. First, a general electronic signature method will be briefly described.

Figure 1 shows an electronic signature system for implementing a general electronic signature method.

Unlike paper documents, it is not possible to stamp or sign digitized data. Therefore, to prove the creator of digitized data, an electronic mechanism that has the same effect as stamping or signing a paper document is required. This mechanism is called an electronic signature. For example, a mechanism in which signature data known only to the creator of the data is associated with the data and provided to the recipient, and the signature data is then verified on the recipient's side, is called an electronic signature method.

The electronic signature system 1 that realizes the electronic signature method is composed of, for example, a signer-side information processing device 2 and a verifier-side information processing device 3.

The signer's information processing device 2 and the verifier's information processing device 3 are information processing devices used by the signer and the verifier, respectively, and are configured to be able to communicate with each other.

The signer side information processing device 2 has a key generation unit Gen and an electronic signature generation unit Sig.

The key generation unit Gen generates a signer-specific private key (signature key) sk and a public key (verification key) pk, and transmits and outputs only the public key pk to the verifier-side information processing device 3.

The electronic signature generation unit Sig applies a hash function to the document M to generate a hash value h. The electronic signature generation unit Sig generates an electronic signature σ based on the hash value h using the private key sk. The electronic signature generation unit Sig then transmits the document M and the electronic signature σ to the verifier-side information processing device 3.

On the other hand, the verifier side information processing device 3 is equipped with an electronic signature verification unit Ver.

When the electronic signature verification unit Ver acquires the public key pk, the document M, and the electronic signature σ, it verifies the electronic signature σ using the public key pk.

As a result, the verifier proves that the signer has the private key sk, while keeping the private key sk completely secret from anyone other than the signer.

(Digital signature method using the LWE problem)
In the above description, when a hash value h generated from a document M is signed using a private key sk, an electronic signature σ is generated by signing the hash value h generated from the document M with the private key sk. At this time, it is assumed that the electronic signature σ can be verified only by the public key pk, and that the private key sk cannot be derived from the public key pk.

This is because the public key pk is generated by inputting the private key sk into a specified function. That is, for this reason, information signed with the private key sk can only be verified with the corresponding public key pk.

Therefore, if the private key sk could be derived from the public key pk by performing a certain calculation, the confidentiality of the private key sk would be lost, making it possible for a third party to tamper with the document M.

Because the private key sk needs to be kept secret, the specific function used to generate the public key pk from the private key sk has until now been a method that uses functions that are difficult to solve even with a computer, such as the prime factorization problem or the discrete logarithm problem. This prevents the private key sk from being derived from the public key pk, and maintains the confidentiality of the private key sk.

However, with the advent of quantum computers, it has become possible to easily solve functions related to problems that were previously considered difficult to solve, such as the prime factorization problem and the discrete logarithm problem, because solution algorithms exist. In other words, with the advent of quantum computers, it has become possible to derive the private key sk from the public key pk, and it is becoming increasingly difficult to ensure the confidentiality of the private key sk.

In light of this, there is a demand for an electronic signature method that makes it difficult to derive the private key sk from the public key pk, even when using a quantum computer.

In the following, an electronic signature scheme in which it is difficult to derive a private key sk from a public key pk even using a quantum computer will be referred to as a highly quantum-resistant electronic signature scheme or an electronic signature scheme using a quantum-resistant encryption scheme.

As a result, an electronic signature method using the LWE (Learning with Error) problem has been proposed as one of the highly quantum-resistant electronic signature methods. The following formula (1) shows an example of a function for generating a private key and a public key when using the LWE problem.

Here, in formula (1), when the private key is s∈( _Fq ) ⁿ , (a _i , b _i ) is the public key. That is, formula (1) is composed of linear equations from i=1 to m, but each linear equation has e _i (error term) added, making it difficult to perform matrix calculations. For this reason, it is said that in electronic signature methods using the LWE (Learning with Error) problem, even quantum computers cannot derive the private key from the public key.

In addition, in formula (1), _Fq is expressed as a finite field of order q. Also, s and _ai written in bold are vectors. Also, ( _Fq ) ⁿ is expressed by adding subscript q and superscript n to the bold F in (1).

In a digital signature scheme using the LWE problem in formula (1), the number of instances is often m=n, and is expressed as O(n ² ) elements of _Fq . In addition, due to the vector dot product operation, the multiplication in the operation of formula (1) is required O(n ² ) times.

However, in the case of the electronic signature method shown in formula (1), it is known that the data size of the electronic signature becomes large and the time required for calculation is high. Due to the high difficulty of the calculation, it is said that although it is possible to ensure security, it is not practical.

(Digital signature method using the Ring-LWE problem)
Therefore, a digital signature scheme using the Ring-LWE problem as shown in the following equation (2) has been proposed.

Here, in formula (2), when the private key is _s∈Rq , (a _i , b _i ) is the public key. That is, formula (2) is composed of linear equations from i=1 to m. However, in the electronic signature method using the Ring-LWE problem, it is assumed that only m=1 is used.

In addition, in formula (2), _Fq is expressed as a finite field of order q. a is not a vector but a polynomial. s is also not a vector but a polynomial.

For f(X), ^XN +1 (N: power of 2) is often used. Furthermore, m=1 is often used.

That is, when the Ring-LWE problem is used, the number of instances is m=1, so that _Fq can be expressed with O(n) elements.

As described above, in the case of a digital signature scheme using the LWE problem, the number of multiplications required is O(n ² ).

In contrast, in the case of a digital signature scheme using Ring-LWE, the number of multiplications of _Fq by FFT (Fast Fourier Transform)/NTT (Number-Theoretic Transform) to obtain an instance (a, a·s+e) is O(n log n), which reduces the amount of calculation. Note that in the digital signature scheme using Ring-LWE, a and s are polynomials.

However, in the case of digital signature methods using the Ring-LWE problem, in practice, instances are often derived from a seed, so the benefits of improving calculation speed are greater than those of reducing the data size of the digital signature.

Furthermore, in the case of a digital signature scheme obtained by applying the Fiat-Shamir transformation to an interactive protocol, the challenge space in the challenge-and-response based protocol used in the interactive protocol changes from _Fq to _Rq , thereby reducing soundness errors.

In other words, the electronic signature method using the Ring-LWE problem requires less calculations than the electronic signature method using the LWE problem, can increase the calculation speed, and can reduce soundness errors.

(Electronic signature method using multivariate problem (MQ problem))
Above, we have explained electronic signature schemes that use the LWE (Learning with Error) problem and the Ring-LWE problem as examples of highly quantum-resistant electronic signature schemes.

However, the LWE problem is not the only difficult problem that has been proposed; other problems have also been proposed, and in recent years, an electronic signature method using the multivariate quadratic problem (MQ) has also been proposed.

The MQ problem is a problem that uses the MQ function, and has long been recognized as being difficult, so electronic signature methods that use the MQ problem have been known to be highly secure. However, it has been pointed out that electronic signature methods that use the MQ problem are difficult to use in practice, as the size of the electronic signature increases and the calculation speed slows down. For this reason, despite the recognition that it is highly reliable in terms of security, electronic signature methods that use the MQ problem have been avoided, and electronic signature methods that use other problems that do not have the same quantum resistance as electronic signature methods that use the MQ problem have been selected.

An MQ function is, for example, m n-variable quadratic polynomials f1(x1, ..., xn), ..., fm(x1, ..., xn) defined over a ring K.

For example, consider the case where y = (y1, ..., ym) = (f1(s), ..., fm(s)) is calculated by substituting vector s = (s1, ..., sn) ∈ ^Kn into this MQ function.

In this case, due to the characteristics of the MQ function, even if f1(x1, ..., xn), ..., fm(x1, ..., xn) are known, it is a difficult process to restore vector s from y.

Then, by taking advantage of the characteristics of the MQ function and substituting the vector s, which serves as the private key, into the MQ function to obtain the value y, which is used as the public key, a highly confidential private key and public key can be generated. This is the electronic signature method using the MQ problem.

More specifically, a function that deals with the MQ problem is, for example, a function as shown in the following formula (3).

Here, in formula (3), when _the private key is s∈( _Fq ) ⁿ , F(s) is a quadratic polynomial consisting of F(s)= ^sTAis + _bTs + ^c _, and is the public key. In formula (3), the "T" in the upper right of s and _b is a transposition symbol.

In other words, equation (3) is composed of m quadratic equations, where i = 1 to m, but because the degree is so high, it is said that even a quantum computer cannot solve it quickly.

In addition, in equation (3), s and b written in bold are vectors, and A is a matrix.

In addition, in a digital signature scheme using the MQ problem shown in formula (3), the number of instances m = n is often used. Furthermore, an instance can be expressed by O(n ³ ) elements of _Fq , and the number of multiplications of _Fq required is O(n ³ ).

Furthermore, for each i, A _i s is the product of a matrix and a vector, so the number of multiplications is n ^2. Furthermore, the product of s ^T and (A _i s + b _i ) (= s ^T A i _s + b _i ^T s) is the product of a vector and a vector, so the number of multiplications in total is mn ² ×mn, since the range of i is 1≦i≦m. That is, when m=n, which is often used as a parameter, the total number of multiplications is n ³ +n ² .

　Thus, electronic signature methods using the MQ problem are known to be highly secure, but because they require a large amount of calculations and it is not possible to increase the calculation speed, they are considered to be difficult to use in practice.

(Digital signature method using the Ring-MQ problem)
Therefore, in this disclosure, we propose an electronic signature method in which the MQ problem is replaced with the Ring-MQ problem, in a manner similar to the case in which the LWE problem is replaced with the Ring-LWE problem, thereby making it possible to increase the computational complexity and computational speed of the electronic signature method.

The Ring-MQ problem is a problem of finding s from the value of a public key F( _s ) associated with a Ring- _MQ function F, which includes two sequential multiplications, one of which is composed of a multiply-and-accumulate operation on Fq and the other of which is composed of a multiplication on _Rq , where s∈Rq is a private key.

More specifically, as shown in FIG. 2, the Ring-MQ function calculation process is realized by a product-sum calculation process C1 that executes a product-sum calculation on _Fq between an input private key s and a parameter A, and a multiplication process C2 that performs a multiplication (product) on _Rq between the calculation result of the product-sum calculation process C1 and the private key s.

The Ring-MQ function calculation process in Figure 2 derives the public key F(s) from the input private key s by the process shown in the flowchart in Figure 3.

That is, in step S1, the product-sum calculation process C1 sets parameter A.

In step S2, the product-sum calculation process C1 accepts input of the private key s.

In step S3, the product-sum calculation process C1 calculates the product-sum of the parameter A and the private key s in _Fq , and outputs the result to the multiplication process C2.

In step S4, the multiplication process C2 multiplies the result of the product-sum calculation of the parameter A and the private key s in _Fq by the private key s to obtain the product.

In step S5, the multiplication process C2 multiplies the product-sum calculation result of the parameter A and the private key s in _Fq by the private key s, and outputs the multiplication result as the public key F(s).

By the above process, the public key F(s) is obtained from the private key s. At this point, the problem of obtaining the private key s from the public key F(s) is the Ring-MQ problem.

More specifically, the Ring-MQ problem is, for example, the problem of finding the private key s from the value of the public key F(s) shown in the following equation (4).

Here, in formula (4), when the private key is _s∈Rq , F(s)=s·A _i (s)+b _i s+c _i is the public key. s is not a vector but a polynomial. In formula (4), the formula is composed of quadratic equations with i=1 to m, but the number of instances is assumed to be m=1.

Therefore, in the digital signature scheme using the Ring-MQ problem of formula (4), an instance can be expressed by O(n ² ) elements of _Fq . Also, the number of multiplications of _Fq by FFT/NTT is O(n ² ), which is smaller than the number of multiplications in the MQ problem (O(n ³ )).

Furthermore, since the number of instances corresponding to the function in the Ring-MQ problem is assumed to be m=1, the number of multiplications of A(s) on _Fq is calculated as follows.

In other words, the operation of corresponding the elements of Rq to a vector is called vec, as shown in the following equation (5).

Furthermore, by using a _ij εF _q (a finite field of order q) corresponding to the definition of A, it becomes possible to perform calculation as shown in the following formula (6).

As shown in equation (6), multiplication appears only in matrix operations, so the number of multiplications is n ² .

Furthermore, if the multiplication of s and (A(s) + b) on _Rq (= s · A _i (s) + b _i s) is performed using FFT after zero-padding the n coefficients of s up to 2n-1, the number of multiplications on _Fq will be 3n log 2n + 4n.

In other words, in an electronic signature method using the MQ problem, the private key s is composed of a vector, but in an electronic signature method using the Ring-MQ problem, the private key s is a polynomial rather than a vector. As a result, in an electronic signature method using the Ring-MQ problem, it is possible to reduce the amount of calculations required for processing while ensuring the same level of security as when the MQ problem is used.

In addition, similarly to the case where the LWE problem is transformed into the Ring-LWE problem, when the MQ problem is transformed into the Ring-MQ problem, in the case of an electronic signature scheme obtained by applying the Fiat-Shamir transformation to an interactive protocol, the challenge space changes from _Fq to _Rq , and the soundness error is reduced.

As described above, by using the Ring-MQ problem instead of the MQ problem in an electronic signature method, it is possible to reduce the amount of calculations and increase the calculation speed without reducing the security obtained by using the MQ problem, and it is also possible to reduce soundness errors.

As a result, by using the Ring-MQ problem, it is possible to realize a practical electronic signature method using the MQ problem.

As a result, it will be possible to realize a practical electronic signature method that is quantum-resistant and highly secure.

Then, we will explain the electronic signature system proposed in this disclosure that applies the electronic signature method using the Ring-MQ problem.

<<2. Preferred embodiment>>
Next, a configuration example of an electronic signature system when the technology of the present disclosure is applied to the general electronic signature system of Fig. 1 will be described. This configuration example is obtained by applying a known method (such as Fiat-Shamir transformation) to convert an authentication protocol into an electronic signature system for a configuration example of an authentication protocol using the Ring-MQ problem. Therefore, in the following description, an example of an authentication protocol using the Ring-MQ problem will be described with reference to Fig. 4. Regarding the conversion from an authentication protocol to an electronic signature system, an example using the Fiat-Shamir transformation will be described after the description of the authentication protocol.

In the authentication protocol 11 in FIG. 4, a verifier verifies that a prover holds a private key, without knowing the prover's private key, based on signature information (electronic signature) generated using a private key held only by the prover.

The authentication protocol 11 is composed of a prover-side information processing device 31 used by the prover, and a verifier-side information processing device 32 used by the verifier.

In authentication protocol 11, the prover information processing device 31 returns a response to a challenge from the verifier information processing device 32, and the verifier information processing device 32 verifies the contents of the response, thereby executing an authentication protocol that verifies that the prover holds the private key.

The authentication protocol in authentication protocol 11 is an interactive protocol consisting of an odd number of passes, such as three passes or five passes, depending on the number of interactions between the two parties. Note that in the following of this disclosure, an example of five passes will be described, but the number of passes can be three passes or seven passes or more, as long as it is an odd number.

The prover-side information processing device 31 is included in the signer-side information processing device 2 in FIG. 1, and has a key generation unit 51 and an authentication information generation unit 52. The part that receives the hash values h1 and h2 of the verifier-side information processing device 32 and generates challenges ε and ch accordingly is also included in the signer-side information processing device 2 in FIG. 1.

The key generation unit 51 generates the private key sk and public key pk used for the electronic signature, and supplies the public key pk to the verifier side information processing device 32 to share it. Note that here, the private key sk=s and the public key pk=(A, b, y) are assumed, where y is a function that deals with the Ring-MQ problem, y=s·A(s)+b·s. In addition, since it is a function that deals with the Ring-MQ problem, the private key sk=s is a polynomial, and unlike in the case of dealing with the MQ problem, the private key s is not a vector.

The authentication information generation unit 52 generates hash values h1 and h2 and supplies them to the verifier-side information processing device 32. At this time, after supplying the hash value h1 to the verifier-side information processing device 32, the authentication information generation unit 52 acquires a challenge ε selected and supplied (returned) by the verifier, generates a hash value h2 using the challenge ε, and transmits it to the verifier-side information processing device 32.

After transmitting the hash value h2, the authentication information generation unit 52 generates a response σ', which is signature information, based on the challenge ch provided by the verifier-side information processing device 32, and provides it to the verifier-side information processing device 32 together with the document M.

The verifier-side information processing device 32 includes an authentication information verification unit 71. The authentication information verification unit 71 receives the document M and the response σ', and performs verification of the response σ'. The configuration that realizes the function corresponding to the authentication information verification unit 71 is included in the verifier-side information processing device 3 in FIG. 1.

The authentication information verification unit 71 acquires the hash values h1 and h2 supplied from the prover side information processing device 31, and generates a challenge using an algorithm related to the Fiat-Shamir transformation and supplies it to the prover side information processing device 31.

More specifically, the authentication information verification unit 71 acquires the hash value h1 when it is supplied from the prover side information processing device 31, then selects a challenge ε and supplies it to the prover side information processing device 31. The authentication information verification unit 71 then acquires the hash value h2 generated based on the challenge ε, and after acquiring the hash value h2, generates a challenge ch and supplies it to the prover side information processing device 31.

When the authentication information verification unit 71 receives the response σ' supplied by the prover information processing device 31 based on the challenge ch along with the document M, it uses the public key pk shared in advance together with the information contained in the response σ' to calculate hash values h1', h2' corresponding to the hash values h1, h2, and verifies whether the response σ' is legitimate by comparing it with the hash values h1, h2 supplied in generating the challenge.

In FIG. 4, the path along which the authentication information generation unit 52 supplies the hash value h1 is the first path, the path along which the authentication information verification unit 71 supplies the challenge ε is the second path, the path along which the authentication information generation unit 52 supplies the hash value h2 is the third path, the path along which the authentication information verification unit 71 supplies the challenge ch is the fourth path, and the path along which the authentication information generation unit 52 supplies the document M and the response σ' is the fifth path.

In other words, the first through fifth passes are the five passes, which is an odd number of passes as described above. The process in which the key generation unit 51 supplies the public key pk to the authentication information verification unit 71 is a process that occurs before the fifth pass. In addition, the verifier information processing device 32 may separately transmit the verification result of the response σ' to the prover information processing device 31.

<Configuration Example of Prover Side Information Processing Device>
Next, a configuration example of the prover side information processing device 31 will be described with reference to FIG.

The prover information processing device 31 is composed of a control unit 101, an input unit 102, an output unit 103, a storage unit 104, a communication unit 105, a drive 106, and a removable storage medium 107, which are interconnected via a bus 108 and can transmit and receive data and programs.

The control unit 101 is composed of a processor and a memory, and controls the overall operation of the prover side information processing device 31. The control unit 101 also includes a key generation unit 51 and an authentication information generation unit 52. Note that the key generation unit 51 and the authentication information generation unit 52 have been explained with reference to FIG. 4, so their explanation will be omitted.

The input unit 102 is made up of input devices such as a keyboard, mouse, and touch panel through which the user inputs operation commands, and supplies various input signals to the control unit 101.

The output unit 103 is controlled by the control unit 101, and includes a display unit and an audio output unit. The output unit 103 outputs and displays images of the operation screen and processing results on the display unit, which is made up of a display device such as an LCD (Liquid Crystal Display) or an organic EL (Electro Luminescence). The output unit 103 also controls the audio output unit, which is made up of an audio output device, to play various types of audio, music, sound effects, etc.

The memory unit 104 consists of a HDD (Hard Disk Drive), SSD (Solid State Drive), or semiconductor memory, and is controlled by the control unit 101 to write and read various data and programs.

The communication unit 105 is controlled by the control unit 101, and realizes wired or wireless communications such as LAN (Local Area Network) or Bluetooth (registered trademark), and transmits and receives various data and programs to and from the verifier's information processing device 32 and various other devices via the network as necessary.

The drive 106 reads and writes data to a removable storage medium 107 such as a magnetic disk (including a flexible disk), an optical disk (including a CD-ROM (Compact Disc-Read Only Memory) and a DVD (Digital Versatile Disc)), a magneto-optical disk (including an MD (Mini Disc)), or a semiconductor memory.

<Configuration example of verifier side information processing device>
Next, a configuration example of the verifier side information processing device 32 will be described with reference to FIG.

The verifier information processing device 32 is composed of a control unit 131, an input unit 132, an output unit 133, a storage unit 134, a communication unit 135, a drive 136, and a removable storage medium 137, which are interconnected via a bus 138 and can transmit and receive data and programs.

The control unit 131 is composed of a processor and a memory, and controls the overall operation of the verifier side information processing device 32. The control unit 131 also includes an authentication information verification unit 71. Note that the authentication information verification unit 71 has been described with reference to FIG. 4, so its description will be omitted.

Furthermore, the input unit 132 through the bus 138 have a configuration corresponding to the input unit 102 through the bus 108 described with reference to FIG. 5, so a description thereof will be omitted.

<Authentication Information Verification Process>
Next, the authentication information verification process according to the authentication protocol 11 in FIG. 4 will be described with reference to the flowchart in FIG.

In step S31, the key generation unit 51 of the prover side information processing device 31 generates a private key sk. In this example, as described above, the private key sk is set as private key sk=s.

In step S32, the key generation unit 51 generates a public key pk based on the private key sk, and supplies both the private key sk and the public key pk to the authentication information generation unit 52, and controls the communication unit 105 to distribute and share the public key pk with the verifier-side information processing device 32.

The public key pk is defined as pk = (A, b, y), where y is a function consisting of a multi-degree multivariate polynomial that deals with the Ring-MQ problem: y = s A(s) + b s.

In step S51, the authentication information verification unit 71 of the verifier side information processing device 32 controls the communication unit 135 to obtain the public key pk provided by the prover side information processing device 31.

In step S33, the authentication information generation unit 52 calculates the hash value h1 by calculating the following formula (7) and transmits it to the verifier side information processing device 32.

That is, as shown in equation (7) “Generate seed tree {seed _i } i = 1, ..., N [s] _i , [a] _i , [c] _i ← seed _i ,” the authentication information generation unit 52 generates a seed value seed _i for i = 1, ..., N-1, and generates random numbers [s] _i , [a] _i , [c] _i based on the seed value seed _i .

In addition, the authentication information generation unit 52 calculates a = [a] ₁ + ... + [a] _N , _c = -a · _s , [s] _N = s - [s] 1 - ... - [s] N-1, and [c] _N = c - [c] ₁ - ... - [c] _{N -} 1 based on the random numbers [s] i , [a] _i , and [c] _i .

Furthermore, the authentication information generation unit 52 multiplies the seed value seed _i by the function Comm for i=1, . . . N-1 to calculate a commitment value comm _i = Comm(seed _i ) and, for i=N, calculates a commitment value comm _N = Comm(seed _N , [s] _N , [c] _N ).

Then, the authentication information generating unit 52 generates a hash value h1=Hash(M, comm ₁ , . . . , comm _N ) by multiplying the commitment value comm _i , where i=1, . . . , N, by the hash function Hash, and transmits it to the verifier side information processing device 32 .

In step S52, the authentication information verification unit 71 obtains the hash value h1 provided by the prover side information processing device 31.

In step S53, the authentication information verification unit 71 selects one challenge ε from an element of the ring _Rq having ^qn ways, as shown in the following formula (8). Then, the authentication information verification unit 71 transmits the selected challenge ε to the prover side information processing device 31.

In step S34, the authentication information generation unit 52 obtains the challenge ε from the verifier side information processing device 32.

In step S35, the authentication information generation unit 52 calculates the hash value h2 by calculating the following equation (9) and transmits it to the verifier side information processing device 32.

That is, the authentication information generation unit 52 calculates, for i = 1, ..., N, [z] _i = yb · [s] _i , [w] _i = A ([s] _i ), [α] _i = ε · [w] _i + [a] _i , α = [α] ₁ + ... + [α] _N .

Furthermore, the authentication information generating unit 52 calculates [v] _i =α·[s] _i -[c] _i -ε·[z] _i for i=1, . . . , N.

Furthermore, the authentication information generating unit 52 creates a predetermined set broad _i =([α] _i , [v] _i ) for i=1, . . .

Then, the authentication information generating unit 52 generates a hash value h2=Hash(M, broad ₁ , . . . , broad _N ) by multiplying the set broad _i of i=1, . . . , N by a hash function Hash, and transmits it to the verifier side information processing device 32 .

In step S54, the authentication information verification unit 71 obtains the hash value h2 provided by the prover side information processing device 31.

In step S55, the authentication information verification unit 71 selects which of the N existing verification patterns to use, as shown in the following formula (10). That is, which of i=1, ..., N, which is the pattern of i of the seed value seed _i , is selected to use. Then, the authentication information verification unit 71 issues the selected verification pattern as a challenge ch and transmits it to the prover side information processing device 31.

In step S36, the authentication information generation unit 52 acquires the challenge ch from the verifier side information processing device 32.

In step S37, the authentication information generation unit 52 generates a response σ' by calculating the following formula (11) and transmits it as a response together with the document M to the verifier side information processing device 32.

That is, as shown by “Generate path from {seed _i } _i and ch” in equation (11), the authentication information generation unit 52 generates a value path called a seed tree path for calculating a seed value seed _i other than seed _ch , based on the seed value seed _i and the challenge ch.

In addition, the authentication information generation unit 52 generates a value view according to the challenge ch. If the challenge ch is N, the value view is the value path itself. Otherwise (if the challenge ch is other than N), the value view is {path, [s] _N , [c] _N }.

Then, the authentication information generating unit 52 generates a response σ′={view, [α] _ch , comm _ch } based on the values view, and [α] _ch , comm _ch , and transmits it together with the document M to the verifier side information processing device 32 .

In step S56, the authentication information verification unit 71 obtains the response σ' and the document M.

In step S57, the authentication information verification unit 71 calculates the following formula (12) to analyze the response σ' and calculate the hash values h1' and h2' in the challenge ch that correspond to the hash values h1 and h2 in the challenge ch.

That is, as shown in formula (12) "For i ≠ ch seed _i ← view comm _i = comm(seed _i ) [s] _i , [a] _i , [c] _i ← seed _i ", the authentication information verification unit 71 sets the seed value seed _i to view for i other than i=ch, calculates the function comm _i = comm(seed _i ) (however, for i=N, comm(seed _N , [s] _N , [c] _N )), and generates random numbers [s] _i , [a] _i , and [c] _i .

Furthermore, the authentication information verification unit 71 calculates [z] _i = y-b·[s] _i , [w] _i = A([s] _i ), [α] _i = ε·[w] _i + [a] _i for i other than i=ch. Furthermore, the authentication information verification unit 71 calculates α=[α] ₁ + ... + [α] _N . That is, the authentication information verification unit 71 calculates α by adding the sum of [α] _i other than i=ch derived using the public key pk and [α] _ch included in the response σ.

Furthermore, the authentication information verifying unit 71 calculates [v] _i =α·[s] _i -[c] _i -ε·[z] _i for i other than i=ch.

Furthermore, the authentication information verification unit 71 calculates [v] _ch =-[v] ₁ -...-[v] _N . That is, the authentication information verification unit 71 calculates [v] _ch by subtracting all [v] _i except for i=ch.

Then, the authentication information verification unit 71 calculates a set broad _i = ([α] _i , [v] _i ) for i other than i = ch. The authentication information verification unit 71 multiplies the commitment value comm _i for i = 1, ..., N by the hash function Hash to generate a hash value h1' = Hash (M, comm ₁ , ..., comm _N ). The authentication information verification unit 71 multiplies the set broad _i for i = 1, ..., N by the hash function Hash to generate a hash value h2' = Hash (M, broad ₁ , ..., broad _N ).

That is, the authentication information verifying unit 71 generates a hash value h1' using the document M, the commitment value comm _i other than i=ch derived using the public key pk, and the commitment value comm _ch for i=ch included in the response σ'.

In addition, the authentication information verification unit 71 generates a hash value h2' using the document M, the set broad _i (=([α] _i , [v] _i )) other than i=ch derived using the public key pk, and the set broad _ch (=([α] _ch , [v] _ch )) obtained from [α] ch of i= _ch included in the response σ' and the derived [v] _ch .

In other words, the authentication information verification unit 71 calculates hash values h1' and h2' corresponding to hash values h1 and h2 from the public key pk and response σ'.

In step S58, the authentication information verification unit 71 determines whether the hash values h1 and h2 obtained before generating the challenge ch match the corresponding hash values h1' and h2', as shown in formula (13).

If the two match in step S58, the process proceeds to step S59, and the authentication information verification unit 71 determines that the response σ' is valid.

If the two do not match in step S60, the process proceeds to step S60, and the authentication information verification unit 71 determines that the response σ' is not valid.

In step S61, the authentication information verification unit 71 transmits the verification result to the prover side information processing device 31.

In step S38, the authentication information generation unit 52 obtains the verification result.

Here, we will show the conversion from an authentication protocol using the Fiat-Shamir transformation to an electronic signature system. Through the above series of processes, it becomes possible to verify whether the response σ' is legitimate or not by comparing the hash values h1, h2 generated by the prover side information processing device 31 with the hash values h1', h2' generated from the response σ' based on the hash values h1, h2 in the verifier side information processing device 32 using a function that handles the Ring-MQ problem. In the above authentication protocol 11, instead of receiving the challenge ε, ch from the verifier, the prover generates the challenge ε, ch using the hash values (e.g. h1, h2) generated immediately before receiving the challenge, sets the electronic signature σ = (h1, h2, σ'), and considers the prover as the signer, thereby making it possible to apply the technology disclosed herein to the electronic signature system 1 in FIG. 1.

Furthermore, by applying the technology of the present disclosure, in the calculation of the following equation (14) for finding [z] in equations (9) and (12) when calculating the hash value h2, the number of multiplications related to _Fq is O(n log n).

On the other hand, in a digital signature verification process that uses a function that handles the conventional MQ problem, the calculation of the above-mentioned formula (14) is calculated as shown in the following formula (15).

That is, in equation (15), for i=1, . . . N, the sum of products of γ _i and (y _i −b _i [s] _i ) is calculated.

As a result, the number of multiplications related to _Fq in the calculation of formula (15) is O(n ² ). Therefore, the number of multiplications related to _Fq in the digital signature verification process using the function dealing with the Ring-MQ problem of the present disclosure, O(n log n), is smaller than the number of multiplications using a conventional function dealing with the MQ problem, O(n ² ), making it possible to reduce the amount of calculation and improve the calculation speed.

For information on an electronic signature method using functions that deal with the traditional MQ problem, please refer to "Building MPCitH-based Signatures from MQ, MinRank, RankSD and PKP Thibauld Feneuil1,2 1CryptoExperts, Paris, France 2Sorbonne Universit´e, CNRS, INRIA, Institut de Math´ematiques de Jussieu-Paris Rive Gauche, Ouragan, Paris, France". In addition, hereafter, "Building MPCitH-based Signatures from MQ, MinRank, RankSD and PKP Thibauld Feneuil1,2 1CryptoExperts, Paris, France 2Sorbonne Universit´e, CNRS, INRIA, Institut de Math´ematiques de Jussieu-Paris Rive Gauche, Ouragan, Paris, France" will be simply referred to as the reference.

In addition, since γ _i is unnecessary for i=1, . . . N, each sampling is unnecessary, so that the calculation load can be reduced.

As a result, for example, with regard to the false positive probability, in the electronic signature verification process of the present disclosure using the Ring-MQ problem (where _Rq is a field), where the degree deg f of the polynomial f used when defining _Rq := _Fq [X]/(f(X)) is (1/(q ^{deg f} )), whereas in the electronic signature verification process using a function dealing with the conventional MQ problem, the probability becomes (2/q-1/ ^q2 ), making it possible to make it smaller.

In other words, the electronic signature verification process disclosed herein can reduce the amount of calculations and improve the calculation speed, while also reducing the probability of false positives, making it possible to achieve more accurate electronic signature verification.

<Comparison of communication volume between digital signature methods using the Ring-MQ problem and the MQ problem>
Next, a comparison of communication volumes between digital signature schemes using the Ring-MQ problem and the MQ problem will be described.

According to the above reference, the amount of communication when converting the above-mentioned MPC (Multi-Party Computation) to ZKP using MPCitH (Sacrificing) is expressed by the following formula (16).

Here, λ is a security parameter, τ is the number of parallel repetitions, N is the number of parties in MPC, and cost _MPC is the part of the MPC protocol that depends on the communication volume.

Incidentally, cost _MPC is expressed as shown in Fig. 8. In Fig. 8, from the top of the figure, a partial cost MPC that depends on the communication volume of the MPC protocol and a soundness error are described from the left side of the figure for each of an electronic signature scheme that handles the MQ problem without using an extension field, an electronic signature scheme that handles the MQ problem using _an extension field, and an electronic signature scheme that handles the Ring-MQ problem of the present disclosure.

That is, in the case of a digital signature scheme that handles the MQ problem without using an extension field, the portion of the MPC protocol that depends on the amount of communication, cost _MPC , is ((2n+1)·log q), and the soundness error is (1/N+(1−1/N)·(2/q−1/q ² )).

In addition, in the case of a digital signature scheme dealing with the MQ problem using an extension field, the partial cost _MPC that depends on the communication volume of the MPC protocol is ((n+nη+η)·log q) using the parameter η used in the reference literature, and the soundness error is (1/N+(1-1/N)·(2/q ^η -1/q ^2η )).

Furthermore, in the case of the electronic signature method that deals with the Ring-MQ problem of the present disclosure, the portion of the MPC protocol that depends on the communication volume, cost _MPC , is ((3deg f)·log q), and the soundness error is (1/N+(1−1/N)·(2/q ^{deg f} )).

From these comparisons, it is clear that the electronic signature method that deals with the Ring-MQ problem disclosed herein can reduce the amount of communication when compared with electronic signature methods that deal with the MQ problem without using extension fields, and electronic signature methods that deal with the MQ problem using extension fields.

<Comparison of digital signature lengths>
Next, a comparison of the signature lengths of digital signatures in digital signature schemes using the Ring-MQ problem and the MQ problem will be described with reference to FIG.

In Figure 9, from the top right, information on the signature length for an electronic signature method that deals with the MQ problem without using an extension field, an electronic signature method that deals with the MQ problem using an extension field, and an electronic signature method that deals with the Ring-MQ problem disclosed herein is shown.

In FIG. 9 , from the right, there are the number of parties N of MPC, the order q of the field _Fq , the parameter η used in the reference literature, the degree n (=deg f) of the modulus polynomial f of _Rq , the number of parallel repetitions τ, and the signature length.

In other words, in the case of an electronic signature method that deals with the MQ problem without using an extension field, the number of MPC parties N is 256, q is 256, η is 1, n is 40, the number of parallel repetitions τ is 39, and the signature length (Signature Size) is 9463B.

In addition, in the case of an electronic signature method that uses an extension field to deal with the MQ problem, the number of MPC parties N is 256, q is 256, η is 2, n is 40, the number of parallel repetitions τ is 25, and the signature length (Signature Size) is 7114B.

In the case of the electronic signature method that deals with the Ring-MQ problem disclosed herein, the number of MPC parties N is 256, q is 256, η is -, n is 40, the number of parallel repetitions τ is 16, and the signature length (Signature Size) is 4544B.

As shown in Figure 9, it is clear that the electronic signature method disclosed herein that addresses the Ring-MQ problem can reduce the number of signatures by up to half compared to other electronic signature methods.

As a result, the electronic signature method disclosed herein that addresses the Ring-MQ problem makes it possible to improve communication speeds and processing speeds related to calculations.

As described above, the electronic signature method disclosed herein uses a function that deals with the Ring-MQ problem, making it possible to reduce the amount of calculations, improve the calculation speed, and reduce the load associated with the calculations.

In addition, it is possible to reduce communication volume and signature length, improving communication speed and reducing the load associated with communication.

By using a function that handles the Ring-MQ problem, it is possible to reduce the amount of calculation and communication, thereby reducing the load related to calculation and communication, and it is possible to make a practical electronic signature method while ensuring the security of the electronic signature method for the MQ problem.

As a result, it will be possible to realize a practical, quantum-resistant, and highly secure electronic signature system.

Note that although the above has been described as an example related to a digital signature scheme, it may also be applied to stream encryption.

<<3. Example of execution by software>>
The above-mentioned series of processes can be executed by hardware, but can also be executed by software. When the series of processes are executed by software, the programs constituting the software are installed from a recording medium into a computer built into dedicated hardware, or into, for example, a general-purpose computer capable of executing various functions by installing various programs.

Figure 10 shows an example of the configuration of a general-purpose computer. This computer has a built-in CPU (Central Processing Unit) 1001. An input/output interface 1005 is connected to the CPU 1001 via a bus 1004. A ROM (Read Only Memory) 1002 and a RAM (Random Access Memory) 1003 are connected to the bus 1004.

Connected to the input/output interface 1005 are an input unit 1006 consisting of input devices such as a keyboard and mouse through which the user inputs operation commands, an output unit 1007 which outputs a processing operation screen and images of the processing results to a display device, a storage unit 1008 consisting of a hard disk drive for storing programs and various data, and a communication unit 1009 consisting of a LAN (Local Area Network) adapter and the like, which executes communication processing via a network such as the Internet. Also connected is a drive 1010 which reads and writes data to removable storage media 1011 such as a magnetic disk (including a flexible disk), an optical disk (including a CD-ROM (Compact Disc-Read Only Memory) and a DVD (Digital Versatile Disc)), a magneto-optical disk (including an MD (Mini Disc)), or a semiconductor memory.

The CPU 1001 executes various processes according to a program stored in the ROM 1002, or a program read from a removable storage medium 1011 such as a magnetic disk, optical disk, magneto-optical disk, or semiconductor memory and installed in the storage unit 1008, and loaded from the storage unit 1008 to the RAM 1003. The RAM 1003 also stores data necessary for the CPU 1001 to execute various processes, as appropriate.

In a computer configured as described above, the CPU 1001 loads a program stored in the storage unit 1008, for example, into the RAM 1003 via the input/output interface 1005 and the bus 1004, and executes the program, thereby performing the above-mentioned series of processes.

The program executed by the computer (CPU 1001) can be provided, for example, by recording it on a removable storage medium 1011 such as a package medium. The program can also be provided via a wired or wireless transmission medium such as a local area network, the Internet, or digital satellite broadcasting.

In a computer, a program can be installed in the storage unit 1008 via the input/output interface 1005 by inserting the removable storage medium 1011 into the drive 1010. The program can also be received by the communication unit 1009 via a wired or wireless transmission medium and installed in the storage unit 1008. Alternatively, the program can be pre-installed in the ROM 1002 or storage unit 1008.

The program executed by the computer may be a program in which processing is performed chronologically in the order described in this specification, or a program in which processing is performed in parallel or at the required timing, such as when called.

Note that the CPU 1001 in FIG. 10 realizes the functions of the control unit 101 in FIG. 5 and the control unit 131 in FIG. 6.

In addition, in this specification, a system refers to a collection of multiple components (devices, modules (parts), etc.), regardless of whether all the components are in the same housing. Therefore, multiple devices housed in separate housings and connected via a network, and a single device in which multiple modules are housed in a single housing, are both systems.

Note that the embodiments of this disclosure are not limited to the above-described embodiments, and various modifications are possible without departing from the spirit of this disclosure.

For example, the present disclosure can be configured as a cloud computing system in which a single function is shared and processed collaboratively by multiple devices over a network.

In addition, each step described in the above flowchart can be executed by a single device, or can be shared and executed by multiple devices.

Furthermore, when one step includes multiple processes, the multiple processes included in that one step can be executed by one device, or can be shared and executed by multiple devices.

The present disclosure can also be configured as follows.
<1> s∈R _q is set as a private key, and F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function is set as a public key,
generating a digital signature based on the private key;
verifying, by using the public key, whether the electronic signature is authentic.
<2> The information processing method according to <1>, wherein the public key is F(s)=(A, b, y) consisting of a multi-degree multivariate polynomial that forms the Ring-MQ function, where y=s·A(s)+b·s.
<3> The private key is kept private by the certifier;
The public key is publicly available and is shared with a verifier who verifies whether the electronic signature is authentic;
a prover device operated by the prover generates the digital signature based on a challenge provided by a verifier device operated by the verifier, the private key, and the public key;
The information processing method according to <1>, wherein the verifier device verifies the electronic signature based on the challenge and the public key.
<4> The information processing method according to <3>, wherein the challenge is generated by an algorithm based on the Fiat-Shamir transformation.
<5> The information processing method according to <3>, wherein the challenge is information selected by the verifier by operating the verifier side device.
<6> The prover device,
generating a first hash value based on a plurality of random numbers based on a seed value having a pattern of 1, . . . , N and a first calculation result calculated from the private key, and transmitting the first hash value to the verifier device;
receiving a pattern selected by the verifier from the patterns 1, . . . , N provided by the verifier device as a challenge;
generating the digital signature based on the random number corresponding to the challenge pattern and the first calculation result, and transmitting the digital signature to the verifier device;
The verifier device includes:
receiving the first hash value from the prover device;
transmit a pattern selected by the verifier from the patterns 1, . . . , N as a challenge to the prover device;
The information processing method described in <3>, further comprising: calculating a value corresponding to the first hash value from the electronic signature based on the pattern selected as the challenge, the public key, and information contained in the electronic signature; and verifying the electronic signature based on whether or not it matches the first hash value received from the prover device.
<7> The prover side device,
generating a first hash value based on a plurality of random numbers based on the seed value having the pattern of 1, . . . , N and a first calculation result calculated from the private key, and transmitting the first hash value to the verifier device;
receiving a random number selected by the verifier from an element of the ring _Rq having q ⁿ ways, the selected random number being supplied from the verifier side device;
generating a second hash value different from the first hash value based on a second calculation result calculated from the plurality of random numbers, the selected random number, and the public key, and transmitting the second hash value to the verifier device;
receiving a pattern selected by the verifier as a challenge;
generating the electronic signature based on a random number corresponding to the challenge pattern, the first calculation result, and the second calculation result, and transmitting the electronic signature to the verifier device;
The verifier device includes:
receiving the first hash value;
transmitting the selected random number to the prover device;
receiving the second hash value transmitted from the prover device;
sending said pattern as a challenge to said prover device;
The information processing method described in <6>, further comprising: calculating values corresponding to the first hash value and the second hash value from the electronic signature based on the pattern selected as the challenge, the public key, and information contained in the electronic signature; and verifying the electronic signature based on whether or not the first hash value and the second hash value received from the prover device match.
<8> A key generation unit that sets _s∈Rq as a private key and sets F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function as a public key;
an electronic signature generating unit that generates an electronic signature based on the private key;
and an electronic signature verification unit that verifies whether the electronic signature is authentic using the public key.
<9> A key generation unit that sets _s∈Rq as a private key and sets F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function as a public key;
an electronic signature generating unit that generates an electronic signature based on the private key;
A program that causes a computer to function as an electronic signature verification unit that verifies whether the electronic signature is authentic using the public key.

11 Authentication protocol, 31 Prover side information processing device, 32 Verifier side information processing device, 51 Key generation unit, 52 Authentication information generation unit, 71 Authentication information verification unit

Claims (9)

_s∈Rq is set as a private key, and F(s) consisting of a multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function is set as a public key,
generating a digital signature based on the private key;
verifying, by using the public key, whether the electronic signature is authentic. 2. The information processing method according to claim 1, wherein the public key is F(s)=(A, b, y) consisting of a multi-degree multivariate polynomial forming the Ring-MQ function, where y=s·A(s)+b·s. the private key is kept private by the certifier;
The public key is publicly available and is shared with a verifier who verifies whether the electronic signature is authentic;
a prover device operated by the prover generates the digital signature based on a challenge provided by a verifier device operated by the verifier, the private key, and the public key;
The information processing method according to claim 1 , wherein the verifier device verifies the electronic signature based on the challenge and the public key. The information processing method according to claim 3 , wherein the challenge is generated by an algorithm based on the Fiat-Shamir transformation. The information processing method according to claim 3 , wherein the challenge is information selected by the verifier by operating the verifier side device. The prover device includes:
generating a first hash value based on a plurality of random numbers based on a seed value having a pattern of 1, . . . , N and a first calculation result calculated from the private key, and transmitting the first hash value to the verifier device;
receiving a pattern selected by the verifier from the patterns 1, . . . , N provided by the verifier device as a challenge;
generating the digital signature based on the random number corresponding to the challenge pattern and the first calculation result, and transmitting the digital signature to the verifier device;
The verifier device includes:
receiving the first hash value from the prover device;
transmit a pattern selected by the verifier from the patterns 1, . . . , N as a challenge to the prover device;
4. The information processing method according to claim 3, further comprising: calculating a value corresponding to the first hash value from the electronic signature based on the pattern selected as the challenge, the public key, and information contained in the electronic signature; and verifying the electronic signature based on whether or not it matches the first hash value received from the prover device. The prover device includes:
generating a first hash value based on a plurality of random numbers based on the seed value having the pattern of 1, . . . , N and a first calculation result calculated from the private key, and transmitting the first hash value to the verifier device;
receiving a random number selected by the verifier from an element of the ring _Rq having q ⁿ ways, the selected random number being supplied from the verifier side device;
generating a second hash value different from the first hash value based on a second calculation result calculated from the plurality of random numbers, the selected random number, and the public key, and transmitting the second hash value to the verifier device;
receiving a pattern selected by the verifier as a challenge;
generating the electronic signature based on a random number corresponding to the challenge pattern, the first calculation result, and the second calculation result, and transmitting the electronic signature to the verifier device;
The verifier device includes:
receiving the first hash value;
transmitting the selected random number to the prover device;
receiving the second hash value transmitted from the prover device;
sending said pattern as a challenge to said prover device;
7. The information processing method according to claim 6, further comprising: calculating values corresponding to the first hash value and the second hash value from the electronic signature based on the pattern selected as the challenge, the public key, and information contained in the electronic signature; and verifying the electronic signature based on whether or not the first hash value and the second hash value received from the prover device match. a key generation unit that sets _s∈Rq as a private key and sets F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function as a public key;
an electronic signature generating unit that generates an electronic signature based on the private key;
and an electronic signature verification unit that verifies whether the electronic signature is authentic using the public key. a key generation unit that sets _s∈Rq as a private key and sets F(s) consisting of a multi-degree multivariate polynomial forming a Ring-MQ (Multivariate Quadratic) function as a public key;
an electronic signature generating unit that generates an electronic signature based on the private key;
A program that causes a computer to function as an electronic signature verification unit that verifies whether the electronic signature is authentic using the public key.

Images