nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Efficient Noninteractive Certification of RSA Moduli and Beyond

verfasst von : Sharon Goldberg, Leonid Reyzin, Omar Sagga, Foteini Baldimtsi

Erschienen in: Advances in Cryptology – ASIACRYPT 2019

Verlag: Springer International Publishing

Einloggen

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

search-config

KI-gestützte Suche

Aus

Abstract

In many applications, it is important to verify that an RSA public key (N, e) specifies a permutation over the entire space \(\mathbb {Z}_N\), in order to prevent attacks due to adversarially-generated public keys. We design and implement a simple and efficient noninteractive zero-knowledge protocol (in the random oracle model) for this task. Applications concerned about adversarial key generation can just append our proof to the RSA public key without any other modifications to existing code or cryptographic libraries. Users need only perform a one-time verification of the proof to ensure that raising to the power e is a permutation of the integers modulo N. For typical parameter settings, the proof consists of nine integers modulo N; generating the proof and verifying it both require about nine modular exponentiations.

We extend our results beyond RSA keys and also provide efficient noninteractive zero-knowledge proofs for other properties of N, which can be used to certify that N is suitable for the Paillier cryptosystem, is a product of two primes, or is a Blum integer. As compared to the recent work of Auerbach and Poettering (PKC 2018), who provide two-message protocols for similar languages, our protocols are more efficient and do not require interaction, which enables a broader class of applications.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Shorter QA-NIZK and SPS with Tighter Security

Nächstes Kapitel Shorter Pairing-Based Arguments Under Standard Assumptions

Nur mit Berechtigung zugänglich

It has been observed that such an N could be detected by checking if N has small divisors. However, the risk of being detected is not usually an adequate deterrent, unless implemented and deployed as part of a protocol. But if such a check is deployed, then the adversary, knowing what check has been deployed, could set divisors of N to be just slightly larger than the limits of the check, and thus still ensure that \(\mathbb {Z}_N-\mathbb {Z}_N^*\) is a nonnegligible fraction of \(\mathbb {Z}_N\).

Specifically, in TumbleBit, the Tumbler provides the payee Bob with a value z called a “puzzle,” and a proof that its solution will transfer some of Tumbler’s money to Bob. This solution is a value \(\epsilon \) such that \(z= \epsilon ^e \bmod N\). The protocol crucially relies on uniqueness of \(\epsilon \), because the proof that the solution will unlock money applies to only one of the solutions of z. When Alice wants to pay Bob, she learns the solution to the puzzle in exchange for paying money to the Tumbler, and then gives that solution to Bob as payment. If RSA is not a permutation, then a malicious Tumbler can provide the payee Bob with a puzzle z that has two valid solutions \(\epsilon _1 \ne \epsilon _2\), where \(z=(\epsilon _1)^e = (\epsilon _2)^e \mod N\), and a proof that \(\epsilon _1\) transfers money. Then, to steal money, the Tumbler gives payer Alice the solution \(\epsilon _2\) in exchange for her money, which does not permit Bob to obtain the Tumbler’s money and complete the transaction.

As opposed to a proof system where soundness needs to hold unconditionally, in an argument system it is sufficient that soundness holds with respect to a computationally bounded adversary \(\mathrm {P}^*\).

[AP18]

Auerbach, B., Poettering, B.: Hashing solutions instead of generating problems: on the interactive certification of RSA moduli. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 403–430. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-76581-5_14CrossRef

[Ber98]

Bernstein, D.J.: Detecting perfect powers in essentially linear time. Math. Comput. 67, 1253–1283 (1998)MathSciNetCrossRef

[BFGN17]

Benhamouda, F., Ferradi, H., Géraud, R., Naccache, D.: Non-interactive provably secure attestations for arbitrary RSA prime generation algorithms. In: Foley, S.N., Gollmann, D., Snekkenes, E. (eds.) ESORICS 2017. LNCS, vol. 10492, pp. 206–223. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-66402-6_13CrossRef

[BFL89]

Boyar, J., Friedl, K., Lund, C.: Practical zero-knowledge proofs: giving hints and using deficiencies. In: Quisquater, J.-J., Vandewalle, J. (eds.) EUROCRYPT 1989. LNCS, vol. 434, pp. 155–172. Springer, Heidelberg (1990). https://doi.org/10.1007/3-540-46885-4_18CrossRef

[BLP07]

Bernstein, D.J., Lenstra, H.W., Pila, J.: Detecting perfect powers by factoring into coprimes. Math. Comput. 76(257), 385–388 (2007)MathSciNetCrossRef

[bou]

bouncycastle c# api. https://www.bouncycastle.org/csharp/index.html

[BR93]

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73. ACM (1993)

[BY96]

Bellare, M., Yung, M.: Certifying permutations: noninteractive zero-knowledge based on any trapdoor permutation. J. Cryptol. 9(3), 149–166 (1996). https://cseweb.ucsd.edu/~mihir/papers/cct.htmlMathSciNetCrossRef

[CM99]

Camenisch, J., Michels, M.: Proving in zero-knowledge that a number is the product of two safe primes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 107–122. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_8CrossRefMATH

[CMS99]

Cachin, C., Micali, S., Stadler, M.: Computationally private information retrieval with polylogarithmic communication. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 402–414. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48910-X_28CrossRef

[cod]

Tumblebit setup implementation. https://github.com/osagga/TumbleBitSetup

[CPP07]

Catalano, D., Pointcheval, D. and Pornin, T. Trapdoor hard-to-invert group isomorphisms and their application to password-based authentication. J. Cryptol. 20(1), 115–149, 2007. http://www.di.ens.fr/~pointche/Documents/Papers/2006_joc.pdfMathSciNetCrossRef

[DJ01]

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

[FKMV12]

Faust, S., Kohlweiss, M., Marson, G.A., Venturi, D.: On the non-malleability of the Fiat-Shamir transform. In: Galbraith, S., Nandi, M. (eds.) INDOCRYPT 2012. LNCS, vol. 7668, pp. 60–79. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34931-7_5CrossRef

[FS86]

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). https://doi.org/10.1007/3-540-47721-7_12CrossRef

[GM84]

Goldwasser, S., Micali, S.: Probabilistic encryption. J. Comput. Syst. Sci. 28(2), 270–299 (1984)MathSciNetCrossRef

[GMR98]

Gennaro, R., Micciancio, D., Rabin, T.: An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products. In: Gong, L., Reiter, M.K. (eds.) CCS 19, Proceedings of the 5th ACM Conference on Computer and Communications Security, San Francisco, CA, USA, 3–5 November 1998, pp. 67–72. ACM (1998). http://eprint.iacr.org/1998/008

[HAB+17]

Heilman, E., Alshenibr, L., Baldimtsi, F., Scafuro, A. and Goldberg, S.: Tumblebit: an untrusted bitcoin-compatible anonymous payment hub. In: 24th Annual Network and Distributed System Security Symposium, NDSS. The Internet Society (2017). https://eprint.iacr.org/2016/575.pdf

[HMRT12]

Hazay, C., Mikkelsen, G.L., Rabin, T., Toft, T.: Efficient RSA key generation and threshold paillier in the two-party setting. In: Dunkelman, O. (ed.) CT-RSA 2012. LNCS, vol. 7178, pp. 313–331. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-27954-6_20CrossRefMATH

[Hoe63]

Hoeffding, W.: Probability inequalities for sums of bounded random variables. J. Am. Stat. Assoc. 58(301), 13–30 (1963)MathSciNetCrossRef

[KKM12]

Kakvi, S.A., Kiltz, E., May, A.: Certifying RSA. In: Wang, X., Sako, K. (eds.) ASIACRYPT 2012. LNCS, vol. 7658, pp. 404–414. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-34961-4_25CrossRef

[Lin17]

Lindell, Y.: Fast secure two-party ECDSA signing. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 613–644. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_21CrossRef

[LMRS04]

Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_5CrossRef

[MKJR16]

Moriarty, K., Kaliski, B., Jonsson, J., Rusch, A.: RFC 8017: PKCS #1: RSA Cryptography Specifications Version 2.2. Internet Engineering Task Force (IETF) (2016). https://tools.ietf.org/html/rfc8017

[MPS00]

MacKenzie, P., Patel, S., Swaminathan, R.: Password-authenticated key exchange based on RSA. In: Okamoto, T. (ed.) ASIACRYPT 2000. LNCS, vol. 1976, pp. 599–613. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44448-3_46CrossRef

[MRV99]

Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, 17–18 October 1999, New York, NY, USA, pp. 120–130. IEEE Computer Society (1999)

[Ntu]

Tumblebit implementation in.net core. https://github.com/NTumbleBit/NTumbleBit/

[Sho09]

Shoup, V.: A Computational Introduction to Number Theory and Algebra, 2nd edn. Cambridge University Press (2009). http://www.shoup.net/ntb/ntb-v2.pdf

[Str17]

Stratis Blockchain: Bitcoin privacy is a breeze: tumblebit successfully integrated into breeze, August 2017. https://stratisplatform.com/2017/08/10/bitcoin-privacy-tumblebit-integrated-into-breeze/

[WCZ03]

Wong, D.S., Chan, A.H., Zhu, F.: More efficient password authenticated key exchange based on RSA. In: Johansson, T., Maitra, S. (eds.) INDOCRYPT 2003. LNCS, vol. 2904, pp. 375–387. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-24582-7_28CrossRef

Titel: Efficient Noninteractive Certification of RSA Moduli and Beyond
verfasst von: Sharon Goldberg
Leonid Reyzin
Omar Sagga
Foteini Baldimtsi
Verlag: Springer International Publishing
Buch: Advances in Cryptology – ASIACRYPT 2019
Print ISBN: 978-3-030-34617-1

Electronic ISBN: 978-3-030-34618-8

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-34618-8_24

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

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

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner