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
),
(by construction),
(received from
as
).
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.
![](https://webcf.waybackmachine.org/web/20230720012135/https://habrastorage.org/getpro/habr/upload_files/5f0/854/b10/5f0854b10500a872594ef2c07ee9d80d.png)
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.