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 $\{\mathbf{x},\mathsf{R}=[-\mathbf{x}]\mathsf{G}_1\}$ and the certificate $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}.$

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 $\hslash(\cdot).$

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

Protocol messages.

1. $P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1$

2. $P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{G}_1$

3. $P \longrightarrow V : \mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}$

The actions of the parties.

demonstrates to that he posesses (knows) $\mathbf{x}.$ In order to achieve this, the subsequent actions are executed:

1. selects $\upsilon\in_R\!(0,m-1] (\textit {commitment}),$ computes $\mathsf{S}=[\upsilon]\mathsf{G}_1 (\textit {witness}),$ verifies the condition $\mathsf{S}\stackrel{?}\neq\infty.$ If $\mathsf{S}=\infty$ then it chooses a new $\upsilon$ and repeats all the necessary computations and checks;

2. reads an actual certificate $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ and checks the DS $\mathfrak{B}\Leftarrow{\rm{Verify}}( \hslash(\mathsf{R}||D_{\mathsf{R}}), \Im_{\mathsf{R}}, \rm{P}_T),$ where $\rm{P}_T$ is the trusted party's public key If $\mathfrak{B}=False$ then the session ends. If $\mathfrak{B}=True$ then it selects $\phi\in_R\!(0, m-1]$ and computes $\mathsf{T}=[\phi]\mathsf{G}_1$ ( $\textit{challenge}$ ). If $\mathsf{T}=\infty$ then it selects a new $\phi$ and repeats all the necessary computations and checks;

3. checks the condition $\mathsf{T}\stackrel{?}\neq\infty,$ if it is true, then it computes $\mathsf{N}=[\mathbf{x}]\mathsf{T}+\mathsf{S}=[\mathbf{x}\phi+\upsilon \pmod m]\mathsf{G}_1$ $(\textit{response}$ ), otherwise the session ends;

4. computes $\mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R}.$ Then it checks $x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}.$ 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: $\upsilon$ ( $\textit{commitment}$ by construction), $\mathsf{T}$ (received from as a $\textit{challenge}$ ). knows $\mathsf{S}$ (received from as a $\textit{witness}$ ), $\phi$ (by construction), $\mathsf{N}$ (received from as a $\textit{response}$ ).

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

computes $\mathsf{A}=[\upsilon]\mathsf{T}=[\upsilon\phi\pmod m]\mathsf{G}_1,$ $g_1=\hslash(x_{\mathsf{A}}\|y_{\mathsf{A}}).$

computes $\mathsf{B}=[\phi]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1,$ $g_3=\hslash(x_{\mathsf{B}}\|y_{\mathsf{B}}).$

Obviously, $\mathsf{A}=\mathsf{B}$ 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 $\hslash(g_1\|M\|\ldots).$

2. checks the signature for some message using given the hash function value $\hslash(g_3\|M'\|\ldots).$

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 $\upsilon, \phi$ are only known to and respectively. Then an attacker can get $\upsilon$ or $\phi$ by finding an ECDLP solution given $\mathsf{S}$ or $\mathsf{T}$ respectively. It is also possible to find a DLP solution if $e_m(\mathsf{S}, \mathsf{G}_1)$ or $e_m(\mathsf{T}, \mathsf{G}_1).$ The purpose of the $e_m(\cdot, \cdot)$ function, as well as the relationship between ECDLP and DLP, is explained in Appendix A. Since only someone who knows $\upsilon$ or $\phi,$ 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 $\mathsf{S}'=[\upsilon']\mathsf{G}_1$ instead of $\mathsf{S},$ $\mathsf{T}'=[\phi']\mathsf {G}_1$ instead of $\mathsf{T}$ and $\mathsf{N}'=[\mathbf{x}]\mathsf{T}'+\mathsf{S}'$ instead of $\mathsf{N}$ when $\upsilon'\neq \upsilon, \phi'\neq\phi.$ For example, these may be messages from another session. However, will overwhelmingly reject the provided proof, since $\mathsf{Q}'=\mathsf{N}'+[\phi]\mathsf{R}=[\mathbf{x}(\phi'-\phi)+ \upsilon'\pmod m]\mathsf{G}_1$ and $x_{\mathsf{Q}'}=x_{\mathsf{S}'}$ with negligible probability. In addition, $\mathsf{A}'=[\upsilon]\mathsf{T}'=[\upsilon\phi'\pmod m]\mathsf{G}_1,$ $\mathsf{B}'=[\phi]\mathsf{S}'=[\phi\upsilon'\pmod m]\mathsf{G}_1$ and $\mathsf{A}'=\mathsf{B}'$ 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 $\mathsf{Q}$ is given by a pair of coordinates $x_{\mathsf{Q}}, y_{\mathsf{Q}} \in\mathbb{F}_p.$ If $\mathsf{Q}$ belongs to the curve, then the equation $y_{\mathsf{Q}}^2=x_{\mathsf{Q}}^3+ax_{\mathsf{Q}}+b$ is true for some $a, b\in\mathbb{F }_p.$ This equation can be interpreted as $y_{\mathsf{Q}}^2 \equiv r \bmod p,$ where is a quadratic residue and then there are only two solutions $\pm y_\mathsf{Q}.$ For $y_\mathsf{Q}<p$ the solution is $-y_\mathsf{Q}\bmod p=p-y_\mathsf{Q}.$ If $y_{\mathsf{Q}}$ is even, then $(p-y_{\mathsf{Q}})$ is odd, and vice versa. In the general case, of two solutions, one is always even and the other is odd.

Let the point $\mathsf{Q}$ be represented by the coordinate $x_{\mathsf{Q}}.$ We will transmit over the communication channel $(x_{\mathsf{Q}}, \mathfrak{s}),$ where $\mathfrak{s}$ 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 $\mathfrak{s}=0$ means even, and $\mathfrak{s}=1$ means odd. For example, for $(x_\mathsf{Q}, 1)$ one should get a pair $\{y_{\mathsf{Q}}, p-y_{\mathsf{Q}}\}$ and then choose an odd solution from this pair.

$\lceil\log_{2}p\rceil+1$ bits of memory is required to store an arbitrary point on the curve. In $\mathbb{F}_p,$ the square root is computed using the Tonelli-Shanks algorithm of asymptotic computational complexity $O(\log_{2}^2{p})$ [Cohen_etc._2006] (section 11.1.5).

Then, to restore the $\mathsf{Q}$ point, it's necessary to perform the following actions:

1. For a given coordinate $x_{\mathsf{Q}},$ a certain coordinate is computed using the Tonelli-Shanks algorithm.

2. If $(\mathfrak{s}=1)\land(y_*\bmod 2\neq 0)$ then $y_\mathsf{Q}=y_*.$

3. If $(\mathfrak{s}=1)\land(y_*\bmod 2=0)$ then $y_\mathsf{Q}=p-y_*.$

4. If $(\mathfrak{s}=0)\land(y_*\bmod 2=0)$ then $y_\mathsf{Q}=y_*.$

5. If $(\mathfrak{s}=0)\land(y_*\bmod 2\neq 0)$ then $y_\mathsf{Q}=p-y_*.$

If the compact representation is used, then $3(\lceil\log_{2}{p}\rceil+1)$ bits would need to be transmitted to deliver $\mathsf{S},$ $\mathsf{T},$ and $\mathsf{N}$ in total. For comparison, in the original Schnorr protocol, under the same conditions, for the delivery of $\mathsf{S}, \phi$ and $\psi$ in total, it is necessary to send $2(\lceil\log_{2}m\rceil)+\lceil\log_{2}p \rceil+1$ 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 $\mathsf{G}_1,$ the scalar product $\mathsf{Q}_1=[\alpha]\mathsf{G}_1$ is on average 85.37% more efficient than the scalar products $\mathsf{Q}_2=[\alpha]\mathsf{P},$ where $\mathsf{P}\neq\mathsf{G}_1\neq const.$ The measurement results are summarized in Table 1.

IDS mode and public key certificates

owns the key pair $\{\mathbf{x}, \mathsf{R}\}.$ A corresponding certificate is issued for the public key $\mathsf{R}.$ The following question needs to be answered: what benefit can be gained from the IDS mode with a public key certificate?

Let the certificate $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ be issued for the public key $\mathsf{R},$ where $\Im_{\mathsf{R}} \Leftarrow{\rm{Sign}}(\hslash(\mathsf{R}||D_{\mathsf{R}}), \rm{S}_T)$ — DS of trusted party $D_{\mathsf{R} }$ — personal data of and $\rm{S}_T$ — 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 $\mathsf{P}'$ from the certificate $\{D',\mathsf{P}', \Im_{\mathsf{P}'}\}.$ Let's also assume that all necessary checks have confirmed the authenticity and integrity of $\mathsf{P}', D'.$

As a result, has two certificates $\{D_{\mathsf{R}},\mathsf{R}, \Im_{\mathsf{R}}\}$ and $\{D',\mathsf{P}', \Im_{ \mathsf{P}'}\},$ each issued by a trusted CA. Consider the case when $D_{\mathsf{R}}\neq D' (D_{\mathsf{R}}=D'$ is treated uniquely). As a result, is unable to make a correct choice about $D_{\mathsf{R}}$ or because there is no decision criterion. Obviously, such uncertainty is unacceptable.

If the IDS mode is enabled, then when making a decision about $D_{\mathsf{R}}$ 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 $\mathsf{S}, \phi,$ and $\psi$ 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 $\mathsf{R},$ it is not necessary to have authority to compute $\mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R}= [\psi-\phi\mathbf{x}\pmod m]\mathsf{G}_1$ and then check $x_{\mathsf{Q}}\stackrel{?}{=}x_{\mathsf{S}}.$

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 $\mathsf{S}=[\upsilon]\mathsf{G}_1$ and $\mathsf{T}=[\phi]\mathsf{G}_1$ are computed using the generating element $\mathsf{G}_1,$ 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 $\mathsf{Q}=[\psi]\mathsf{G}_1+[\phi]\mathsf{R},$ only partial optimization is allowed. However, in the modified protocol, when computing the points $\mathsf{N}$ and $\mathsf{Q}=\mathsf{N}+[\phi]\mathsf{R},$ as well as the scalar multiplications $\mathsf{A}=[\upsilon]\mathsf{T}$ and $\mathsf{B}=[\phi]\mathsf{S}$ 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.

On Schnorr identification protocol compatibility with instant digital signature mode