[{"doi":"10.1007/978-3-032-07024-1_18","author":[{"last_name":"Neiheiser","id":"f09651b9-fec0-11ec-b5d8-934aff0e52a4","full_name":"Neiheiser, Ray","orcid":"0000-0001-7227-8309","first_name":"Ray"},{"first_name":"Eleftherios","full_name":"Kokoris Kogias, Eleftherios","orcid":"0000-0002-8827-3382","last_name":"Kokoris Kogias","id":"f5983044-d7ef-11ea-ac6d-fd1430a26d30"}],"arxiv":1,"volume":15751,"type":"conference","month":"01","acknowledgement":"This work was supported by the Austrian Science Fund (FWF) SFB project SpyCoDe F8502 and the Vienna Science and Technology Fund (WWTF) project SCALE2 CT22-045.","publication_status":"published","oa_version":"Preprint","alternative_title":["LNCS"],"OA_place":"repository","_id":"21042","oa":1,"project":[{"_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e","name":"Interface Theory for Security and Privacy","grant_number":"F8502"},{"_id":"7bdd2f70-9f16-11ee-852c-b7950bc6d277","name":"SeCure, privAte, and interoperabLe layEr 2","grant_number":"ICT22-045"}],"quality_controlled":"1","page":"307-323","OA_type":"green","abstract":[{"lang":"eng","text":"Many blockchains such as Ethereum execute all incoming transactions sequentially significantly limiting the potential throughput. A common approach to scale execution is parallel execution engines that fully utilize modern multi-core architectures. Parallel execution is then either done optimistically, by executing transactions in parallel and detecting conflicts on the fly, or guided, by requiring exhaustive client transaction hints and scheduling transactions accordingly.\r\n\r\nHowever, recent studies have shown that the performance of parallel execution engines depends on the nature of the underlying workload. In fact, in some cases, only a 60% speed-up compared to sequential execution could be obtained. This is the case, as transactions that access the same resources must be executed sequentially. For example, if 10% of the transactions in a block access the same resource, the execution cannot meaningfully scale beyond 10 cores. Therefore, a single popular application can bottleneck the execution and limit the potential throughput.\r\n\r\nIn this paper, we introduce Anthemius, a block construction algorithm that optimizes parallel transaction execution throughput. We evaluate Anthemius exhaustively under a range of workloads, and show that Anthemius enables the underlying parallel execution engine to process over twice as many transactions."}],"date_created":"2026-01-25T23:01:40Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.48550/arXiv.2502.10074"}],"date_published":"2026-01-01T00:00:00Z","department":[{"_id":"KrPi"}],"publication":"29th International Conference on Financial Cryptography and Data Security","day":"01","language":[{"iso":"eng"}],"title":"Anthemius: Efficient and modular block assembly for concurrent execution","intvolume":"     15751","conference":{"location":"Miyakojima, Japan","start_date":"2025-04-14","name":"FC: Financial Cryptography and Data Security","end_date":"2025-04-18"},"scopus_import":"1","article_processing_charge":"No","date_updated":"2026-02-12T13:39:07Z","publication_identifier":{"isbn":["9783032070234"],"issn":["0302-9743"],"eissn":["1611-3349"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"chicago":"Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient and Modular Block Assembly for Concurrent Execution.” In <i>29th International Conference on Financial Cryptography and Data Security</i>, 15751:307–23. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">https://doi.org/10.1007/978-3-032-07024-1_18</a>.","short":"R. Neiheiser, E. Kokoris Kogias, in:, 29th International Conference on Financial Cryptography and Data Security, Springer Nature, 2026, pp. 307–323.","mla":"Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient and Modular Block Assembly for Concurrent Execution.” <i>29th International Conference on Financial Cryptography and Data Security</i>, vol. 15751, Springer Nature, 2026, pp. 307–23, doi:<a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">10.1007/978-3-032-07024-1_18</a>.","ama":"Neiheiser R, Kokoris Kogias E. Anthemius: Efficient and modular block assembly for concurrent execution. In: <i>29th International Conference on Financial Cryptography and Data Security</i>. Vol 15751. Springer Nature; 2026:307-323. doi:<a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">10.1007/978-3-032-07024-1_18</a>","ieee":"R. Neiheiser and E. Kokoris Kogias, “Anthemius: Efficient and modular block assembly for concurrent execution,” in <i>29th International Conference on Financial Cryptography and Data Security</i>, Miyakojima, Japan, 2026, vol. 15751, pp. 307–323.","ista":"Neiheiser R, Kokoris Kogias E. 2026. Anthemius: Efficient and modular block assembly for concurrent execution. 29th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15751, 307–323.","apa":"Neiheiser, R., &#38; Kokoris Kogias, E. (2026). Anthemius: Efficient and modular block assembly for concurrent execution. In <i>29th International Conference on Financial Cryptography and Data Security</i> (Vol. 15751, pp. 307–323). Miyakojima, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-07024-1_18\">https://doi.org/10.1007/978-3-032-07024-1_18</a>"},"publisher":"Springer Nature","corr_author":"1","year":"2026","external_id":{"arxiv":["2502.10074"]},"status":"public"},{"department":[{"_id":"KrPi"}],"publication":"29th International Conference on Financial Cryptography and Data Security","day":"01","abstract":[{"text":"The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under “resource variability”, i.e., if the total hashing power varies greatly over time.\r\nProofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.\r\nThe Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof of work as a voting mechanism. Honest miners who contribute hashing power towards securing the chain try to extend the longest chain they are aware of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming that at any point in time, a majority of the hashing power is controlled by honest parties. This also holds under “resource variability”, i.e., if the total hashing power varies greatly over time.\r\n\r\nProofs of space (PoSpace) have been suggested as a more sustainable replacement for proofs of work. Unfortunately, no construction of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic availability, is known. In this work, we prove that without additional assumptions no such protocol exists. We exactly quantify this impossibility result by proving a bound on the length of the fork required for double spending as a function of the adversarial capabilities. This bound holds for any chain selection rule, and we also show a chain selection rule (albeit a very strange one) that almost matches this bound.\r\n\r\nConcretely, we consider a security game in which the honest parties at any point control 0 > 1\r\n times more space than the adversary. The adversary can change the honest space by a factor 1+- E with every block (dynamic availability), and “replotting” the space (which allows answering two challenges using the same space) takes as much time as p blocks.\r\nWe prove that no matter what chain selection rule is used, in this game the adversary can create a fork of length o^2 . p/E that will be picked as the winner by the chain selection rule.\r\nWe also provide an upper bound that matches the lower bound up to a factor o. There exists a chain selection rule (albeit a very strange one) which in the above game requires forks of length at least o . p/E\r\nOur results show the necessity of additional assumptions to create a secure PoSpace based longest-chain blockchain. The Chia network in addition to PoSpace uses a verifiable delay function. Our bounds show that an additional primitive like that is necessary.","lang":"eng"}],"date_created":"2026-02-01T23:01:43Z","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.2505.14891","open_access":"1"}],"date_published":"2026-01-01T00:00:00Z","title":"On the (in)security of Proofs-of-space based longest-chain blockchains","intvolume":"     15752","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","conference":{"start_date":"2025-04-14","location":"Miyakojima, Japan","name":"FC: Financial Cryptography and Data Security","end_date":"2025-04-18"},"article_processing_charge":"No","date_updated":"2026-04-15T08:45:18Z","publication_identifier":{"isbn":["9783032070340"],"eissn":["1611-3349"],"issn":["0302-9743"]},"corr_author":"1","year":"2026","status":"public","external_id":{"arxiv":["2505.14891"]},"citation":{"mla":"Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space Based Longest-Chain Blockchains.” <i>29th International Conference on Financial Cryptography and Data Security</i>, vol. 15752, Springer Nature, 2026, pp. 127–42, doi:<a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">10.1007/978-3-032-07035-7_8</a>.","chicago":"Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space Based Longest-Chain Blockchains.” In <i>29th International Conference on Financial Cryptography and Data Security</i>, 15752:127–42. Springer Nature, 2026. <a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">https://doi.org/10.1007/978-3-032-07035-7_8</a>.","short":"M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.","apa":"Baig, M. A., &#38; Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space based longest-chain blockchains. In <i>29th International Conference on Financial Cryptography and Data Security</i> (Vol. 15752, pp. 127–142). Miyakojima, Japan: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">https://doi.org/10.1007/978-3-032-07035-7_8</a>","ista":"Baig MA, Pietrzak KZ. 2026. On the (in)security of Proofs-of-space based longest-chain blockchains. 29th International Conference on Financial Cryptography and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15752, 127–142.","ama":"Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain blockchains. In: <i>29th International Conference on Financial Cryptography and Data Security</i>. Vol 15752. Springer Nature; 2026:127-142. doi:<a href=\"https://doi.org/10.1007/978-3-032-07035-7_8\">10.1007/978-3-032-07035-7_8</a>","ieee":"M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based longest-chain blockchains,” in <i>29th International Conference on Financial Cryptography and Data Security</i>, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142."},"publisher":"Springer Nature","arxiv":1,"type":"conference","volume":15752,"month":"01","acknowledgement":"This research was funded in whole or in part by the Austrian Science Fund (FWF) 10.55776/F85.","publication_status":"published","doi":"10.1007/978-3-032-07035-7_8","author":[{"full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","last_name":"Baig","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"oa_version":"Preprint","alternative_title":["LNCS"],"oa":1,"_id":"21134","related_material":{"record":[{"status":"public","id":"21651","relation":"dissertation_contains"}]},"OA_place":"repository","quality_controlled":"1","OA_type":"green","page":"127-142","project":[{"_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1","grant_number":"F8509","name":"Security and Privacy by Design for Complex Systems"}]},{"alternative_title":["ISTA Thesis"],"oa_version":"Published Version","supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"degree_awarded":"PhD","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"month":"03","type":"dissertation","publication_status":"published","file":[{"file_name":"PhD-Thesis-Mirza-Ahad-Baig - Library Submission.zip","content_type":"application/x-zip-compressed","file_size":139353434,"access_level":"closed","file_id":"21655","creator":"mbaig","checksum":"c3986dba90653dac97adba662ebff238","relation":"source_file","date_updated":"2026-04-13T08:24:13Z","date_created":"2026-04-03T17:28:48Z"},{"file_name":"2026_Baig_Mirza_Ahad_Thesis.pdf","content_type":"application/pdf","file_size":1942037,"access_level":"open_access","creator":"mbaig","checksum":"292a5989262521f7c145a109d1f348cb","file_id":"21656","date_updated":"2026-04-15T07:37:25Z","relation":"main_file","date_created":"2026-04-03T17:29:30Z"}],"doi":"10.15479/AT-ISTA-21651","author":[{"full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig"}],"oa":1,"_id":"21651","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"21134"},{"id":"20587","relation":"part_of_dissertation","status":"public"}]},"OA_place":"publisher","title":"On secure chain selection rules from physical resources in a permissionless setting","language":[{"iso":"eng"}],"license":"https://creativecommons.org/licenses/by-nc-sa/4.0/","day":"04","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"date_created":"2026-04-02T09:31:34Z","abstract":[{"text":"Blockchains enable distributed consensus in permissionless settings, where participants\r\nare unknown, dynamically changing, and do not trust each other. While Bitcoin,\r\nbased on Proof-of-Work (PoW), was the first protocol in this model, significant\r\nresearch has focused on permissionless protocols using alternative physical resources,\r\nspecifically Proof-of-Space (PoSpace) and Verifiable Delay Functions (VDFs). This\r\nthesis investigates the theoretical limits and design space of longest-chain protocols in\r\nthe fully permissionless and dynamically available settings using these three resources.\r\nFirst, we address the feasibility of blockchains relying solely on storage as a resource.\r\nWe prove a fundamental impossibility result: there exists no secure longest-chain\r\nprotocol based exclusively on Proof-of-Space in the fully permissionless or dynamically\r\navailable settings. Further, we quantify the adversarial capabilities required to execute\r\na double-spend attack. Our result formally justifies the necessity of coupling PoSpace\r\nwith time-dependent primitives (such as VDFs) or to move to less permissive settings\r\n(quasi-permissionless or permissioned) to ensure security.\r\nSecond, we generalize Nakamoto-like heaviest chain consensus to protocols utilizing\r\ncombinations of multiple physical resources. We analyze chain selection rules governed\r\nby a weight function Γ(S, V,W), which assigns weight to blocks based on recorded\r\nSpace (S), VDF speed (V ), and Work (W). We provide a complete classification\r\nof secure weight functions, proving that a weight function is secure against private\r\ndouble-spend attacks if and only if it is homogeneous in the timed resources (V,W)\r\nand sub-homogeneous in S. This framework unifies existing protocols like Bitcoin and\r\nChia under a single theoretical model and provides a powerful tool for designing new\r\nlongest-chain blockchains from a mix of physical resources.","lang":"eng"}],"ddc":["000"],"date_published":"2026-03-04T00:00:00Z","year":"2026","corr_author":"1","status":"public","citation":{"mla":"Baig, Mirza Ahad. <i>On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting</i>. Institute of Science and Technology Austria, 2026, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21651\">10.15479/AT-ISTA-21651</a>.","short":"M.A. Baig, On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting, Institute of Science and Technology Austria, 2026.","chicago":"Baig, Mirza Ahad. “On Secure Chain Selection Rules from Physical Resources in a Permissionless Setting.” Institute of Science and Technology Austria, 2026. <a href=\"https://doi.org/10.15479/AT-ISTA-21651\">https://doi.org/10.15479/AT-ISTA-21651</a>.","apa":"Baig, M. A. (2026). <i>On secure chain selection rules from physical resources in a permissionless setting</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-21651\">https://doi.org/10.15479/AT-ISTA-21651</a>","ista":"Baig MA. 2026. On secure chain selection rules from physical resources in a permissionless setting. Institute of Science and Technology Austria.","ama":"Baig MA. On secure chain selection rules from physical resources in a permissionless setting. 2026. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-21651\">10.15479/AT-ISTA-21651</a>","ieee":"M. A. Baig, “On secure chain selection rules from physical resources in a permissionless setting,” Institute of Science and Technology Austria, 2026."},"publisher":"Institute of Science and Technology Austria","user_id":"8b945eb4-e2f2-11eb-945a-df72226e66a9","has_accepted_license":"1","article_processing_charge":"No","publication_identifier":{"issn":["2663-337X"],"isbn":["978-3-99078-078-7"]},"date_updated":"2026-04-15T08:45:19Z","file_date_updated":"2026-04-15T07:37:25Z"},{"publisher":"Association for Computing Machinery","citation":{"ieee":"K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, and M. X. Yeo, “When is liquid democracy possible?: On the manipulation of variance,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Huatulco, Mexico, 2025, pp. 241–251.","ama":"Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. When is liquid democracy possible?: On the manipulation of variance. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2025:241-251. doi:<a href=\"https://doi.org/10.1145/3732772.3733544\">10.1145/3732772.3733544</a>","ista":"Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. 2025. When is liquid democracy possible?: On the manipulation of variance. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 241–251.","apa":"Chatterjee, K., Gilbert, S., Schmid, S., Svoboda, J., &#38; Yeo, M. X. (2025). When is liquid democracy possible?: On the manipulation of variance. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 241–251). Huatulco, Mexico: Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3732772.3733544\">https://doi.org/10.1145/3732772.3733544</a>","short":"K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, M.X. Yeo, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2025, pp. 241–251.","chicago":"Chatterjee, Krishnendu, Seth Gilbert, Stefan Schmid, Jakub Svoboda, and Michelle X Yeo. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 241–51. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3732772.3733544\">https://doi.org/10.1145/3732772.3733544</a>.","mla":"Chatterjee, Krishnendu, et al. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2025, pp. 241–51, doi:<a href=\"https://doi.org/10.1145/3732772.3733544\">10.1145/3732772.3733544</a>."},"status":"public","external_id":{"isi":["001525534800030"]},"corr_author":"1","year":"2025","date_updated":"2026-02-16T11:46:51Z","file_date_updated":"2025-08-05T07:15:31Z","publication_identifier":{"isbn":["9798400718854"]},"conference":{"location":"Huatulco, Mexico","start_date":"2025-06-16","end_date":"2025-06-20","name":"PODC: Symposium on Principles of Distributed Computing"},"article_processing_charge":"No","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","language":[{"iso":"eng"}],"ec_funded":1,"title":"When is liquid democracy possible?: On the manipulation of variance","date_published":"2025-06-13T00:00:00Z","ddc":["000"],"abstract":[{"lang":"eng","text":"Liquid democracy is a transitive vote delegation mechanism over voting graphs. It enables each voter to delegate their vote(s) to another better-informed voter, with the goal of collectively making a better decision. The question of whether liquid democracy outperforms direct voting has been previously studied in the context of local delegation mechanisms (where voters can only delegate to someone in their neighbourhood) and binary decision problems. It has previously been shown that it is impossible for local delegation mechanisms to outperform direct voting in general graphs. This raises the question: for which classes of graphs do local delegation mechanisms yield good results?\r\nIn this work, we analyse (1) properties of specific graphs and (2) properties of local delegation mechanisms on these graphs, determining where local delegation actually outperforms direct voting. We show that a critical graph property enabling liquid democracy is that the voting outcome of local delegation mechanisms preserves a sufficient amount of variance, thereby avoiding situations where delegation falls behind direct voting1. These insights allow us to prove our main results, namely that there exist local delegation mechanisms that perform no worse and in fact quantitatively better than direct voting in natural graph topologies like complete, random d-regular, and bounded degree graphs, lending a more nuanced perspective to previous impossibility results."}],"date_created":"2025-07-21T08:18:26Z","main_file_link":[{"url":"https://eprint.iacr.org/2025/745","open_access":"1"}],"publication":"Proceedings of the ACM Symposium on Principles of Distributed Computing","department":[{"_id":"KrCh"},{"_id":"KrPi"}],"day":"13","project":[{"call_identifier":"H2020","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818"}],"isi":1,"OA_type":"hybrid","page":"241-251","quality_controlled":"1","OA_place":"publisher","_id":"20053","oa":1,"tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","author":[{"full_name":"Chatterjee, Krishnendu","orcid":"0000-0002-4561-241X","first_name":"Krishnendu","last_name":"Chatterjee","id":"2E5DCA20-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Gilbert, Seth","first_name":"Seth","last_name":"Gilbert"},{"first_name":"Stefan","full_name":"Schmid, Stefan","last_name":"Schmid"},{"orcid":"0000-0002-1419-3267","full_name":"Svoboda, Jakub","first_name":"Jakub","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425","last_name":"Svoboda"},{"last_name":"Yeo","id":"2D82B818-F248-11E8-B48F-1D18A9856A87","first_name":"Michelle X","full_name":"Yeo, Michelle X","orcid":"0009-0001-3676-4809"}],"doi":"10.1145/3732772.3733544","file":[{"date_created":"2025-08-05T07:15:31Z","date_updated":"2025-08-05T07:15:31Z","relation":"main_file","file_id":"20122","creator":"dernst","checksum":"cd628fe54d96e9fc6cc789bb8145422b","access_level":"open_access","file_size":783297,"file_name":"2025_PODC_Chatterjee.pdf","content_type":"application/pdf","success":1}],"acknowledgement":"This work was partially supported by MOE-T2EP20122-0014 (DataDriven Distributed Algorithms), German Research Foundation (DFG) project ReNO (SPP 2378) from 2023-2027, ERC CoG 863818 (ForMSMArt) and Austrian Science Fund (FWF) 10.55776/COE12.","publication_status":"published","type":"conference","month":"06"},{"OA_place":"repository","oa":1,"_id":"19600","project":[{"call_identifier":"H2020","name":"Formal Methods for Stochastic Models: Algorithms and Applications","grant_number":"863818","_id":"0599E47C-7A3F-11EA-A408-12923DDC885E"}],"page":"207-223","OA_type":"green","quality_controlled":"1","author":[{"first_name":"Zeta","full_name":"Avarikioti, Zeta","last_name":"Avarikioti"},{"last_name":"Bastankhah","full_name":"Bastankhah, Mahsa","first_name":"Mahsa"},{"full_name":"Maddah-Ali, Mohammad Ali","first_name":"Mohammad Ali","last_name":"Maddah-Ali"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"},{"full_name":"Svoboda, Jakub","orcid":"0000-0002-1419-3267","first_name":"Jakub","last_name":"Svoboda","id":"130759D2-D7DD-11E9-87D2-DE0DE6697425"},{"id":"2D82B818-F248-11E8-B48F-1D18A9856A87","last_name":"Yeo","orcid":"0009-0001-3676-4809","full_name":"Yeo, Michelle X","first_name":"Michelle X"}],"doi":"10.1007/978-3-031-82349-7_15","acknowledgement":"This work was supported in part by the ERC CoG 863818 (ForM-SMArt), Austrian Science Fund (FWF) 10.55776/COE12, and MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grants.","publication_status":"published","volume":15263,"type":"conference","month":"04","oa_version":"Submitted Version","alternative_title":["LNCS"],"date_updated":"2025-11-05T07:52:35Z","publication_identifier":{"isbn":["9783031823480"],"eissn":["1611-3349"],"issn":["0302-9743"]},"conference":{"end_date":"2024-09-20","name":"ESORICS: European Symposium on Research in Computer Security","location":"Bydgoszcz, Poland","start_date":"2024-09-16"},"scopus_import":"1","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","citation":{"ieee":"Z. Avarikioti, M. Bastankhah, M. A. Maddah-Ali, K. Z. Pietrzak, J. Svoboda, and M. X. Yeo, “Route discovery in private payment channel networks,” in <i>Computer Security. ESORICS 2024 International Workshops</i>, Bydgoszcz, Poland, 2025, vol. 15263, pp. 207–223.","ama":"Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX. Route discovery in private payment channel networks. In: <i>Computer Security. ESORICS 2024 International Workshops</i>. Vol 15263. Springer Nature; 2025:207-223. doi:<a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">10.1007/978-3-031-82349-7_15</a>","apa":"Avarikioti, Z., Bastankhah, M., Maddah-Ali, M. A., Pietrzak, K. Z., Svoboda, J., &#38; Yeo, M. X. (2025). Route discovery in private payment channel networks. In <i>Computer Security. ESORICS 2024 International Workshops</i> (Vol. 15263, pp. 207–223). Bydgoszcz, Poland: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">https://doi.org/10.1007/978-3-031-82349-7_15</a>","ista":"Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX. 2025. Route discovery in private payment channel networks. Computer Security. ESORICS 2024 International Workshops. ESORICS: European Symposium on Research in Computer Security, LNCS, vol. 15263, 207–223.","chicago":"Avarikioti, Zeta, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof Z Pietrzak, Jakub Svoboda, and Michelle X Yeo. “Route Discovery in Private Payment Channel Networks.” In <i>Computer Security. ESORICS 2024 International Workshops</i>, 15263:207–23. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">https://doi.org/10.1007/978-3-031-82349-7_15</a>.","short":"Z. Avarikioti, M. Bastankhah, M.A. Maddah-Ali, K.Z. Pietrzak, J. Svoboda, M.X. Yeo, in:, Computer Security. ESORICS 2024 International Workshops, Springer Nature, 2025, pp. 207–223.","mla":"Avarikioti, Zeta, et al. “Route Discovery in Private Payment Channel Networks.” <i>Computer Security. ESORICS 2024 International Workshops</i>, vol. 15263, Springer Nature, 2025, pp. 207–23, doi:<a href=\"https://doi.org/10.1007/978-3-031-82349-7_15\">10.1007/978-3-031-82349-7_15</a>."},"status":"public","year":"2025","date_published":"2025-04-01T00:00:00Z","abstract":[{"text":"In this work, we explore route discovery in private payment channel networks. We first determine what “ideal\" privacy for a routing protocol means in this setting. We observe that protocols achieving this strong privacy definition exist by leveraging Multi-Party Computation but they are inherently inefficient as they must involve the entire network. We then present protocols with weaker privacy guarantees but much better efficiency (involving only a small fraction of the nodes). The core idea is that both sender and receiver gossip a message which propagates through the network, and the moment any node in the network receives both messages, a path is found. In our first protocol the message is always sent to all neighbouring nodes with a delay proportional to the fees of that edge. In our second protocol the message is only sent to one neighbour chosen randomly with a probability proportional to its degree. We additionally propose a more realistic notion of privacy in order to measure the privacy leakage of our protocols in practice. Our realistic notion of privacy challenges an adversary that join the network with a fixed budget to create channels to guess the sender and receiver of a transaction upon receiving messages from our protocols. Simulations of our protocols on the Lightning network topology (for random transactions and uniform fees) show that 1) forming edges with high degree nodes is a more effective attack strategy for the adversary, 2) there is a tradeoff between the number of nodes involved in our protocols (privacy) and the optimality of the discovered path, and 3) our protocols involve a very small fraction of the network on average.","lang":"eng"}],"date_created":"2025-04-20T22:01:28Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2021/1539"}],"publication":"Computer Security. ESORICS 2024 International Workshops","department":[{"_id":"KrPi"},{"_id":"KrCh"}],"day":"01","language":[{"iso":"eng"}],"ec_funded":1,"intvolume":"     15263","title":"Route discovery in private payment channel networks"},{"intvolume":"     15606","title":"On the soundness of algebraic attacks against code-based assumptions","language":[{"iso":"eng"}],"day":"28","publication":"44th Annual International Conference on the Theory and Applications of Cryptographic Techniques","department":[{"_id":"KrPi"}],"main_file_link":[{"url":"https://www.research-collection.ethz.ch/handle/20.500.11850/732894","open_access":"1"}],"date_created":"2025-05-19T14:15:01Z","abstract":[{"lang":"eng","text":"We study recent algebraic attacks (Briaud-Øygarden EC’23) on the Regular Syndrome Decoding (RSD) problem and the assumptions underlying the correctness of their attacks’ complexity estimates. By relating these assumptions to interesting algebraic-combinatorial problems, we prove that they do not hold in full generality. However, we show that they are (asymptotically) true for most parameter sets, supporting the soundness of algebraic attacks on RSD. Further, we prove—without any heuristics or assumptions—that RSD can be broken in polynomial time whenever the number of error blocks times the square of the size of error blocks is larger than 2 times the square of the dimension of the code.\r\nAdditionally, we use our methodology to attack a variant of the Learning With Errors problem where each error term lies in a fixed set of constant size. We prove that this problem can be broken in polynomial time, given a sufficient number of samples. This result improves on the seminal work by Arora and Ge (ICALP’11), as the attack’s time complexity is independent of the LWE modulus."}],"date_published":"2025-04-28T00:00:00Z","corr_author":"1","year":"2025","status":"public","citation":{"apa":"Cueto Noval, M., Merz, S.-P., Stählin, P., &#38; Ünal, A. (2025). On the soundness of algebraic attacks against code-based assumptions. In <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i> (Vol. 15606, pp. 385–415). Madrid, Spain: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">https://doi.org/10.1007/978-3-031-91095-1_14</a>","ista":"Cueto Noval M, Merz S-P, Stählin P, Ünal A. 2025. On the soundness of algebraic attacks against code-based assumptions. 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques. EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol. 15606, 385–415.","ieee":"M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic attacks against code-based assumptions,” in <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, Madrid, Spain, 2025, vol. 15606, pp. 385–415.","ama":"Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic attacks against code-based assumptions. In: <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>. Vol 15606. Springer Nature; 2025:385-415. doi:<a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">10.1007/978-3-031-91095-1_14</a>","mla":"Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against Code-Based Assumptions.” <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, vol. 15606, Springer Nature, 2025, pp. 385–415, doi:<a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">10.1007/978-3-031-91095-1_14</a>.","short":"M. Cueto Noval, S.-P. Merz, P. Stählin, A. Ünal, in:, 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer Nature, 2025, pp. 385–415.","chicago":"Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal. “On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In <i>44th Annual International Conference on the Theory and Applications of Cryptographic Techniques</i>, 15606:385–415. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91095-1_14\">https://doi.org/10.1007/978-3-031-91095-1_14</a>."},"publisher":"Springer Nature","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","conference":{"location":"Madrid, Spain","start_date":"2025-05-04","name":"EUROCRYPT: International Conference on the Theory and Applications of Cryptographic Techniques","end_date":"2025-05-08"},"scopus_import":"1","publication_identifier":{"eisbn":["9783031910951"],"isbn":["9783031910944"],"eissn":["1611-3349"],"issn":["0302-9743"]},"date_updated":"2025-05-28T06:12:39Z","alternative_title":["LNCS"],"oa_version":"Submitted Version","month":"04","volume":15606,"type":"conference","publication_status":"published","acknowledgement":"We thank Pierre Briaud and Morten Øygarden for helpful discussions on algebraic attacks on RSD, and the EC reviewers for helpful comments.","doi":"10.1007/978-3-031-91095-1_14","author":[{"full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246","first_name":"Miguel","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"last_name":"Merz","first_name":"Simon-Philipp","full_name":"Merz, Simon-Philipp"},{"last_name":"Stählin","full_name":"Stählin, Patrick","first_name":"Patrick"},{"id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","last_name":"Ünal","orcid":"0000-0002-8929-0221","full_name":"Ünal, Akin","first_name":"Akin"}],"quality_controlled":"1","OA_type":"green","page":"385-415","_id":"19712","oa":1,"OA_place":"repository"},{"_id":"19738","oa":1,"OA_place":"repository","page":"37-75","OA_type":"green","quality_controlled":"1","month":"05","volume":15677,"type":"conference","author":[{"last_name":"Acharya","first_name":"Anasuya","full_name":"Acharya, Anasuya"},{"full_name":"Azari, Karen","first_name":"Karen","last_name":"Azari"},{"full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad","id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig"},{"full_name":"Hofheinz, Dennis","first_name":"Dennis","last_name":"Hofheinz"},{"full_name":"Kamath, Chethan","first_name":"Chethan","last_name":"Kamath"}],"doi":"10.1007/978-3-031-91829-2_2","alternative_title":["LNCS"],"oa_version":"Preprint","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_identifier":{"isbn":["9783031918285"],"issn":["0302-9743"],"eissn":["1611-3349"]},"date_updated":"2025-06-02T07:01:45Z","article_processing_charge":"No","conference":{"end_date":"2025-05-15","name":"PKC: Public-Key Cryptography","start_date":"2025-05-12","location":"Roros, Norway"},"scopus_import":"1","status":"public","year":"2025","publisher":"Springer Nature","citation":{"mla":"Acharya, Anasuya, et al. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.” <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, vol. 15677, Springer Nature, 2025, pp. 37–75, doi:<a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">10.1007/978-3-031-91829-2_2</a>.","short":"A. Acharya, K. Azari, M.A. Baig, D. Hofheinz, C. Kamath, in:, 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Springer Nature, 2025, pp. 37–75.","chicago":"Acharya, Anasuya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, and Chethan Kamath. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.” In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, 15677:37–75. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">https://doi.org/10.1007/978-3-031-91829-2_2</a>.","ista":"Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. 2025. Securely instantiating ‘Half Gates’ garbling in the standard model. 28th IACR International Conference on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 15677, 37–75.","apa":"Acharya, A., Azari, K., Baig, M. A., Hofheinz, D., &#38; Kamath, C. (2025). Securely instantiating ‘Half Gates’ garbling in the standard model. In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i> (Vol. 15677, pp. 37–75). Roros, Norway: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">https://doi.org/10.1007/978-3-031-91829-2_2</a>","ieee":"A. Acharya, K. Azari, M. A. Baig, D. Hofheinz, and C. Kamath, “Securely instantiating ‘Half Gates’ garbling in the standard model,” in <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, Roros, Norway, 2025, vol. 15677, pp. 37–75.","ama":"Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. Securely instantiating ‘Half Gates’ garbling in the standard model. In: <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>. Vol 15677. Springer Nature; 2025:37-75. doi:<a href=\"https://doi.org/10.1007/978-3-031-91829-2_2\">10.1007/978-3-031-91829-2_2</a>"},"day":"05","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"publication":"28th IACR International Conference on Practice and Theory of Public-Key Cryptography","date_published":"2025-05-05T00:00:00Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/281"}],"date_created":"2025-05-25T22:17:02Z","abstract":[{"lang":"eng","text":"Garbling is a fundamental cryptographic primitive, with numerous theoretical and practical applications. Since the first construction by Yao (FOCS’82, ’86), a line of work has concerned itself with reducing the communication and computational complexity of that construction. One of the most efficient garbling schemes presently is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite its widespread adoption, the provable security of this scheme has been based on assumptions whose only instantiations are in idealized models. For example, in their original paper, Zahur, Rosulek, and Evans showed that hash functions satisfying a notion called circular correlation robustness (CCR) suffice for this task, and then proved that CCR secure hash functions can be instantiated in the random permutation model.\r\nIn this work, we show how to securely instantiate the Half Gates scheme in the standard model. To this end, we first show how this scheme can be securely instantiated given a (family of) weak CCR hash function, a notion that we introduce. Furthermore, we show how a weak CCR hash function can be used to securely instantiate other efficient garbling schemes, namely the ones by Rosulek and Roy (Crypto’21) and Heath (Eurocrypt’24). Thus we believe this notion to be of independent interest.\r\nFinally, we construct such weak CCR hash functions using indistinguishability obfuscation and one-way functions. The security proof of this construction constitutes our main technical contribution. While our construction is not practical, it serves as a proof of concept supporting the soundness of these garbling schemes, which we regard to be particularly important given the recent initiative by NIST to standardize garbling, and the optimizations in Half Gates being potentially adopted."}],"intvolume":"     15677","title":"Securely instantiating ‘Half Gates’ garbling in the standard model","language":[{"iso":"eng"}]},{"OA_place":"repository","_id":"20844","oa":1,"project":[{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"OA_type":"green","page":"171-202","quality_controlled":"1","author":[{"last_name":"Dujmovic","full_name":"Dujmovic, Jesko","first_name":"Jesko"},{"last_name":"Günther","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","first_name":"Christoph Ullrich","full_name":"Günther, Christoph Ullrich"},{"first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654","last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87"}],"doi":"10.1007/978-3-032-12290-2_6","publication_status":"published","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.","month":"12","type":"conference","volume":16271,"alternative_title":["LNCS"],"oa_version":"Preprint","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783032122896"]},"date_updated":"2025-12-29T11:44:16Z","article_processing_charge":"No","conference":{"name":"TCC: Theory of Cryptography","end_date":"2025-12-05","start_date":"2025-12-01","location":"Aarhus, Denmark"},"scopus_import":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publisher":"Springer Nature","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>.","short":"J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, 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>.","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.","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>"},"status":"public","corr_author":"1","year":"2025","date_published":"2025-12-05T00:00:00Z","date_created":"2025-12-21T23:01:33Z","main_file_link":[{"url":"https://eprint.iacr.org/2025/1723","open_access":"1"}],"abstract":[{"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.","lang":"eng"}],"day":"05","department":[{"_id":"KrPi"}],"publication":"23rd International Conference on Theory of Cryptography","language":[{"iso":"eng"}],"title":"Space-deniable proofs","intvolume":"     16271"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"start_date":"2025-12-01","location":"Aarhus, Denmark","name":"TCC: Theory of Cryptography","end_date":"2025-12-05"},"scopus_import":"1","article_processing_charge":"No","date_updated":"2025-12-29T11:51:13Z","publication_identifier":{"isbn":["9783032122926"],"eissn":["1611-3349"],"issn":["0302-9743"]},"year":"2025","status":"public","citation":{"short":"S. Agrawal, A. Modi, A. Yadav, S. Yamada, in:, 23rd International Conference on Theory of Cryptography, Springer Nature, 2025, pp. 259–290.","chicago":"Agrawal, Shweta, Anuja Modi, Anshu Yadav, and Shota Yamada. “Zeroizing Attacks against Evasive and Circular Evasive LWE.” In <i>23rd International Conference on Theory of Cryptography</i>, 16269:259–90. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">https://doi.org/10.1007/978-3-032-12293-3_9</a>.","mla":"Agrawal, Shweta, et al. “Zeroizing Attacks against Evasive and Circular Evasive LWE.” <i>23rd International Conference on Theory of Cryptography</i>, vol. 16269, Springer Nature, 2025, pp. 259–90, doi:<a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">10.1007/978-3-032-12293-3_9</a>.","ama":"Agrawal S, Modi A, Yadav A, Yamada S. Zeroizing attacks against evasive and circular evasive LWE. In: <i>23rd International Conference on Theory of Cryptography</i>. Vol 16269. Springer Nature; 2025:259-290. doi:<a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">10.1007/978-3-032-12293-3_9</a>","ieee":"S. Agrawal, A. Modi, A. Yadav, and S. Yamada, “Zeroizing attacks against evasive and circular evasive LWE,” in <i>23rd International Conference on Theory of Cryptography</i>, Aarhus, Denmark, 2025, vol. 16269, pp. 259–290.","apa":"Agrawal, S., Modi, A., Yadav, A., &#38; Yamada, S. (2025). Zeroizing attacks against evasive and circular evasive LWE. In <i>23rd International Conference on Theory of Cryptography</i> (Vol. 16269, pp. 259–290). Aarhus, Denmark: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-12293-3_9\">https://doi.org/10.1007/978-3-032-12293-3_9</a>","ista":"Agrawal S, Modi A, Yadav A, Yamada S. 2025. Zeroizing attacks against evasive and circular evasive LWE. 23rd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 16269, 259–290."},"publisher":"Springer Nature","department":[{"_id":"KrPi"}],"publication":"23rd International Conference on Theory of Cryptography","day":"05","abstract":[{"text":"We develop new attacks against the Evasive LWE family of assumptions, in both the public and private-coin regime. To the best of our knowledge, ours are the first attacks against Evasive LWE in the public-coin regime, for any instantiation from the family. Our attacks are summarized below.\r\n\r\nPublic-Coin Attacks.\r\n1.The recent work by Hseih, Lin and Luo [17] constructed the first Attribute Based Encryption (ABE) for unbounded depth circuits by relying on the “circular” evasive LWE assumption. This assumption has been popularly considered as a safe, public-coin instance of Evasive LWE in contrast to its “private-coin” cousins (for instance, see [10, 11]).\r\nWe provide the first attack against this assumption, challenging the widely held belief that this is a public-coin assumption.\r\n2. We demonstrate a counter-example against vanilla public-coin evasive LWE by Wee [26] in an unnatural parameter regime. Our attack crucially relies on the error in the pre-condition being larger than the error in the post-condition, necessitating a refinement of the assumption.\r\n\r\nPrivate-Coin Attacks.\r\n1. The recent work by Agrawal, Kumari and Yamada [2] constructed the first functional encryption scheme for pseudorandom functionalities (PRFE) and extended this to obfuscation for pseudorandom functionalities (PRIO) [4] by relying on private-coin evasive LWE. We provide a new attack against the assumption stated in the first posting of their work (subsequently refined to avoid these attacks).\r\n2. The recent work by Branco et al. [8] (concurrently to [4]) provides a construction of obfuscation for pseudorandom functionalities by relying on private-coin evasive LWE. We provide a new attack against their stated assumption.\r\n3. Branco et al. [8] showed that there exist contrived, “self-referential” classes of pseudorandom functionalities for which pseudorandom obfuscation cannot exist. We extend their techniques to develop an analogous result for pseudorandom functional encryption.\r\n\r\nWhile Evasive LWE was developed to specifically avoid “zeroizing attacks”, our work shows that in certain settings, such attacks can still apply.","lang":"eng"}],"date_created":"2025-12-21T23:01:33Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/375"}],"date_published":"2025-12-05T00:00:00Z","title":"Zeroizing attacks against evasive and circular evasive LWE","intvolume":"     16269","language":[{"iso":"eng"}],"oa":1,"_id":"20845","OA_place":"repository","quality_controlled":"1","OA_type":"green","page":"259-290","volume":16269,"type":"conference","month":"12","acknowledgement":"We thank Rachel Lin for expressing concern about the applicability of “HJL-style” attacks [15] on the construction in [2] during a talk by the first author about [2]. This was the starting point of the investigation that led us to develop the attack in [5, Sec 4.1]. The first author also thanks Hoeteck Wee for sharing his rationale for introducing evasive LWE.\r\nThe first author is supported by the CyStar center of excellence, the VHAR faculty chair, and the C3iHub fellowship. The third author thanks Cystar, IIT Madras, for supporting a visit to IIT Madras during which the collaboration was initiated. The 4th author is partly supported by JST CREST Grant Number JPMJCR22M1.","publication_status":"published","doi":"10.1007/978-3-032-12293-3_9","author":[{"last_name":"Agrawal","first_name":"Shweta","full_name":"Agrawal, Shweta"},{"last_name":"Modi","full_name":"Modi, Anuja","first_name":"Anuja"},{"first_name":"Anshu","full_name":"Yadav, Anshu","id":"dc8f1524-403e-11ee-bf07-9649ad996e21","last_name":"Yadav"},{"last_name":"Yamada","full_name":"Yamada, Shota","first_name":"Shota"}],"oa_version":"Preprint","alternative_title":["LNCS"]},{"doi":"10.1007/978-3-032-12290-2_16","author":[{"last_name":"Brandt","full_name":"Brandt, Nicholas","first_name":"Nicholas"},{"last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","first_name":"Miguel","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246"},{"full_name":"Günther, Christoph Ullrich","first_name":"Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther"},{"orcid":"0000-0002-8929-0221","full_name":"Ünal, Akin","first_name":"Akin","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","last_name":"Ünal"},{"full_name":"Wohnig, Stella","first_name":"Stella","last_name":"Wohnig"}],"month":"12","type":"conference","volume":16271,"publication_status":"published","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.","alternative_title":["LNCS"],"oa_version":"Preprint","OA_place":"repository","_id":"20846","oa":1,"project":[{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"quality_controlled":"1","page":"478-511","OA_type":"green","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2025/1045"}],"date_created":"2025-12-21T23:01:34Z","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"}],"date_published":"2025-12-05T00:00:00Z","day":"05","publication":"23rd International Conference on Theory of Cryptography","department":[{"_id":"KrPi"}],"language":[{"iso":"eng"}],"title":"Constrained verifiable random functions without obfuscation and friends","intvolume":"     16271","article_processing_charge":"No","scopus_import":"1","conference":{"end_date":"2025-12-05","name":"TCC: Theory of Cryptography","start_date":"2025-12-01","location":"Aarhus, Denmark"},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783032122896"]},"date_updated":"2025-12-29T11:11:29Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","citation":{"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>.","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>.","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.","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.","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.","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>"},"publisher":"Springer Nature","year":"2025","corr_author":"1","status":"public"},{"title":"Kauri: BFT consensus with pipelined tree-based dissemination and aggregation","language":[{"iso":"eng"}],"department":[{"_id":"KrPi"}],"publication":"ACM Transactions on Computer Systems","day":"05","abstract":[{"text":"With the growing interest in blockchains, permissioned approaches to consensus have received increasing attention. Unfortunately, the BFT consensus algorithms that are the backbone of most of these blockchains scale poorly and offer limited throughput. In fact, many state-of-the-art BFT consensus algorithms require a single leader process to receive and validate votes from a quorum of processes and then broadcast the result, which is inherently non-scalable. Recent approaches avoid this bottleneck by using dissemination/aggregation trees to propagate values and collect and validate votes. However, the use of trees increases the round latency, which limits the throughput for deeper trees. In this paper we propose Kauri, a BFT communication abstraction that sustains high throughput as the system size grows by leveraging a novel pipelining technique to perform scalable dissemination and aggregation on trees. Furthermore, when the number of faults is moderate (arguably the most common case in practice), our construction is able to recover from faults in an optimal number of reconfiguration steps. We implemented and experimentally evaluated Kauri with up to 800 processes. Our results show that Kauri outperforms the throughput of state-of-the-art permissioned blockchain protocols, by up to 58x without compromising latency. Interestingly, in some cases, the parallelization provided by Kauri can also decrease the latency.","lang":"eng"}],"date_created":"2026-01-20T10:14:23Z","main_file_link":[{"open_access":"1","url":"https://doi.org/10.1145/3769423"}],"date_published":"2025-09-05T00:00:00Z","year":"2025","corr_author":"1","status":"public","PlanS_conform":"1","citation":{"apa":"Neiheiser, R., Matos, M., &#38; Rodrigues, L. (2025). Kauri: BFT consensus with pipelined tree-based dissemination and aggregation. <i>ACM Transactions on Computer Systems</i>. Association for Computing Machinery. <a href=\"https://doi.org/10.1145/3769423\">https://doi.org/10.1145/3769423</a>","ista":"Neiheiser R, Matos M, Rodrigues L. 2025. Kauri: BFT consensus with pipelined tree-based dissemination and aggregation. ACM Transactions on Computer Systems., 3769423.","ieee":"R. Neiheiser, M. Matos, and L. Rodrigues, “Kauri: BFT consensus with pipelined tree-based dissemination and aggregation,” <i>ACM Transactions on Computer Systems</i>. Association for Computing Machinery, 2025.","ama":"Neiheiser R, Matos M, Rodrigues L. Kauri: BFT consensus with pipelined tree-based dissemination and aggregation. <i>ACM Transactions on Computer Systems</i>. 2025. doi:<a href=\"https://doi.org/10.1145/3769423\">10.1145/3769423</a>","mla":"Neiheiser, Ray, et al. “Kauri: BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation.” <i>ACM Transactions on Computer Systems</i>, 3769423, Association for Computing Machinery, 2025, doi:<a href=\"https://doi.org/10.1145/3769423\">10.1145/3769423</a>.","short":"R. Neiheiser, M. Matos, L. Rodrigues, ACM Transactions on Computer Systems (2025).","chicago":"Neiheiser, Ray, Miguel Matos, and Luis Rodrigues. “Kauri: BFT Consensus with Pipelined Tree-Based Dissemination and Aggregation.” <i>ACM Transactions on Computer Systems</i>. Association for Computing Machinery, 2025. <a href=\"https://doi.org/10.1145/3769423\">https://doi.org/10.1145/3769423</a>."},"publisher":"Association for Computing Machinery","has_accepted_license":"1","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","scopus_import":"1","article_type":"original","article_processing_charge":"Yes (via OA deal)","date_updated":"2026-01-21T08:11:23Z","publication_identifier":{"issn":["0734-2071"],"eissn":["1557-7333"]},"oa_version":"Published Version","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"type":"journal_article","month":"09","acknowledgement":"We thank the ACM TOCS Editors and the reviewers for their help in improving the manuscript. This work was partially supported by CAPES - Brazil (Coordenação de Aperfeiçoamento de Pessoal de Nível Superior) and byFundação para a Ciência e Tecnologia (FCT) under project UIDB/50021/2020 and grant 2020.05270.BD, and via project COSMOS (via the OE with ref. PTDC/EEI-COM/29271/2017, via the łPrograma Operacional Regional de Lisboa na sua componente FEDER” with ref. Lisboa-01-0145-FEDER-029271) and project Angainor with reference LISBOA-01-0145-FEDER-031456, grant agreement number 952226, and project GLOG, with reference LISBOA2030-FEDER-00771200, and project BIG (Enhancing the research and innovation potential of Tecnico through blockchain technologies and design Innovation for social Good), and project ScalableCosmosConsensus, and the Austrian Science Fund (FWF) SFB project SpyCoDe F8502 and the Vienna Science and Technology Fund (WWTF) project SCALE2 CT22-045","publication_status":"epub_ahead","doi":"10.1145/3769423","article_number":"3769423","author":[{"id":"f09651b9-fec0-11ec-b5d8-934aff0e52a4","last_name":"Neiheiser","orcid":"0000-0001-7227-8309","full_name":"Neiheiser, Ray","first_name":"Ray"},{"first_name":"Miguel","full_name":"Matos, Miguel","last_name":"Matos"},{"first_name":"Luis","full_name":"Rodrigues, Luis","last_name":"Rodrigues"}],"quality_controlled":"1","OA_type":"hybrid","project":[{"grant_number":"F8502","name":"Interface Theory for Security and Privacy","_id":"34a1b658-11ca-11ed-8bc3-c75229f0241e"},{"name":"SeCure, privAte, and interoperabLe layEr 2","grant_number":"ICT22-045","_id":"7bdd2f70-9f16-11ee-852c-b7950bc6d277"}],"_id":"21017","oa":1,"OA_place":"publisher"},{"day":"17","department":[{"_id":"KrPi"}],"publication":"45th Annual International Cryptology Conference","main_file_link":[{"url":"https://eprint.iacr.org/2025/1035","open_access":"1"}],"date_created":"2026-02-17T07:41:04Z","abstract":[{"text":"Continuous Group Key Agreement (CGKA) is the primitive underlying secure group messaging. It allows a large group of N users to maintain a shared secret key that is frequently rotated by the\r\ngroup members in order to achieve forward secrecy and post compromise security. The group messaging scheme Messaging Layer Security (MLS) standardized by the IETF makes use of a CGKA called TreeKEM which arranges the N group members in a binary tree. Here, each node is associated with a public-key, each user is assigned one of the leaves, and a user knows the corresponding secret keys from their leaf to the root. To update the key material known to them, a user must just replace keys at log(N) nodes, which requires them to create and upload log(N) ciphertexts. Such updates must be processed sequentially by all users, which for large groups is impractical. To allow for concurrent updates, TreeKEM uses the “propose and commit” paradigm, where multiple users can concurrently propose to update (by just sampling a fresh leaf key), and a single user can then commit to all proposals at once. Unfortunately, this process destroys the binary tree structure as the tree gets pruned and some nodes must be “blanked” at the cost of increasing the in-degree of others, which makes the commit operation, as well as, future commits more costly. In the worst case, the update cost (in terms of uploaded ciphertexts) per user can grow from log(N) to Ω(N). In this work we provide two main contributions. First, we show that MLS’ communication complexity is bad not only in the worst case but also if the proposers and committers are chosen at random: even if there’s just one update proposal for every commit the expected cost is already over √N, and it approaches N as this ratio changes towards more proposals. Our second contribution is a new variant of propose and commit for\r\nTreeKEM which for moderate amounts of update proposals per commit provably achieves an update cost of Θ(log(N)) assuming the proposers and committers are chosen at random.","lang":"eng"}],"date_published":"2025-08-17T00:00:00Z","title":"Continuous group-key agreement: Concurrent updates without pruning","intvolume":"     16007","language":[{"iso":"eng"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"No","conference":{"name":"CRYPTO: International Cryptology Conference","end_date":"2025-08-21","start_date":"2025-08-17","location":"Santa Barbara, CA, United States"},"publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"isbn":["9783032019127"],"eisbn":["9783032019134"]},"date_updated":"2026-02-18T07:36:42Z","year":"2025","status":"public","citation":{"ieee":"B. Auerbach, M. Cueto Noval, B. Erol, and K. Z. Pietrzak, “Continuous group-key agreement: Concurrent updates without pruning,” in <i>45th Annual International Cryptology Conference</i>, Santa Barbara, CA, United States, 2025, vol. 16007, pp. 141–172.","ama":"Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. Continuous group-key agreement: Concurrent updates without pruning. In: <i>45th Annual International Cryptology Conference</i>. Vol 16007. Springer Nature; 2025:141-172. doi:<a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">10.1007/978-3-032-01913-4_5</a>","apa":"Auerbach, B., Cueto Noval, M., Erol, B., &#38; Pietrzak, K. Z. (2025). Continuous group-key agreement: Concurrent updates without pruning. In <i>45th Annual International Cryptology Conference</i> (Vol. 16007, pp. 141–172). Santa Barbara, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">https://doi.org/10.1007/978-3-032-01913-4_5</a>","ista":"Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. 2025. Continuous group-key agreement: Concurrent updates without pruning. 45th Annual International Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 16007, 141–172.","short":"B. Auerbach, M. Cueto Noval, B. Erol, K.Z. Pietrzak, in:, 45th Annual International Cryptology Conference, Springer Nature, 2025, pp. 141–172.","chicago":"Auerbach, Benedikt, Miguel Cueto Noval, Boran Erol, and Krzysztof Z Pietrzak. “Continuous Group-Key Agreement: Concurrent Updates without Pruning.” In <i>45th Annual International Cryptology Conference</i>, 16007:141–72. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">https://doi.org/10.1007/978-3-032-01913-4_5</a>.","mla":"Auerbach, Benedikt, et al. “Continuous Group-Key Agreement: Concurrent Updates without Pruning.” <i>45th Annual International Cryptology Conference</i>, vol. 16007, Springer Nature, 2025, pp. 141–72, doi:<a href=\"https://doi.org/10.1007/978-3-032-01913-4_5\">10.1007/978-3-032-01913-4_5</a>."},"publisher":"Springer Nature","month":"08","volume":16007,"type":"conference","publication_status":"published","acknowledgement":"B. Auerbach and B. Erol—Conducted part of this work at ISTA.","doi":"10.1007/978-3-032-01913-4_5","author":[{"first_name":"Benedikt","orcid":"0000-0002-7553-6606","full_name":"Auerbach, Benedikt","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","last_name":"Auerbach"},{"last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246","first_name":"Miguel"},{"last_name":"Erol","full_name":"Erol, Boran","first_name":"Boran"},{"first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak"}],"alternative_title":["LNCS"],"oa_version":"Preprint","_id":"21262","oa":1,"OA_place":"repository","quality_controlled":"1","OA_type":"green","page":"141-172"},{"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","conference":{"location":"Santa Barbara, CA, United States","start_date":"2025-08-17","end_date":"2025-08-221","name":"CRYPTO: International Cryptology Conference"},"article_processing_charge":"No","date_updated":"2026-02-19T07:50:33Z","publication_identifier":{"eissn":["1611-3349"],"issn":["0302-9743"],"eisbn":["9783032018878"],"isbn":["9783032018861"]},"year":"2025","status":"public","citation":{"mla":"Belohorec, Juraj, et al. “On Extractability of the KZG Family of Polynomial Commitment Schemes.” <i>45th Annual International Cryptology Conference</i>, vol. 16005, Springer Nature, 2025, pp. 584–616, doi:<a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">10.1007/978-3-032-01887-8_19</a>.","short":"J. Belohorec, P. Dvořák, C. Hoffmann, P. Hubáček, K. Mašková, M. Pastyřík, in:, 45th Annual International Cryptology Conference, Springer Nature, 2025, pp. 584–616.","chicago":"Belohorec, Juraj, Pavel Dvořák, Charlotte Hoffmann, Pavel Hubáček, Kristýna Mašková, and Martin Pastyřík. “On Extractability of the KZG Family of Polynomial Commitment Schemes.” In <i>45th Annual International Cryptology Conference</i>, 16005:584–616. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">https://doi.org/10.1007/978-3-032-01887-8_19</a>.","apa":"Belohorec, J., Dvořák, P., Hoffmann, C., Hubáček, P., Mašková, K., &#38; Pastyřík, M. (2025). On extractability of the KZG family of polynomial commitment schemes. In <i>45th Annual International Cryptology Conference</i> (Vol. 16005, pp. 584–616). Santa Barbara, CA, United States: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">https://doi.org/10.1007/978-3-032-01887-8_19</a>","ista":"Belohorec J, Dvořák P, Hoffmann C, Hubáček P, Mašková K, Pastyřík M. 2025. On extractability of the KZG family of polynomial commitment schemes. 45th Annual International Cryptology Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 16005, 584–616.","ama":"Belohorec J, Dvořák P, Hoffmann C, Hubáček P, Mašková K, Pastyřík M. On extractability of the KZG family of polynomial commitment schemes. In: <i>45th Annual International Cryptology Conference</i>. Vol 16005. Springer Nature; 2025:584-616. doi:<a href=\"https://doi.org/10.1007/978-3-032-01887-8_19\">10.1007/978-3-032-01887-8_19</a>","ieee":"J. Belohorec, P. Dvořák, C. Hoffmann, P. Hubáček, K. Mašková, and M. Pastyřík, “On extractability of the KZG family of polynomial commitment schemes,” in <i>45th Annual International Cryptology Conference</i>, Santa Barbara, CA, United States, 2025, vol. 16005, pp. 584–616."},"publisher":"Springer Nature","department":[{"_id":"KrPi"}],"publication":"45th Annual International Cryptology Conference","day":"17","abstract":[{"text":"We present a unifying framework for proving the knowledge-soundness of KZG-like polynomial commitment schemes, encompassing both univariate and multivariate variants. By conceptualizing the proof technique of Lipmaa, Parisella, and Siim for the univariate KZG scheme (EUROCRYPT 2024), we present tools and falsifiable hardness assumptions that permit black-box extraction of the multivariate KZG scheme. Central to our approach is the notion of a canonical Proof-of-Knowledge of a Polynomial (PoKoP) of a polynomial commitment scheme, which we use to capture the extractability notion required in constructions of practical zk-SNARKs. We further present an explicit polynomial decomposition lemma for multivariate polynomials, enabling a more direct analysis of interpolating extractors and bridging the gap between univariate and multivariate commitments. Our results provide the first standard-model proofs of extractability for the multivariate KZG scheme and many of its variants under falsifiable assumptions.","lang":"eng"}],"main_file_link":[{"url":"https://eprint.iacr.org/2025/514","open_access":"1"}],"date_created":"2026-02-18T10:59:58Z","date_published":"2025-08-17T00:00:00Z","intvolume":"     16005","title":"On extractability of the KZG family of polynomial commitment schemes","language":[{"iso":"eng"}],"oa":1,"_id":"21323","OA_place":"repository","quality_controlled":"1","OA_type":"green","page":"584-616","type":"conference","volume":16005,"month":"08","acknowledgement":"Juraj Belohorec, Pavel Hubáček, and Kristýna Mašková were partially supported by the Academy of Sciences of the Czech Republic (RVO 67985840), Czech Science Foundation GAČR grant No. 25-16311S, and by Zircuit. Pavel Dvořák was supported by Czech Science Foundation GAČR grant No. 22-14872O. Juraj Belohorec and Kristýna Mašková were supported by the grant SVV–2025–260822.","publication_status":"published","doi":"10.1007/978-3-032-01887-8_19","author":[{"last_name":"Belohorec","first_name":"Juraj","full_name":"Belohorec, Juraj"},{"full_name":"Dvořák, Pavel","first_name":"Pavel","last_name":"Dvořák"},{"id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","last_name":"Hoffmann","orcid":"0000-0003-2027-5549","full_name":"Hoffmann, Charlotte","first_name":"Charlotte"},{"full_name":"Hubáček, Pavel","first_name":"Pavel","last_name":"Hubáček"},{"last_name":"Mašková","first_name":"Kristýna","full_name":"Mašková, Kristýna"},{"first_name":"Martin","full_name":"Pastyřík, Martin","last_name":"Pastyřík"}],"oa_version":"Preprint","alternative_title":["LNCS"]},{"doi":"10.4230/LIPIcs.AFT.2025.16","file":[{"file_size":1061847,"success":1,"content_type":"application/pdf","file_name":"2025_LIPIcsAFT_Baig.pdf","creator":"dernst","checksum":"b638adcd4fbffa77116c35393e165eb7","file_id":"20598","access_level":"open_access","date_created":"2025-11-04T08:19:02Z","relation":"main_file","date_updated":"2025-11-04T08:19:02Z"}],"article_number":"16","author":[{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad"},{"full_name":"Günther, Christoph Ullrich","first_name":"Christoph Ullrich","id":"ec98511c-eb8e-11eb-b029-edd25d7271a1","last_name":"Günther"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z","first_name":"Krzysztof Z"}],"type":"conference","volume":354,"arxiv":1,"month":"10","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.","publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)"},"oa_version":"Published Version","alternative_title":["LIPIcs"],"related_material":{"record":[{"id":"21651","relation":"dissertation_contains","status":"public"}]},"OA_place":"publisher","_id":"20587","oa":1,"project":[{"_id":"34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f","grant_number":"F8512","name":"Security and Privacy by Design for Complex Systems"},{"name":"Security and Privacy by Design for Complex Systems","grant_number":"F8509","_id":"34a34d57-11ca-11ed-8bc3-a2688a8724e1"}],"quality_controlled":"1","OA_type":"gold","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"}],"main_file_link":[{"url":"https://eprint.iacr.org/2025/1410","open_access":"1"}],"date_created":"2025-11-02T23:01:34Z","date_published":"2025-10-06T00:00:00Z","ddc":["000"],"department":[{"_id":"KrPi"}],"publication":"7th Conference on Advances in Financial Technologies","day":"06","language":[{"iso":"eng"}],"title":"Nakamoto consensus from multiple resources","intvolume":"       354","conference":{"name":"AFT: Conference on Advances in Financial Technologies","end_date":"2025-10-10","location":"Pittsburgh, PA, United States","start_date":"2025-10-08"},"scopus_import":"1","article_processing_charge":"Yes","date_updated":"2026-04-15T08:45:18Z","file_date_updated":"2025-11-04T08:19:02Z","publication_identifier":{"isbn":["9783959774000"],"issn":["1868-8969"]},"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","has_accepted_license":"1","citation":{"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>","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.","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.","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>.","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.","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>."},"publisher":"Schloss Dagstuhl - Leibniz-Zentrum für Informatik","year":"2025","corr_author":"1","external_id":{"arxiv":["2508.01448"]},"status":"public"},{"article_processing_charge":"No","publication_identifier":{"issn":["2663-337X"]},"date_updated":"2026-04-16T09:11:08Z","file_date_updated":"2026-01-02T10:39:26Z","has_accepted_license":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","citation":{"ieee":"C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute of Science and Technology Austria, 2025.","ama":"Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20920\">10.15479/AT-ISTA-20920</a>","ista":"Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute of Science and Technology Austria.","apa":"Hoffmann, C. (2025). <i>Theory and applications of verifiable delay functions</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20920\">https://doi.org/10.15479/AT-ISTA-20920</a>","chicago":"Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20920\">https://doi.org/10.15479/AT-ISTA-20920</a>.","short":"C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute of Science and Technology Austria, 2025.","mla":"Hoffmann, Charlotte. <i>Theory and Applications of Verifiable Delay Functions</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20920\">10.15479/AT-ISTA-20920</a>."},"publisher":"Institute of Science and Technology Austria","corr_author":"1","year":"2025","status":"public","date_created":"2026-01-02T10:46:47Z","abstract":[{"text":"Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18) are functions that require a prescribed number of sequential steps T to evaluate, yet their output can be verified in time much faster than T. Since their introduction, VDFs have gained a lot of attention due to their applications in blockchain protocols, randomness beacons, timestamping and deniability. This thesis explores the theory and applications of VDFs, focusing on enhancing their soundness, efficiency and practicality.\r\n\r\nThe only practical VDFs known to date are based on repeated squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T).\r\nThe iterated squaring assumption states that, for a random group element x, the result of VDF cannot be computed significantly faster than performing T sequential squarings if the group order is unknown. To make the result verifiable a prover can compute a proof of exponentiation (PoE) \\pi. Given \\pi, the output of VDF can be verified in time much less than T.\r\n\r\nWe first present new constructions of statistically sound proofs of exponentiation, which are an important building block in the construction of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness means that the proofs remain secure against computationally unbounded adversaries, in particular, it remains secure even when the group order is known. We thereby address limitations in previous PoE protocols which either required (non-standard) hardness assumptions or a lot of parallel repetitions. Our construction significantly reduces the proof size of statistically sound PoEs that allow for a structured exponent, which leads to better efficiency of SNARKs and other applications.\r\n\r\nSecondly, we introduce improved batching techniques for PoEs, which allow multiple proofs to be aggregated and verified with minimal overhead. These protocols optimize communication and computation complexity in large-scale blockchain environments and enable scalable remote benchmarking of parallel computation resources.\r\n\r\nWe then construct VDFs with enhanced properties such as zero-knowledge and watermarkability. It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable new cryptographic primitives called short-lived proofs and signatures. The validity of such proofs and signatures expires after a predefined amount of time T, i.e., they are deniable after time T. Our constructions improve upon the constructions by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably weaker assumptions).\r\n\r\nFinally, we apply PoEs in the realm of primality testing, providing cryptographically sound proofs of non-primality for large Proth numbers. This work gives a surprising application of VDFs in the area of computational number theory.\r\n\r\nTogether, our contributions advance both the theoretical foundations and the real-world usability of VDFs in general and in particular of PoEs, making them more adaptable and secure for current and emerging cryptographic applications.","lang":"eng"}],"ddc":["004"],"date_published":"2025-12-31T00:00:00Z","day":"31","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"language":[{"iso":"eng"}],"title":"Theory and applications of verifiable delay functions","related_material":{"record":[{"id":"13143","relation":"part_of_dissertation","status":"public"},{"relation":"part_of_dissertation","id":"20701","status":"public"},{"id":"12176","relation":"part_of_dissertation","status":"public"},{"status":"public","id":"20556","relation":"earlier_version"},{"status":"public","relation":"part_of_dissertation","id":"19778"}]},"OA_place":"publisher","_id":"20920","oa":1,"page":"116","file":[{"file_id":"20921","creator":"choffman","checksum":"8a099fbf54963bd0be38f7ce73658682","access_level":"closed","file_size":8355494,"content_type":"application/x-zip-compressed","file_name":"2025_Hoffmann_Charlotte_Source.zip","date_created":"2026-01-02T10:39:16Z","date_updated":"2026-01-02T10:39:16Z","relation":"source_file"},{"access_level":"open_access","file_id":"20922","creator":"choffman","checksum":"9521c07bfb2bb5b14a49c09fcfc96474","content_type":"application/pdf","success":1,"file_name":"2025_Hoffmann_Charlotte_Thesis.pdf","file_size":2258804,"date_updated":"2026-01-02T10:39:26Z","relation":"main_file","date_created":"2026-01-02T10:39:26Z"}],"doi":"10.15479/AT-ISTA-20920","author":[{"first_name":"Charlotte","full_name":"Hoffmann, Charlotte","orcid":"0000-0003-2027-5549","last_name":"Hoffmann","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7"}],"month":"12","type":"dissertation","publication_status":"published","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"alternative_title":["ISTA Thesis"],"oa_version":"Published Version","supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"degree_awarded":"PhD"},{"publisher":"Institute of Science and Technology Austria","citation":{"mla":"Hoffmann, Charlotte. <i>Theory and Applications of Verifiable Delay Functions</i>. Institute of Science and Technology Austria, 2025, doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20556\">10.15479/AT-ISTA-20556</a>.","short":"C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute of Science and Technology Austria, 2025.","chicago":"Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.” Institute of Science and Technology Austria, 2025. <a href=\"https://doi.org/10.15479/AT-ISTA-20556\">https://doi.org/10.15479/AT-ISTA-20556</a>.","apa":"Hoffmann, C. (2025). <i>Theory and applications of verifiable delay functions</i>. Institute of Science and Technology Austria. <a href=\"https://doi.org/10.15479/AT-ISTA-20556\">https://doi.org/10.15479/AT-ISTA-20556</a>","ista":"Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute of Science and Technology Austria.","ieee":"C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute of Science and Technology Austria, 2025.","ama":"Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:<a href=\"https://doi.org/10.15479/AT-ISTA-20556\">10.15479/AT-ISTA-20556</a>"},"status":"public","corr_author":"1","year":"2025","file_date_updated":"2026-01-08T14:11:39Z","date_updated":"2026-04-16T09:11:09Z","publication_identifier":{"issn":["2663-337X"]},"article_processing_charge":"No","has_accepted_license":"1","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","language":[{"iso":"eng"}],"title":"Theory and applications of verifiable delay functions","date_published":"2025-10-31T00:00:00Z","ddc":["004"],"abstract":[{"lang":"eng","text":"Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18) are functions that require a prescribed number of sequential steps T to evaluate, yet their output can be verified in time much faster than T. Since their introduction, VDFs have gained a lot of attention due to their applications in blockchain protocols, randomness beacons, timestamping and deniability. This thesis explores the theory and applications of VDFs, focusing on enhancing their soundness, efficiency and practicality.\r\n\r\nThe only practical VDFs known to date are based on repeated squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T).\r\nThe iterated squaring assumption states that, for a random group element x, the result of VDF cannot be computed significantly faster than performing T sequential squarings if the group order is unknown. To make the result verifiable a prover can compute a proof of exponentiation (PoE) \\pi. Given \\pi, the output of VDF can be verified in time much less than T.\r\n\r\nWe first present new constructions of statistically sound proofs of exponentiation, which are an important building block in the construction of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness means that the proofs remain secure against computationally unbounded adversaries, in particular, it remains secure even when the group order is known. We thereby address limitations in previous PoE protocols which either required (non-standard) hardness assumptions or a lot of parallel repetitions. Our construction significantly reduces the proof size of statistically sound PoEs that allow for a structured exponent, which leads to better efficiency of SNARKs and other applications.\r\n\r\nSecondly, we introduce improved batching techniques for PoEs, which allow multiple proofs to be aggregated and verified with minimal overhead. These protocols optimize communication and computation complexity in large-scale blockchain environments and enable scalable remote benchmarking of parallel computation resources.\r\n\r\nWe then construct VDFs with enhanced properties such as zero-knowledge and watermarkability. It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable new cryptographic primitives called short-lived proofs and signatures. The validity of such proofs and signatures expires after a predefined amount of time T, i.e., they are deniable after time T. Our constructions improve upon the constructions by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably weaker assumptions).\r\n\r\nFinally, we apply PoEs in the realm of primality testing, providing cryptographically sound proofs of non-primality for large Proth numbers. This work gives a surprising application of VDFs in the area of computational number theory.\r\n\r\nTogether, our contributions advance both the theoretical foundations and the real-world usability of VDFs in general and in particular of PoEs, making them more adaptable and secure for current and emerging cryptographic applications."}],"date_created":"2025-10-27T14:16:56Z","department":[{"_id":"GradSch"},{"_id":"KrPi"}],"day":"31","page":"116","OA_place":"publisher","related_material":{"record":[{"status":"public","relation":"part_of_dissertation","id":"13143"},{"status":"public","id":"12176","relation":"part_of_dissertation"},{"status":"public","id":"20701","relation":"part_of_dissertation"},{"relation":"later_version","id":"20920","status":"public"},{"relation":"part_of_dissertation","id":"19778","status":"public"}]},"_id":"20556","tmp":{"legal_code_url":"https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode","short":"CC BY-NC-SA (4.0)","image":"/images/cc_by_nc_sa.png","name":"Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC BY-NC-SA 4.0)"},"degree_awarded":"PhD","supervisor":[{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"oa_version":"Published Version","alternative_title":["ISTA Thesis"],"author":[{"id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","last_name":"Hoffmann","orcid":"0000-0003-2027-5549","full_name":"Hoffmann, Charlotte","first_name":"Charlotte"}],"doi":"10.15479/AT-ISTA-20556","file":[{"checksum":"1fffa4e2c33dd0b9f883d615504a2858","creator":"choffman","file_id":"20573","access_level":"closed","file_size":2259304,"file_name":"2025_Hoffmann_Charlotte_Thesis.pdf","content_type":"application/pdf","date_created":"2025-10-28T14:33:03Z","date_updated":"2026-01-08T14:11:39Z","relation":"main_file"},{"date_created":"2025-10-28T14:35:06Z","relation":"source_file","date_updated":"2025-11-11T09:34:54Z","creator":"choffman","checksum":"076ea98a1f0a86c3bbc990b6b9460dc2","file_id":"20574","access_level":"closed","file_size":9987633,"file_name":"2025_Hoffmann_Charlotte_Source.zip","content_type":"application/x-zip-compressed"}],"publication_status":"published","type":"dissertation","month":"10"},{"publication_status":"published","month":"01","volume":15674,"type":"conference","author":[{"orcid":"0000-0003-2027-5549","full_name":"Hoffmann, Charlotte","first_name":"Charlotte","id":"0f78d746-dc7d-11ea-9b2f-83f92091afe7","last_name":"Hoffmann"},{"last_name":"Pietrzak","id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","first_name":"Krzysztof Z","full_name":"Pietrzak, Krzysztof Z","orcid":"0000-0002-9139-1654"}],"doi":"10.1007/978-3-031-91820-9_2","alternative_title":["LNCS"],"oa_version":"Preprint","_id":"19778","oa":1,"OA_place":"repository","related_material":{"record":[{"status":"public","relation":"dissertation_contains","id":"20920"},{"relation":"dissertation_contains","id":"20556","status":"public"}]},"page":"36-66","OA_type":"green","quality_controlled":"1","day":"01","publication":"28th IACR International Conference on Practice and Theory of Public-Key Cryptography","department":[{"_id":"KrPi"},{"_id":"GradSch"}],"date_published":"2025-01-01T00:00:00Z","date_created":"2025-06-03T07:30:21Z","main_file_link":[{"open_access":"1","url":"https://ia.cr/2024/481"}],"abstract":[{"lang":"eng","text":"A verifiable delay function VDF(x, T)->(y, π) maps an input x and time parameter T to an output y together with an efficiently verifiable proof π certifying that y was correctly computed. The function runs in T sequential steps, and it should not be possible to compute y much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., y = x^2^T. There are two constructions for the proof of exponentiation (PoE) certifying that y = x^2^T, with Wesolowski (Eurocrypt’19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS’19).\r\nA recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt’22) are short-lived proofs and signatures, which are proofs and signatures that are only sound for some time t, but after that can be forged by anyone. For this they rely on “watermarkable VDFs”, where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on “zero-knowledge VDFs”, where instead of the output y, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski’s PoE, for the watermarkable VDFs there’s currently no security proof.\r\n\r\nIn this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al.’s construction in several dimensions (faster forging times, arguably weaker assumptions).\r\nA key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for y = x^2^T, but instead give a (watermarked or zk) proof for the more basic statement that \r\nx^l, y^l satisfy x^l = x ^r, y^l = y^r for some r, together with a normal PoE for y^l = (x^l)^2^T."}],"intvolume":"     15674","title":"Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation","language":[{"iso":"eng"}],"user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","publication_identifier":{"eisbn":["9783031918209"],"isbn":["9783031918193"],"eissn":["1611-3349"],"issn":["0302-9743"]},"date_updated":"2026-04-16T09:11:09Z","article_processing_charge":"No","scopus_import":"1","conference":{"location":"Roros, Norway","start_date":"2025-05-12","name":"PKC: Public-Key Cryptography","end_date":"2025-05-15"},"status":"public","year":"2025","corr_author":"1","publisher":"Springer Nature","citation":{"ama":"Hoffmann C, Pietrzak KZ. Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation. In: <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>. Vol 15674. Springer Nature; 2025:36-66. doi:<a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">10.1007/978-3-031-91820-9_2</a>","ieee":"C. Hoffmann and K. Z. Pietrzak, “Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation,” in <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, Roros, Norway, 2025, vol. 15674, pp. 36–66.","apa":"Hoffmann, C., &#38; Pietrzak, K. Z. (2025). Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation. In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i> (Vol. 15674, pp. 36–66). Roros, Norway: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">https://doi.org/10.1007/978-3-031-91820-9_2</a>","ista":"Hoffmann C, Pietrzak KZ. 2025. Watermarkable and zero-knowledge Verifiable Delay Functions from any proof of exponentiation. 28th IACR International Conference on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography, LNCS, vol. 15674, 36–66.","chicago":"Hoffmann, Charlotte, and Krzysztof Z Pietrzak. “Watermarkable and Zero-Knowledge Verifiable Delay Functions from Any Proof of Exponentiation.” In <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, 15674:36–66. Springer Nature, 2025. <a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">https://doi.org/10.1007/978-3-031-91820-9_2</a>.","short":"C. Hoffmann, K.Z. Pietrzak, in:, 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Springer Nature, 2025, pp. 36–66.","mla":"Hoffmann, Charlotte, and Krzysztof Z. Pietrzak. “Watermarkable and Zero-Knowledge Verifiable Delay Functions from Any Proof of Exponentiation.” <i>28th IACR International Conference on Practice and Theory of Public-Key Cryptography</i>, vol. 15674, Springer Nature, 2025, pp. 36–66, doi:<a href=\"https://doi.org/10.1007/978-3-031-91820-9_2\">10.1007/978-3-031-91820-9_2</a>."}},{"alternative_title":["LNCS"],"oa_version":"Preprint","doi":"10.1007/978-3-031-78011-0_14","author":[{"id":"0b2a4358-bb35-11ec-b7b9-e3279b593dbb","last_name":"Anastos","full_name":"Anastos, Michael","first_name":"Michael"},{"last_name":"Auerbach","id":"D33D2B18-E445-11E9-ABB7-15F4E5697425","first_name":"Benedikt","full_name":"Auerbach, Benedikt","orcid":"0000-0002-7553-6606"},{"id":"3EDE6DE4-AA5A-11E9-986D-341CE6697425","last_name":"Baig","full_name":"Baig, Mirza Ahad","first_name":"Mirza Ahad"},{"first_name":"Miguel","full_name":"Cueto Noval, Miguel","orcid":"0000-0002-2505-4246","last_name":"Cueto Noval","id":"ffc563a3-f6e0-11ea-865d-e3cce03d17cc"},{"id":"5fca0887-a1db-11eb-95d1-ca9d5e0453b3","last_name":"Kwan","orcid":"0000-0002-4003-7567","full_name":"Kwan, Matthew Alan","first_name":"Matthew Alan"},{"id":"2D7ABD02-F248-11E8-B48F-1D18A9856A87","last_name":"Pascual Perez","first_name":"Guillermo","orcid":"0000-0001-8630-415X","full_name":"Pascual Perez, Guillermo"},{"id":"3E04A7AA-F248-11E8-B48F-1D18A9856A87","last_name":"Pietrzak","first_name":"Krzysztof Z","orcid":"0000-0002-9139-1654","full_name":"Pietrzak, Krzysztof Z"}],"month":"12","volume":15364,"type":"conference","publication_status":"published","isi":1,"quality_controlled":"1","page":"413-443","OA_type":"green","OA_place":"repository","oa":1,"_id":"18702","language":[{"iso":"eng"}],"title":"The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging","intvolume":"     15364","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2024/1097"}],"date_created":"2024-12-22T23:01:47Z","abstract":[{"lang":"eng","text":"In this work we prove lower bounds on the (communication) cost of maintaining a shared key among a dynamic group of users. Being “dynamic” means one can add and remove users from the group. This captures important protocols like multicast encryption (ME) and continuous group-key agreement (CGKA), which is the primitive underlying many group messaging applications. We prove our bounds in a combinatorial setting where the state of the protocol progresses in rounds. The state of the protocol in each round is captured by a set system, with each of its elements specifying a set of users who share a secret key. We show this combinatorial model implies bounds in symbolic models for ME and CGKA that capture, as building blocks, PRGs, PRFs, dual PRFs, secret sharing, and symmetric encryption in the setting of ME, and PRGs, PRFs, dual PRFs, secret sharing, public-key encryption, and key-updatable public-key encryption in the setting of CGKA. The models are related to the ones used by Micciancio and Panjwani (Eurocrypt’04) and Bienstock et al. (TCC’20) to analyze ME and CGKA, respectively. We prove – using the Bollobás’ Set Pairs Inequality – that the cost (number of uploaded ciphertexts) for replacing a set of d users in a group of size n is Ω(dln(n/d)). Our lower bound is asymptotically tight and both improves on a bound of Ω(d) by Bienstock et al. (TCC’20), and generalizes a result by Micciancio and Panjwani (Eurocrypt’04), who proved a lower bound of Ω(log(n)) for d=1. "}],"date_published":"2024-12-02T00:00:00Z","day":"02","department":[{"_id":"MaKw"},{"_id":"KrPi"}],"publication":"22nd International Conference on Theory of Cryptography","citation":{"short":"M. Anastos, B. Auerbach, M.A. Baig, M. Cueto Noval, M.A. Kwan, G. Pascual Perez, K.Z. Pietrzak, in:, 22nd International Conference on Theory of Cryptography, Springer Nature, 2024, pp. 413–443.","chicago":"Anastos, Michael, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval, Matthew Alan Kwan, Guillermo Pascual Perez, and Krzysztof Z Pietrzak. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” In <i>22nd International Conference on Theory of Cryptography</i>, 15364:413–43. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>.","mla":"Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications to Multicast Encryption and Group Messaging.” <i>22nd International Conference on Theory of Cryptography</i>, vol. 15364, Springer Nature, 2024, pp. 413–43, doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>.","ama":"Anastos M, Auerbach B, Baig MA, et al. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In: <i>22nd International Conference on Theory of Cryptography</i>. Vol 15364. Springer Nature; 2024:413-443. doi:<a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">10.1007/978-3-031-78011-0_14</a>","ieee":"M. Anastos <i>et al.</i>, “The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging,” in <i>22nd International Conference on Theory of Cryptography</i>, Milan, Italy, 2024, vol. 15364, pp. 413–443.","apa":"Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual Perez, G., &#38; Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. In <i>22nd International Conference on Theory of Cryptography</i> (Vol. 15364, pp. 413–443). Milan, Italy: Springer Nature. <a href=\"https://doi.org/10.1007/978-3-031-78011-0_14\">https://doi.org/10.1007/978-3-031-78011-0_14</a>","ista":"Anastos M, Auerbach B, Baig MA, Cueto Noval M, Kwan MA, Pascual Perez G, Pietrzak KZ. 2024. The cost of maintaining keys in dynamic groups with applications to multicast encryption and group messaging. 22nd International Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol. 15364, 413–443."},"publisher":"Springer Nature","corr_author":"1","year":"2024","status":"public","external_id":{"isi":["001545628900014"]},"article_processing_charge":"No","scopus_import":"1","conference":{"end_date":"2024-12-06","name":"TCC: Theory of Cryptography","start_date":"2024-12-02","location":"Milan, Italy"},"publication_identifier":{"isbn":["9783031780103"],"eissn":["1611-3349"],"issn":["0302-9743"]},"date_updated":"2025-12-02T13:55:46Z","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"oa":1,"_id":"18755","OA_place":"repository","page":"207-239","OA_type":"green","quality_controlled":"1","isi":1,"publication_status":"published","acknowledgement":"Ehsan Ebrahimi is supported by the Luxembourg National Research Fund under the Junior CORE project QSP (C22/IS/17272217/QSP/Ebrahimi).","month":"12","type":"conference","volume":15486,"author":[{"full_name":"Ebrahimi, Ehsan","first_name":"Ehsan","last_name":"Ebrahimi"},{"id":"dc8f1524-403e-11ee-bf07-9649ad996e21","last_name":"Yadav","full_name":"Yadav, Anshu","first_name":"Anshu"}],"doi":"10.1007/978-981-96-0891-1_7","oa_version":"Preprint","user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","publication_identifier":{"issn":["0302-9743"],"eissn":["1611-3349"],"isbn":["9789819608904"]},"date_updated":"2025-09-09T12:00:12Z","article_processing_charge":"No","conference":{"start_date":"2024-12-09","location":"Kolkata, India","name":"ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security","end_date":"2024-12-13"},"scopus_import":"1","status":"public","external_id":{"isi":["001443889100007"]},"year":"2024","publisher":"Springer Nature","citation":{"mla":"Ebrahimi, Ehsan, and Anshu Yadav. “Strongly Secure Universal Thresholdizer.” <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, vol. 15486, Springer Nature, 2024, pp. 207–39, doi:<a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">10.1007/978-981-96-0891-1_7</a>.","chicago":"Ebrahimi, Ehsan, and Anshu Yadav. “Strongly Secure Universal Thresholdizer.” In <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, 15486:207–39. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">https://doi.org/10.1007/978-981-96-0891-1_7</a>.","short":"E. Ebrahimi, A. Yadav, in:, 30th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2024, pp. 207–239.","ista":"Ebrahimi E, Yadav A. 2024. Strongly secure universal thresholdizer. 30th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security vol. 15486, 207–239.","apa":"Ebrahimi, E., &#38; Yadav, A. (2024). Strongly secure universal thresholdizer. In <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i> (Vol. 15486, pp. 207–239). Kolkata, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">https://doi.org/10.1007/978-981-96-0891-1_7</a>","ama":"Ebrahimi E, Yadav A. Strongly secure universal thresholdizer. In: <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>. Vol 15486. Springer Nature; 2024:207-239. doi:<a href=\"https://doi.org/10.1007/978-981-96-0891-1_7\">10.1007/978-981-96-0891-1_7</a>","ieee":"E. Ebrahimi and A. Yadav, “Strongly secure universal thresholdizer,” in <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, Kolkata, India, 2024, vol. 15486, pp. 207–239."},"day":"12","department":[{"_id":"KrPi"}],"publication":"30th International Conference on the Theory and Application of Cryptology and Information Security","date_published":"2024-12-12T00:00:00Z","date_created":"2025-01-05T23:01:56Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2024/2078"}],"abstract":[{"text":"A universalthresholdizer (UT), constructed from a threshold fully homomorphic encryption by Boneh et. al , Crypto 2018, is a general framework for universally thresholdizing many cryptographic schemes. However, their framework is insufficient to construct strongly secure threshold schemes, such as threshold signatures and threshold public-key encryption, etc.\r\n\r\nIn this paper, we strengthen the security definition for a universal thresholdizer and propose a scheme which satisfies our stronger security notion. Our UT scheme is an improvement of Boneh et. al ’s construction at the level of threshold fully homomorphic encryption using a key homomorphic pseudorandom function. We apply our strongly secure UT scheme to construct strongly secure threshold signatures and threshold public-key encryption.","lang":"eng"}],"intvolume":"     15486","title":"Strongly secure universal thresholdizer","language":[{"iso":"eng"}]},{"title":"Evasive LWE assumptions: Definitions, classes, and counterexamples","intvolume":"     15487","language":[{"iso":"eng"}],"publication":"30th International Conference on the Theory and Application of Cryptology and Information Security","department":[{"_id":"KrPi"}],"day":"13","date_published":"2024-12-13T00:00:00Z","abstract":[{"lang":"eng","text":"The evasive LWE assumption, proposed by Wee [Eurocrypt’22 Wee] for constructing a lattice-based optimal broadcast encryption, has shown to be a powerful assumption, adopted by subsequent works to construct advanced primitives ranging from ABE variants to obfuscation for null circuits. However, a closer look reveals significant differences among the precise assumption statements involved in different works, leading to the fundamental question of how these assumptions compare to each other. In this work, we initiate a more systematic study on evasive LWE assumptions:\r\n(i) Based on the standard LWE assumption, we construct simple counterexamples against three private-coin evasive LWE variants, used in [Crypto’22 Tsabary, Asiacrypt’22 VWW, Crypto’23 ARYY] respectively, showing that these assumptions are unlikely to hold.\r\n\r\n(ii) Based on existing evasive LWE variants and our counterexamples, we propose and define three classes of plausible evasive LWE assumptions, suitably capturing all existing variants for which we are not aware of non-obfuscation-based counterexamples.\r\n\r\n(iii) We show that under our assumption formulations, the security proofs of [Asiacrypt’22 VWW] and [Crypto’23 ARYY] can be recovered, and we reason why the security proof of [Crypto’22 Tsabary] is also plausibly repairable using an appropriate evasive LWE assumption."}],"date_created":"2025-01-05T23:01:56Z","main_file_link":[{"open_access":"1","url":"https://eprint.iacr.org/2024/2000"}],"external_id":{"isi":["001443890800014"]},"status":"public","year":"2024","publisher":"Springer Nature","citation":{"mla":"Brzuska, Chris, et al. “Evasive LWE Assumptions: Definitions, Classes, and Counterexamples.” <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, vol. 15487, Springer Nature, 2024, pp. 418–49, doi:<a href=\"https://doi.org/10.1007/978-981-96-0894-2_14\">10.1007/978-981-96-0894-2_14</a>.","short":"C. Brzuska, A. Ünal, I.K.Y. Woo, in:, 30th International Conference on the Theory and Application of Cryptology and Information Security, Springer Nature, 2024, pp. 418–449.","chicago":"Brzuska, Chris, Akin Ünal, and Ivy K.Y. Woo. “Evasive LWE Assumptions: Definitions, Classes, and Counterexamples.” In <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, 15487:418–49. Springer Nature, 2024. <a href=\"https://doi.org/10.1007/978-981-96-0894-2_14\">https://doi.org/10.1007/978-981-96-0894-2_14</a>.","ista":"Brzuska C, Ünal A, Woo IKY. 2024. Evasive LWE assumptions: Definitions, classes, and counterexamples. 30th International Conference on the Theory and Application of Cryptology and Information Security. ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security, LNCS, vol. 15487, 418–449.","apa":"Brzuska, C., Ünal, A., &#38; Woo, I. K. Y. (2024). Evasive LWE assumptions: Definitions, classes, and counterexamples. In <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i> (Vol. 15487, pp. 418–449). Kolkata, India: Springer Nature. <a href=\"https://doi.org/10.1007/978-981-96-0894-2_14\">https://doi.org/10.1007/978-981-96-0894-2_14</a>","ieee":"C. Brzuska, A. Ünal, and I. K. Y. Woo, “Evasive LWE assumptions: Definitions, classes, and counterexamples,” in <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>, Kolkata, India, 2024, vol. 15487, pp. 418–449.","ama":"Brzuska C, Ünal A, Woo IKY. Evasive LWE assumptions: Definitions, classes, and counterexamples. In: <i>30th International Conference on the Theory and Application of Cryptology and Information Security</i>. Vol 15487. Springer Nature; 2024:418-449. doi:<a href=\"https://doi.org/10.1007/978-981-96-0894-2_14\">10.1007/978-981-96-0894-2_14</a>"},"user_id":"317138e5-6ab7-11ef-aa6d-ffef3953e345","date_updated":"2025-09-09T12:00:51Z","publication_identifier":{"isbn":["9789819608935"],"eissn":["1611-3349"],"issn":["0302-9743"]},"scopus_import":"1","conference":{"location":"Kolkata, India","start_date":"2024-12-09","end_date":"2024-12-13","name":"ASIACRYPT: Conference on the Theory and Application of Cryptology and Information Security"},"article_processing_charge":"No","oa_version":"Preprint","alternative_title":["LNCS"],"acknowledgement":"The authors thank the anonymous reviewers for insightful comments which very much improved this work, in particular, sharing with us the counterexamples against a prior version of Hiding Evasive LWE, and against public-coin Evasive LWE when the sampler inputs B. Chris Brzuska and Ivy K. Y. Woo are supported by Research Council of Finland grant 358950. We thank Russell W. F. Lai and Hoeteck Wee for helpful discussions.","publication_status":"published","volume":15487,"type":"conference","month":"12","author":[{"last_name":"Brzuska","first_name":"Chris","full_name":"Brzuska, Chris"},{"first_name":"Akin","orcid":"0000-0002-8929-0221","full_name":"Ünal, Akin","id":"f6b56fb6-dc63-11ee-9dbf-f6780863a85a","last_name":"Ünal"},{"full_name":"Woo, Ivy K.Y.","first_name":"Ivy K.Y.","last_name":"Woo"}],"doi":"10.1007/978-981-96-0894-2_14","OA_type":"green","page":"418-449","quality_controlled":"1","isi":1,"_id":"18756","oa":1,"OA_place":"repository"}]