Skip to main content

2017 | OriginalPaper | Buchkapitel

Reusing Nonces in Schnorr Signatures

(and Keeping It Secure...)

verfasst von : Marc Beunardeau, Aisling Connolly, Houda Ferradi, Rémi Géraud, David Naccache, Damien Vergnaud

Erschienen in: Computer Security – ESORICS 2017

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

The provably secure Schnorr signature scheme is popular and efficient. However, each signature requires a fresh modular exponentiation, which is typically a costly operation. As the increased uptake in connected devices revives the interest in resource-constrained signature algorithms, we introduce a variant of Schnorr signatures that mutualises exponentiation efforts.
Combined with precomputation techniques (which would not yield as interesting results for the original Schnorr algorithm), we can amortise the cost of exponentiation over several signatures: these signatures share the same nonce. Sharing a nonce is a deadly blow to Schnorr signatures, but is not a security concern for our variant.
Our Scheme is provably secure, asymptotically-faster than Schnorr when combined with efficient precomputation techniques, and experimentally 2 to 6 times faster than Schnorr for the same number of signatures when using 1 MB of static storage.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Fußnoten
1
In contrast to the weak version, the adversary is allowed to forge for a message that they have queried before, provided that their forgery is not an oracle response.
 
2
See the full version of this paper for a discussion on some particularly interesting moduli.
 
3
This conversion function can read the string as a binary number and reduce it \(\bmod q_i\) for example.
 
4
The compact form allows not to send the nonce \(\ell \) times, which gives an “amortized” size of the signature, and avoid an overhead in communication.
 
5
One can note, \({\frac{p-1}{q_i}} = 2 q_1 \cdots q_{i-1} q_{i+1} \cdots q_\ell \).
 
6
BPV is a special case of E-BPV where \(h=2\). As such they share the same precomputing step.
 
7
For Schnorr, the exponent’s size is Q; for our scheme, it is P.
 
8
In practice, it turns out that \(h=v=8\) performs slightly better, due to various implementation speed-ups possible in this situation.
 
Literatur
1.
Zurück zum Zitat Agnew, G.B., Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A.: An implementation for a fast public-key cryptosystem. J. Crypto. 3(2), 63–79 (1991)MathSciNetCrossRefMATH Agnew, G.B., Mullin, R.C., Onyszchuk, I.M., Vanstone, S.A.: An implementation for a fast public-key cryptosystem. J. Crypto. 3(2), 63–79 (1991)MathSciNetCrossRefMATH
2.
Zurück zum Zitat Aranha, D.F., Fouque, P.-A., Gérard, B., Kammerer, J.-G., Tibouchi, M., Zapalowicz, J.-C.: GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 262–281. Springer, Heidelberg (2014). doi:10.1007/978-3-662-45611-8_14 Aranha, D.F., Fouque, P.-A., Gérard, B., Kammerer, J.-G., Tibouchi, M., Zapalowicz, J.-C.: GLV/GLS decomposition, power analysis, and attacks on ECDSA signatures with single-bit nonce bias. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 262–281. Springer, Heidelberg (2014). doi:10.​1007/​978-3-662-45611-8_​14
3.
Zurück zum Zitat Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Juels, A., Wright, R.N., Vimercati, S. (eds.) ACM CCS 2006, 30 October–3 November, pp. 390–399. ACM Press, Alexandria (2006) Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Juels, A., Wright, R.N., Vimercati, S. (eds.) ACM CCS 2006, 30 October–3 November, pp. 390–399. ACM Press, Alexandria (2006)
4.
Zurück zum Zitat Boyko, V., Peinado, M., Venkatesan, R.: Speeding up discrete log and factoring based schemes via precomputations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 221–235. Springer, Heidelberg (1998). doi:10.1007/BFb0054129 CrossRef Boyko, V., Peinado, M., Venkatesan, R.: Speeding up discrete log and factoring based schemes via precomputations. In: Nyberg, K. (ed.) EUROCRYPT 1998. LNCS, vol. 1403, pp. 221–235. Springer, Heidelberg (1998). doi:10.​1007/​BFb0054129 CrossRef
5.
Zurück zum Zitat Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200–207. Springer, Heidelberg (1993). doi:10.1007/3-540-47555-9_18 CrossRef Brickell, E.F., Gordon, D.M., McCurley, K.S., Wilson, D.B.: Fast exponentiation with precomputation. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 200–207. Springer, Heidelberg (1993). doi:10.​1007/​3-540-47555-9_​18 CrossRef
7.
Zurück zum Zitat Coron, J.-S., M’Raïhi, D., Tymen, C.: Fast generation of pairs (k, [k]P) for koblitz elliptic curves. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 151–164. Springer, Heidelberg (2001). doi:10.1007/3-540-45537-X_12 CrossRef Coron, J.-S., M’Raïhi, D., Tymen, C.: Fast generation of pairs (k, [k]P) for koblitz elliptic curves. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 151–164. Springer, Heidelberg (2001). doi:10.​1007/​3-540-45537-X_​12 CrossRef
8.
Zurück zum Zitat Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 389–399. Springer, Heidelberg (1995). doi:10.1007/BFb0053453 Rooij, P.: Efficient exponentiation using precomputation and vector addition chains. In: Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 389–399. Springer, Heidelberg (1995). doi:10.​1007/​BFb0053453
9.
Zurück zum Zitat de Rooij, P.: On Schnorr’s preprocessing for digital signature schemes. J. Crypto. 10(1), 1–16 (1997)CrossRefMATH de Rooij, P.: On Schnorr’s preprocessing for digital signature schemes. J. Crypto. 10(1), 1–16 (1997)CrossRefMATH
11.
Zurück zum Zitat Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). doi:10.1007/3-540-47721-7_12 CrossRef Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). doi:10.​1007/​3-540-47721-7_​12 CrossRef
15.
Zurück zum Zitat Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman and Hall/CRC Press (2007) Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman and Hall/CRC Press (2007)
17.
Zurück zum Zitat Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994). doi:10.1007/3-540-48658-5_11 Lim, C.H., Lee, P.J.: More flexible exponentiation with precomputation. In: Desmedt, Y.G. (ed.) CRYPTO 1994. LNCS, vol. 839, pp. 95–107. Springer, Heidelberg (1994). doi:10.​1007/​3-540-48658-5_​11
18.
Zurück zum Zitat M’Raïhi, D., Naccache, D.: Batch exponentiation: a fast DLP-based signature generation strategy. In: Gong, L., Stearn, J. (eds.) CCS 1996, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, March 14–16, pp. 58–61. ACM (1996), http://doi.acm.org/10.1145/238168.238187 M’Raïhi, D., Naccache, D.: Batch exponentiation: a fast DLP-based signature generation strategy. In: Gong, L., Stearn, J. (eds.) CCS 1996, Proceedings of the 3rd ACM Conference on Computer and Communications Security, New Delhi, India, March 14–16, pp. 58–61. ACM (1996), http://​doi.​acm.​org/​10.​1145/​238168.​238187
19.
Zurück zum Zitat Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Cryptography and Computational Number Theory, pp. 331–342. Springer (2001) Nguyen, P.Q., Shparlinski, I.E., Stern, J.: Distribution of modular sums and the security of the server aided exponentiation. In: Cryptography and Computational Number Theory, pp. 331–342. Springer (2001)
20.
Zurück zum Zitat Nguyen, P., Stern, J.: The hardness of the hidden subset sum problem and its cryptographic implications. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 31–46. Springer, Heidelberg (1999). doi:10.1007/3-540-48405-1_3 CrossRef Nguyen, P., Stern, J.: The hardness of the hidden subset sum problem and its cryptographic implications. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 31–46. Springer, Heidelberg (1999). doi:10.​1007/​3-540-48405-1_​3 CrossRef
21.
Zurück zum Zitat Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996). doi:10.1007/3-540-68339-9_33 Pointcheval, D., Stern, J.: Security proofs for signature schemes. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 387–398. Springer, Heidelberg (1996). doi:10.​1007/​3-540-68339-9_​33
22.
Zurück zum Zitat Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Crypto. 13(3), 361–396 (2000)CrossRefMATH Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Crypto. 13(3), 361–396 (2000)CrossRefMATH
23.
24.
Zurück zum Zitat Schroeppel, R., Orman, H., O’Malley, S., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 43–56. Springer, Heidelberg (1995). doi:10.1007/3-540-44750-4_4 Schroeppel, R., Orman, H., O’Malley, S., Spatscheck, O.: Fast key exchange with elliptic curve systems. In: Coppersmith, D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 43–56. Springer, Heidelberg (1995). doi:10.​1007/​3-540-44750-4_​4
25.
Zurück zum Zitat Shanks, D.: Class number, a theory of factorization and genera. Proc. Symp. Pure Math. 20, 415–440 (1970)CrossRef Shanks, D.: Class number, a theory of factorization and genera. Proc. Symp. Pure Math. 20, 415–440 (1970)CrossRef
Metadaten
Titel
Reusing Nonces in Schnorr Signatures
verfasst von
Marc Beunardeau
Aisling Connolly
Houda Ferradi
Rémi Géraud
David Naccache
Damien Vergnaud
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-66402-6_14