[{"doi":"10.1007/978-3-032-12290-2_16","citation":{"chicago":"Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal, and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation and Friends.” In <i>23rd International Conference on Theory of Cryptography</i>, 16271:478–511. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">https://doi.org/10.1007/978-3-032-12290-2_16</a>.","ieee":"N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained verifiable random functions without obfuscation and friends,” in <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16271, pp. 478–511.","mla":"Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation and Friends.” <i>23rd International Conference on Theory of Cryptography</i>, vol. 16271, Springer Nature, 2025, pp. 478–511, doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">10.1007/978-3-032-12290-2_16</a>.","ama":"Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable random functions without obfuscation and friends. In: <i>23rd International Conference on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:478-511. doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">10.1007/978-3-032-12290-2_16</a>","apa":"Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., &#38; Wohnig, S. (2025). Constrained verifiable random functions without obfuscation and friends. In <i>23rd International Conference on Theory of Cryptography</i> (Vol. 16271, pp. 478–511). Aarhus, Denmark: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_16\">https://doi.org/10.1007/978-3-032-12290-2_16</a>","ista":"Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained verifiable random functions without obfuscation and friends. 23rd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 16271, 478–511.","short":"N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511."},"volume":16271,"quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","corr_author":"1","date_created":"2025-12-21T23:01:34Z","type":"conference","alternative_title":["LNCS"],"conference":{"end_date":"2025-12-05","name":"TCC: Theory of Cryptography","start_date":"2025-12-01","location":"Aarhus, Denmark"},"publication":"23rd International Conference on Theory of Cryptography","status":"public","oa_version":"Preprint","_id":"20846","publication_identifier":{"isbn":["9783032122896"],"issn":["0302-9743"],"eissn":["1611-3349"]},"publication_status":"published","OA_place":"repository","intvolume":"     16271","day":"05","acknowledgement":"We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","OA_type":"green","scopus_import":"1","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}],"publisher":"Springer Nature","abstract":[{"text":"CVRFs are PRFs that unify the properties of verifiable and constrained PRFs. Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy in 2014, it has been an open problem to construct CVRFs without using heavy machinery such as multilinear maps, obfuscation or functional encryption.\r\nWe solve this problem by constructing a prefix-constrained verifiable PRF that does not rely on the aforementioned assumptions. Essentially, our construction is a verifiable version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group elements. These outputs can be verified using pairings since the underlying PRG is of degree 2.\r\nWe prove the selective security of our construction under the Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which we dub recursive Decisional Diffie-Hellman (recursive DDH).\r\nWe prove the soundness of recursive DDH in the generic group model assuming the hardness of the Multivariate Quadratic (MQ) problem and a new variant thereof, which we call MQ+.\r\nLast, in terms of applications, we observe that our CVRF is also an exponent (C)VRF in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25) with various applications to threshold cryptography in mind. In addition to that, we give further applications for prefix-CVRFs in the blockchain setting, namely, stake-pooling and compressible randomness beacons.","lang":"eng"}],"language":[{"iso":"eng"}],"page":"478-511","year":"2025","month":"12","oa":1,"article_processing_charge":"No","department":[{"_id":"KrPi"}],"date_published":"2025-12-05T00:00:00Z","main_file_link":[{"url":"https://eprint.iacr.org/2025/1045","open_access":"1"}],"author":[{"last_name":"Brandt","first_name":"Nicholas","full_name":"Brandt, Nicholas"},{"orcid":"0000-0002-2505-4246","last_name":"Cueto Noval","first_name":"Miguel","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel"},{"full_name":"Günther, Christoph Ullrich","first_name":"Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther"},{"first_name":"Akin","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","orcid":"0000-0002-8929-0221","last_name":"Ünal","full_name":"Ünal, Akin"},{"full_name":"Wohnig, Stella","last_name":"Wohnig","first_name":"Stella"}],"title":"Constrained verifiable random functions without obfuscation and friends","date_updated":"2025-12-29T11:11:29Z"},{"project":[{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8512","_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f"},{"grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","abstract":[{"text":"The blocks in the Bitcoin blockchain \"record\" the amount of work W that went into creating them through proofs of work. When honest parties control a majority of the work, consensus is achieved by picking the chain with the highest recorded weight. Resources other than work have been considered to secure such longest-chain blockchains. In Chia, blocks record the amount of disk-space S (via a proof of space) and sequential computational steps V (through a VDF).\r\nIn this paper, we ask what weight functions Γ(S,V,W) (that assign a weight to a block as a function of the recorded space, speed, and work) are secure in the sense that whenever the weight of the resources controlled by honest parties is larger than the weight of adversarial parties, the blockchain is secure against private double-spending attacks.\r\nWe completely classify such functions in an idealized \"continuous\" model: Γ(S,V,W) is secure against private double-spending attacks if and only if it is homogeneous of degree one in the \"timed\" resources V and W, i.e., αΓ(S,V,W) = Γ(S,α V, α W). This includes the Bitcoin rule Γ(S,V,W) = W and the Chia rule Γ(S,V,W) = S ⋅ V. In a more realistic model where blocks are created at discrete time-points, one additionally needs some mild assumptions on the dependency on S (basically, the weight should not grow too much if S is slightly increased, say linear as in Chia).\r\nOur classification is more general and allows various instantiations of the same resource. It provides a powerful tool for designing new longest-chain blockchains. E.g., consider combining different PoWs to counter centralization, say the Bitcoin PoW W₁ and a memory-hard PoW W₂. Previous work suggested to use W₁+W₂ as weight. Our results show that using e.g., √{W₁}⋅ √{W₂} or min{W₁,W₂} are also secure, and we argue that in practice these are much better choices.","lang":"eng"}],"language":[{"iso":"eng"}],"month":"10","year":"2025","oa":1,"tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"external_id":{"arxiv":["2508.01448"]},"article_processing_charge":"Yes","department":[{"_id":"KrPi"}],"main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1410"}],"author":[{"full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig"},{"last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich"},{"last_name":"Pietrzak","orcid":"0000-0002-9139-1654","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","full_name":"Pietrzak, Krzysztof Z"}],"date_published":"2025-10-06T00:00:00Z","title":"Nakamoto consensus from multiple resources","date_updated":"2026-04-15T08:45:18Z","doi":"10.4230/LIPIcs.AFT.2025.16","article_number":"16","citation":{"mla":"Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” <i>7th Conference on Advances in Financial Technologies</i>, vol. 354, 16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>.","ama":"Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources. In: <i>7th Conference on Advances in Financial Technologies</i>. Vol 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:<a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">10.4230/LIPIcs.AFT.2025.16</a>","apa":"Baig, M. A., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Nakamoto consensus from multiple resources. In <i>7th Conference on Advances in Financial Technologies</i> (Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>","ista":"Baig MA, Günther CU, Pietrzak KZ. 2025. Nakamoto consensus from multiple resources. 7th Conference on Advances in Financial Technologies. AFT: Conference on Advances in Financial Technologies, LIPIcs, vol. 354, 16.","short":"M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.","chicago":"Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Nakamoto Consensus from Multiple Resources.” In <i>7th Conference on Advances in Financial Technologies</i>, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025. <a href=\"https://doi.org/10.4230/LIPIcs.AFT.2025.16\">https://doi.org/10.4230/LIPIcs.AFT.2025.16</a>.","ieee":"M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple resources,” in <i>7th Conference on Advances in Financial Technologies</i>, Pittsburgh, PA, United States, 2025, vol. 354."},"volume":354,"quality_controlled":"1","file_date_updated":"2025-11-04T08:19:02Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"creator":"dernst","file_name":"2025_LIPIcsAFT_Baig.pdf","date_created":"2025-11-04T08:19:02Z","success":1,"access_level":"open_access","file_id":"20598","content_type":"application/pdf","relation":"main_file","checksum":"b638adcd4fbffa77116c35393e165eb7","file_size":1061847,"date_updated":"2025-11-04T08:19:02Z"}],"related_material":{"record":[{"relation":"dissertation_contains","id":"21651","status":"public"}]},"corr_author":"1","date_created":"2025-11-02T23:01:34Z","arxiv":1,"conference":{"location":"Pittsburgh, PA, United States","name":"AFT: Conference on Advances in Financial Technologies","start_date":"2025-10-08","end_date":"2025-10-10"},"type":"conference","alternative_title":["LIPIcs"],"status":"public","publication":"7th Conference on Advances in Financial Technologies","oa_version":"Published Version","publication_identifier":{"issn":["1868-8969"],"isbn":["9783959774000"]},"_id":"20587","day":"06","intvolume":"       354","OA_place":"publisher","publication_status":"published","ddc":["000"],"has_accepted_license":"1","OA_type":"gold","acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF)\r\n10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license\r\nto any author-accepted manuscript version arising from this submission.","scopus_import":"1"},{"conference":{"end_date":"2025-12-05","start_date":"2025-12-01","name":"TCC: Theory of Cryptography","location":"Aarhus, Denmark"},"type":"conference","alternative_title":["LNCS"],"publication":"23rd International Conference on Theory of Cryptography","oa_version":"Preprint","status":"public","corr_author":"1","date_created":"2025-12-21T23:01:33Z","OA_type":"green","acknowledgement":"Jesko Dujmovic: Funded by the European Union (ERC, LACONIC, 101041207). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them.\r\nChristoph U. Günther and Krzysztof Pietrzak: This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.","scopus_import":"1","publication_identifier":{"issn":["0302-9743"],"isbn":["9783032122896"],"eissn":["1611-3349"]},"_id":"20844","OA_place":"repository","day":"05","intvolume":"     16271","publication_status":"published","citation":{"chicago":"Dujmovic, Jesko, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Space-Deniable Proofs.” In <i>23rd International Conference on Theory of Cryptography</i>, 16271:171–202. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">https://doi.org/10.1007/978-3-032-12290-2_6</a>.","ieee":"J. Dujmovic, C. U. Günther, and K. Z. Pietrzak, “Space-deniable proofs,” in <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16271, pp. 171–202.","mla":"Dujmovic, Jesko, et al. “Space-Deniable Proofs.” <i>23rd International Conference on Theory of Cryptography</i>, vol. 16271, Springer Nature, 2025, pp. 171–202, doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">10.1007/978-3-032-12290-2_6</a>.","ama":"Dujmovic J, Günther CU, Pietrzak KZ. Space-deniable proofs. In: <i>23rd International Conference on Theory of Cryptography</i>. Vol 16271. Springer Nature; 2025:171-202. doi:<a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">10.1007/978-3-032-12290-2_6</a>","ista":"Dujmovic J, Günther CU, Pietrzak KZ. 2025. Space-deniable proofs. 23rd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 16271, 171–202.","apa":"Dujmovic, J., Günther, C. U., &#38; Pietrzak, K. Z. (2025). Space-deniable proofs. In <i>23rd International Conference on Theory of Cryptography</i> (Vol. 16271, pp. 171–202). Aarhus, Denmark: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-12290-2_6\">https://doi.org/10.1007/978-3-032-12290-2_6</a>","short":"J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 171–202."},"volume":16271,"doi":"10.1007/978-3-032-12290-2_6","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","cryptoeprintid":1,"quality_controlled":"1","das_tickbox":"1","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1723"}],"author":[{"full_name":"Dujmovic, Jesko","first_name":"Jesko","last_name":"Dujmovic"},{"first_name":"Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther","full_name":"Günther, Christoph Ullrich"},{"full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak"}],"date_published":"2025-12-05T00:00:00Z","date_updated":"2026-07-21T09:17:38Z","title":"Space-deniable proofs","external_id":{"cryptoeprintid":["2025/1723"]},"article_processing_charge":"No","department":[{"_id":"KrPi"}],"publisher":"Springer Nature","abstract":[{"lang":"eng","text":"We introduce and construct a new proof system called Non-interactive Arguments of Knowledge or Space (NArKoS), where a space-bounded prover can convince a verifier they know a secret, while having access to sufficient space allows one to forge indistinguishable proofs without the secret.\r\nAn application of NArKoS are space-deniable proofs, which are proofs of knowledge (say for authentication in access control) that are sound when executed by a lightweight device like a smart-card or an RFID chip that cannot have much storage, but are deniable (in the strong sense of online deniability) as the verifier, like a card reader, can efficiently forge such proofs.\r\nWe construct NArKoS in the random oracle model using an OR-proof combining a sigma protocol (for the proof of knowledge of the secret) with a new proof system called simulatable Proof of Transient Space (simPoTS). We give two different constructions of simPoTS, one based on labelling graphs with high pebbling complexity, a technique used in the construction of memory-hard functions and proofs of space, and a more practical construction based on the verifiable space-hard functions from TCC’24 where a prover must compute a root of a sparse polynomial. In both cases, the main challenge is making the proofs efficiently simulatable."}],"project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}],"oa":1,"language":[{"iso":"eng"}],"year":"2025","month":"12","page":"171-202"},{"oa":1,"month":"05","year":"2024","page":"315-344","isi":1,"language":[{"iso":"eng"}],"abstract":[{"lang":"eng","text":"Memory-hard functions (MHF) are functions whose evaluation provably requires\r\na lot of memory. While MHFs are an unkeyed primitive, it is natural to consider the\r\nnotion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling\r\nthe public parameters one also samples a trapdoor which allows evaluating the\r\nfunction much cheaper.\r\nBiryukov and Perrin (Asiacrypt’17) were the first to consider TMHFs and put\r\nforth a candidate TMHF construction called Diodon that is based on the Scrypt\r\nMHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s initial hash chain\r\nis replaced by a sequence of squares in a group of unknown order where the order of\r\nthe group is the trapdoor. For a length n sequence of squares and a group of order\r\nN, Diodon’s cumulative memory complexity (CMC) is O(n2log N) without the\r\ntrapdoor and O(n log(n) log(N)2) with knowledge of it.\r\nWhile Scrypt is proven to be optimally memory-hard in the random oracle\r\nmodel (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been\r\nproven so far. In this work, we fill this gap by rigorously analyzing a specific\r\ninstantiation of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)\r\nwhich almost matches the upper bound. Our proof is based Alwen et al.’s lower\r\nbound on Scrypt’s CMC but requires non-trivial modifications due to the algebraic\r\nstructure of Diodon. Most importantly, our analysis involves a more elaborate\r\ncompression argument and a solvability criterion for certain systems of Diophantine\r\nequations."}],"publisher":"Springer Nature","project":[{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"date_updated":"2025-09-08T07:35:40Z","title":"Trapdoor memory-hard functions","main_file_link":[{"url":"https://eprint.iacr.org/2024/312","open_access":"1"}],"author":[{"id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","orcid":"0000-0002-7553-6606","last_name":"Auerbach","full_name":"Auerbach, Benedikt"},{"full_name":"Günther, Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","last_name":"Günther"},{"full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654"}],"date_published":"2024-05-01T00:00:00Z","department":[{"_id":"KrPi"}],"external_id":{"isi":["001274940200011"]},"article_processing_charge":"No","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","quality_controlled":"1","volume":14653,"citation":{"short":"B. Auerbach, C.U. Günther, K.Z. Pietrzak, in:, 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Nature, 2024, pp. 315–344.","ista":"Auerbach B, Günther CU, Pietrzak KZ. 2024. Trapdoor memory-hard functions. 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol. 14653, 315–344.","apa":"Auerbach, B., Günther, C. U., &#38; Pietrzak, K. Z. (2024). Trapdoor memory-hard functions. In <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i> (Vol. 14653, pp. 315–344). Zurich, Switzerland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">https://doi.org/10.1007/978-3-031-58734-4_11</a>","ama":"Auerbach B, Günther CU, Pietrzak KZ. Trapdoor memory-hard functions. In: <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>. Vol 14653. Springer Nature; 2024:315-344. doi:<a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">10.1007/978-3-031-58734-4_11</a>","mla":"Auerbach, Benedikt, et al. “Trapdoor Memory-Hard Functions.” <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, vol. 14653, Springer Nature, 2024, pp. 315–44, doi:<a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">10.1007/978-3-031-58734-4_11</a>.","ieee":"B. Auerbach, C. U. Günther, and K. Z. Pietrzak, “Trapdoor memory-hard functions,” in <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, Zurich, Switzerland, 2024, vol. 14653, pp. 315–344.","chicago":"Auerbach, Benedikt, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Trapdoor Memory-Hard Functions.” In <i>43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, 14653:315–44. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-58734-4_11\">https://doi.org/10.1007/978-3-031-58734-4_11</a>."},"doi":"10.1007/978-3-031-58734-4_11","scopus_import":"1","acknowledgement":"We thank the Eurocrypt reviewers for their thorough review and for pointing out related works. This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","day":"01","intvolume":"     14653","publication_status":"published","publication_identifier":{"issn":["0302-9743"],"isbn":["9783031587337"],"eissn":["1611-3349"]},"_id":"17051","status":"public","publication":"43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques","oa_version":"Preprint","conference":{"location":"Zurich, Switzerland","start_date":"2024-05-26","name":"EUROCRYPT: Theory and Applications of Cryptographic Techniques","end_date":"2024-05-30"},"type":"conference","alternative_title":["LNCS"],"date_created":"2024-05-26T22:00:58Z","corr_author":"1"},{"OA_place":"publisher","intvolume":"      2024","day":"01","publication_status":"published","publication_identifier":{"issn":["2299-0984"]},"_id":"18961","ddc":["000"],"acknowledgement":"We thank Raluca-Georgia Diugan for her initial contributions and support afterward.\r\nThis research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","has_accepted_license":"1","OA_type":"gold","date_created":"2025-01-29T13:39:34Z","corr_author":"1","oa_version":"Published Version","publication":"Proceedings on Privacy Enhancing Technologies","status":"public","conference":{"start_date":"2024-07-15","name":"PETs: Privacy Enhancing Technologies Symposium ","location":"Bristol, UK/Virtual","end_date":"2024-07-20"},"type":"journal_article","file_date_updated":"2025-01-29T13:44:47Z","quality_controlled":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","file":[{"file_name":"2024_ProcPrivacyEnhTech_Guenther.pdf","creator":"dernst","date_created":"2025-01-29T13:44:47Z","success":1,"access_level":"open_access","file_id":"18962","relation":"main_file","content_type":"application/pdf","checksum":"348ed6adcf6ad2f925227bde1758cae6","date_updated":"2025-01-29T13:44:47Z","file_size":611567}],"doi":"10.56553/popets-2024-0134","volume":2024,"citation":{"chicago":"Günther, Christoph Ullrich, and Krzysztof Z Pietrzak. “Deniability in Automated Contact Tracing: Impossibilities and Possibilities.” <i>Proceedings on Privacy Enhancing Technologies</i>. Privacy Enhancing Technologies Symposium Advisory Board, 2024. <a href=\"https://doi.org/10.56553/popets-2024-0134\">https://doi.org/10.56553/popets-2024-0134</a>.","ieee":"C. U. Günther and K. Z. Pietrzak, “Deniability in automated contact tracing: Impossibilities and possibilities,” <i>Proceedings on Privacy Enhancing Technologies</i>, vol. 2024, no. 4. Privacy Enhancing Technologies Symposium Advisory Board, pp. 636–648, 2024.","ama":"Günther CU, Pietrzak KZ. Deniability in automated contact tracing: Impossibilities and possibilities. <i>Proceedings on Privacy Enhancing Technologies</i>. 2024;2024(4):636-648. doi:<a href=\"https://doi.org/10.56553/popets-2024-0134\">10.56553/popets-2024-0134</a>","short":"C.U. Günther, K.Z. Pietrzak, Proceedings on Privacy Enhancing Technologies 2024 (2024) 636–648.","ista":"Günther CU, Pietrzak KZ. 2024. Deniability in automated contact tracing: Impossibilities and possibilities. Proceedings on Privacy Enhancing Technologies. 2024(4), 636–648.","apa":"Günther, C. U., &#38; Pietrzak, K. Z. (2024). Deniability in automated contact tracing: Impossibilities and possibilities. <i>Proceedings on Privacy Enhancing Technologies</i>. Bristol, UK/Virtual: Privacy Enhancing Technologies Symposium Advisory Board. <a href=\"https://doi.org/10.56553/popets-2024-0134\">https://doi.org/10.56553/popets-2024-0134</a>","mla":"Günther, Christoph Ullrich, and Krzysztof Z. Pietrzak. “Deniability in Automated Contact Tracing: Impossibilities and Possibilities.” <i>Proceedings on Privacy Enhancing Technologies</i>, vol. 2024, no. 4, Privacy Enhancing Technologies Symposium Advisory Board, 2024, pp. 636–48, doi:<a href=\"https://doi.org/10.56553/popets-2024-0134\">10.56553/popets-2024-0134</a>."},"article_type":"original","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"article_processing_charge":"No","issue":"4","date_updated":"2025-04-15T08:16:04Z","title":"Deniability in automated contact tracing: Impossibilities and possibilities","author":[{"last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich"},{"orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z"}],"date_published":"2024-07-01T00:00:00Z","tmp":{"image":"/images/cc_by.png","short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"page":"636-648","year":"2024","month":"07","language":[{"iso":"eng"}],"oa":1,"project":[{"grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"abstract":[{"lang":"eng","text":"Automated contact tracing (ACT) emerged as a promising measure to curb the spread of Covid-19. Users enable ACT on their smartphones to automatically record contacts with other users. If a user tests positive for the disease, they report their diagnosis to alert their contacts.\r\nDesigning effective ACT protocols is challenging since they need to be efficient and secure while also ensuring users' privacy. As ACT protocols necessarily leak some information by design, defining privacy is difficult. For example, a user cannot deny having met another user. Ideally, however, the user can plausibly deny everything else, in particular, when they met. We call this privacy property contact-time deniability.\r\nWhile some early works discussed contact-time deniability informally, it has received little attention since then. We investigate deniability from a rigorous, theoretical point of view and arrive at the following impossibility result:\r\nA decentralized protocol with unidirectional communication cannot be contact-time deniable and replay-secure. This holds even if malicious users treat smartphones as black-boxes.\r\n Unidirectional protocols are usually very efficient and many proposals are unidirectional, e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility result considerably constrains the design space of efficient, secure, and private ACT protocols. However, it can also be used as a guide; we discuss several possibilities to achieve contact-time deniability in practice."}],"publisher":"Privacy Enhancing Technologies Symposium Advisory Board"}]