This post describes a modification of the Schnorr identification protocol which is compatible with the instant digital signature mode.

**Introduction**

The __article__ describes the interactive Schnorr identification protocol (hereinafter referred to as the Schnorr protocol) and formulates the problem of compatibility of this protocol with the instant digital signature (IDS) mode. This post shows how to modify the Schnorr protocol to provide such compatibility.

**IDS-compatible Schnorr protocol**

Recall that some information about the arithmetic of elliptic curve points, as well as an explanation of ECDLP and DLP, was explained by our __previous publication__.

For the sake of simplicity, we will leave everything that concerns the Schnorr protocol unchanged, including the key pair and the certificate

If we interpret the __necessary condition__, then IDS-compatibility is possible when and are able to compute some common secret component. Such a component can be expressed as a shared session secret key. We will show how to do this using the example of the Schnorr protocol. Let's denote the cryptographic hash function as

Let's make some changes to the protocol. Let's use the following trick: we'll "hide" the ephemeris at a point on the curve. This causes also turn into a point. As a result, we get the following protocol.

*Protocol messages.*

1.

2.

3.

*The actions of the parties.*

demonstrates to that he posesses (knows) In order to achieve this, the subsequent actions are executed:

1. selects computes verifies the condition If then it chooses a new and repeats all the necessary computations and checks;

2. reads an actual certificate and checks the DS where is the trusted party's public key If then the session ends. If then it selects and computes (). If then it selects a new and repeats all the necessary computations and checks;

3. checks the condition if it is true, then it computes ), otherwise the session ends;

4. computes Then it checks If equal then the proof is accepted, and rejected otherwise.

So, suppose that the identification step was successful and accepted the proof provided by

At this point, has the following set of data: ( by construction), (received from as a ). knows (received from as a ), (by construction), (received from as a ).

The parties independently compute a shared session secret key in accordance with the following rules:

computes

computes

Obviously, due to commutativity. Therefore, As for the IDS, then:

1. generates a signature for the given message using given the value of the hash function

2. checks the signature for some message using given the hash function value

The advantage of the above mentioned solution is that the changes relate to arithmetic operations and do not affect the logic of the protocol. This is an important circumstance, since any fundamental modifications would lead to the need to study the cryptographic strength of the new design with all the ensuing consequences.

Earlier, we noted that we have a protocol with similar functionality that solves this problem, but at the same time allows us to recognize that the prover belongs to a certain local community of registered participants.

**Preliminary analysis**

Let's note that are only known to and respectively. Then an attacker can get or by finding an ECDLP solution given or respectively. It is also possible to find a DLP solution if or The purpose of the function, as well as the relationship between ECDLP and DLP, is explained in __Appendix A__. Since only someone who knows or as well as the secret key of an arbitrary DS scheme chosen for this goal is able to generate the IDS.

An active attacker, using interception and blocking techniques, is able to impose instead of instead of and instead of when For example, these may be messages from another session. However, will overwhelmingly reject the provided proof, since and with negligible probability. In addition, and with negligible probability.

**The amount of information transmitted**

We will use the compact curve point representation [Cohen_etc._2006] (section 13.2.5).

The point is given by a pair of coordinates If belongs to the curve, then the equation is true for some This equation can be interpreted as where is a quadratic residue and then there are only two solutions For the solution is If is even, then is odd, and vice versa. In the general case, of two solutions, one is always even and the other is odd.

Let the point be represented by the coordinate We will transmit over the communication channel where is a binary variable that allows us to determine the desired solution from a pair of possible ones. Let's make it a rule that means even, and means odd. For example, for one should get a pair and then choose an odd solution from this pair.

bits of memory is required to store an arbitrary point on the curve. In the square root is computed using the Tonelli-Shanks algorithm of asymptotic computational complexity [Cohen_etc._2006] (section 11.1.5).

Then, to restore the point, it's necessary to perform the following actions:

1. For a given coordinate a certain coordinate is computed using the Tonelli-Shanks algorithm.

2. If then

3. If then

4. If then

5. If then

If the compact representation is used, then bits would need to be transmitted to deliver and in total. For comparison, in the original Schnorr protocol, under the same conditions, for the delivery of and in total, it is necessary to send bits.

**Computation optimization**

The complexity depends on the methods for computing the scalar multiplication, as well as the choice of the computing platform. Thus, for example, tests that were carried out using a test bench implemented in the Scala v2.13.6 programming language on a MacBook Pro (15-inch, 2016) hardware platform with a 4-core Intel Core i7 processor running macOS Monterey version 12.6.2 using primitives from the __PBC library__ show that due to the preprocessing possible for the constant the scalar product is on average 85.37% more efficient than the scalar products where The measurement results are summarized in Table 1.

**IDS mode and public key certificates**

owns the key pair A corresponding certificate is issued for the public key The following question needs to be answered: what benefit can be gained from the IDS mode with a public key certificate?

Let the certificate be issued for the public key where — DS of trusted party — personal data of and — secret key of intended for generating the certificate's DS.

Let's set up a thought experiment and, in the absence of the DS mode, assume that sends some digitally certified personal data Furthermore, claims that is his own personal data. It should be noted right away that this data could have been obtained in various ways, for example, as a result of collusion, the use of social engineering methods, or simply copied from publicly available long-term memory. To verify the digital signature, must use the public key from the certificate Let's also assume that all necessary checks have confirmed the authenticity and integrity of

As a result, has two certificates and each issued by a trusted CA. Consider the case when is treated uniquely). As a result, is unable to make a correct choice about or because there is no decision criterion. Obviously, such uncertainty is unacceptable.

If the IDS mode is enabled, then when making a decision about or relies on the proof that was provided to at the identification stage. reasons using the following logic.

A DS for personal data can only be generated by someone who simultaneously has access to the variables of a separate identification protocol session, both public and secret, including the secret key for generating a DS.

Let's assume that the digital signature was obtained as a result of collusion. To do this, an attacker must force the owner of personal data to certify this data with his DS, but with the inclusion of some auxiliary data, about which the certifier does not know anything. Based on the associated risk model, such an event seems implausible. It is overwhelmingly likely that the witness will refuse to include such data fearing undesirable consequences, such as implicit debt imposition, blacklisting, account blocking, and so on.

**Open verification in the Schnorr protocol**

The peculiarity of the Schnorr protocol is that anyone with access to the variables and can verify the correctness of the evaluation made by towards the proof given by

Indeed, the variables mentioned above are transmitted over an insecure communication channel and, therefore, are publicly available. Since anyone can use the public key it is not necessary to have authority to compute and then check

The practical meaning here is the ability to control the actions of both and This is important in the case when disagreements may arise. For example, when claims to have provided the correct proof, but denies it.

**Summary**

Estimates of the amount of transmitted information for the original Schnorr protocol and the modification described above differ insignificantly.

The original Schnorr protocol uses three scalar multiplications, while the modification of the protocol uses four such multiplications. Since the scalar multiplications and are computed using the generating element the optimization is possible. This optimization allows to reduce computational complexity in exchange for the allocation of additional memory for storing intermediate results (see Table 1). Note that in the original protocol, when computing the point only partial optimization is allowed. However, in the modified protocol, when computing the points and as well as the scalar multiplications and such optimization is impossible.

In the proposed modification of the protocol, open verification is not feasible.

**Conclusion**

It should be attested that we were able to solve the problem for a particular protocol in a relatively simple way. However, for an arbitrary identification protocol, the problem of compatibility with the IDS mode remains open. In the future, we will attempt to find a solution to the problem for some well-known identification protocol that is different from the Schnorr protocol.

The text of the article in pdf format can be downloaded here.

**Bibliography**

[Cohen_etc._2006] Cohen, H., Frey, G., Roberto Avanzi, R., Doche C., Lange, T., Nguyen, K. and Vercauteren, F. Handbook of Elliptic and Hyperelliptic Curve Cryptography, Chapman and Hall /CRC, 2006.