Non-malleable Time-Lock Puzzles and Applications

Cody Freitag¹⁰,
Ilan Komargodski^11,12,
Rafael Pass¹⁰ &
…
Naomi Sirkin¹⁰

Part of the book series: Lecture Notes in Computer Science ((LNSC,volume 13044))

Included in the following conference series:

Theory of Cryptography Conference

820 Accesses
11 Citations

Abstract

Time-lock puzzles are a mechanism for sending messages “to the future”, by allowing a sender to quickly generate a puzzle with an underlying message that remains hidden until a receiver spends a moderately large amount of time solving it. We introduce and construct a variant of a time-lock puzzle which is non-malleable, which roughly guarantees that it is impossible to “maul” a puzzle into one for a related message without solving it.

Using non-malleable time-lock puzzles, we achieve the following applications:

The first fair non-interactive multi-party protocols for coin flipping and auctions in the plain model without setup.
Practically efficient fair multi-party protocols for coin flipping and auctions proven secure in the (auxiliary-input) random oracle model.

As a key step towards proving the security of our protocols, we introduce the notion of functional non-malleability, which protects against tampering attacks that affect a specific function of the related messages. To support an unbounded number of participants in our protocols, our time-lock puzzles satisfy functional non-malleability in the fully concurrent setting. We additionally show that standard (non-functional) non-malleability is impossible to achieve in the concurrent setting (even in the random oracle model).

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic

$34.99 /Month

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Buy Now

Chapter: USD 29.95; Price excludes VAT (USA)

eBook: USD 84.99; Price excludes VAT (USA)

Softcover Book: USD 109.99; Price excludes VAT (USA)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Multi-instance Publicly Verifiable Time-Lock Puzzle and Its Applications

On the (Im)possibility of Time-Lock Puzzles in the Quantum Random Oracle Model

On the Security of Time-Lock Puzzles and Timed Commitments

Notes

1.
The concurrent works of [3, 4, 28] consider similar notions of non-malleability for time-lock puzzles. See Sect. 1.3 for a detailed comparison.
2.
The puzzle of [45] for a message s and difficulty T is a tuple $(g,N,T, s\oplus g^{2^T}\bmod N)$, where N is an RSA group modulus and g is a random element from $\mathbb Z_N$. The puzzle is trivially malleable since the message is one-time padded.
3.
In the context of coin flipping, if a malicious party aborts prematurely, this can bias the output [13] causing the fairness issue mentioned above. Boneh and Naor [9] used timed primitives and interaction to circumvent the issue in the two-party case, but we care about the multi-party case and prefer to avoid interaction as much as possible.
4.
We note that our construction is conceptually similar to the Fujisaki-Okamoto (FO) transformation [21] used to generically transform any CPA-secure public-key encryption scheme into a CCA-secure one using a random oracle. However, since our setting and required guarantees are different, the actual proof turns out to be much more delicate and challenging.
5.
As we discuss in the Sect. 1.3, concurrent works allow the distinguisher to be bounded depth.
6.
Our ABO-string model is a variant of the multi-string model of Groth and Ostrovsky [25], where it is assumed that a majority of the public parameters are honestly generated.
7.
For this, we assume that sampling uniformly random safe primes can be done efficiently; this is a pretty common assumption, see [48] for more details.
8.
It is possible to make this protocol maliciously secure using concurrent non-malleable zero-knowledge proofs [2, 32, 34, 38], proving that each party acted honestly, but this (1) makes the construction significantly less efficient, and (2) requires either trusted setup and additional hardness assumptions, or additional rounds of interaction.
9.
We emphasize that only Sect. 1.3, Appendix A, and the separation regarding the different notions of non-malleability (given in the full version) were added based on these works. All other definitions and results that appear are completely independent of these works.

References

Barak, B.: Constant-round coin-tossing with a man in the middle or realizing the shared random string model. In: 43rd Symposium on Foundations of Computer Science FOCS, pp. 345–355 (2002)
Google Scholar
Barak, B., Prabhakaran, M., Sahai, A.: Concurrent non-malleable zero knowledge. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 345–354 (2006)
Google Scholar
Baum, C., David, B., Dowsley, R., Nielsen, J.B., Oechsner, S.: Craft: composable randomness and almost fairness from time. Cryptology ePrint Archive, Report 2020/784 (2020). https://eprint.iacr.org/2020/784
Baum, C., David, B., Dowsley, R., Nielsen, J.B., Oechsner, S.: TARDIS: a foundation of time-lock puzzles in UC. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 429–459. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_15
Chapter Google Scholar
Bentov, I., Pass, R., Shi, E.: Snow white: provably secure proofs of stake. IACR Cryptol. ePrint Arch. 2016, 919 (2016)
Google Scholar
Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: ITCS (2016)
Google Scholar
Boneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25
Chapter Google Scholar
Boneh, D., Bünz, B., Fisch, B.: A survey of two verifiable delay functions. IACR Cryptol. ePrint Arch. 2018, 712 (2018)
MATH Google Scholar
Boneh, D., Naor, M.: Timed commitments. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 236–254. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-44598-6_15
Chapter Google Scholar
Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. In: FOCS, pp. 136–145. IEEE Computer Society (2001)
Google Scholar
Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Concurrent non-malleable commitments (and more) in 3 rounds. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 270–299. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53015-3_10
Chapter MATH Google Scholar
Ciampi, M., Ostrovsky, R., Siniscalchi, L., Visconti, I.: Four-round concurrent non-malleable commitments from one-way functions. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 127–157. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-63715-0_5
Chapter Google Scholar
Cleve, R.: Limits on the security of coin flips when half the processors are faulty (extended abstract). In: Proceedings of the 18th Annual ACM Symposium on Theory of Computing, STOC, pp. 364–369 (1986)
Google Scholar
Coretti, S., Dodis, Y., Guo, S., Steinberger, J.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 227–258. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_9
Chapter Google Scholar
Dachman-Soled, D., Komargodski, I., Pass, R.: Non-malleable codes for bounded parallel-time tampering. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 535–565. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84252-9_18
Chapter Google Scholar
Daian, P., Pass, R., Shi, E.: Snow White: robustly reconfigurable consensus and applications to provably secure proof of stake. In: Goldberg, I., Moore, T. (eds.) FC 2019. LNCS, vol. 11598, pp. 23–41. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-32101-7_2
Chapter Google Scholar
David, B., Gaži, P., Kiayias, A., Russell, A.: Ouroboros praos: an adaptively-secure, semi-synchronous proof-of-stake blockchain. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 66–98. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_3
Chapter Google Scholar
Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography (extended abstract). In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC, pp. 542–552 (1991)
Google Scholar
Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. IACR Cryptol. ePrint Arch. 2019, 619 (2019)
Google Scholar
Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2
Chapter Google Scholar
Fujisaki, E., Okamoto, T.: Secure integration of asymmetric and symmetric encryption schemes. J. Cryptol. 26(1), 80–101 (2013)
Article MathSciNet Google Scholar
Goyal, V.: Constant round non-malleable protocols using one way functions. In: Fortnow, L., Vadhan, S.P. (eds.) Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pp. 695–704 (2011)
Google Scholar
Goyal, V., Lee, C., Ostrovsky, R., Visconti, I.: Constructing non-malleable commitments: a black-box approach. In: 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS, pp. 51–60 (2012)
Google Scholar
Goyal, V., Pandey, O., Richelson, S.: Textbook non-malleable commitments. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pp. 1128–1141 (2016)
Google Scholar
Groth, J., Ostrovsky, R.: Cryptography in the multi-string model. J. Cryptol. 27(3), 506–543 (2014)
Article MathSciNet Google Scholar
Hohenberger, S., Myers, S., Pass, R., Shelat, A.: An overview of ANONIZE: a large-scale anonymous survey system. IEEE Secur. Priv. 13(2), 22–29 (2015)
Article Google Scholar
Kalai, Y.T., Khurana, D.: Non-interactive non-malleability from quantum supremacy. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11694, pp. 552–582. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26954-8_18
Chapter Google Scholar
Katz, J., Loss, J., Xu, J.: On the security of time-lock puzzles and timed commitments. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12552, pp. 390–413. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_14
Chapter Google Scholar
Khurana, D.: Round optimal concurrent non-malleability from polynomial hardness. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 139–171. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70503-3_5
Chapter Google Scholar
Khurana, D., Sahai, A.: How to achieve non-malleability in one or two rounds. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 564–575 (2017)
Google Scholar
Lin, H., Pass, R.: Non-malleability amplification. In: Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC, pp. 189–198 (2009)
Google Scholar
Lin, H., Pass, R.: Constant-round non-malleable commitments from any one-way function. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pp. 705–714 (2011)
Google Scholar
Lin, H., Pass, R., Soni, P.: Two-round and non-interactive concurrent non-malleable commitments from time-lock puzzles. In: 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS, pp. 576–587. IEEE Computer Society (2017)
Google Scholar
Lin, H., Pass, R., Tseng, W.-L.D., Venkitasubramaniam, M.: Concurrent non-malleable zero knowledge proofs. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 429–446. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_23
Chapter Google Scholar
Lin, H., Pass, R., Venkitasubramaniam, M.: Concurrent non-malleable commitments from any one-way function. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 571–588. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_31
Chapter Google Scholar
Malavolta, G., Thyagarajan, S.A.K.: Homomorphic time-lock puzzles and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22
Chapter Google Scholar
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC, pp. 427–437. ACM (1990)
Google Scholar
Ostrovsky, R., Pandey, O., Visconti, I.: Efficiency preserving transformations for concurrent non-malleable zero knowledge. In: Micciancio, D. (ed.) TCC 2010. LNCS, vol. 5978, pp. 535–552. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-11799-2_32
Chapter Google Scholar
Pandey, O., Pass, R., Vaikuntanathan, V.: Adaptive one-way functions and applications. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 57–74. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-85174-5_4
Chapter Google Scholar
Pass, R., Rosen, A.: Concurrent non-malleable commitments. In: 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 563–572 (2005)
Google Scholar
Pass, R., Rosen, A.: New and improved constructions of non-malleable cryptographic protocols. In: Proceedings of the 37th Annual ACM Symposium on Theory of Computing, STOC, pp. 533–542 (2005)
Google Scholar
Pass, R., Rosen, A.: Concurrent nonmalleable commitments. SIAM J. Comput. 37(6), 1891–1925 (2008)
Article MathSciNet Google Scholar
Pass, R., Wee, H.: Constant-round non-malleable commitments from sub-exponential one-way functions. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 638–655. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_32
Chapter Google Scholar
Pietrzak, K.: Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference, ITCS, pp. 60:1–60:15 (2019)
Google Scholar
Rivest, R.L., Shamir, A., Wagner, D.A.: Time-lock puzzles and timed-release crypto,: technical report. Massachusetts Institute of Technology, Cambridge, MA, USA (1996)
Google Scholar
Rotem, L., Segev, G.: Generically speeding-up repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring delay functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 481–509. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17
Chapter Google Scholar
Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_12
Chapter Google Scholar
Von Zur Gathen, J., Shparlinski, I.E.: Generating safe primes. J. Math. Cryptol. 7(4), 333–365 (2013)
MathSciNet MATH Google Scholar
Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: FOCS (2010)
Google Scholar
Wesolowski, B.: Efficient verifiable delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13
Chapter Google Scholar

Download references

Acknowledgements

This work was supported in part by NSF Award SATC-1704788, NSF Award RI-1703846, NSF Award DGE-1650441, AFOSR Award FA9550-18-1-0267, DARPA Award HR00110C0086, and a JP Morgan Faculty Award. Ilan Komargodski is supported in part by an Alon Young Faculty Fellowship and by an ISF grant (No. 1774/20). This research is based upon work supported in part by the Office of the Director of National Intelligence (ODNI), Intelligence Advanced Research Projects Activity (IARPA), via 2019-19-020700006. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of ODNI, IARPA, or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for governmental purposes notwithstanding any copyright annotation therein.

Author information

Authors and Affiliations

Cornell Tech, New York City, USA
Cody Freitag, Rafael Pass & Naomi Sirkin
Hebrew University, Jerusalem, Israel
Ilan Komargodski
NTT Research, Palo Alto, USA
Ilan Komargodski

Authors

Cody Freitag
View author publications
You can also search for this author in PubMed Google Scholar
Ilan Komargodski
View author publications
You can also search for this author in PubMed Google Scholar
Rafael Pass
View author publications
You can also search for this author in PubMed Google Scholar
Naomi Sirkin
View author publications
You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Naomi Sirkin .

Editor information

Editors and Affiliations

Georgetown University, Washington, WA, USA
Kobbi Nissim
The University of Texas at Austin, Austin, TX, USA
Brent Waters

A Discussion of Non-malleable Definitions

We briefly discuss the different notions of non-malleability studied in this work. Specifically, we compare standard non-malleability (Definition 3.4), non- malleability against depth-bounded distinguishers, and functional non-malleability (Definition 4.1). In Sect. 1.3, we also discuss the definitions considered in the concurrent works of [3, 4, 28].

Common to all of our definitions, there is a depth-bounded man-in-the-middle (MIM) attacker, which we call $\mathcal {A}$, that on input a puzzle z with solution s tries to output a different puzzle $\tilde{z}$ to a related value $\tilde{s}$. Here, $\mathcal {A}$ is depth-bounded relative to the difficulty of the puzzle, so it should not be able to solve the puzzle. The definitions vary in what it means for $\tilde{s}$ to be “related” to s. For our standard notion of non-malleability, we require that no unbounded distinguisher $\mathcal {D} $ on input $\tilde{s}$ can tell if it came from the experiment starting with s or the all-zero string. In the definition of non-malleability against depth-bounded distinguishers, $\mathcal {D} $ is restricted to be depth-bounded in the same way as $\mathcal {A}$. In the case of functional non-malleability, the (unbounded) distinguisher $\mathcal {D} $ receives instead as input $f(\tilde{s})$ where f is a low-depth function. We parameterize functional non-malleability by an output length m. When $m = |s|$, this captures plain non-malleability by considering f to be the identity function. When $m = 1$, this captures depth-bounded distinguisher non-malleability as f essentially plays the role of the depth-bounded distinguisher $\mathcal {D} $. In Theorem 4.2, we show how to construct a time-lock puzzle satisfying functional non-malleability for any output length m assuming a time-lock puzzle that is secure.

When considering concurrent non-malleability, the MIM attacker $\mathcal {A}$ receives possibly multiple puzzles $z_1,\ldots , z_{n_L}$ that have solutions $s_1,\ldots , s_{n_L}$ as input and tries to output multiple puzzles $\tilde{z}_1, \ldots , \tilde{z}_{n_R}$ (different from its inputs) corresponding to $\tilde{s}_1, \ldots , \tilde{s}_{n_R}$. In the most general form, we can consider some distinguisher $\mathcal {D} $ that receives as input $f(\tilde{s}_1,\ldots , \tilde{s}_{n_R})$ and tries to tell if it came from the experiment starting with $s_1,\ldots , s_{n_L}$ or with $n_{L}$ all-zero strings. We show in the full version that if the MIM attacker can encode a time-lock puzzle into the value $f(\tilde{s}_1,\ldots , \tilde{s}_{n_R})$ (where f may be the identity), then the construction cannot be secure against an unbounded distinguisher. In particular, if the function’s output length m is greater than the output length of the time-lock puzzle, the scheme may not be secure. On the other hand, our construction of Theorem 4.2 works for functional non-malleability even in the fully concurrent setting, as the output length of f is bounded. So, as long as the output length of the function f is sufficiently small, we can support unbounded concurrency.

Finally, our separation in the full version gives a construction that satisfies plain (non-concurrent) non-malleability against depth-bounded distinguishers yet does not satisfy non-malleability against unbounded distinguishers. We remark that in the setting where the message length for the puzzle is 1 bit, these notions are equivalent by simply considering the depth-bounded distinguisher that outputs the bit it gets as input. Moreover, it can be shown that they are equivalent as long as the message length is in $O(\log \lambda )$. Therefore, this separation necessarily relies on the fact that the message length for the puzzle is in $\omega (\log \lambda )$.

We summarize the various relationships between the definitions in Fig. 1.

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Cite this paper

Freitag, C., Komargodski, I., Pass, R., Sirkin, N. (2021). Non-malleable Time-Lock Puzzles and Applications. In: Nissim, K., Waters, B. (eds) Theory of Cryptography. TCC 2021. Lecture Notes in Computer Science(), vol 13044. Springer, Cham. https://doi.org/10.1007/978-3-030-90456-2_15

Download citation

DOI: https://doi.org/10.1007/978-3-030-90456-2_15
Published: 04 November 2021
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-90455-5
Online ISBN: 978-3-030-90456-2
eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

the International Association for Cryptologic Research (opens in a new tab)