Black-Box Timed Commitments from Time-Lock Puzzles
Pages 460 - 493
Abstract
A Timed Commitment (TC) with time parameter t is hiding for time at most t, that is, commitments can be force-opened by any third party within time t. In addition to various cryptographic assumptions, the security of all known TC schemes relies on the sequentiality assumption of repeated squarings in hidden-order groups. The repeated squaring assumption is therefore a security bottleneck.
In this work, we give a black-box construction of TCs from any time-lock puzzle (TLP) by additionally relying on one-way permutations and collision-resistant hashing.
Currently, TLPs are known from (a) the specific repeated squaring assumption, (b) the general (necessary) assumption on the existence of worst-case non-parallelizing languages and indistinguishability obfuscation, and (c) any iteratively sequential function and the hardness of the circular small-secret LWE problem. The latter admits a plausibly post-quantum secure instantiation.
Hence, thanks to the generality of our transform, we get i) the first TC whose timed security is based on the existence of non-parallelizing languages and ii) the first TC that is plausibly post-quantum secure.
We first define quasi publicly-verifiable TLPs (QPV-TLPs) and construct them from any standard TLP in a black-box manner without relying on any additional assumptions. Then, we devise a black-box commit-and-prove system to transform any QPV-TLPs into a TC.
References
[1]
Agrawalr, S., Malavolta, G., Zhang, T.: Time-lock puzzles from lattices. In: Reyzin, L., Stebila, D. (eds.) Advances in Cryptology – CRYPTO 2024. CRYPTO 2024. LNCS, vol. 14922. Springer, Cham (2024).
[2]
Baum C, David B, Dowsley R, Nielsen JB, and Oechsner S Canteaut A and Standaert F-X TARDIS: a foundation of time-lock puzzles in UC Advances in Cryptology – EUROCRYPT 2021 2021 Cham Springer 429-459
[3]
Carsten Baum, Bernardo David, Rafael Dowsley, Ravi Kishore, Jesper Buus Nielsen, and Sabine Oechsner. CRAFT: Composable randomness beacons and output-independent abort MPC from time. In Alexandra Boldyreva and Vladimir Kolesnikov, editors, PKC 2023, Part I, volume 13940 of LNCS, pages 439–470, Atlanta, GA, USA, May 7–10, 2023. Springer, Heidelberg, Germany
[4]
Barak B et al. Kilian J et al. On the (Im)possibility of obfuscating programs Advances in Cryptology — CRYPTO 2001 2001 Heidelberg Springer 1-18
[5]
Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: Sudan, M. (eds.) ITCS 2016, 14–16 January, pp. 345–356. ACM, Cambridge, MA, USA (2016)
[6]
Boneh D and Naor M Bellare M Timed commitments Advances in Cryptology — CRYPTO 2000 2000 Heidelberg Springer 236-254
[7]
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: 42nd FOCS, 14–17 October, pp. 136–145. IEEE Computer Society Press, Las Vegas, NV, USA (2001)
[8]
Choi SG, Dachman-Soled D, Malkin T, and Wee H Reingold O Simple, black-box constructions of adaptively secure protocols Theory of Cryptography 2009 Heidelberg Springer 387-402
[9]
Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGs from sub-exponential DDH. In: Handschuh, H., Lysyanskaya, A. (eds) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. LNCS, vol. 14084. Springer, Cham (2023).
[10]
Chvojka, P., Jager, T.: Simple, fast, efficient, and tightly-secure non-malleable non-interactive timed commitments. In: Boldyreva, A., Kolesnikov, V. (eds.) Public-Key Cryptography – PKC 2023. PKC 2023. LNCS, vol. 13940. Springer, Cham (2023).
[11]
Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for from LWE. In: 62nd FOCS, 7–10 February, Denver, CO, USA, pp. 68–79. IEEE Computer Society Press (2022)
[12]
Chatterjee, R., Liang, X., Pandey, O.: Improved black-box constructions of composable secure computation. Cryptology ePrint Archive, Report 2020/494 (2020). https://eprint.iacr.org/2020/494
[13]
Ciampi, M., Orsini, E., Siniscalchi, L. Four-round black-box non-malleable schemes from one-way permutations. In: Kiltz, E., Vaikuntanathan, V. (eds.) Theory of Cryptography. TCC 2022. LNCS, vol. 13748. Springer, Cham (2022).
[14]
Freitag C, Komargodski I, Pass R, and Sirkin N Nissim K and Waters B Non-malleable time-lock puzzles and applications Theory of Cryptography 2021 Cham Springer 447-479
[15]
Goldreich O and Kahan A How to construct constant-round zero-knowledge proof systems for NP J. Cryptol. 1996 9 3 167-189
[16]
Goyal, V., Lee, C.-K., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach. In: 53rd FOCS, 20–23 October, pp. 51–60, New Brunswick, NJ, USA. IEEE Computer Society Press (2012)
[17]
Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or A completeness theorem for protocols with honest majority. In: Aho, A. (ed.) 19th ACM STOC, 25–27 May, pp. 218–229. ACM Press, New York City (1987)
[18]
Goldreich, O.: The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press (2001)
[19]
Hulett, J., Jawale, R., Khurana, D., Srinivasan, A.: SNARGs for P from Sub-exponential DDH and QR. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology – EUROCRYPT 2022. EUROCRYPT 2022. LNCS, vol. 13276. Springer, Cham (2022).
[20]
Halevi S and Micali S Koblitz N Practical and provably-secure commitment schemes from collision-free hashing Advances in Cryptology — CRYPTO ’96 1996 Heidelberg Springer 201-215
[21]
Hazay C and Venkitasubramaniam M Robshaw M and Katz J On the power of secure two-party computation Advances in Cryptology – CRYPTO 2016 2016 Heidelberg Springer 397-429
[22]
Ishai, Y., Kushilevitz, E., Lindell, Y., Petrank, F.: Black-box constructions for secure computation. In: Kleinberg, J.M (eds.) 38th ACM STOC, 21–23 May, Seattle, WA, USA, pp. 99–108. ACM Press (2006)
[23]
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Johnson, D.S., Feige, U. (eds.) 39th ACM STOC, 11–13 June, San Diego, CA, USA, pp. 21–30. ACM Press (2007)
[24]
Jaques S, Montgomery H, Rosie R, and Roy A Adhikari A, Küsters R, and Preneel B Time-release cryptography from minimal circuit assumptions Progress in Cryptology – INDOCRYPT 2021 2021 Cham Springer 584-606
[25]
Kiyoshima S Garay JA and Gennaro R Round-efficient black-box construction of composable multi-party computation Advances in Cryptology – CRYPTO 2014 2014 Heidelberg Springer 351-368
[26]
Kiyoshima S Micciancio D and Ristenpart T Round-optimal black-box commit-and-prove with succinct communication Advances in Cryptology – CRYPTO 2020 2020 Cham Springer 533-561
[27]
Kiyoshima, S.: Holographic SNARGs for P and Batch-NP from (polynomially hard) learning with errors. In: Rothblum, G., Wee, H. (eds.) Theory of Cryptography. TCC 2023. LNCS, vol. 14371. Springer, Cham (2023).
[28]
Katz J, Loss J, and Xu J Pass R and Pietrzak K On the security of time-lock puzzles and timed commitments Theory of Cryptography 2020 Cham Springer 390-413
[29]
Khurana D, Ostrovsky R, and Srinivasan A Beimel A and Dziembowski S Round optimal black-box “Commit-and-Prove” Theory of Cryptography 2018 Cham Springer 286-313
[30]
Lindell Y A note on constant-round zero-knowledge proofs of knowledge J. Cryptol. 2013 26 4 638-654
[31]
Lindell, Y.: How to simulate it - a tutorial on the simulation proof technique. Cryptology ePrint Archive, Paper 2016/046 (2016). https://eprint.iacr.org/2016/046
[32]
Lai, R.W.F., Malavolta, G.: Lattice-Based Timed Cryptography. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023. CRYPTO 2023. LNCS, vol. 14085. Springer, Cham (2023).
[33]
Lin H and Pass R Safavi-Naini R and Canetti R Black-Box constructions of composable protocols without set-up Advances in Cryptology – CRYPTO 2012 2012 Heidelberg Springer 461-478
[34]
Lin, H., Pass, R., Soni, P.: Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles. In Umans, C (ed.) 58th FOCS, 15–17 October, Berkeley, CA, USA, pp. 576–587. IEEE Computer Society Press (2017)
[35]
Pietrzak, K.: Simple verifiable delay functions. In: Blum, A (ed.) ITCS 2019, 10–12 January, San Diego, CA, USA, vol. 124, pp. 60:1–60:15. LIPIcs (2019)
[36]
Pass R and Wee H Reingold O Black-box constructions of two-party protocols from one-way functions Theory of Cryptography 2009 Heidelberg Springer 403-418
[37]
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto. Technical report, USA (1996)
[38]
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B (ed.) 46th ACM STOC, 31 May–3 June, New York, NY, USA, pp. 475–484. ACM Press (2014)
[39]
Thyagarajan, D.A.K., Castagnos, G., Laguillaumie, F., Malavolta, G.: Efficient CCA timed commitments in class groups. In: Vigna. G., Shi, E (eds.) ACM CCS 2021, pp. 2663–2684, Virtual Event, Republic of Korea, 15–19 November. ACM Press (2021)
[40]
Wesolowski B Ishai Y and Rijmen V Efficient verifiable delay functions Advances in Cryptology – EUROCRYPT 2019 2019 Cham Springer 379-407
[41]
Waters, B., Wu, D.J.: Adaptively-sound succinct arguments for NP from indistinguishability obfuscation. In: Mohar, B., Shinkar, I., O’Donnell, R. (eds.) Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, 24-28 June, Vancouver, BC, Canada, pp. 387–398. ACM (2024)
[42]
Zhang, F., Maram, D., Malvai, H., Goldfeder, S., Juels, A.: DECO: liberating web data using decentralized oracles for TLS. In: Ligatti, J., Ou, X., Katz, J., Vigna, G. (eds.) ACM CCS 2020, 9–13 November, pp. 1919–1938, Virtual Event, USA. ACM Press (2020)
Index terms have been assigned to the content through auto-classification.
Recommendations
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Dec 2024
501 pages
© International Association for Cryptologic Research 2025.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 02 December 2024
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 03 Mar 2025