{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T01:04:17Z","timestamp":1772240657903,"version":"3.50.1"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Everlasting security models the setting where hardness assumptions hold during the execution of a protocol but may get broken in the future. Due to the strength of this adversarial model, achieving any meaningful security guarantees for composable protocols is impossible without relying on hardware assumptions (M\u00fcller-Quade and Unruh, JoC\u201910). For this reason, a rich line of research has tried to leverage physical assumptions to construct well-known everlasting cryptographic primitives, such as commitment schemes. The only known everlastingly UC secure commitment scheme, due to M\u00fcller-Quade and Unruh (JoC\u201910), assumes honestly generated hardware tokens. The authors leave the possibility of constructing everlastingly UC secure commitments from malicious hardware tokens as an open problem. Goyal et al. (Crypto\u201910) constructs unconditionally UC-secure commitments and secure computation from malicious hardware tokens, with the caveat that the honest tokens must encapsulate other tokens. This extra restriction rules out interesting classes of hardware tokens, such as physically uncloneable functions (PUFs). In this work, we present the first construction of an everlastingly UC-secure commitment scheme in the fully malicious token model<jats:italic>without requiring<\/jats:italic>honest token encapsulation. Our scheme assumes the existence of PUFs and is secure in the common reference string model. We also show that our results are tight by giving an impossibility proof for everlasting UC-secure<jats:italic>computation<\/jats:italic>from non-erasable tokens (such as PUFs), even with trusted setup.<\/jats:p>","DOI":"10.1007\/s00145-022-09432-4","type":"journal-article","created":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:03:02Z","timestamp":1656633782000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Everlasting UC Commitments from Fully Malicious PUFs"],"prefix":"10.1007","volume":"35","author":[{"given":"Bernardo","family":"Magri","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giulio","family":"Malavolta","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Schr\u00f6der","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dominique","family":"Unruh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,1]]},"reference":[{"key":"9432_CR1","doi-asserted-by":"crossref","unstructured":"F. Armknecht, D. Moriyama, A.-R. Sadeghi, M. Yung. Towards a unified security model for physically unclonable functions. in K. Sako, editor, Topics in Cryptology \u2013 CT-RSA\u00a02016, vol. 9610 of Lecture Notes in Computer Science, San Francisco, CA, USA. (Springer, Heidelberg, 2016), pp. 271\u2013287","DOI":"10.1007\/978-3-319-29485-8_16"},{"key":"9432_CR2","doi-asserted-by":"crossref","unstructured":"D. Beaver. Correlated pseudorandomness and the complexity of private computations. in 28th Annual ACM Symposium on Theory of Computing, Philadephia, PA, USA. (ACM Press, 1996), pp. 479\u2013488","DOI":"10.1145\/237814.237996"},{"key":"9432_CR3","doi-asserted-by":"crossref","unstructured":"C. Brzuska, M. Fischlin, H. Schr\u00f6der, S. Katzenbeisser. Physically uncloneable functions in the universal composition framework. in P. Rogaway, editor, Advances in Cryptology \u2013 CRYPTO\u00a02011, vol. 6841 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, (Springer, Heidelberg, Germany, 2011), pp. 51\u201370","DOI":"10.1007\/978-3-642-22792-9_4"},{"key":"9432_CR4","doi-asserted-by":"crossref","unstructured":"S. Badrinarayanan, D. Khurana, R. Ostrovsky, and I. Visconti. Unconditional UC-secure computation with (stronger-malicious) PUFs. in J.-S. Coron, J.\u00a0B. Nielsen, editors, Advances in Cryptology \u2013 EUROCRYPT\u00a02017, Part\u00a0I, vol. 10210 of Lecture Notes in Computer Science, Paris, France. (Springer, Heidelberg, 2017) pp. 382\u2013411","DOI":"10.1007\/978-3-319-56620-7_14"},{"key":"9432_CR5","doi-asserted-by":"crossref","unstructured":"R. Canetti. Universally composable security: a new paradigm for cryptographic protocols. in 42nd Annual Symposium on Foundations of Computer Science, , Las Vegas, NV, USA. (IEEE Computer Society Press, 2001), pp. 136\u2013145","DOI":"10.1109\/SFCS.2001.959888"},{"key":"9432_CR6","doi-asserted-by":"crossref","unstructured":"C. Cachin, C. Cr\u00e9peau, J. Marcil. Oblivious transfer with a memory-bounded receiver. in 39th Annual Symposium on Foundations of Computer Science, (Palo Alto, CA, USA, 1998). IEEE Computer Society Press, pp. 493\u2013502","DOI":"10.1109\/SFCS.1998.743500"},{"key":"9432_CR7","doi-asserted-by":"crossref","unstructured":"R. Canetti, M. Fischlin. Universally composable commitments. in J. Kilian, editor, Advances in Cryptology\u2014CRYPTO\u00a02001, vol. 2139 of Lecture Notes in Computer Science, Santa Barbara, CA, USA (Springer, Heidelberg, Germany, 2001), pp. 19\u201340","DOI":"10.1007\/3-540-44647-8_2"},{"key":"9432_CR8","doi-asserted-by":"crossref","unstructured":"N. Chandran, V. Goyal, and A. Sahai. New constructions for UC secure computation using tamper-proof hardware. In N. P. Smart, editor, Advances in Cryptology \u2013 EUROCRYPT\u00a02008, vol. 4965 of Lecture Notes in Computer Science, Istanbul, Turkey, (Springer, Heidelberg, Germany, 2008) pp. 545\u2013562","DOI":"10.1007\/978-3-540-78967-3_31"},{"key":"9432_CR9","doi-asserted-by":"crossref","unstructured":"R. Canetti, Y. Lindell, R. Ostrovsky, A. Sahai. Universally composable two-party and multi-party secure computation. in 34th Annual ACM Symposium on Theory of Computing. (ACM Press, Montr\u00e9al, Qu\u00e9bec, Canada, 2002), pp. 494\u2013503","DOI":"10.1145\/509907.509980"},{"key":"9432_CR10","doi-asserted-by":"crossref","unstructured":"C. Cachin, U. M. Maurer. Unconditional security against memory-bounded adversaries, in B. S. Kaliski Jr., editor, Advances in Cryptology \u2013 CRYPTO\u201997, vol. 1294 of Lecture Notes in Computer Science, Santa Barbara, CA, USA. (Springer, Heidelberg, Germany 1997), pp. 292\u2013306","DOI":"10.1007\/BFb0052243"},{"key":"9432_CR11","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd. Efficient concurrent zero-knowledge in the auxiliary string model. in B. Preneel, editor, Advances in Cryptology \u2013 EUROCRYPT\u00a02000, vol. 1807 of Lecture Notes in Computer Science, Bruges, Belgium (Springer, Heidelberg, Germany, 2000) pp. 418\u2013430","DOI":"10.1007\/3-540-45539-6_30"},{"key":"9432_CR12","doi-asserted-by":"crossref","unstructured":"D. Dachman-Soled, N. Fleischhacker, J. Katz, A. Lysyanskaya, D. Schr\u00f6der. Feasibility and infeasibility of secure computation with malicious PUFs. In Juan\u00a0A. Garay and Rosario Gennaro, editors, Advances in Cryptology \u2013 CRYPTO\u00a02014, Part\u00a0II, vol. 8617 of Lecture Notes in Computer Science, Santa Barbara, CA, USA. (Springer, Heidelberg, Germany, 2014), pp. 405\u2013420","DOI":"10.1007\/978-3-662-44381-1_23"},{"key":"9432_CR13","doi-asserted-by":"crossref","unstructured":"N. D\u00f6ttling, D. Kraschewski, J. M\u00fcller-Quade, T. Nilges. General statistically secure computation with bounded-resettable hardware tokens. in Y. Dodis, J.\u00a0B. Nielsen, editors, TCC\u00a02015: 12th Theory of Cryptography Conference, Part\u00a0I, vol. 9014 of Lecture Notes in Computer Science, Warsaw, Poland, (Springer, Heidelberg, Germany, 2015), pp. 319\u2013344","DOI":"10.1007\/978-3-662-46494-6_14"},{"key":"9432_CR14","doi-asserted-by":"crossref","unstructured":"N. D\u00f6ttling, D. Kraschewski, J. M\u00fcller-Quade. Unconditional and composable security using a single stateful tamper-proof hardware token. in Y. Ishai, editor, TCC\u00a02011: 8th Theory of Cryptography Conference, vol. 6597 of Lecture Notes in Computer Science, Providence, RI, USA. (Springer, Heidelberg, Germany, 2011), pp. 164\u2013181","DOI":"10.1007\/978-3-642-19571-6_11"},{"key":"9432_CR15","doi-asserted-by":"crossref","unstructured":"S. Dziembowski, U.\u00a0M. Maurer. The bare bounded-storage model: The tight bound on the storage requirement for key agreement. IEEE Trans. Inf. Theory, 54(6), 2790\u20132792 (2008)","DOI":"10.1109\/TIT.2008.921864"},{"key":"9432_CR16","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, J. B. Nielsen. Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. in Moti Yung, editor, Advances in Cryptology \u2013 CRYPTO\u00a02002, vol. 2442 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August\u00a018\u201322. (Springer, Heidelberg, Germany, 2002) pp. 581\u2013596","DOI":"10.1007\/3-540-45708-9_37"},{"key":"9432_CR17","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, A. Scafuro. Unconditionally secure and universally composable commitments from physical assumptions. in K. Sako, P. Sarkar, editors, Advances in Cryptology \u2013 ASIACRYPT\u00a02013, Part\u00a0II, vol. 8270 of Lecture Notes in Computer Science, Bengalore, India, December\u00a01\u20135. (Springer, Heidelberg, Germany, 2013), pp. 100\u2013119","DOI":"10.1007\/978-3-642-42045-0_6"},{"key":"9432_CR18","doi-asserted-by":"crossref","unstructured":"V. Goyal, Y. Ishai, M. Mahmoody, A. Sahai. Interactive locking, zero-knowledge pcps, and unconditional cryptography. in T. Rabin, editor, Advances in Cryptology \u2013 CRYPTO\u00a02010, vol. 6223 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August\u00a015\u201319. (Springer, Heidelberg, Germany, 2010), pp. 173\u2013190","DOI":"10.1007\/978-3-642-14623-7_10"},{"key":"9432_CR19","doi-asserted-by":"crossref","unstructured":"V. Goyal, Y. Ishai, A. Sahai, R. Venkatesan, A. Wadia. Founding cryptography on tamper-proof hardware tokens. in D. Micciancio, editor, TCC\u00a02010: 7th Theory of Cryptography Conference, vol. 5978 of Lecture Notes in Computer Science, Zurich, Switzerland, February\u00a09\u201311. (Springer, Heidelberg, Germany, 2010), pp. 308\u2013326","DOI":"10.1007\/978-3-642-11799-2_19"},{"key":"9432_CR20","doi-asserted-by":"crossref","unstructured":"C. Hazay, A. Polychroniadou, M. Venkitasubramaniam. Composable security in the tamper-proof hardware model under minimal complexity. in Theory of Cryptography Conference. (Springer, 2016), pp. 367\u2013399","DOI":"10.1007\/978-3-662-53641-4_15"},{"key":"9432_CR21","doi-asserted-by":"crossref","unstructured":"R. Impagliazzo, Leonid\u00a0A. Levin, and Michael Luby. Pseudo-random generation from one-way functions (extended abstracts). In 21st Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May\u00a015\u201317. (ACM Press, 1989), pp. 12\u201324","DOI":"10.1145\/73007.73009"},{"key":"9432_CR22","doi-asserted-by":"crossref","unstructured":"J. Katz. Universally composable multi-party computation using tamper-proof hardware. in M. Naor, editor, Advances in Cryptology \u2013 EUROCRYPT\u00a02007, vol. 4515 of Lecture Notes in Computer Science, Barcelona, Spain, May\u00a020\u201324. (Springer, Heidelberg, Germany, 2007), pp. 115\u2013128","DOI":"10.1007\/978-3-540-72540-4_7"},{"key":"9432_CR23","doi-asserted-by":"crossref","unstructured":"J. Kilian. Founding cryptography on oblivious transfer. in 20th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, May\u00a02\u20134. (ACM Press, 1988), pp. 20\u201331","DOI":"10.1145\/62212.62215"},{"key":"9432_CR24","doi-asserted-by":"crossref","unstructured":"R. Maes. Physically Unclonable Functions: Constructions, Properties and Applications, vol. 9783642413957. 11, 2013.","DOI":"10.1007\/978-3-642-41395-7_2"},{"key":"9432_CR25","unstructured":"J. Mechler, J. M\u00fcller-Quade, T. Nilges. Universally composable (non-interactive) two-party computation from untrusted reusable hardware tokens. IACR Cryptology ePrint Archive, 2016:615 (2016)"},{"key":"9432_CR26","doi-asserted-by":"crossref","unstructured":"J. M\u00fcller-Quade and Dominique Unruh. Long-term security and universal composability. In S.\u00a0P. Vadhan, editor, TCC\u00a02007: 4th Theory of Cryptography Conference, vol. 4392 of Lecture Notes in Computer Science, Amsterdam, The Netherlands, February\u00a021\u201324. (Springer, Heidelberg, Germany, 2007), pp. 41\u201360","DOI":"10.1007\/978-3-540-70936-7_3"},{"key":"9432_CR27","doi-asserted-by":"crossref","unstructured":"J. M\u00fcller-Quade, D. Unruh. Long-term security and universal composability. Journal of Cryptology, 23(4):594\u2013671 (2010)","DOI":"10.1007\/s00145-010-9068-8"},{"key":"9432_CR28","doi-asserted-by":"crossref","unstructured":"T. Moran, G. Segev. David and Goliath commitments: UC computation for asymmetric parties using tamper-proof hardware. in N.P. Smart, editor, Advances in Cryptology \u2013 EUROCRYPT\u00a02008, vol. 4965 of Lecture Notes in Computer Science, Istanbul, Turkey, April\u00a013\u201317. (Springer, Heidelberg, Germany, 2008), pp. 527\u2013544","DOI":"10.1007\/978-3-540-78967-3_30"},{"key":"9432_CR29","doi-asserted-by":"crossref","unstructured":"C. Orlandi, R. Ostrovsky, V. Rao, A. Sahai, I. Visconti. Statistical concurrent non-malleable zero knowledge. in Y. Lindell, editor, TCC\u00a02014: 11th Theory of Cryptography Conference, vol. 8349 of Lecture Notes in Computer Science, San Diego, CA, USA, February\u00a024\u201326. (Springer, Heidelberg, Germany, 2014), pp. 167\u2013191","DOI":"10.1007\/978-3-642-54242-8_8"},{"key":"9432_CR30","doi-asserted-by":"crossref","unstructured":"R. Ostrovsky, A. Scafuro, I. Visconti, and A. Wadia. Universally composable secure computation with (malicious) physically uncloneable functions. In T. Johansson, P.\u00a0Q. Nguyen, editors, Advances in Cryptology \u2013 EUROCRYPT\u00a02013, volume 7881 of Lecture Notes in Computer Science, Athens, Greece, May\u00a026\u201330. (Springer, Heidelberg, Germany, 2013), pp. 702\u2013718","DOI":"10.1007\/978-3-642-38348-9_41"},{"key":"9432_CR31","doi-asserted-by":"crossref","unstructured":"C. Peikert, V. Vaikuntanathan, B. Waters. A framework for efficient and composable oblivious transfer. in D. Wagner, editor, Advances in Cryptology \u2013 CRYPTO\u00a02008, vol. 5157 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August\u00a017\u201321. (Springer, Heidelberg, Germany, 2008), pp. 554\u2013571","DOI":"10.1007\/978-3-540-85174-5_31"},{"key":"9432_CR32","doi-asserted-by":"crossref","unstructured":"C. Peikert, B. Waters. Lossy trapdoor functions and their applications. in R.\u00a0E. Ladner, C. Dwork, editors, 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May\u00a017\u201320. (ACM Press, 2008), pp. 187\u2013196","DOI":"10.1145\/1374376.1374406"},{"key":"9432_CR33","doi-asserted-by":"crossref","unstructured":"W. Quach. Uc-secure OT from lwe, revisited. in C. Galdi, V. Kolesnikov, editors, Security and Cryptography for Networks - 12th International Conference, SCN 2020, Amalfi, Italy, September 14\u201316, 2020, Proceedings, vol. 12238 of Lecture Notes in Computer Science. (Springer, 2020), pp. 192\u2013211","DOI":"10.1007\/978-3-030-57990-6_10"},{"key":"9432_CR34","doi-asserted-by":"crossref","unstructured":"M.\u00a0O. Rabin. Hyper encryption and everlasting secrets. in Algorithms and Complexity, 5th Italian Conference, CIAC 2003, Rome, Italy, May 28\u201330, 2003, Proceedings, (Rome, Italy, 2003), pp. 7\u201310","DOI":"10.1007\/3-540-44849-7_7"},{"key":"9432_CR35","doi-asserted-by":"crossref","unstructured":"D. Unruh. Everlasting multi-party computation. in R. Canetti, J. A. Garay, editors, Advances in Cryptology \u2013 CRYPTO\u00a02013, Part\u00a0II, volume 8043 of Lecture Notes in Computer Science, Santa Barbara, CA, USA, August\u00a018\u201322. (Springer, Heidelberg, Germany, 2013), pp. 380\u2013397","DOI":"10.1007\/978-3-642-40084-1_22"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09432-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-022-09432-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09432-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,9,28]],"date-time":"2024-09-28T06:38:23Z","timestamp":1727505503000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-022-09432-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["9432"],"URL":"https:\/\/doi.org\/10.1007\/s00145-022-09432-4","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"1 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 June 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"20"}}