PURED: A Unified Framework for Resource-Hard Functions
Pages 126 - 149
Abstract
Algorithm hardness can be described by 5 categories: hardness in computation, in sequential computation, in memory, in energy consumption (or bandwidth), in code size. Similarly, hardness can be a concern for solving or for verifying, depending on the context, and can depend on a secret trapdoor or be universally hard. Two main lines of research investigated such problems: cryptographic puzzles, that gained popularity thanks to blockchain consensus systems (where solving must be moderately hard, and verification either public or private), and white box cryptography (where solving must be hard without knowledge of the secret key). In this work, we improve upon the classification framework proposed by Biryukov and Perrin in Asiacypt 2017 and offer a united hardness framework, PURED, that can be used for measuring all these kinds of hardness, both in solving and verifying. We also propose three new constructions that fill gaps previously uncovered by the literature (namely, trapdoor proof of CMC, trapdoor proof of code, and a hard challenge in sequential time trapdoored in verification), and analyse their hardness in the PURED framework.
References
[1]
Abadi M, Burrows M, Manasse M, and Wobber T Moderately hard, memory-bound functions ACM Trans. Internet Technol. 2005 5 2 299-327
[2]
Abliz, M., Znati, T.: A guided tour puzzle for denial of service prevention. In: 2009 Annual Computer Security Applications Conference, pp. 279–288 (2009)
[3]
Ali, I.M., Caprolu, M., Pietro, R.D.: Foundations, properties, and security applications of puzzles: a survey. ACM Comput. Surv. 53(4), 72:1–72:38 (2020)
[4]
Alwen J and Blocki J Robshaw M and Katz J Efficiently computing data-independent memory-hard functions Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 241-271
[5]
Alwen J, Blocki J, and Pietrzak K Nielsen JB and Rijmen V Sustained space complexity Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 99-130
[6]
Alwen J, Chen B, Pietrzak K, Reyzin L, and Tessaro S Coron J-S and Nielsen JB Scrypt is maximally memory-hard Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 33-62
[7]
Alwen, J., et al.: On the memory-hardness of data-independent password-hashing functions. In: Proceedings of the 2018 on Asia Conference on Computer and Communications Security, ASIACCS 2018, pp. 51–65. Association for Computing Machinery, New York (2018)
[8]
Alwen, J., Serbinenko, V.: High parallel complexity graphs and memory-hard functions. In: Proceedings of the Forty-Seventh Annual ACM Symposium on Theory of Computing, STOC 2015, pp. 595–603. Association for Computing Machinery, New York (2015).
[9]
Ateniese, G., Chen, L., Francati, D., Papadopoulos, D., Tang, Q.: Verifiable capacity-bound functions: a new primitive from Kolmogorov complexity (revisiting space-based security in the adaptive setting). Cryptology ePrint Archive, Paper 2021/162 (2021). https://eprint.iacr.org/2021/162,
[10]
Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Koutsougeras, C., Vitter, J.S. (eds.) Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, New Orleans, Louisiana, USA, 5–8 May 1991, pp. 21–31. ACM (1991).
[11]
Back, A.: Hashcash - a denial of service counter-measure (2002)
[12]
Baldimtsi F, Kiayias A, Zacharias T, and Zhang B Cheon JH and Takagi T Indistinguishable proofs of work or knowledge Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 902-933
[13]
Biryukov A, Bouillaguet C, and Khovratovich D Sarkar P and Iwata T Cryptographic schemes based on the ASASA structure: black-box, white-box, and public-key (extended abstract) Advances in Cryptology – ASIACRYPT 2014 2014 Heidelberg Springer 63-84
[14]
Biryukov, A., Dinu, D., Khovratovich, D.: Argon2: new generation of memory-hard functions for password hashing and other applications. In: 2016 IEEE European Symposium on Security and Privacy (EuroS &P), pp. 292–302 (2016).
[15]
Biryukov, A., Khovratovich, D.: Egalitarian computing (MTP 1.2). CoRR abs/1606.03588 (2016). http://arxiv.org/abs/1606.03588
[16]
Biryukov, A., Khovratovich, D.: Equihash: asymmetric proof-of-work based on the generalized birthday problem. Ledger 2, 1–30 (2017). https://ledger.pitt.edu/ojs/ledger/article/view/48
[17]
Biryukov A and Perrin L Takagi T and Peyrin T Symmetrically and asymmetrically hard cryptography Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 417-445
[18]
Blocki, J., Ren, L., Zhou, S.: Bandwidth-hard functions: reductions and lower bounds. In: Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, pp. 1820–1836. Association for Computing Machinery, New York (2018)
[19]
Blum L, Blum M, and Shub M Chaum D, Rivest RL, and Sherman AT Comparison of two pseudo-random number generators Advances in Cryptology 1983 Boston Springer 61-78
[20]
Bogdanov, A., Isobe, T.: White-box cryptography revisited: space-hard ciphers. In: Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, CCS 2015, pp. 1058–1069. Association for Computing Machinery, New York (2015).
[21]
Bogdanov A, Isobe T, and Tischhauser E Cheon JH and Takagi T Towards practical whitebox cryptography: optimizing efficiency and space hardness Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 126-158
[22]
Boneh D, Bonneau J, Bünz B, and Fisch B Shacham H and Boldyreva A Verifiable delay functions Advances in Cryptology – CRYPTO 2018 2018 Cham Springer 757-788
[23]
Boneh D, Corrigan-Gibbs H, and Schechter S Cheon JH and Takagi T Balloon hashing: a memory-hard function providing provable protection against sequential attacks Advances in Cryptology – ASIACRYPT 2016 2016 Heidelberg Springer 220-248
[24]
Boneh D, Freeman D, Katz J, and Waters B Jarecki S and Tsudik G Signing a linear subspace: signature schemes for network coding Public Key Cryptography – PKC 2009 2009 Heidelberg Springer 68-87
[25]
Chase M and Lysyanskaya A Dwork C On signatures of knowledge Advances in Cryptology - CRYPTO 2006 2006 Heidelberg Springer 78-96
[26]
Chen M et al. Multiparty generation of an RSA modulus J. Cryptol. 2022 35 2 12
[27]
Coelho, F., Larroche, A., Colin, B.: Itsuku: a memory-hardened proof-of-work scheme. IACR Cryptology ePrint Archive, p. 1168 (2017). http://eprint.iacr.org/2017/1168
[28]
Cohen B and Pietrzak K Nielsen JB and Rijmen V Simple proofs of sequential work Advances in Cryptology – EUROCRYPT 2018 2018 Cham Springer 451-467
[29]
De Feo L, Masson S, Petit C, and Sanso A Galbraith SD and Moriai S Verifiable delay functions from supersingular isogenies and pairings Advances in Cryptology – ASIACRYPT 2019 2019 Cham Springer 248-277
[30]
Delerablée C, Lepoint T, Paillier P, and Rivain M Lange T, Lauter K, and Lisoněk P White-box security notions for symmetric encryption schemes Selected Areas in Cryptography – SAC 2013 2014 Heidelberg Springer 247-264
[31]
Dobson, S., Galbraith, S.D.: Trustless groups of unknown order with hyperelliptic curves. IACR Cryptology ePrint Archive, p. 196 (2020). https://eprint.iacr.org/2020/196
[32]
Dwork C and Naor M Brickell EF Pricing via processing or combatting junk mail Advances in Cryptology — CRYPTO’ 92 1993 Heidelberg Springer 139-147
[33]
Dziembowski S, Faust S, Kolmogorov V, and Pietrzak K Gennaro R and Robshaw M Proofs of space Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 585-605
[34]
Ethereum Community: ethash—ethereum wiki. https://eth.wiki/en/concepts/ethash/ethash
[35]
Garg, S., Gentry, C., Sahai, A., Waters, B.: Witness encryption and its applications. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 467–476. Association for Computing Machinery, New York (2013).
[36]
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems. In: Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC 2085, pp. 291–304. Association for Computing Machinery, New York (1985)
[37]
Kamara S Muntean T, Poulakis D, and Rolland R Proofs of storage: theory, constructions and applications Algebraic Informatics 2013 Heidelberg Springer 7-8
[38]
Liu J, Jager T, Kakvi SA, and Warinschi B How to build time-lock encryption Des. Codes Crypt. 2018 86 11 2549-2586
[39]
Mahmoody, M., Moran, T., Vadhan, S.: Publicly verifiable proofs of sequential work. In: Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS 2013, pp. 373–388. Association for Computing Machinery, New York (2013).
[40]
Percival, C.: Stronger key derivation via sequential memory-hard functions (2009)
[41]
Pietrzak, K.: Simple verifiable delay functions. In: Blum, A. (ed.) 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, San Diego, California, USA, 10–12 January 2019. LIPIcs, vol. 124, pp. 60:1–60:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019).
[42]
Poupard G and Stern J Imai H and Zheng Y Short proofs of knowledge for factoring Public Key Cryptography 2000 Heidelberg Springer 147-166
[43]
Provos, N., Mazières, D.: A future-adaptive password scheme. In: Proceedings of the Annual Conference on USENIX Annual Technical Conference, ATEC 1999, p. 32. USENIX Association (1999)
[44]
Ren L and Devadas S Kalai Y and Reyzin L Bandwidth hard functions for ASIC resistance Theory of Cryptography 2017 Cham Springer 466-492
[45]
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology, USA (1996)
[46]
Rivest, R.L.: Description of the LCS35 time capsule crypto-puzzle (1999). https://people.csail.mit.edu/rivest/lcs35-puzzle-description.txt
[47]
Schnorr CP Brassard G Efficient identification and signatures for smart cards Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 239-252
[48]
Thompson, C.D.: Area-time complexity for VLSI. In: Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing, STOC 1979, pp. 81–88. Association for Computing Machinery, New York (1979)
[49]
Vitto, G.: Factoring primes to factor moduli: backdooring and distributed generation of semiprimes. IACR Cryptology ePrint Archive, p. 1610 (2021). https://eprint.iacr.org/2021/1610
[50]
Walfish, M., Vutukuru, M., Balakrishnan, H., Karger, D., Shenker, S.: DDoS defense by offense. In: Proceedings of the 2006 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM 2006, pp. 303–314. Association for Computing Machinery, New York (2006)
[51]
Wesolowski B Efficient verifiable delay functions J. Cryptol. 2020 33 4 2113-2147
[52]
Youden WJ Index for rating diagnostic tests Cancer 1950 3 1 32-35
Recommendations
Symmetrically and Asymmetrically Hard Cryptography
Advances in Cryptology – ASIACRYPT 2017AbstractThe main efficiency metrics for a cryptographic primitive are its speed, its code size and its memory complexity. For a variety of reasons, many algorithms have been proposed that, instead of optimizing, try to increase one of these hardness ...
A method for secure and efficient block cipher using white-box cryptography
ICUIMC '12: Proceedings of the 6th International Conference on Ubiquitous Information Management and CommunicationNowadays many information should be protected securely. Generally, they are encrypted by cryptographic algorithm. A secret value is used as encryption key which must not be exposed as public. However, the key can be extracted by adversary using white ...
A Modular Approach to the Incompressibility of Block-Cipher-Based AEADs
Advances in Cryptology – ASIACRYPT 2022AbstractIncompressibility is one of the most fundamental security goals in white-box cryptography. Given recent advances in the design of efficient and incompressible block ciphers such as SPACE, SPNbox and WhiteBlock, we demonstrate the feasibility of ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2023
276 pages
ISBN:978-3-031-56234-1
DOI:10.1007/978-3-031-56235-8
© The Author(s), under exclusive license to Springer Nature Switzerland AG 2024.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 29 March 2024
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 10 Dec 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in