nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions

verfasst von : Tibor Jager, David Niehues

Erschienen in: Selected Areas in Cryptography – SAC 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

Verifiable random functions (VRFs) are essentially digital signatures with additional properties, namely verifiable uniqueness and pseudorandomness, which make VRFs a useful tool, e.g., to prevent enumeration in DNSSEC Authenticated Denial of Existence and the CONIKS key management system, or in the random committee selection of the Algorand blockchain.

Most standard-model VRFs rely on admissible hash functions (AHFs) to achieve security against adaptive attacks in the standard model. Known AHF constructions are based on error-correcting codes, which yield asymptotically efficient constructions. However, previous works do not clarify how the code should be instantiated concretely in the real world. The rate and the minimal distance of the selected code have significant impact on the efficiency of the resulting cryptosystem, therefore it is unclear if and how the aforementioned constructions can be used in practice.

First, we explain inherent limitations of code-based AHFs. Concretely, we assume that even if we were given codes that achieve the well-known Gilbert-Varshamov or McEliece-Rodemich-Rumsey-Welch bounds, existing AHF-based constructions of verifiable random functions (VRFs) can only be instantiated quite inefficiently. Then we introduce and construct computational AHFs (cAHFs). While classical AHFs are information-theoretic, and therefore work even in presence of computationally unbounded adversaries, cAHFs provide only security against computationally bounded adversaries. However, we show that cAHFs can be instantiated significantly more efficiently. Finally, we use our cAHF to construct the currently most efficient verifiable random function with full adaptive security in the standard model.

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 Using TopGear in Overdrive: A More Efficient ZKPoK for SPDZ

Nächstes Kapitel Tight Security Bounds for Generic Stream Cipher Constructions

Nur mit Berechtigung zugänglich

That is, digital signatures where for any given (public key, message)-pair there exists only one unique string that is accepted as a signature by the verification algorithm.

Codes based on expander graphs can get close to this bound, while not achieving it [43].

For the VRFs in [22, 25, 27, 29, 48] this is identical to the input length.

A detailed dicussion of keyed hash functions can be found in [28].

One could tighten the upper bound \(t_\mathcal {B} \) to \(t_\mathcal {A} + Q\). However, it would at most save a factor of two in the run time of \(\mathcal {B} \) and would complicate the analysis. We therefore use the slightly less tight bound.

We do not consider the VRF in Appendix C of [48], because it relies on a polynomial q-type assumption.

Abdalla, M., Fiore, D., Lyubashevsky, V.: From selective to full security: semi-generic transformations in the standard model. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 316–333. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-30057-8_19CrossRef

Attrapadung, N., Matsuda, T., Nishimaki, R., Yamada, S., Yamakawa, T.: Adaptively single-key secure constrained PRFs for NC1. IACR Cryptol. ePrint Arch. 2018, 1000 (2018)MATH

Attrapadung, N., Matsuda, T., Nishimaki, R., Yamada, S., Yamakawa, T.: Constrained PRFs for \(\rm NC^1\) in traditional groups. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 543–574. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_19CrossRefMATH

Bellare, M., Ristenpart, T.: Simulation without the artificial abort: simplified proof and improved concrete security for waters’ IBE scheme. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 407–424. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01001-9_24CrossRef

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) ACM CCS 93, pp. 62–73. ACM Press (November 1993)

Bellare, M., Rogaway, P.: The exact security of digital signatures-how to sign with RSA and Rabin. In: Maurer, U. (ed.) EUROCRYPT 1996. LNCS, vol. 1070, pp. 399–416. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68339-9_34CrossRef

Bitansky, N.: Verifiable random functions from non-interactive witness-indistinguishable proofs. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 567–594. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_19CrossRef

Boneh, D., Boyen, X.: Efficient selective-ID secure identity-based encryption without random oracles. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 223–238. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_14CrossRef

Boneh, D., Boyen, X.: Secure identity based encryption without random oracles. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 443–459. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_27CrossRef

10.

Boneh, D., Franklin, M.K.: Identity based encryption from the Weil pairing. SIAM J. Comput. 32(3), 586–615 (2003)MathSciNetCrossRef

11.

Boneh, D., Lynn, B., Shacham, H.: Short signatures from the Weil pairing. J. Cryptol. 17(4), 297–319 (2004)MathSciNetCrossRef

12.

Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)MathSciNetCrossRef

13.

Cash, D., Hofheinz, D., Kiltz, E., Peikert, C.: Bonsai trees, or how to delegate a lattice basis. J. Cryptol. 25(4), 601–639 (2012)MathSciNetCrossRef

14.

Chen, Y., Huang, Q., Zhang, Z.: Sakai-Ohgishi-kasahara identity-based non-interactive key exchange revisited and more. Int. J. Inf. Secur. 15(1), 15–33 (2016)CrossRef

15.

Cheon, J.H.: Security analysis of the strong Diffie-Hellman problem. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 1–11. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_1CrossRef

16.

Dumer, I., Micciancio, D., Sudan, M.: Hardness of approximating the minimum distance of a linear code. In: 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, 17–18 October, 1999, New York, NY, USA, pp. 475–485. IEEE Computer Society (1999)

17.

Freire, E.S.V., Hofheinz, D., Paterson, K.G., Striecks, C.: Programmable hash functions in the multilinear setting. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 513–530. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_28CrossRefMATH

18.

Gilad, Y., Hemo, R., Micali, S., Vlachos, G., Zeldovich, N.: Algorand: scaling byzantine agreements for cryptocurrencies. In: Proceedings of the 26th Symposium on Operating Systems Principles, Shanghai, China, October 28–31, 2017, pp. 51–68. ACM (2017)

19.

Gilbert, E.N.: A comparison of signalling alphabets. Bell Syst. Tech. J. 31, 504–522 (1952)CrossRef

20.

Goldberg, S., Reyzin, L., Papadopoulos, D., Vcelak, J.: Verifiable random functions (VRFs). Internet-Draft draft-irtf-cfrg-vrf-04, IETF Secretariat, February 2019. http://www.ietf.org/internet-drafts/draft-irtf-cfrg-vrf-04.txt

21.

Grassl, M.: Bounds on the minimum distance of linear codes and quantum codes (2007). http://www.codetables.de. Accessed 20 Jan 2019

22.

Hofheinz, D., Jager, T.: Verifiable random functions from standard assumptions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 336–362. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_14CrossRef

23.

Hofheinz, D., Jager, T., Kiltz, E.: Short signatures from weaker assumptions. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 647–666. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_35CrossRef

24.

Hofheinz, D., Kiltz, E.: Programmable hash functions and their applications. J. Cryptol. 25(3), 484–527 (2012)MathSciNetCrossRef

25.

Jager, T.: Verifiable random functions from weaker assumptions. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9015, pp. 121–143. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46497-7_5CrossRef

26.

Jager, T., Kurek, R.: Short digital signatures and ID-KEMs via truncation collision resistance. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018. LNCS, vol. 11273, pp. 221–250. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03329-3_8CrossRef

27.

Katsumata, S.: On the untapped potential of encoding predicates by arithmetic circuits and their applications. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 95–125. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70700-6_4CrossRef

28.

Katz, J., Lindell, Y.: Introduction to Modern Cryptography. Chapman and Hall/CRC Press, Boca Raton (2007)CrossRef

29.

Kohl, L.: Hunting and gathering – verifiable random functions from standard assumptions with short proofs. In: Lin, D., Sako, K. (eds.) PKC 2019. LNCS, vol. 11443, pp. 408–437. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17259-6_14CrossRef

30.

Libert, B., Stehlé, D., Titiu, R.: Adaptively secure distributed PRFs from \(\sf LWE\). In: Beimel, A., Dziembowski, S. (eds.) TCC 2018. LNCS, vol. 11240, pp. 391–421. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-03810-6_15CrossRef

31.

Lysyanskaya, A.: Unique signatures and verifiable random functions from the DH-DDH separation. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 597–612. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_38CrossRef

32.

MacWilliams, F.J., Sloane, N.J.A.: The Theory of Error Correcting Codes, 10th edn. North Holland Mathematical Library, Amsterdam (1998)MATH

33.

McEliece, R.J., Rodemich, E.R., Rumsey Jr., H., Welch, L.R.: New upper bounds on the rate of a code via the Delsarte-MacWilliams inequalities. IEEE Trans. Inf. Theory 23(2), 157–166 (1977)MathSciNetCrossRef

34.

Melara, M.S., Blankstein, A., Bonneau, J., Felten, E.W., Freedman, M.J.: CONIKS: bringing key transparency to end users. In: Jung, J., Holz, T. (eds.) USENIX Security 2015, pp. 383–398. USENIX Association (August 2015)

35.

Micali, S., Rabin, M.O., Vadhan, S.P.: Verifiable random functions. In: 40th FOCS, pp. 120–130. IEEE Computer Society Press (October 1999)

36.

National Institute of Standards and Technology. FIPS PUB 180–4: Secure hash standard, August 2015. https://doi.org/10.6028/NIST.FIPS.180-4

37.

National Institute of Standards and Technology. FIPS PUB 202: SHA-3 standard: permutation-based hash and extendable-output functions, August 2015. https://doi.org/10.6028/NIST.FIPS.202

38.

Papadopoulos, D., et al.: Making NSEC5 practical for DNSSEC. Cryptol. ePrint Arch. Rep. 2017, 099 (2017). http://eprint.iacr.org/2017/099

39.

Peterson, W.W., Weldon, E.J.: Error-Correcting Codes, 2nd edn. MIT Press, Cambridge (1988). 9 print editionMATH

40.

Shoup, V.: Sequences of games: a tool for taming complexity in security proofs. Cryptol. ePrint Arch. Rep. 2004, 332 (2004). http://eprint.iacr.org/2004/332

41.

Shum, K.W., Aleshnikov, I., Kumar, P.V., Stichtenoth, H., Deolalikar, V.: A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound. IEEE Trans. Inf. Theory 47(6), 2225–2241 (2001)MathSciNetCrossRef

42.

Sipser, M., Spielman, D.A.: Expander codes. IEEE Trans. Inf. Theory 42(6), 1710–1722 (1996)MathSciNetCrossRef

43.

Ta-Shma, A.: Explicit, almost optimal, epsilon-balanced codes. In: Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19–23, 2017, pp. 238–251. ACM (2017)

44.

Vardy, A.: The intractability of computing the minimum distance of a code. IEEE Trans. Inf. Theory 43(6), 1757–1766 (1997)MathSciNetCrossRef

45.

Varshamov, R.R.: Estimate of the number of signals in error correcting codes. Docklady Acad. Nauk SSSR 117(5), 739–741 (1957)MATH

46.

Vcelak, J., Goldberg, S., Papadopoulos, D., Huque, S., Lawrence, D.: NSEC5, DNSSEC authenticated denial of existence. Internet-Draft draft-vcelak-nsec5-08, IETF Secretariat, December 2018. http://www.ietf.org/internet-drafts/draft-vcelak-nsec5-08.txt

47.

Waters, B.: Efficient identity-based encryption without random oracles. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 114–127. Springer, Heidelberg (2005). https://doi.org/10.1007/11426639_7CrossRef

48.

Yamada, S.: Asymptotically compact adaptively secure lattice IBEs and verifiable random functions via generalized partitioning techniques. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10403, pp. 161–193. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63697-9_6CrossRef

49.

Zémor, G.: On expander codes. IEEE Trans. Inf. Theory 47(2), 835–837 (2001)MathSciNetCrossRef

Titel: On the Real-World Instantiability of Admissible Hash Functions and Efficient Verifiable Random Functions
verfasst von: Tibor Jager
David Niehues
Verlag: Springer International Publishing
Buch: Selected Areas in Cryptography – SAC 2019
Print ISBN: 978-3-030-38470-8

Electronic ISBN: 978-3-030-38471-5

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-38471-5_13

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"