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 and distributed uniformly and independently on the interval otherwise and for large this probability is vanishingly small. For example, for A similar argument applies to where is a generator of (Appendix A).

When describing DS schemes and identification protocols, we will proceed from the assumption that there is a pair of linked keys where is a secret key, and is a public one for which a certificate is issued. In this certificate, is the personal data of the owner of is the DS of the trusted party (the certification authority responsible for issuing and maintaining certificates).

Let's call the functions of signing and verifying the digital signature as and respectively. Let's denote the cryptographic hash function by (Appendix B). Then where is the secret key of the trusted party consigned for signing.

Before use, is checked for authenticity, integrity, and relevance. The latter task is done by checking a list of revoked certificates. is computed, where is the public key of trusted party If is valid, then the boolean variable and this means integrity, authenticity of and otherwise 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

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 when design identification protocols.

DS schemes based on pairing

Hereinafter let's call the one who sign the message as the 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:

1. Computes

2. Generates the signature

Let there be some signature and a message The verifier performs the following actions:

1. Computes

2. Checks the authenticity, integrity and relevance of if the relevance is not confirmed or then it completes the verification of the DS.

3. Computes

4. Checks

Then if If then with v.s.p.

It is clear that 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

Let's look at another DS scheme from [Boneh_Shacham_Lynn_2004]. There is a given hash function   (Appendix B). The witness performs the following steps:

1. Computes

2. Generates the signature

There is a message and signature The verifier does the following steps:

1. Computes

2. Checks the authenticity, integrity and relevance of if the relevance is not confirmed or then it completes the verification of the DS.

3. Checks

If and then, due to the bilinearity, If and/or then with v.s.p.

Both above-mentioned DS schemes use the 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.

Actions of the parties.

proves to that it owns (knows) To do this, the following steps are performed:

1. selects computes checks If then selects a new re-executes the necessary computations and checks.

2. reads the current certificate and checks the DS of the trusted party If then the session ends. If then it chooses and computes If then it chooses a new and re-executes the necessary computations and checks.

3. checks if it is true, it computes otherwise the session ends.

4. computes Then it checks 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.

Actions of the parties.

proves to that it owns (knows) To do this, the following steps are performed:

1. As in Protocol 1.

2. As in Protocol 1.

3. checks if it is true, it computes otherwise the session ends.

4. computes Then it checks 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:

1. computes

2. computes

Obviously, 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 instead of such that with v.s.p. The computes as

computes and checks computes and computes It is obvious that

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 and own key pairs and respectively. There are certificates and issued for and

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

Protocol 3

Protocol messages.

Actions of the parties.

proves to that it owns (knows) To do this, the following steps are performed:

1. reads the current certificate and verifies the DS of the trusted party If then the session ends. If then it selects computes checks If then it chooses a new and re-executes the necessary computations and checks.

2. reads the current certificate and verifies the DS of the trusted party If then the session ends. If then it chooses and computes If then it chooses a new and re-executes the necessary computations and checks.

3. checks if it is true, it computes otherwise the session ends.

4. computes Then it checks 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:

1. computes

2. computes 

It is clear that due to commutativity.

Preliminary analysis

Let bogus verifier owns the key pair with v.s.p.

We restrict ourselves to the analysis of Protocol 3, in which it is necessary to impose instead of in order to impersonate the verifier (replace with ). However, the attacker does not know the ephemeris. To reveal one need to solve an ECDLP/DLP given  or

Another strategy is to solve ECDLP/DLP given or Then The relationship between ECDLP and DLP is explained in Appendix A.

The attacker has access to and is able to impose instead of and instead of while and being with v.s.p. computes as

computes Obviously, with v.s.p. In addition, the attacker can choose arbitrary and Let but with v.s.p.

It is easy to show that replacement of does not lead to the desired result. To do this, when computing we set However, with v.s.p.

If we assume that the attacker imposes instead of but there is no replacement of then the impersonation of is also impossible, since with v.s.p.

Note that or Therefore, with v.s.p.

When computing replacing with some seems to be counterproductive. If such a replacement is allowed, then with v.s.p., there will be a discrepancy in Let Then with v.s.p.

The amount of information transmitted

If compact representation is used, then one needs to transfer bits in Protocol 1 and Protocol 2 in order to deliver and in total.

In Protocol 3, must inform of the serial number of Let's suppose that bits need to be allocated to store this number in long-term memory. Then one needs to send bits in order to deliver and in total.

Other overheads are allowed. The amount of information transmitted satisfies the asymptotic estimate

Computational complexity

In addition to the scalar multiplication, whose computation features are described here, in the Protocol 3 parties and compute and respectively.

In this case, and are computed only once. and store the computed values in secured long-term memory. As a result, and store and respectively.

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

Since due to the bilinearity, then optimization is possible when computing (Table 1).

Let the affine points and represented compactly, then it will be necessary to restore the coordinates of and with using the Tonelli-Shanks algorithm of asymptotic complexity [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 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 and but only can provide conclusive evidence because it owns the long-term secret key and knows the ephemeris Only can verify the proof because it knows the ephemeris

In addition, only and can independently compute and such that since they own the secret keys and

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." 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.” LNCS 2947, (2004) 277–290.

[Fiat_Shamir_1987] Fiat, A. and Shamir, "How to prove yourself: Practical solutions to identification and signature problems.” LNCS 263, (1987) 186–194.

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

[Montgomery_1987] Montgomery, Peter L. "Speeding the Pollard and Elliptic Curve Methods of Factorization.” (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.” 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. 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 Pairing in Characteristic Three.” 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 and ” (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.” Springer Berlin/Heidelberg, (2009) 254–271.

[Ghosh_etc._2010]  Ghosh, S., Mukhopadhyay, D. and Roychowdhury, D. "High Speed Flexible Pairing Cryptoprocessor on FPGA Platform.” vol. 6487, (2010) 450–466.

[Estibals_2010] Estibals, N. "Compact Hardware for Computing the Tate Pairing over 128-Bit Security Supersingular Curves.” vol. 6487, (2010) 397–416.

[Ghosh_etc._2011] Ghosh, S., Roychowdhury, D. and Das, A. "High Speed Cryptoprocessor for Pairing on 128-bit Secure Supersingular Elliptic Curves over Characteristic Two Fields.” (2011) 442–458.

[Beuchat_etc._2011] Beuchat, J.-L.,  Detrey, J., Estibals, N.,  Okamoto, E. and  Rodriguez-Henriquez, F. "Fast Architectures for the Pairing over Small-Characteristic Supersingular Elliptic Curves.” 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.” 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 ” (2012) 166–183.