Top

Published in:

2019 | OriginalPaper | Chapter

Using Level-1 Homomorphic Encryption to Improve Threshold DSA Signatures for Bitcoin Wallet Security

Authors : Dan Boneh, Rosario Gennaro, Steven Goldfeder

Published in: Progress in Cryptology – LATINCRYPT 2017

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recently Gennaro et al. (ACNS ’16) presented a threshold-optimal signature algorithm for DSA. Threshold-optimality means that if security is set so that it is required to have \(t+1\) servers to cooperate to sign, then it is sufficient to have \(n=t+1\) honest servers in the network. Obviously threshold optimality compromises robustness since if \(n=t+1\), a single corrupted player can prevent the group from signing. Still, in their protocol, up to t corrupted players cannot produce valid signatures. Their protocol requires six rounds which is already an improvement over the eight rounds of the classic threshold DSA of Gennaro et al. (Eurocrypt ’99) (which is not threshold optimal since \(n \ge 3t+1\) if robust and \(n \ge 2t+1\) if not).

We present a new and improved threshold-optimal DSA signature scheme, which cuts the round complexity to four rounds. Our protocol is based on the observation that given an encryption of the secret key, the encryption of a DSA signature can be computed in only four rounds if using a level-1 Fully Homomorphic Encryption scheme (i.e. a scheme that supports at least one multiplication), and we instantiate it with the very efficient level-1 FHE scheme of Catalano and Fiore (CCS ’15).

As noted in Gennaro et al. (ACNS ’16), the schemes have very compelling application in securing Bitcoin wallets from thefts happening due to DSA secret key exposure. Given that network latency can be a major bottleneck in an interactive protocol, a scheme with reduced round complexity is highly desirable. We implement and benchmark our scheme and find it to be very efficient in practice.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter On Trees, Chains and Fast Transactions in the Blockchain

next chapter Environmental Authentication in Malware

i.e. a scheme where given \(c=E(m)\) and \(c'=E(m')\) it is possible to compute \(\hat{c}=E(m+m')\) where \(+\) is a group operation over the message space, e.g. [41] and its threshold version in [31].

Bitcoin uses ECDSA, the DSA scheme implemented over a group of points of an elliptic curve. As in [25] we ignore this fact since our results hold for a generic version of DSA which is independent of the underlying group where the scheme is implemented (provided the group is of prime order and DSA is obviously unforgeable in this implementation.).

The rationale for that is that provided a bad server in a denial-of-service attack can be easily identified – that is the case in both our protocol and the protocol of [25] – then the corrupted server can be rebooted, restarted from a trusted basis, and the adversary eliminated.

A preliminary version of [25] provided a simple extension of [36] to the n-out-of-n case which however required O(n) rounds to complete. The same version also uses a standard combinatorial construction to go from n-out-of-n to the generic n, t case, but that requires \(O(n^t)\) local long-term storage by each server.

We are considering non-malleability with respect to opening [20] in which the adversary is allowed to see the decommitted values, and is required to produce a related decommitment. A stronger security definition (non-malleability with respect to commitment) simply requires that the adversary cannot produce a commitment to a related message after being given just the committed values of the honest parties. However for information-theoretic commitments (like the ones considered in this paper) the latter definition does not make sense. Indeed information-theoretic secrecy implies that given a commitment, any message could be a potential decommitment. What specifies the meaning of the commitment is a valid opening of it.

In [25] they require an independent commitment scheme, but following our Lemma 1 it suffices that the scheme is non-malleable.

Again, in [25] the proof requires independent commitments but thanks to our Lemma 1 we can relax that assumption to non-malleable commitments.

This is not possible in the key generation part, since \(\mathcal F\) must “hit” the target public key y in order to subsequently forge.

https://github.com/square/jna-gmp.

Andresen, G.: Github: Shared Wallets Design. https://gist.github.com/gavinandresen/4039433. Accessed 20 Mar 2014

Baudron, O., Fouque, P.-A., Pointcheval, D., Poupard, G., Stern, J.: Practical multi-candidate election system. In: PODC 2001 (2001)

Barić, N., Pfitzmann, B.: Collision-free accumulators and fail-stop signature schemes without trees. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 480–494. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-69053-0_33CrossRef

Bar-Ilan, J., Beaver, D.: Non-cryptographic fault-tolerant computing in constant number of rounds of interaction. In: PODC, pp. 201–209 (1989)

Bitcoin Forum member dree12. List of Bitcoin Heists (2013). https://bitcointalk.org/index.php?topic=83794.0

Bitcoin Forum member gmaxwell. List of Bitcoin Heists (2013). https://bitcointalk.org/index.php?topic=279249.0

Bitcoin wiki: Transactions. https://en.bitcoin.it/wiki/Transactions. Accessed 11 Feb 2014

Bitcoin wiki: Elliptic Curve Digital Signature Algorithm. https://en.bitcoin.it/wiki/Elliptic_Curve_Digital_Signature_Algorithm. Accessed 11 feb 2014

Bitcoin wiki: Elliptic Curve Digital Signature Algorithm. https://en.bitcoin.it/w/index.php?title=Secp256k1&oldid=51490. Accessed 11 Feb 2014

10.

Bonneau, J., Narayanan, A., Miller, A., Clark, J., Kroll, J.A., Felten, E.W.: Mixcoin: anonymity for bitcoin with accountable mixes. In: Christin, N., Safavi-Naini, R. (eds.) FC 2014. LNCS, vol. 8437, pp. 486–504. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-45472-5_31CrossRef

11.

Camenisch, J., Kiayias, A., Yung, M.: On the portability of generalized schnorr proofs. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 425–442. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_25CrossRef

12.

Camenisch, J., Krenn, S., Shoup, V.: A framework for practical universally composable zero-knowledge protocols. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 449–467. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_24CrossRef

13.

Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: Proceedings of 42nd IEEE Symposium on Foundations of Computer Science, FOCS 2001, pp. 136–145 (2001)

14.

Canetti, R., Gennaro, R., Herzberg, A., Naor, D.: Proactive security: Long-term protection against break-ins. RSA Laboratories’ CryptoBytes 3(1), 1–8 (1997)

15.

Canetti, R., Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Adaptive security for threshold cryptosystems. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 98–116. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_7CrossRef

16.

Catalano, D., Fiore, D.: Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data. In: ACM Conference on Computer and Communications Security, pp. 1518–1529 (2015)

17.

Damgård, I., Groth, J.: Non-interactive and reusable non-malleable commitment schemes. In: Proceedings of 35th ACM Symposium on Theory of Computing, STOC 2003, pp. 426–437 (2003)

18.

Damgård, I., Jurik, M.: A generalisation, a simplification and some applications of Paillier’s probabilistic public-key system. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 119–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_9CrossRefMATH

19.

Damgård, I., Koprowski, M.: Practical threshold RSA signatures without a trusted dealer. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 152–165. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_10CrossRef

20.

Di Crescenzo, G., Ishai, Y., Ostrovsky, R.: Non-interactive and non-malleable commitment. In: Proceedings of 30th ACM Symposium on Theory of Computing, STOC 1998, pp. 141–150 (1998)

21.

Di Crescenzo, G., Katz, J., Ostrovsky, R., Smith, A.: Efficient and non-interactive non-malleable commitment. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 40–59. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44987-6_4CrossRef

22.

Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. SIAM J. Comp. 30(2), 391–437 (2000)CrossRef

23.

Fujisaki, E., Okamoto, T.: Statistical zero knowledge protocols to prove modular polynomial relations. In: Kaliski, B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 16–30. Springer, Heidelberg (1997). https://doi.org/10.1007/BFb0052225CrossRef

24.

Gennaro, R.: Multi-trapdoor commitments and their applications to proofs of knowledge secure under concurrent man-in-the-middle attacks. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 220–236. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_14CrossRef

25.

Gennaro, R., Goldfeder, S., Narayanan, A.: Threshold-optimal DSA/ECDSA signatures and an application to bitcoin wallet security. In: Manulis, M., Sadeghi, A.-R., Schneider, S. (eds.) ACNS 2016. LNCS, vol. 9696, pp. 156–174. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-39555-5_9CrossRefMATH

26.

Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust threshold DSS signatures. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 354–371. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_31CrossRef

27.

Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Secure distributed key generation for discrete-log based cryptosystems. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 295–310. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_21CrossRef

28.

Gennaro, R., Micali, S.: Independent zero-knowledge sets. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 34–45. Springer, Heidelberg (2006). https://doi.org/10.1007/11787006_4CrossRef

29.

Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)MathSciNetCrossRef

30.

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. SIAM J. Comput. 18(1), 186–208 (1989) MathSciNetCrossRef

31.

Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T., Nicolosi, A.A.: Efficient RSA key generation and threshold Paillier in the two-party setting

32.

Jarecki, S., Lysyanskaya, A.: Adaptively secure threshold cryptography: introducing concurrency, removing erasures. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 221–242. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_16CrossRef

33.

Johnson, D., Menezes, A., Vanstone, S.: The elliptic curve digital signature algorithm (ECDSA). Int. J. Inf. Secur. 1(1), 36–63 (2001)CrossRef

34.

Kaspersky Labs. Financial cyber threats in 2013. Part 2: malware (2013). http://securelist.com/analysis/kaspersky-security-bulletin/59414/financial-cyber-threats-in-2013-part-2-malware/

35.

Lindell, Y.: Fast Secure Two-Party ECDSA Signing. IACR Cryptology ePrint Archive 2017: 552 (2017)

36.

MacKenzie, P., Reiter, M.: Two-party generation of DSA signatures. Int. J. Inf. Secur. 2, 218–239 (2004)CrossRef

37.

MacKenzie, P., Yang, K.: On simulation-sound trapdoor commitments. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 382–400. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_23CrossRef

38.

Meiklejohn, S., et al.: A fistful of bitcoins: characterizing payments among men with no names. In: Proceedings of the 2013 Conference on Internet Measurement Conference, pp. 127–140. ACM (2013)

39.

Mukherjee, P., Wichs, D.: Two round multiparty computation via multi-key FHE. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 735–763. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_26CrossRef

40.

Nakamoto, S.: Bitcoin: a peer-to-peer electronic cash system. Consulted 1, 2012 (2008)

41.

Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223–238. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_16CrossRef

42.

Paillier Threshold Encryption Toolbox. http://cs.utdallas.edu/dspl/cgi-bin/pailliertoolbox/manual.pdf

43.

Pedersen, T.P.: Distributed provers with applications to undeniable signatures. In: Davies, D.W. (ed.) EUROCRYPT 1991. LNCS, vol. 547, pp. 221–242. Springer, Heidelberg (1991). https://doi.org/10.1007/3-540-46416-6_20CrossRef

44.

Rivest, R., Shamir, A., Adelman, L.: A method for obtaining digital signature and public key cryptosystems. Commun. ACM 21, 120–126 (1978)MathSciNetCrossRef

45.

Shamir, A.: How to share a secret. Commun. ACM 22, 612–613 (1979)MathSciNetCrossRef

Title: Using Level-1 Homomorphic Encryption to Improve Threshold DSA Signatures for Bitcoin Wallet Security
Authors: Dan Boneh
Rosario Gennaro
Steven Goldfeder
Publisher: Springer International Publishing
Book: Progress in Cryptology – LATINCRYPT 2017
Print ISBN: 978-3-030-25282-3

Electronic ISBN: 978-3-030-25283-0

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-25283-0_19

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner