Abstract
In ESORICS 2021, Chvojka et al. introduced the idea of taking a time-lock puzzle and using its solution to generate the keys of a public key encryption (PKE) scheme [12]. They use this to define a timed-release encryption (TRE) scheme, in which the secret key is encrypted ‘to the future’ using a time-lock puzzle, whilst the public key is published. This allows multiple parties to encrypt a message to the public key of the PKE scheme. Then, once a solver has spent a prescribed length of time evaluating the time-lock puzzle, they obtain the secret key and hence can decrypt all of the messages.
In this work we introduce TIDE (TIme Delayed Encryption), a novel approach to constructing timed-release encryption based upon the RSA cryptosystem, where instead of directly encrypting the secret key to the future, we utilise number-theoretic techniques to allow the solver to factor the RSA modulus, and hence derive the decryption key. We implement TIDE on a desktop PC and on Raspberry Pi devices validating that TIDE is both efficient and practically implementable. We provide evidence of practicality with an extensive implementation study detailing the source code and practical performance of TIDE.
Independent.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In [12] they offer a generalised version of this definition, to incorporate what they define sequential timed-release encryption. This is beyond the scope of this work, and we instead specify the “non-sequential” case.
References
Ausubel, L.: A generalized Vickrey auction. Econo0 metrica (1999)
Barak, B., et al.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_1
Bitansky, N., Goldwasser, S., Jain, A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized encodings. In: Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (2016)
Blass, E., Kerschbaum, F.: BOREALIS: building block for sealed bid auctions on blockchains. In: Proceedings of the 15th ACM Asia Conference on Computer and Communications Security (2020)
Blum, L., Blum, M., Shub, M.: A simple unpredictable pseudo-random number generator. J. Comput. 15(2), 364–383 (1986)
Blume, A., Heidhues, P.: All equilibria of the Vickrey auction. J. Econ. Theory 114(1), 170–177 (2004)
Bogetoft, P., et al.: Secure multiparty computation goes live. In: Dingledine, R., Golle, P. (eds.) FC 2009. LNCS, vol. 5628, pp. 325–343. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03549-4_20
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
Brandt, F.: Auctions. In: Handbook of Financial Cryptography and Security. Chapman and Hall/CRC (2010)
Burdges, J., De Feo, L.: Delay encryption. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 302–326. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_11
Cathalo, J., Libert, B., Quisquater, J.-J.: Efficient and non-interactive timed-release encryption. In: Qing, S., Mao, W., López, J., Wang, G. (eds.) ICICS 2005. LNCS, vol. 3783, pp. 291–303. Springer, Heidelberg (2005). https://doi.org/10.1007/11602897_25
Chvojka, P., Jager, T., Slamanig, D., Striecks, C.: Versatile and sustainable timed-release encryption and sequential time-lock puzzles (extended abstract). In: Bertino, E., Shulman, H., Waidner, M. (eds.) ESORICS 2021. LNCS, vol. 12973, pp. 64–85. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-88428-4_4
Cohen, B., Pietrzak, K.: The chia network blockchain (2019)
Cormen, T., Leiserson, C., Rivest, R., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2009)
Crandall, R., Pomerance, C.: Prime Numbers: A Computational Perspective. Springer, New York (2005). https://doi.org/10.1007/0-387-28979-8
Ephraim, N., Freitag, C., Komargodski, I., Pass, R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 125–154. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_5
De Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable delay functions from supersingular isogenies and pairings. In: Galbraith, S.D., Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248–277. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-34578-5_10
Freitag, C., Komargodski, I., Pass, R., Sirkin, N.: Non-malleable time-lock puzzles and applications. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, vol. 13044, pp. 447–479. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_15
Friedlander, J., Pomerance, C., Shparlinski, I.: Period of the power generator and small values of Carmichael’s function. Math. Comput. 70, 1591–1605 (2000)
Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP is secure under the RSA assumption. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 260–274. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44647-8_16
Galal, H.S., Youssef, A.M.: Verifiable sealed-bid auction on the ethereum blockchain. In: Zohar, A., et al. (eds.) FC 2018. LNCS, vol. 10958, pp. 265–278. Springer, Heidelberg (2019). https://doi.org/10.1007/978-3-662-58820-8_18
Goodstein, R.L.: Boolean Algebra. Dover Publications (2007)
Griffin, F., Shparlinski, I.: On the linear complexity profile of the power generator. IEEE Trans. Inf. Theory 46(6), 2159–2162 (2000)
Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing (2021)
Juels, A., Szydlo, M.: A two-server, sealed-bid auction protocol. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 72–86. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36504-4_6
Katz, J., Lindell, Y.: Introduction to Modern Cryptography, 2nd edn. CRC Press (2014)
Liu, J., Garcia, F., Ryan, M.: Time-release protocol from bitcoin and witness encryption for sat. Korean Circ. J. 40(10), 530–535 (2015)
Loe, A.F., Medley, L., O’Connell, C., Quaglia, E.A.: TIDE: a novel approach to constructing timed-release encryption. Cryptology ePrint Archive (2021)
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
Mao, W.: Timed-release cryptography. In: Vaudenay, S., Youssef, A.M. (eds.) SAC 2001. LNCS, vol. 2259, pp. 342–357. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45537-X_27
Miller, G.: Riemann’s hypothesis and tests for primality. J. Comput. Syst. Sci. 13(3), 300–317 (1976)
Pietrzak, K.: Simple verifiable delay functions. In: 10th Innovations in Theoretical Computer Science Conference, ITCS 2019 (2019)
Rabin, M.: Digitalized signatures and public-key functions as intractable as factorization. In: MIT/LCS/TR-212. MIT Laboratory for Computer Science (1979)
Rivest, R., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM 21(2), 120–126 (1983)
Rivest, R., Shamir, A., Wagner, D.: Time-lock puzzles and timed-release crypto. In: MIT/LCS/TR-684. MIT Laboratory for Computer Science (1996)
Sako, K.: An auction protocol which hides bids of losers. In: Imai, H., Zheng, Y. (eds.) PKC 2000. LNCS, vol. 1751, pp. 422–432. Springer, Heidelberg (2000). https://doi.org/10.1007/978-3-540-46588-1_28
Vickrey, W.: Counterspeculation, auctions, and competitive sealed tenders. J. Finance 16(1), 8–37 (1961)
Zhandry, M.: On ELFs, deterministic encryption, and correlated-input security. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478, pp. 3–32. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_1
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Loe, A.F., Medley, L., O’Connell, C., Quaglia, E.A. (2022). TIDE: A Novel Approach to Constructing Timed-Release Encryption. In: Nguyen, K., Yang, G., Guo, F., Susilo, W. (eds) Information Security and Privacy. ACISP 2022. Lecture Notes in Computer Science, vol 13494. Springer, Cham. https://doi.org/10.1007/978-3-031-22301-3_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-22301-3_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-22300-6
Online ISBN: 978-3-031-22301-3
eBook Packages: Computer ScienceComputer Science (R0)