ENCRY 16 авг 2023 в 11:05

Pairing-based identification protocols compatible with instant digital signature mode

9 мин

662

In our previous post, we presented a modified Schnorr protocol compatible with the Instant Digital Signature (IDS) mode and also announced the design of other protocols with this feature. In this post we describe such protocols based on the pairing function.

Introduction

The following text is dedicated to the description of two digital signature (DS) schemes based on the pairing function (Appendix A). These schemes are then transformed into IDS-compatible identification protocols. We specified and investigated the problem of impersonation, that is, the substitution of one party involved in protocol, with another one. The achieved result consists in the design and analysis of a new IDS-compatible identification protocol, with impersonation presumably impossible for it.

We will use the abbreviation v.s.p. to denote a vanishingly small probability. This means that for some $\alpha\in\mathbb{F}_m$ and $\beta$ distributed uniformly and independently on the interval otherwise ${\beta\in_R\! (0,m-1]},$ ${\Pr[\alpha=\beta]=m^{-1}}$ and for large this probability is vanishingly small. For example, $\Pr[\alpha=\beta]\sim 10^{-49}$ for $m\sim 2^{160}.$ A similar argument applies to $\Pr[g^{\alpha}=g^{\beta}],$ where is a generator of $\mathbb{G}_3$ (Appendix A).

When describing DS schemes and identification protocols, we will proceed from the assumption that there is a pair of linked keys $\{\mathbf{x},\mathsf{P}=[\mathbf{x}]\mathsf{G}_1\},$ where $\mathbf{x}$ is a secret key, ${\mathbf{x}\in_R\!(0,m-1]},$ and $\mathsf{P}$ is a public one for which a certificate $\{D,\mathsf{P}, \Im_{\rm{T}}\}$ is issued. In this certificate, is the personal data of the owner of $\mathsf{P},$ $\Im_{\rm{T}}$ is the DS of the trusted party $\rm{T}$ (the certification authority responsible for issuing and maintaining certificates).

Let's call the functions of signing and verifying the digital signature as ${\rm{Sign}}(\cdot,\cdot)$ and ${\rm{Verify}}(\cdot,\cdot,\cdot),$ respectively. Let's denote the cryptographic hash function by $\hslash(\cdot)$ (Appendix B). Then $\Im_{\rm{T}}\Leftarrow{\rm{Sign}}(\hslash(\mathsf{P}||D), \rm{S}_{\rm{T}}),$ where $\rm{S}_{\rm{T}}$ is the secret key of the trusted party $\rm{T},$ consigned for signing.

Before use, $\mathsf{P}$ is checked for authenticity, integrity, and relevance. The latter task is done by checking a list of revoked certificates. $\mathfrak{B}\Leftarrow{\rm{Verify}}(\hslash(\mathsf{P}||D), \Im_{\rm{T}}, \rm{P}_{\rm{T}})$ is computed, where $\rm{P}_{\rm{T}}$ is the public key of trusted party $\rm{T}.$ If $\Im_{\rm{T}}$ is valid, then the boolean variable $\mathfrak{B}=True$ and this means integrity, authenticity of $\mathsf{P}$ and otherwise $\mathfrak{B}=False.$ The trusted party can use any DS scheme, for example, one of those described below.

For the sake of simplicity, let's assume that different DS schemes and identification protocols use the same public key $\mathsf{P}.$

It should be noted that most of the known DS schemes use simple equations. This is important, because this simplifies their understanding and analysis. We will be guided by the same $\textit{modus operandi}$ when design identification protocols.

DS schemes based on pairing

Hereinafter let's call the one who sign the message ${M\in\{0,1\}^*}$ as the $\textit{witness}.$ Below there are descriptions of two DS schemes based on pairing (Appendix A).

In the DS scheme [Zhang_Safavi-Naini_Susilo_2004] for a given message the witness performs the following actions:

Computes $\phi=\hslash(M).$
Generates the signature $\mathsf{S}=[\frac{1}{\phi+\mathbf{x}\pmod m}]\mathsf{G}_1=[\psi]\mathsf{G}_1.$

Let there be some signature $\mathsf{S}'=[\psi']\mathsf{G}_1$ and a message The verifier performs the following actions:

Computes $\phi'=\hslash(M').$
Checks the authenticity, integrity and relevance of $\mathsf{P},$ if the relevance is not confirmed or $\mathfrak{B}=False,$ then it completes the verification of the DS.
Computes $g'=e_m([\phi']\mathsf{G}_1+ \mathsf{P}, \mathsf{S}')=e_m([\phi'+\mathbf{x}\pmod m]\mathsf{G}_1, [\psi']\mathsf{G}_1)=g^{\psi'(\phi'+\mathbf{x})\pmod m}.$
Checks $g'\stackrel{?}{=}e_m(\mathsf{G}_1, \mathsf{G}_1).$

Then if $(\psi'=\psi)\land(\phi'=\phi)\Rightarrow (M'=M)\land(\mathsf{S'}=\mathsf{S}).$ If $(\psi'\neq\psi)\lor(\phi'\neq\phi)$ then with v.s.p.

It is clear that $g=e_m(\mathsf{G}_1, \mathsf{G}_1)$ is computed only once and stored in the local long-term memory. Authenticity and integrity of needs to be guaranteed. For example, it can be stored in secure memory along with the secret key $\mathbf{x}.$

Let's look at another DS scheme from [Boneh_Shacham_Lynn_2004]. There is a given hash function $H:\{0,1\}^*\mapsto\mathbb{G}_1$ (Appendix B). The witness performs the following steps:

Computes $\mathsf{Q}=H(M)=[\upsilon]\mathsf{G}_1.$
Generates the signature $\mathsf{S}=[\mathbf{x}]\mathsf{Q}=[\mathbf{x}\upsilon\pmod m]\mathsf{G}_1.$

There is a message and signature $\mathsf{S}'.$ The verifier does the following steps:

Computes $\mathsf{Q}'=H(M').$
Checks the authenticity, integrity and relevance of $\mathsf{P},$ if the relevance is not confirmed or $\mathfrak{B}=False,$ then it completes the verification of the DS.
Checks $e_m(\mathsf{P},\mathsf{Q}')\stackrel{?}{=}e_m(\mathsf{G}_1,\mathsf{S}').$

If $\mathsf{Q}'=\mathsf{Q}=[\upsilon]\mathsf{G}_1$ and $\mathsf{S}'=\mathsf{S}=[\mathbf{x}\upsilon\pmod m]\mathsf{G}_1,$ then, due to the bilinearity, $e_m(\mathsf{P},\mathsf{Q}')=e_m([\mathbf{x}]\mathsf{G}_1, [\upsilon]\mathsf{G}_1)=e_m([\mathbf{x}\upsilon\pmod m]\mathsf{G}_1, \mathsf{G}_1)=e_m(\mathsf{G}_1, \mathsf{G}_1)^{\mathbf{x}\upsilon\pmod m}=g^{\mathbf{x}\upsilon\pmod m}.$ If $\mathsf{Q}'\neq\mathsf{Q}$ and/or $\mathsf{S}'\neq\mathsf{S},$ then $e_m(\mathsf{P},\mathsf{Q}')= e_m(\mathsf{G}_1,\mathsf{S}')$ with v.s.p.

Both above-mentioned DS schemes use the $e_m(\cdot, \cdot)$ pairing function, but differ in computational complexity of check. In the [Zhang_Safavi-Naini_Susilo_2004] scheme, when checking the DS, only one pairing is computed, while in [Boneh_Shacham_Lynn_2004] it is necessary to compute two pairings.

IDS-compatible identification protocols based on pairing

According to the Fiat-Shamir heuristic [Fiat_Shamir_1987], each DS scheme has its own identification protocol. However, we will be interested in IDS-compatible versions of such protocols.

Below there is a description of the IDS-compatible identification protocol for the DS scheme from [Zhang_Safavi-Naini_Susilo_2004].

Protocol 1

Protocol messages.

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1$
$P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{G}_1$
$P \longrightarrow V : \mathsf{N}=[(\upsilon+\mathbf{x}\pmod m)^{-1}]\mathsf{T}$

Actions of the parties.

proves to that it owns (knows) $\mathbf{x}.$ To do this, the following steps are performed:

selects ${\upsilon\in_R\!(0,m-1]}$ $(\textit{commitment}),$ computes $\mathsf{S}=[\upsilon]\mathsf{G}_1$ $(\textit{witness}),$ checks $\mathsf{S}\stackrel{?}\neq\infty.$ If $\mathsf{S}=\infty$ then selects a new $\upsilon,$ re-executes the necessary computations and checks.
reads the current certificate $\{D,\mathsf{P}, \Im_{\rm{T}}\}$ and checks the DS of the trusted party $\rm{T}.$ If $\mathfrak{B}=False$ then the session ends. If $\mathfrak{B}=True$ then it chooses ${\phi\in_R\!(0, m-1]}$ and computes $\mathsf{T}=[\phi]\mathsf{G}_1$ $(\textit{challenge}).$ If $\mathsf{T}=\infty,$ then it chooses a new $\phi$ and re-executes the necessary computations and checks.
checks $\mathsf{T}\stackrel{?}\neq\infty,$ if it is true, it computes $\mathsf{N}=[(\upsilon+\mathbf{x}\pmod m)^{- 1}]\mathsf{T}=[\frac{\phi}{\upsilon+\mathbf{x}\pmod m}\pmod m]\mathsf{G}_1$ $(\textit{response})$ otherwise the session ends.
computes $g_2=e_m([\phi^{-1}]\mathsf{S}+[\phi^{-1}]\mathsf{P}, \mathsf{N})=e_m([\phi^{-1}(\upsilon+\mathbf{x})\pmod m]\mathsf{G}_1, \mathsf{N}).$ Then it checks $g_2\stackrel{?}{=}g.$ If equal, then the proof is accepted, and rejected otherwise.

Now let's see what IDS-compatible protocol can be proposed for the DS scheme from [Boneh_Shacham_Lynn_2004].

Protocol 2

Protocol messages.

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{G}_1$
$P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{G}_1$
$P \longrightarrow V : \mathsf{N}=[\upsilon\mathbf{x}\pmod m]\mathsf{T}$

Actions of the parties.

proves to that it owns (knows) $\mathbf{x}.$ To do this, the following steps are performed:

As in Protocol 1.
As in Protocol 1.
checks ${\mathsf{T}\stackrel{?}\neq\infty},$ if it is true, it computes ${\mathsf{N}=[\upsilon\mathbf{x}\pmod m]\mathsf{T}=[\phi\upsilon\mathbf{x}\pmod m]\mathsf{G}_1}$ $(\textit{response}),$ otherwise the session ends.
computes $g_2=e_m([\phi]\mathsf{S}, \mathsf{P})=g^{\phi\upsilon\mathbf{x}\pmod m}.$ Then it checks $g_2\stackrel{?}{=}e_m(\mathsf{N}, \mathsf{G}_1).$ If equal, then the proof is accepted, and rejected otherwise.

For Protocols 1 and 2, in case of successful completion of the identification stage, 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.$
computes $\mathsf{B}=[\phi]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1.$

Obviously, $\mathsf{A}=\mathsf{B}$ due to commutativity.

Impersonation of the verifier

An active attack includes a set of measures taken to replace the information that the parties exchange with each other during the identification protocol. Protocol 1 and Protocol 2 are reliable provided that the probability of an active attack is negligible. For example, when data exchange between and is carried out using NFC (Near-Field Communication) technology or similar.

If the parties interact through other insecure communication channels, including the Internet, then an active attack aimed at impersonating the verifier is possible. Let's call the bogus verifier as The attacker tries to replace with

Let's choose Protocol 2 as the object of attack. Using the interception and blocking technique, the attacker is able to impose $\mathsf{T}'=[\phi']\mathsf{G}_1$ instead of $\mathsf{T},$ such that $\phi'=\phi$ with v.s.p. The computes $\textit{response}$ as $\mathsf{N}'=[\upsilon\mathbf{x}\pmod m]\mathsf{T}'=[\phi'\upsilon\mathbf{x}\pmod m]\mathsf{G}_1.$

computes $\hat{g}_2=e_m([\phi']\mathsf{S}, \mathsf{P})=g^{\phi'\upsilon\mathbf{x}\pmod m}$ and checks $\hat{g}_2\stackrel{?}{=}e_m(\mathsf{N}', \mathsf{G}_1).$ computes ${\mathsf{A}'=[\upsilon]\mathsf{T}'=[\upsilon\phi'\pmod m]\mathsf{G}_1}$ and computes $\mathsf{B}'=[\phi']\mathsf{S}=[\phi'\upsilon\pmod m]\mathsf{G}_1.$ It is obvious that $\mathsf{A}'=\mathsf{B}'.$

The above mentioned reasoning is equally valid for Protocol 1. In addition, the attack is also applicable to modified Schnorr protocol.

In the next section, we will demonstrate a protocol where impersonation is not presumably possible.

Protocol resistant to impersonation

Let's assume that, for ${\mathbf{x}, \mathbf{y}\in_R\!(0,m-1]}$ and own key pairs $\{\mathbf{x}, \mathsf{P}_P=[\mathbf{x}]\mathsf{G}_1\}$ and $\{\mathbf{y},\mathsf{P}_V=[\mathbf{y}]\mathsf{ G}_1\},$ respectively. There are certificates $\{D_P,\mathsf{P}_P, \widetilde{\Im}_{\rm{T}}\}$ and $\{D_V,\mathsf{P}_V, \widehat{\Im}_{\rm{T}}\}$ issued for $\mathsf{P}_P$ and $\mathsf{P}_V.$

Let us consider an IDS-compatible and at the same time impersonation-resistant protocol.

Protocol 3

Protocol messages.

$P \longrightarrow V : \mathsf{S}=[\upsilon]\mathsf{P}_V$
$P \longleftarrow V : \mathsf{T}=[\phi]\mathsf{P}_P$
$P \longrightarrow V : \mathsf{N}=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}$

Actions of the parties.

proves to that it owns (knows) $\mathbf{x}.$ To do this, the following steps are performed:

reads the current certificate $\{D_V,\mathsf{P}_V, \widehat{\Im}_{\rm{T}}\}$ and verifies the DS of the trusted party $\rm{T}.$ If $\mathfrak{B}=False$ then the session ends. If $\mathfrak{B}=True$ then it selects ${\upsilon\in_R\!(0,m-1]}$ $(\textit{commitment}),$ computes $\mathsf{S}=[\upsilon] \mathsf{P}_V=[\upsilon\mathbf{y}\pmod m]\mathsf{G}_1$ $(\textit{witness}),$ checks ${\mathsf{S}\stackrel{?}\neq \infty}.$ If $\mathsf{S}=\infty,$ then it chooses a new $\upsilon$ and re-executes the necessary computations and checks.
reads the current certificate $\{D_P,\mathsf{P}_P, \widetilde{\Im}_{\rm{T}}\}$ and verifies the DS of the trusted party $\rm{T}.$ If $\mathfrak{B}=False$ then the session ends. If $\mathfrak{B}=True$ then it chooses ${\phi\in_R\!(0, m-1]}$ and computes $\mathsf{T}=[\phi]\mathsf{P}_P= [\phi\mathbf{x}\pmod m]\mathsf{G}_1$ $(\textit{challenge}).$ If $\mathsf{T}=\infty,$ then it chooses a new $\phi$ and re-executes the necessary computations and checks.
checks $\mathsf{T}\stackrel{?}\neq\infty.$ if it is true, it computes $\mathsf{N}=[\upsilon^{-1}\mathbf{x}^ {-1}\pmod m]\mathsf{T}=[\phi\upsilon^{-1}\pmod m]\mathsf{G}_1$ $(\textit{response}),$ otherwise the session ends.
computes $g_2=e_m(\mathsf{S}, \mathsf{N})=e_m([\upsilon\mathbf{y}\pmod m]\mathsf{G}_1, [\phi\upsilon^{ -1}\pmod m]\mathsf{G}_1)=g^{\phi\mathbf{y}\pmod m}.$ Then it checks $g_2\stackrel{?}{=}e_m([\phi]\mathsf{P}_V, \mathsf{G}_1).$ If equal, then the proof is accepted, and rejected otherwise.

If accepted the proof provided by then the parties independently compute a shared session secret:

computes $\mathsf{A}=[\upsilon\mathbf{x}^{-1}\pmod m]\mathsf{T}=[\upsilon\phi\pmod m]\mathsf{G}_1.$
computes $\mathsf{B}=[\phi\mathbf{y}^{-1}\pmod m]\mathsf{S}=[\phi\upsilon\pmod m]\mathsf{G}_1.$

It is clear that $\mathsf{A}=\mathsf{B}$ due to commutativity.

Preliminary analysis

Let bogus verifier owns the key pair $\{\mathbf{\acute{y}},\mathsf{P}_{V'}=[\mathbf{\acute{y}}]\mathsf{G} _1\},$ $\mathbf{\acute{y}}=\mathbf{y}$ with v.s.p.

We restrict ourselves to the analysis of Protocol 3, in which it is necessary to impose $\mathsf{S}'=[\upsilon]\mathsf{P}_{V'}$ instead of $\mathsf{S}$ in order to impersonate the verifier (replace with ). However, the attacker does not know the $\upsilon$ ephemeris. To reveal $\upsilon,$ one need to solve an ECDLP/DLP given $\mathsf{S}$ or $e_m(\mathsf{S}, \mathsf{G}_1).$

Another strategy is to solve ECDLP/DLP given $\mathsf{P}_V$ or $e_m(\mathsf{P}_V, \mathsf{G}_1).$ Then ${\mathsf{S}'=[\mathbf{y}^{-1} \mathbf{\acute{y}}\pmod m]\mathsf{S}= [\upsilon]\mathsf{P}_{V'}}.$ The relationship between ECDLP and DLP is explained in Appendix A.

The attacker has access to $\mathsf{P}_P$ and is able to impose $\mathsf{T}'=[\phi']\mathsf{P}_P$ instead of $\mathsf{T}$ and $\mathsf{S}'=[\upsilon']\mathsf{P}_{V'}$ instead of $\mathsf {S},$ while $\phi'=\phi$ and $\upsilon'=\upsilon$ being with v.s.p. computes $\textit{response}$ as $\mathsf{N}'=[\upsilon^{-1}\mathbf{x}^{-1}\pmod m]\mathsf{T}'.$

computes $\hat{g}_2=e_m(\mathsf{S}', \mathsf{N}')=e_m([\upsilon'\mathbf{\acute{y}}\pmod m]\mathsf{G}_1, [\phi'\upsilon^{-1}\pmod m]\mathsf{G}_1)=g^{\upsilon'\mathbf{\acute{y}}\phi'\upsilon^{-1}\pmod m}.$ Obviously, $\hat{g}_2=e_m([\phi']\mathsf{P}_{V'}, \mathsf{G}_1)$ with v.s.p. In addition, the attacker can choose arbitrary $\upsilon'$ and $\phi'.$ Let $\upsilon'=\phi'=1$ but $g^{\mathbf{\acute{y}}\upsilon^{-1}\pmod m}=g^{\mathbf{\acute{y}}}$ with v.s.p.

It is easy to show that replacement of $\mathsf{T}$ does not lead to the desired result. To do this, when computing $\hat{g}_2,$ we set $\mathsf{N}'=\mathsf{N}.$ However, $g^{\upsilon'\mathbf{\acute{y}}\phi\upsilon^{-1}\pmod m}=g^{\phi'\mathbf{\acute{y}}\pmod m }$ with v.s.p.

If we assume that the attacker imposes $\mathsf{T}'$ instead of $\mathsf{T},$ but there is no replacement of $\mathsf{S},$ then the impersonation of is also impossible, since $g^{\upsilon'\mathbf{\acute{y}}\phi\upsilon^{-1}\pmod m}=g^{\phi'\mathbf{\acute{y}}\pmod m}$ with v.s.p.

Note that $\mathsf{A}'=[\upsilon\mathbf{x}^{-1}\pmod m]\mathsf{T}'=[\upsilon\phi'\pmod m]\mathsf{G} _1,$ $\mathsf{B}'=[\phi'\mathbf{\acute{y}}^{-1}\pmod m]\mathsf{S}=[\phi'\upsilon\mathbf{\acute {y}}^{-1}\mathbf{y}\pmod m]\mathsf{G}_1$ or $\mathsf{B}'=[\phi'\mathbf{\acute{y}}^{- 1}\pmod m]\mathsf{S}'=[\phi'\upsilon'\pmod m]\mathsf{G}_1.$ Therefore, $\mathsf{A}'=\mathsf{B}'$ with v.s.p.

When computing $\mathsf{T}',$ replacing $\mathsf{P}_P$ with some $\mathsf{P}_{P'}$ seems to be counterproductive. If such a replacement is allowed, then $\mathsf{P}_{P'}=[\mathbf{\acute{x}}]\mathsf{G}_1,$ $\mathbf{\acute{x}}=\mathbf{x}$ with v.s.p., there will be a discrepancy in $\mathbf{x}.$ Let $\mathsf{S},$ $\mathsf{N}'=[\upsilon^{-1}\mathbf{x}^{-1}\phi'\mathbf{\acute{x}}\pmod m]\mathsf{G}_1.$ Then $g^{\mathbf{y}\mathbf{x}^{-1}\phi'\mathbf{\acute{x}}\pmod m}=g^{\phi'\mathbf{y}\pmod m}$ with v.s.p.

The amount of information transmitted

If compact representation is used, then one needs to transfer $3(\lceil\log_{2}{p}\rceil+1)$ bits in Protocol 1 and Protocol 2 in order to deliver $\mathsf{S},$ $\mathsf{T},$ and $\mathsf{N}$ in total.

In Protocol 3, must inform of the serial number of $\{D_P,\mathsf{P}_P, \widetilde{\Im}_{\rm{T}}\}.$ Let's suppose that $\ell$ bits need to be allocated to store this number in long-term memory. Then one needs to send $3(\lceil\log_{2}{p}\rceil+1)+\ell$ bits in order to deliver $\mathsf{S},$ $\mathsf{T},$ and $\mathsf{N}$ in total.

Other overheads are allowed. The amount of information transmitted satisfies the asymptotic estimate $O(\log_{2}{p}).$

Computational complexity

In addition to the scalar multiplication, whose computation features are described here, in the Protocol 3 parties and compute $\{\upsilon^{-1},$ $\mathbf{x}^{-1}\}$ and $\mathbf{y}^{-1},$ respectively.

In this case, $\mathbf{x}^{-1}$ and $\mathbf{y}^{-1}$ are computed only once. and store the computed values in secured long-term memory. As a result, and store $\{\mathbf{x}, \mathbf{x}^{-1}, \mathsf{P}_P\}$ and $\{\mathbf{y}, \mathbf{y}^{-1}, \mathsf{P}_V\}$ respectively.

computes $\upsilon^{-1}$ in every single session. If on the side the performance of the platform exceeds the bandwidth of the communication channel between and then with $\upsilon$ known, it is appropriate to initiate the computation of $\upsilon^{-1}$ ahead of time, until $\mathsf{ T}.$ This method minimizes the computational delay, since it is plausible to assume that $\upsilon^{-1}$ will be known by the time $\mathsf{N}$ is needed to be computed.

Since $e_m([\phi]\mathsf{P}_V, \mathsf{G}_1)=e_m(\mathsf{P}_V, [\phi]\mathsf{G}_1)$ due to the bilinearity, then optimization is possible when computing $[\phi]\mathsf{G}_1$ (Table 1).

Let the affine points $\mathsf{S},$ $\mathsf{T}$ and $\mathsf{N}$ represented compactly, then it will be necessary to restore the coordinates of $y_{\mathsf{S}},$ $y_{\mathsf{T}}$ and $y_{\mathsf{N}}$ with using the Tonelli-Shanks algorithm of asymptotic complexity $O(\log_{2}^2{p})$ [Cohen_etc._2006] (section 11.1.5) for subsequent computations. However, this is not necessary if point arithmetic is based on the Montgomery elliptic curve [Montgomery_1987]. It is possible to use birational equivalents, for example, twisted Edwards curves [Bernstein_2008].

Methods for multiplicative inversion in $\mathbb{F}_m^*$ are described in [Cohen_etc._2006] (section 11.1).

For the software implementation of the considered protocols, it is advisable to use the primitives of the PBC library.

The problem of hardware implementation of pairings is comprehensively considered in a number of publications [Rodriguez-Henriquez_etc._2006, Beuchat_etc._Nov_2008, Beuchat_etc._2008, Kammler_etc._2009, Ghosh_etc._2010, Estibals_2010, Ghosh_etc._2011, Beuchat_etc._2011, Cheung_etc._2011, Adikari_etc._2012].

Summary

Protocol 1 and Protocol 2, as well as modified Schnorr protocol, have a limited scope due to the risk of impersonation.

Preliminary analysis shows that impersonation is presumably impossible in Protocol 3. Everyone can use the keys $\mathsf{P}_P$ and $\mathsf{P}_V,$ but only can provide conclusive evidence because it owns the long-term secret key $\mathbf{x}$ and knows the ephemeris $\upsilon.$ Only can verify the proof because it knows the ephemeris $\phi.$

In addition, only and can independently compute $\mathsf{A}$ and $\mathsf{B}$ such that $\mathsf{A}=\mathsf{B},$ since they own the secret keys $\mathbf{x}$ and $\mathbf{y}.$

Conclusion

IDS-compatible identification protocols based on the pairing function have been presented and studied. The problem of impersonification is formulated. A new impersonation-resistant IDS-compatible identification protocol has been designed.

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

Bibliography

[Boneh_Shacham_Lynn_2004] Boneh, D., Shacham, H. and Lynn B. "Short Signatures from the Weil Pairing." $\textit{J. Cryptol.},$ Vol. 17, No. 4, (2004) 297–319.

[Zhang_Safavi-Naini_Susilo_2004] Zhang, F., Safavi-Naini, R. and Susilo, W. "An efficient signature scheme from bilinear pairing and its applications.” $\textit{Public Key Cryptography},$ LNCS 2947, (2004) 277–290.

[Fiat_Shamir_1987] Fiat, A. and Shamir, "How to prove yourself: Practical solutions to identification and signature problems.” $\textit{Advances in Cryptology — CRYPTO’86}$ LNCS 263, (1987) 186–194.

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

[Montgomery_1987] Montgomery, Peter L. "Speeding the Pollard and Elliptic Curve Methods of Factorization.” $\textit{Mathematics of Computation},$ (1987) 48 (177): 243–264.

[Bernstein_2008] Bernstein, Daniel J., Birkner, Peter, Joye, Marc, Lange, Tanja, Peters, Christiane. In Vaudenay, Serge (ed.). "Twisted Edwards Curves.” $\textit{Progress in Cryptology — AFRICACRYPT 2008},$ LNCS 5023, (2008) 389–405.

[Rodriguez-Henriquez_etc._2006] Rodríguez-Henríquez, F., Díaz-Pérez, A., Saqib, N. A. and Koč, Č. K. $\textit{Cryptographic Algorithms on Reconfigurable Hardware},$ Signals and Communication Technology. Boston, MA: Springer US, 2006.

[Beuchat_etc._Nov_2008] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E., Shirase, M. and Takagi, T. "Algorithms and Arithmetic Operators for Computing the $\eta T$ Pairing in Characteristic Three.” $\textit{IEEE Transactions on Computers},$ vol. 57, no. 11, (Nov. 2008) 1454–1468.

[Beuchat_etc._2008] Beuchat, J.-L., Brisebarre, N., Detrey, J., Okamoto, E. and Rodriguez-Henriquez, F. "A Comparison Between Hardware Accelerators for the Modified Tate Pairing over $F_{2^m}$ and $F_{3^m}.$ ” $\textit{Pairing-Based Cryptography — Pairing 2008},$ (2008) 297–315.

[Kammler_etc._2009] Kammler, D., Zhang, D., Schwabe, P., Scharwaechter, H., Langenberg, M., Auras, D., Ascheid, G. and Mathar, R. "Designing an ASIP for Cryptographic Pairings over Barreto-Naehrig Curves.” $\textit{Cryptographic Hardware and Embedded Systems — CHES 2009},$ Springer Berlin/Heidelberg, (2009) 254–271.

[Ghosh_etc._2010] Ghosh, S., Mukhopadhyay, D. and Roychowdhury, D. "High Speed Flexible Pairing Cryptoprocessor on FPGA Platform.” $\textit{Pairing-Based Cryptography — Pairing 2010},$ vol. 6487, (2010) 450–466.

[Estibals_2010] Estibals, N. "Compact Hardware for Computing the Tate Pairing over 128-Bit Security Supersingular Curves.” $\textit{Pairing-Based Cryptography — Pairing 2010}$ vol. 6487, (2010) 397–416.

[Ghosh_etc._2011] Ghosh, S., Roychowdhury, D. and Das, A. "High Speed Cryptoprocessor for $\eta T$ Pairing on 128-bit Secure Supersingular Elliptic Curves over Characteristic Two Fields.” $\textit{Cryptographic Hardware and Embedded Systems — CHES 2011},$ (2011) 442–458.

[Beuchat_etc._2011] Beuchat, J.-L., Detrey, J., Estibals, N., Okamoto, E. and Rodriguez-Henriquez, F. "Fast Architectures for the $\eta T$ Pairing over Small-Characteristic Supersingular Elliptic Curves.” $\textit{IEEE Transactions on Computers},$ vol. 60, no. 2, (Feb. 2011) 266–281.

[Cheung_etc._2011] Cheung, R. C. C., Duquesne, S., Fan, J., Guillermin, N., Verbauwhede, I. and Yao, G. X. "FPGA Implementation of Pairings Using Residue Number System and Lazy Reduction.” $\textit{Cryptographic Hardware and Embedded Systems — CHES 2011},$ no. 07, (2011) 421–441.

[Adikari_etc._2012] Adikari, J., Hasan, M. A. and Negre, C. "Towards Faster and Greener Cryptoprocessor for Eta Pairing on Supersingular Elliptic Curve over $F_{2^{1223}}.$ ” $19^{\mbox{th}}$ $\textit{International Conference, Selected Areas in Cryptography 2012},$ (2012) 166–183.