---
OA_place: repository
OA_type: green
_id: '21042'
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."
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.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Ray
full_name: Neiheiser, Ray
id: f09651b9-fec0-11ec-b5d8-934aff0e52a4
last_name: Neiheiser
orcid: 0000-0001-7227-8309
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
orcid: 0000-0002-8827-3382
citation:
ama: 'Neiheiser R, Kokoris Kogias E. Anthemius: Efficient and modular block assembly
for concurrent execution. In: 29th International Conference on Financial Cryptography
and Data Security. Vol 15751. Springer Nature; 2026:307-323. doi:10.1007/978-3-032-07024-1_18'
apa: 'Neiheiser, R., & Kokoris Kogias, E. (2026). Anthemius: Efficient and modular
block assembly for concurrent execution. In 29th International Conference on
Financial Cryptography and Data Security (Vol. 15751, pp. 307–323). Miyakojima,
Japan: Springer Nature. https://doi.org/10.1007/978-3-032-07024-1_18'
chicago: 'Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient
and Modular Block Assembly for Concurrent Execution.” In 29th International
Conference on Financial Cryptography and Data Security, 15751:307–23. Springer
Nature, 2026. https://doi.org/10.1007/978-3-032-07024-1_18.'
ieee: 'R. Neiheiser and E. Kokoris Kogias, “Anthemius: Efficient and modular block
assembly for concurrent execution,” in 29th International Conference on Financial
Cryptography and Data Security, 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.'
mla: 'Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient and Modular
Block Assembly for Concurrent Execution.” 29th International Conference on
Financial Cryptography and Data Security, vol. 15751, Springer Nature, 2026,
pp. 307–23, doi:10.1007/978-3-032-07024-1_18.'
short: R. Neiheiser, E. Kokoris Kogias, in:, 29th International Conference on Financial
Cryptography and Data Security, Springer Nature, 2026, pp. 307–323.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
corr_author: '1'
date_created: 2026-01-25T23:01:40Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-02-12T13:39:07Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-032-07024-1_18
external_id:
arxiv:
- '2502.10074'
intvolume: ' 15751'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2502.10074
month: '01'
oa: 1
oa_version: Preprint
page: 307-323
project:
- _id: 34a1b658-11ca-11ed-8bc3-c75229f0241e
grant_number: F8502
name: Interface Theory for Security and Privacy
- _id: 7bdd2f70-9f16-11ee-852c-b7950bc6d277
grant_number: ICT22-045
name: SeCure, privAte, and interoperabLe layEr 2
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070234'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Anthemius: Efficient and modular block assembly for concurrent execution'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15751
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21134'
abstract:
- lang: eng
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."
acknowledgement: This research was funded in whole or in part by the Austrian Science
Fund (FWF) 10.55776/F85.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain
blockchains. In: 29th International Conference on Financial Cryptography and
Data Security. Vol 15752. Springer Nature; 2026:127-142. doi:10.1007/978-3-032-07035-7_8'
apa: 'Baig, M. A., & Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space
based longest-chain blockchains. In 29th International Conference on Financial
Cryptography and Data Security (Vol. 15752, pp. 127–142). Miyakojima, Japan:
Springer Nature. https://doi.org/10.1007/978-3-032-07035-7_8'
chicago: Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” In 29th International Conference on Financial
Cryptography and Data Security, 15752:127–42. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-07035-7_8.
ieee: M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based
longest-chain blockchains,” in 29th International Conference on Financial Cryptography
and Data Security, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142.
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.'
mla: Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” 29th International Conference on Financial
Cryptography and Data Security, vol. 15752, Springer Nature, 2026, pp. 127–42,
doi:10.1007/978-3-032-07035-7_8.
short: M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial
Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
corr_author: '1'
date_created: 2026-02-01T23:01:43Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-032-07035-7_8
external_id:
arxiv:
- '2505.14891'
intvolume: ' 15752'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.14891
month: '01'
oa: 1
oa_version: Preprint
page: 127-142
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070340'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: On the (in)security of Proofs-of-space based longest-chain blockchains
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15752
year: '2026'
...
---
OA_place: publisher
_id: '21651'
abstract:
- lang: eng
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."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
citation:
ama: Baig MA. On secure chain selection rules from physical resources in a permissionless
setting. 2026. doi:10.15479/AT-ISTA-21651
apa: Baig, M. A. (2026). On secure chain selection rules from physical resources
in a permissionless setting. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT-ISTA-21651
chicago: Baig, Mirza Ahad. “On Secure Chain Selection Rules from Physical Resources
in a Permissionless Setting.” Institute of Science and Technology Austria, 2026.
https://doi.org/10.15479/AT-ISTA-21651.
ieee: M. A. Baig, “On secure chain selection rules from physical resources in a
permissionless setting,” Institute of Science and Technology Austria, 2026.
ista: Baig MA. 2026. On secure chain selection rules from physical resources in
a permissionless setting. Institute of Science and Technology Austria.
mla: Baig, Mirza Ahad. On Secure Chain Selection Rules from Physical Resources
in a Permissionless Setting. Institute of Science and Technology Austria,
2026, doi:10.15479/AT-ISTA-21651.
short: M.A. Baig, On Secure Chain Selection Rules from Physical Resources in a Permissionless
Setting, Institute of Science and Technology Austria, 2026.
corr_author: '1'
date_created: 2026-04-02T09:31:34Z
date_published: 2026-03-04T00:00:00Z
date_updated: 2026-04-15T08:45:19Z
day: '04'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-21651
file:
- access_level: closed
checksum: c3986dba90653dac97adba662ebff238
content_type: application/x-zip-compressed
creator: mbaig
date_created: 2026-04-03T17:28:48Z
date_updated: 2026-04-13T08:24:13Z
file_id: '21655'
file_name: PhD-Thesis-Mirza-Ahad-Baig - Library Submission.zip
file_size: 139353434
relation: source_file
- access_level: open_access
checksum: 292a5989262521f7c145a109d1f348cb
content_type: application/pdf
creator: mbaig
date_created: 2026-04-03T17:29:30Z
date_updated: 2026-04-15T07:37:25Z
file_id: '21656'
file_name: 2026_Baig_Mirza_Ahad_Thesis.pdf
file_size: 1942037
relation: main_file
file_date_updated: 2026-04-15T07:37:25Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '03'
oa: 1
oa_version: Published Version
publication_identifier:
isbn:
- 978-3-99078-078-7
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '21134'
relation: part_of_dissertation
status: public
- id: '20587'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On secure chain selection rules from physical resources in a permissionless
setting
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20053'
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."
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.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. When is liquid democracy
possible?: On the manipulation of variance. In: Proceedings of the ACM Symposium
on Principles of Distributed Computing. Association for Computing Machinery;
2025:241-251. doi:10.1145/3732772.3733544'
apa: 'Chatterjee, K., Gilbert, S., Schmid, S., Svoboda, J., & Yeo, M. X. (2025).
When is liquid democracy possible?: On the manipulation of variance. In Proceedings
of the ACM Symposium on Principles of Distributed Computing (pp. 241–251).
Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733544'
chicago: 'Chatterjee, Krishnendu, Seth Gilbert, Stefan Schmid, Jakub Svoboda, and
Michelle X Yeo. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.”
In Proceedings of the ACM Symposium on Principles of Distributed Computing,
241–51. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733544.'
ieee: 'K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, and M. X. Yeo, “When is
liquid democracy possible?: On the manipulation of variance,” in Proceedings
of the ACM Symposium on Principles of Distributed Computing, Huatulco, Mexico,
2025, pp. 241–251.'
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.'
mla: 'Chatterjee, Krishnendu, et al. “When Is Liquid Democracy Possible?: On the
Manipulation of Variance.” Proceedings of the ACM Symposium on Principles of
Distributed Computing, Association for Computing Machinery, 2025, pp. 241–51,
doi:10.1145/3732772.3733544.'
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.
conference:
end_date: 2025-06-20
location: Huatulco, Mexico
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2025-06-16
corr_author: '1'
date_created: 2025-07-21T08:18:26Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2026-02-16T11:46:51Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1145/3732772.3733544
ec_funded: 1
external_id:
isi:
- '001525534800030'
file:
- access_level: open_access
checksum: cd628fe54d96e9fc6cc789bb8145422b
content_type: application/pdf
creator: dernst
date_created: 2025-08-05T07:15:31Z
date_updated: 2025-08-05T07:15:31Z
file_id: '20122'
file_name: 2025_PODC_Chatterjee.pdf
file_size: 783297
relation: main_file
success: 1
file_date_updated: 2025-08-05T07:15:31Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/745
month: '06'
oa: 1
oa_version: Published Version
page: 241-251
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9798400718854'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: 'When is liquid democracy possible?: On the manipulation of variance'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19600'
abstract:
- lang: eng
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.
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Zeta
full_name: Avarikioti, Zeta
last_name: Avarikioti
- first_name: Mahsa
full_name: Bastankhah, Mahsa
last_name: Bastankhah
- first_name: Mohammad Ali
full_name: Maddah-Ali, Mohammad Ali
last_name: Maddah-Ali
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX.
Route discovery in private payment channel networks. In: Computer Security.
ESORICS 2024 International Workshops. Vol 15263. Springer Nature; 2025:207-223.
doi:10.1007/978-3-031-82349-7_15'
apa: 'Avarikioti, Z., Bastankhah, M., Maddah-Ali, M. A., Pietrzak, K. Z., Svoboda,
J., & Yeo, M. X. (2025). Route discovery in private payment channel networks.
In Computer Security. ESORICS 2024 International Workshops (Vol. 15263,
pp. 207–223). Bydgoszcz, Poland: Springer Nature. https://doi.org/10.1007/978-3-031-82349-7_15'
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 Computer Security. ESORICS 2024 International Workshops,
15263:207–23. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-82349-7_15.
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 Computer
Security. ESORICS 2024 International Workshops, Bydgoszcz, Poland, 2025, vol.
15263, pp. 207–223.
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.'
mla: Avarikioti, Zeta, et al. “Route Discovery in Private Payment Channel Networks.”
Computer Security. ESORICS 2024 International Workshops, vol. 15263, Springer
Nature, 2025, pp. 207–23, doi:10.1007/978-3-031-82349-7_15.
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.
conference:
end_date: 2024-09-20
location: Bydgoszcz, Poland
name: 'ESORICS: European Symposium on Research in Computer Security'
start_date: 2024-09-16
date_created: 2025-04-20T22:01:28Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-11-05T07:52:35Z
day: '01'
department:
- _id: KrPi
- _id: KrCh
doi: 10.1007/978-3-031-82349-7_15
ec_funded: 1
intvolume: ' 15263'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1539
month: '04'
oa: 1
oa_version: Submitted Version
page: 207-223
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Computer Security. ESORICS 2024 International Workshops
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031823480'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Route discovery in private payment channel networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15263
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19712'
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."
acknowledgement: We thank Pierre Briaud and Morten Øygarden for helpful discussions
on algebraic attacks on RSD, and the EC reviewers for helpful comments.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Simon-Philipp
full_name: Merz, Simon-Philipp
last_name: Merz
- first_name: Patrick
full_name: Stählin, Patrick
last_name: Stählin
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
citation:
ama: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic
attacks against code-based assumptions. In: 44th Annual International Conference
on the Theory and Applications of Cryptographic Techniques. Vol 15606. Springer
Nature; 2025:385-415. doi:10.1007/978-3-031-91095-1_14'
apa: 'Cueto Noval, M., Merz, S.-P., Stählin, P., & Ünal, A. (2025). On the soundness
of algebraic attacks against code-based assumptions. In 44th Annual International
Conference on the Theory and Applications of Cryptographic Techniques (Vol.
15606, pp. 385–415). Madrid, Spain: Springer Nature. https://doi.org/10.1007/978-3-031-91095-1_14'
chicago: Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal.
“On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In 44th
Annual International Conference on the Theory and Applications of Cryptographic
Techniques, 15606:385–415. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-91095-1_14.
ieee: M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic
attacks against code-based assumptions,” in 44th Annual International Conference
on the Theory and Applications of Cryptographic Techniques, Madrid, Spain,
2025, vol. 15606, pp. 385–415.
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.'
mla: Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against
Code-Based Assumptions.” 44th Annual International Conference on the Theory
and Applications of Cryptographic Techniques, vol. 15606, Springer Nature,
2025, pp. 385–415, doi:10.1007/978-3-031-91095-1_14.
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.
conference:
end_date: 2025-05-08
location: Madrid, Spain
name: 'EUROCRYPT: International Conference on the Theory and Applications of Cryptographic
Techniques'
start_date: 2025-05-04
corr_author: '1'
date_created: 2025-05-19T14:15:01Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2025-05-28T06:12:39Z
day: '28'
department:
- _id: KrPi
doi: 10.1007/978-3-031-91095-1_14
intvolume: ' 15606'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.research-collection.ethz.ch/handle/20.500.11850/732894
month: '04'
oa: 1
oa_version: Submitted Version
page: 385-415
publication: 44th Annual International Conference on the Theory and Applications of
Cryptographic Techniques
publication_identifier:
eisbn:
- '9783031910951'
eissn:
- 1611-3349
isbn:
- '9783031910944'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the soundness of algebraic attacks against code-based assumptions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15606
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19738'
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Anasuya
full_name: Acharya, Anasuya
last_name: Acharya
- first_name: Karen
full_name: Azari, Karen
last_name: Azari
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Dennis
full_name: Hofheinz, Dennis
last_name: Hofheinz
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
citation:
ama: 'Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. Securely instantiating
‘Half Gates’ garbling in the standard model. In: 28th IACR International Conference
on Practice and Theory of Public-Key Cryptography. Vol 15677. Springer Nature;
2025:37-75. doi:10.1007/978-3-031-91829-2_2'
apa: 'Acharya, A., Azari, K., Baig, M. A., Hofheinz, D., & Kamath, C. (2025).
Securely instantiating ‘Half Gates’ garbling in the standard model. In 28th
IACR International Conference on Practice and Theory of Public-Key Cryptography
(Vol. 15677, pp. 37–75). Roros, Norway: Springer Nature. https://doi.org/10.1007/978-3-031-91829-2_2'
chicago: Acharya, Anasuya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, and Chethan
Kamath. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.”
In 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography, 15677:37–75. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-91829-2_2.
ieee: A. Acharya, K. Azari, M. A. Baig, D. Hofheinz, and C. Kamath, “Securely instantiating
‘Half Gates’ garbling in the standard model,” in 28th IACR International Conference
on Practice and Theory of Public-Key Cryptography, Roros, Norway, 2025, vol.
15677, pp. 37–75.
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.'
mla: Acharya, Anasuya, et al. “Securely Instantiating ‘Half Gates’ Garbling in the Standard
Model.” 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography, vol. 15677, Springer Nature, 2025, pp. 37–75, doi:10.1007/978-3-031-91829-2_2.
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.
conference:
end_date: 2025-05-15
location: Roros, Norway
name: 'PKC: Public-Key Cryptography'
start_date: 2025-05-12
date_created: 2025-05-25T22:17:02Z
date_published: 2025-05-05T00:00:00Z
date_updated: 2025-06-02T07:01:45Z
day: '05'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-031-91829-2_2
intvolume: ' 15677'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/281
month: '05'
oa: 1
oa_version: Preprint
page: 37-75
publication: 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031918285'
issn:
- 0302-9743
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Securely instantiating ‘Half Gates’ garbling in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15677
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20844'
abstract:
- lang: eng
text: "We introduce and construct a new proof system called Non-interactive Arguments
of Knowledge or Space (NArKoS), where a space-bounded prover can convince a verifier
they know a secret, while having access to sufficient space allows one to forge
indistinguishable proofs without the secret.\r\nAn application of NArKoS are space-deniable
proofs, which are proofs of knowledge (say for authentication in access control)
that are sound when executed by a lightweight device like a smart-card or an RFID
chip that cannot have much storage, but are deniable (in the strong sense of online
deniability) as the verifier, like a card reader, can efficiently forge such proofs.\r\nWe
construct NArKoS in the random oracle model using an OR-proof combining a sigma
protocol (for the proof of knowledge of the secret) with a new proof system called
simulatable Proof of Transient Space (simPoTS). We give two different constructions
of simPoTS, one based on labelling graphs with high pebbling complexity, a technique
used in the construction of memory-hard functions and proofs of space, and a more
practical construction based on the verifiable space-hard functions from TCC’24
where a prover must compute a root of a sparse polynomial. In both cases, the
main challenge is making the proofs efficiently simulatable."
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jesko
full_name: Dujmovic, Jesko
last_name: Dujmovic
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Dujmovic J, Günther CU, Pietrzak KZ. Space-deniable proofs. In: 23rd International
Conference on Theory of Cryptography. Vol 16271. Springer Nature; 2025:171-202.
doi:10.1007/978-3-032-12290-2_6'
apa: 'Dujmovic, J., Günther, C. U., & Pietrzak, K. Z. (2025). Space-deniable
proofs. In 23rd International Conference on Theory of Cryptography (Vol.
16271, pp. 171–202). Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_6'
chicago: Dujmovic, Jesko, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Space-Deniable
Proofs.” In 23rd International Conference on Theory of Cryptography, 16271:171–202.
Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_6.
ieee: J. Dujmovic, C. U. Günther, and K. Z. Pietrzak, “Space-deniable proofs,” in
23rd International Conference on Theory of Cryptography, Aarhus, Denmark,
2025, vol. 16271, pp. 171–202.
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.'
mla: Dujmovic, Jesko, et al. “Space-Deniable Proofs.” 23rd International Conference
on Theory of Cryptography, vol. 16271, Springer Nature, 2025, pp. 171–202,
doi:10.1007/978-3-032-12290-2_6.
short: J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference
on Theory of Cryptography, Springer Nature, 2025, pp. 171–202.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:33Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:44:16Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_6
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1723
month: '12'
oa: 1
oa_version: Preprint
page: 171-202
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space-deniable proofs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20845'
abstract:
- lang: eng
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."
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Shweta
full_name: Agrawal, Shweta
last_name: Agrawal
- first_name: Anuja
full_name: Modi, Anuja
last_name: Modi
- first_name: Anshu
full_name: Yadav, Anshu
id: dc8f1524-403e-11ee-bf07-9649ad996e21
last_name: Yadav
- first_name: Shota
full_name: Yamada, Shota
last_name: Yamada
citation:
ama: 'Agrawal S, Modi A, Yadav A, Yamada S. Zeroizing attacks against evasive and circular
evasive LWE. In: 23rd International Conference on Theory of Cryptography.
Vol 16269. Springer Nature; 2025:259-290. doi:10.1007/978-3-032-12293-3_9'
apa: 'Agrawal, S., Modi, A., Yadav, A., & Yamada, S. (2025). Zeroizing attacks
against evasive and circular evasive LWE. In 23rd International Conference
on Theory of Cryptography (Vol. 16269, pp. 259–290). Aarhus, Denmark: Springer
Nature. https://doi.org/10.1007/978-3-032-12293-3_9'
chicago: Agrawal, Shweta, Anuja Modi, Anshu Yadav, and Shota Yamada. “Zeroizing
Attacks against Evasive and Circular Evasive LWE.” In 23rd International Conference
on Theory of Cryptography, 16269:259–90. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12293-3_9.
ieee: S. Agrawal, A. Modi, A. Yadav, and S. Yamada, “Zeroizing attacks against evasive
and circular evasive LWE,” in 23rd International Conference on Theory of Cryptography,
Aarhus, Denmark, 2025, vol. 16269, pp. 259–290.
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.'
mla: Agrawal, Shweta, et al. “Zeroizing Attacks against Evasive and Circular Evasive
LWE.” 23rd International Conference on Theory of Cryptography, vol. 16269,
Springer Nature, 2025, pp. 259–90, doi:10.1007/978-3-032-12293-3_9.
short: S. Agrawal, A. Modi, A. Yadav, S. Yamada, in:, 23rd International Conference
on Theory of Cryptography, Springer Nature, 2025, pp. 259–290.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
date_created: 2025-12-21T23:01:33Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:51:13Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12293-3_9
intvolume: ' 16269'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/375
month: '12'
oa: 1
oa_version: Preprint
page: 259-290
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122926'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zeroizing attacks against evasive and circular evasive LWE
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16269
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20846'
abstract:
- lang: eng
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."
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
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Brandt, Nicholas
last_name: Brandt
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
- first_name: Stella
full_name: Wohnig, Stella
last_name: Wohnig
citation:
ama: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable
random functions without obfuscation and friends. In: 23rd International Conference
on Theory of Cryptography. Vol 16271. Springer Nature; 2025:478-511. doi:10.1007/978-3-032-12290-2_16'
apa: 'Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., & Wohnig, S. (2025).
Constrained verifiable random functions without obfuscation and friends. In 23rd
International Conference on Theory of Cryptography (Vol. 16271, pp. 478–511).
Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_16'
chicago: Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal,
and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” In 23rd International Conference on Theory of Cryptography,
16271:478–511. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_16.
ieee: N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained
verifiable random functions without obfuscation and friends,” in 23rd International
Conference on Theory of Cryptography, Aarhus, Denmark, 2025, vol. 16271, pp.
478–511.
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.'
mla: Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” 23rd International Conference on Theory of Cryptography,
vol. 16271, Springer Nature, 2025, pp. 478–511, doi:10.1007/978-3-032-12290-2_16.
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.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:34Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:11:29Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_16
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1045
month: '12'
oa: 1
oa_version: Preprint
page: 478-511
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constrained verifiable random functions without obfuscation and friends
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
PlanS_conform: '1'
_id: '21017'
abstract:
- lang: eng
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.
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
article_number: '3769423'
article_processing_charge: Yes (via OA deal)
article_type: original
author:
- first_name: Ray
full_name: Neiheiser, Ray
id: f09651b9-fec0-11ec-b5d8-934aff0e52a4
last_name: Neiheiser
orcid: 0000-0001-7227-8309
- first_name: Miguel
full_name: Matos, Miguel
last_name: Matos
- first_name: Luis
full_name: Rodrigues, Luis
last_name: Rodrigues
citation:
ama: 'Neiheiser R, Matos M, Rodrigues L. Kauri: BFT consensus with pipelined tree-based
dissemination and aggregation. ACM Transactions on Computer Systems. 2025.
doi:10.1145/3769423'
apa: 'Neiheiser, R., Matos, M., & Rodrigues, L. (2025). Kauri: BFT consensus
with pipelined tree-based dissemination and aggregation. ACM Transactions on
Computer Systems. Association for Computing Machinery. https://doi.org/10.1145/3769423'
chicago: 'Neiheiser, Ray, Miguel Matos, and Luis Rodrigues. “Kauri: BFT Consensus
with Pipelined Tree-Based Dissemination and Aggregation.” ACM Transactions
on Computer Systems. Association for Computing Machinery, 2025. https://doi.org/10.1145/3769423.'
ieee: 'R. Neiheiser, M. Matos, and L. Rodrigues, “Kauri: BFT consensus with pipelined
tree-based dissemination and aggregation,” ACM Transactions on Computer Systems.
Association for Computing Machinery, 2025.'
ista: 'Neiheiser R, Matos M, Rodrigues L. 2025. Kauri: BFT consensus with pipelined
tree-based dissemination and aggregation. ACM Transactions on Computer Systems.,
3769423.'
mla: 'Neiheiser, Ray, et al. “Kauri: BFT Consensus with Pipelined Tree-Based Dissemination
and Aggregation.” ACM Transactions on Computer Systems, 3769423, Association
for Computing Machinery, 2025, doi:10.1145/3769423.'
short: R. Neiheiser, M. Matos, L. Rodrigues, ACM Transactions on Computer Systems
(2025).
corr_author: '1'
date_created: 2026-01-20T10:14:23Z
date_published: 2025-09-05T00:00:00Z
date_updated: 2026-01-21T08:11:23Z
day: '05'
department:
- _id: KrPi
doi: 10.1145/3769423
has_accepted_license: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/3769423
month: '09'
oa: 1
oa_version: Published Version
project:
- _id: 34a1b658-11ca-11ed-8bc3-c75229f0241e
grant_number: F8502
name: Interface Theory for Security and Privacy
- _id: 7bdd2f70-9f16-11ee-852c-b7950bc6d277
grant_number: ICT22-045
name: SeCure, privAte, and interoperabLe layEr 2
publication: ACM Transactions on Computer Systems
publication_identifier:
eissn:
- 1557-7333
issn:
- 0734-2071
publication_status: epub_ahead
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Kauri: BFT consensus with pipelined tree-based dissemination and aggregation'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21262'
abstract:
- lang: eng
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."
acknowledgement: B. Auerbach and B. Erol—Conducted part of this work at ISTA.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Boran
full_name: Erol, Boran
last_name: Erol
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. Continuous group-key agreement:
Concurrent updates without pruning. In: 45th Annual International Cryptology
Conference. Vol 16007. Springer Nature; 2025:141-172. doi:10.1007/978-3-032-01913-4_5'
apa: 'Auerbach, B., Cueto Noval, M., Erol, B., & Pietrzak, K. Z. (2025). Continuous
group-key agreement: Concurrent updates without pruning. In 45th Annual International
Cryptology Conference (Vol. 16007, pp. 141–172). Santa Barbara, CA, United
States: Springer Nature. https://doi.org/10.1007/978-3-032-01913-4_5'
chicago: 'Auerbach, Benedikt, Miguel Cueto Noval, Boran Erol, and Krzysztof Z Pietrzak.
“Continuous Group-Key Agreement: Concurrent Updates without Pruning.” In 45th
Annual International Cryptology Conference, 16007:141–72. Springer Nature,
2025. https://doi.org/10.1007/978-3-032-01913-4_5.'
ieee: 'B. Auerbach, M. Cueto Noval, B. Erol, and K. Z. Pietrzak, “Continuous group-key
agreement: Concurrent updates without pruning,” in 45th Annual International
Cryptology Conference, Santa Barbara, CA, United States, 2025, vol. 16007,
pp. 141–172.'
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.'
mla: 'Auerbach, Benedikt, et al. “Continuous Group-Key Agreement: Concurrent Updates
without Pruning.” 45th Annual International Cryptology Conference, vol.
16007, Springer Nature, 2025, pp. 141–72, doi:10.1007/978-3-032-01913-4_5.'
short: B. Auerbach, M. Cueto Noval, B. Erol, K.Z. Pietrzak, in:, 45th Annual International
Cryptology Conference, Springer Nature, 2025, pp. 141–172.
conference:
end_date: 2025-08-21
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2025-08-17
date_created: 2026-02-17T07:41:04Z
date_published: 2025-08-17T00:00:00Z
date_updated: 2026-02-18T07:36:42Z
day: '17'
department:
- _id: KrPi
doi: 10.1007/978-3-032-01913-4_5
intvolume: ' 16007'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1035
month: '08'
oa: 1
oa_version: Preprint
page: 141-172
publication: 45th Annual International Cryptology Conference
publication_identifier:
eisbn:
- '9783032019134'
eissn:
- 1611-3349
isbn:
- '9783032019127'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Continuous group-key agreement: Concurrent updates without pruning'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16007
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21323'
abstract:
- lang: eng
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.
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Juraj
full_name: Belohorec, Juraj
last_name: Belohorec
- first_name: Pavel
full_name: Dvořák, Pavel
last_name: Dvořák
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Kristýna
full_name: Mašková, Kristýna
last_name: Mašková
- first_name: Martin
full_name: Pastyřík, Martin
last_name: Pastyřík
citation:
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: 45th Annual International
Cryptology Conference. Vol 16005. Springer Nature; 2025:584-616. doi:10.1007/978-3-032-01887-8_19'
apa: '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.
In 45th Annual International Cryptology Conference (Vol. 16005, pp. 584–616).
Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-032-01887-8_19'
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 45th Annual International Cryptology Conference,
16005:584–616. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-01887-8_19.
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 45th
Annual International Cryptology Conference, Santa Barbara, CA, United States,
2025, vol. 16005, pp. 584–616.
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.'
mla: Belohorec, Juraj, et al. “On Extractability of the KZG Family of Polynomial
Commitment Schemes.” 45th Annual International Cryptology Conference, vol.
16005, Springer Nature, 2025, pp. 584–616, doi:10.1007/978-3-032-01887-8_19.
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.
conference:
end_date: 2025-08-221
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2025-08-17
date_created: 2026-02-18T10:59:58Z
date_published: 2025-08-17T00:00:00Z
date_updated: 2026-02-19T07:50:33Z
day: '17'
department:
- _id: KrPi
doi: 10.1007/978-3-032-01887-8_19
intvolume: ' 16005'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/514
month: '08'
oa: 1
oa_version: Preprint
page: 584-616
publication: 45th Annual International Cryptology Conference
publication_identifier:
eisbn:
- '9783032018878'
eissn:
- 1611-3349
isbn:
- '9783032018861'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: On extractability of the KZG family of polynomial commitment schemes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16005
year: '2025'
...
---
OA_place: publisher
OA_type: gold
_id: '20587'
abstract:
- lang: eng
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."
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."
alternative_title:
- LIPIcs
article_number: '16'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Günther CU, Pietrzak KZ. Nakamoto consensus from multiple resources.
In: 7th Conference on Advances in Financial Technologies. Vol 354. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.AFT.2025.16'
apa: 'Baig, M. A., Günther, C. U., & Pietrzak, K. Z. (2025). Nakamoto consensus
from multiple resources. In 7th Conference on Advances in Financial Technologies
(Vol. 354). Pittsburgh, PA, United States: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.AFT.2025.16'
chicago: Baig, Mirza Ahad, Christoph Ullrich Günther, and Krzysztof Z Pietrzak.
“Nakamoto Consensus from Multiple Resources.” In 7th Conference on Advances
in Financial Technologies, Vol. 354. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2025. https://doi.org/10.4230/LIPIcs.AFT.2025.16.
ieee: M. A. Baig, C. U. Günther, and K. Z. Pietrzak, “Nakamoto consensus from multiple
resources,” in 7th Conference on Advances in Financial Technologies, Pittsburgh,
PA, United States, 2025, vol. 354.
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.'
mla: Baig, Mirza Ahad, et al. “Nakamoto Consensus from Multiple Resources.” 7th
Conference on Advances in Financial Technologies, vol. 354, 16, Schloss Dagstuhl
- Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.AFT.2025.16.
short: M.A. Baig, C.U. Günther, K.Z. Pietrzak, in:, 7th Conference on Advances in
Financial Technologies, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025.
conference:
end_date: 2025-10-10
location: Pittsburgh, PA, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2025-10-08
corr_author: '1'
date_created: 2025-11-02T23:01:34Z
date_published: 2025-10-06T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '06'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.AFT.2025.16
external_id:
arxiv:
- '2508.01448'
file:
- access_level: open_access
checksum: b638adcd4fbffa77116c35393e165eb7
content_type: application/pdf
creator: dernst
date_created: 2025-11-04T08:19:02Z
date_updated: 2025-11-04T08:19:02Z
file_id: '20598'
file_name: 2025_LIPIcsAFT_Baig.pdf
file_size: 1061847
relation: main_file
success: 1
file_date_updated: 2025-11-04T08:19:02Z
has_accepted_license: '1'
intvolume: ' 354'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1410
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: 34a4ce89-11ca-11ed-8bc3-8cc37fb6e11f
grant_number: F8512
name: Security and Privacy by Design for Complex Systems
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 7th Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9783959774000'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Nakamoto consensus from multiple resources
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 354
year: '2025'
...
---
OA_place: publisher
_id: '20920'
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."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
citation:
ama: Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:10.15479/AT-ISTA-20920
apa: Hoffmann, C. (2025). Theory and applications of verifiable delay functions.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20920
chicago: Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.”
Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20920.
ieee: C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute
of Science and Technology Austria, 2025.
ista: Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute
of Science and Technology Austria.
mla: Hoffmann, Charlotte. Theory and Applications of Verifiable Delay Functions.
Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20920.
short: C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute
of Science and Technology Austria, 2025.
corr_author: '1'
date_created: 2026-01-02T10:46:47Z
date_published: 2025-12-31T00:00:00Z
date_updated: 2026-04-16T09:11:08Z
day: '31'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-20920
file:
- access_level: closed
checksum: 8a099fbf54963bd0be38f7ce73658682
content_type: application/x-zip-compressed
creator: choffman
date_created: 2026-01-02T10:39:16Z
date_updated: 2026-01-02T10:39:16Z
file_id: '20921'
file_name: 2025_Hoffmann_Charlotte_Source.zip
file_size: 8355494
relation: source_file
- access_level: open_access
checksum: 9521c07bfb2bb5b14a49c09fcfc96474
content_type: application/pdf
creator: choffman
date_created: 2026-01-02T10:39:26Z
date_updated: 2026-01-02T10:39:26Z
file_id: '20922'
file_name: 2025_Hoffmann_Charlotte_Thesis.pdf
file_size: 2258804
relation: main_file
success: 1
file_date_updated: 2026-01-02T10:39:26Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '116'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '13143'
relation: part_of_dissertation
status: public
- id: '20701'
relation: part_of_dissertation
status: public
- id: '12176'
relation: part_of_dissertation
status: public
- id: '20556'
relation: earlier_version
status: public
- id: '19778'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: Theory and applications of verifiable delay functions
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
OA_place: publisher
_id: '20556'
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."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
citation:
ama: Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:10.15479/AT-ISTA-20556
apa: Hoffmann, C. (2025). Theory and applications of verifiable delay functions.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20556
chicago: Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.”
Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20556.
ieee: C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute
of Science and Technology Austria, 2025.
ista: Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute
of Science and Technology Austria.
mla: Hoffmann, Charlotte. Theory and Applications of Verifiable Delay Functions.
Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20556.
short: C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute
of Science and Technology Austria, 2025.
corr_author: '1'
date_created: 2025-10-27T14:16:56Z
date_published: 2025-10-31T00:00:00Z
date_updated: 2026-04-16T09:11:09Z
day: '31'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-20556
file:
- access_level: closed
checksum: 1fffa4e2c33dd0b9f883d615504a2858
content_type: application/pdf
creator: choffman
date_created: 2025-10-28T14:33:03Z
date_updated: 2026-01-08T14:11:39Z
file_id: '20573'
file_name: 2025_Hoffmann_Charlotte_Thesis.pdf
file_size: 2259304
relation: main_file
- access_level: closed
checksum: 076ea98a1f0a86c3bbc990b6b9460dc2
content_type: application/x-zip-compressed
creator: choffman
date_created: 2025-10-28T14:35:06Z
date_updated: 2025-11-11T09:34:54Z
file_id: '20574'
file_name: 2025_Hoffmann_Charlotte_Source.zip
file_size: 9987633
relation: source_file
file_date_updated: 2026-01-08T14:11:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa_version: Published Version
page: '116'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '13143'
relation: part_of_dissertation
status: public
- id: '12176'
relation: part_of_dissertation
status: public
- id: '20701'
relation: part_of_dissertation
status: public
- id: '20920'
relation: later_version
status: public
- id: '19778'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: Theory and applications of verifiable delay functions
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19778'
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."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Hoffmann C, Pietrzak KZ. Watermarkable and zero-knowledge Verifiable Delay
Functions from any proof of exponentiation. In: 28th IACR International Conference
on Practice and Theory of Public-Key Cryptography. Vol 15674. Springer Nature;
2025:36-66. doi:10.1007/978-3-031-91820-9_2'
apa: 'Hoffmann, C., & Pietrzak, K. Z. (2025). Watermarkable and zero-knowledge
Verifiable Delay Functions from any proof of exponentiation. In 28th IACR International
Conference on Practice and Theory of Public-Key Cryptography (Vol. 15674,
pp. 36–66). Roros, Norway: Springer Nature. https://doi.org/10.1007/978-3-031-91820-9_2'
chicago: Hoffmann, Charlotte, and Krzysztof Z Pietrzak. “Watermarkable and Zero-Knowledge
Verifiable Delay Functions from Any Proof of Exponentiation.” In 28th IACR
International Conference on Practice and Theory of Public-Key Cryptography,
15674:36–66. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-91820-9_2.
ieee: C. Hoffmann and K. Z. Pietrzak, “Watermarkable and zero-knowledge Verifiable
Delay Functions from any proof of exponentiation,” in 28th IACR International
Conference on Practice and Theory of Public-Key Cryptography, Roros, Norway,
2025, vol. 15674, pp. 36–66.
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.'
mla: Hoffmann, Charlotte, and Krzysztof Z. Pietrzak. “Watermarkable and Zero-Knowledge
Verifiable Delay Functions from Any Proof of Exponentiation.” 28th IACR International
Conference on Practice and Theory of Public-Key Cryptography, vol. 15674,
Springer Nature, 2025, pp. 36–66, doi:10.1007/978-3-031-91820-9_2.
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.
conference:
end_date: 2025-05-15
location: Roros, Norway
name: 'PKC: Public-Key Cryptography'
start_date: 2025-05-12
corr_author: '1'
date_created: 2025-06-03T07:30:21Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2026-04-16T09:11:09Z
day: '01'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-031-91820-9_2
intvolume: ' 15674'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2024/481
month: '01'
oa: 1
oa_version: Preprint
page: 36-66
publication: 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography
publication_identifier:
eisbn:
- '9783031918209'
eissn:
- 1611-3349
isbn:
- '9783031918193'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '20920'
relation: dissertation_contains
status: public
- id: '20556'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Watermarkable and zero-knowledge Verifiable Delay Functions from any proof
of exponentiation
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 15674
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '18702'
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. '
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Michael
full_name: Anastos, Michael
id: 0b2a4358-bb35-11ec-b7b9-e3279b593dbb
last_name: Anastos
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Matthew Alan
full_name: Kwan, Matthew Alan
id: 5fca0887-a1db-11eb-95d1-ca9d5e0453b3
last_name: Kwan
orcid: 0000-0002-4003-7567
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
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: 22nd
International Conference on Theory of Cryptography. Vol 15364. Springer Nature;
2024:413-443. doi:10.1007/978-3-031-78011-0_14'
apa: 'Anastos, M., Auerbach, B., Baig, M. A., Cueto Noval, M., Kwan, M. A., Pascual
Perez, G., & Pietrzak, K. Z. (2024). The cost of maintaining keys in dynamic
groups with applications to multicast encryption and group messaging. In 22nd
International Conference on Theory of Cryptography (Vol. 15364, pp. 413–443).
Milan, Italy: Springer Nature. https://doi.org/10.1007/978-3-031-78011-0_14'
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 22nd International Conference on Theory of Cryptography,
15364:413–43. Springer Nature, 2024. https://doi.org/10.1007/978-3-031-78011-0_14.
ieee: M. Anastos et al., “The cost of maintaining keys in dynamic groups
with applications to multicast encryption and group messaging,” in 22nd International
Conference on Theory of Cryptography, Milan, Italy, 2024, vol. 15364, pp.
413–443.
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.'
mla: Anastos, Michael, et al. “The Cost of Maintaining Keys in Dynamic Groups with Applications
to Multicast Encryption and Group Messaging.” 22nd International Conference
on Theory of Cryptography, vol. 15364, Springer Nature, 2024, pp. 413–43,
doi:10.1007/978-3-031-78011-0_14.
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.
conference:
end_date: 2024-12-06
location: Milan, Italy
name: 'TCC: Theory of Cryptography'
start_date: 2024-12-02
corr_author: '1'
date_created: 2024-12-22T23:01:47Z
date_published: 2024-12-02T00:00:00Z
date_updated: 2025-12-02T13:55:46Z
day: '02'
department:
- _id: MaKw
- _id: KrPi
doi: 10.1007/978-3-031-78011-0_14
external_id:
isi:
- '001545628900014'
intvolume: ' 15364'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/1097
month: '12'
oa: 1
oa_version: Preprint
page: 413-443
publication: 22nd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031780103'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The cost of maintaining keys in dynamic groups with applications to multicast
encryption and group messaging
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15364
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '18755'
abstract:
- lang: eng
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."
acknowledgement: Ehsan Ebrahimi is supported by the Luxembourg National Research Fund
under the Junior CORE project QSP (C22/IS/17272217/QSP/Ebrahimi).
article_processing_charge: No
author:
- first_name: Ehsan
full_name: Ebrahimi, Ehsan
last_name: Ebrahimi
- first_name: Anshu
full_name: Yadav, Anshu
id: dc8f1524-403e-11ee-bf07-9649ad996e21
last_name: Yadav
citation:
ama: 'Ebrahimi E, Yadav A. Strongly secure universal thresholdizer. In: 30th
International Conference on the Theory and Application of Cryptology and Information
Security. Vol 15486. Springer Nature; 2024:207-239. doi:10.1007/978-981-96-0891-1_7'
apa: 'Ebrahimi, E., & Yadav, A. (2024). Strongly secure universal thresholdizer.
In 30th International Conference on the Theory and Application of Cryptology
and Information Security (Vol. 15486, pp. 207–239). Kolkata, India: Springer
Nature. https://doi.org/10.1007/978-981-96-0891-1_7'
chicago: Ebrahimi, Ehsan, and Anshu Yadav. “Strongly Secure Universal Thresholdizer.”
In 30th International Conference on the Theory and Application of Cryptology
and Information Security, 15486:207–39. Springer Nature, 2024. https://doi.org/10.1007/978-981-96-0891-1_7.
ieee: E. Ebrahimi and A. Yadav, “Strongly secure universal thresholdizer,” in 30th
International Conference on the Theory and Application of Cryptology and Information
Security, Kolkata, India, 2024, vol. 15486, 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.'
mla: Ebrahimi, Ehsan, and Anshu Yadav. “Strongly Secure Universal Thresholdizer.”
30th International Conference on the Theory and Application of Cryptology and
Information Security, vol. 15486, Springer Nature, 2024, pp. 207–39, doi:10.1007/978-981-96-0891-1_7.
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.
conference:
end_date: 2024-12-13
location: Kolkata, India
name: 'ASIACRYPT: Conference on the Theory and Application of Cryptology and Information
Security'
start_date: 2024-12-09
date_created: 2025-01-05T23:01:56Z
date_published: 2024-12-12T00:00:00Z
date_updated: 2025-09-09T12:00:12Z
day: '12'
department:
- _id: KrPi
doi: 10.1007/978-981-96-0891-1_7
external_id:
isi:
- '001443889100007'
intvolume: ' 15486'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/2078
month: '12'
oa: 1
oa_version: Preprint
page: 207-239
publication: 30th International Conference on the Theory and Application of Cryptology
and Information Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9789819608904'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Strongly secure universal thresholdizer
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15486
year: '2024'
...
---
OA_place: repository
OA_type: green
_id: '18756'
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."
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.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chris
full_name: Brzuska, Chris
last_name: Brzuska
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
- first_name: Ivy K.Y.
full_name: Woo, Ivy K.Y.
last_name: Woo
citation:
ama: 'Brzuska C, Ünal A, Woo IKY. Evasive LWE assumptions: Definitions, classes,
and counterexamples. In: 30th International Conference on the Theory and Application
of Cryptology and Information Security. Vol 15487. Springer Nature; 2024:418-449.
doi:10.1007/978-981-96-0894-2_14'
apa: 'Brzuska, C., Ünal, A., & Woo, I. K. Y. (2024). Evasive LWE assumptions:
Definitions, classes, and counterexamples. In 30th International Conference
on the Theory and Application of Cryptology and Information Security (Vol.
15487, pp. 418–449). Kolkata, India: Springer Nature. https://doi.org/10.1007/978-981-96-0894-2_14'
chicago: 'Brzuska, Chris, Akin Ünal, and Ivy K.Y. Woo. “Evasive LWE Assumptions:
Definitions, Classes, and Counterexamples.” In 30th International Conference
on the Theory and Application of Cryptology and Information Security, 15487:418–49.
Springer Nature, 2024. https://doi.org/10.1007/978-981-96-0894-2_14.'
ieee: 'C. Brzuska, A. Ünal, and I. K. Y. Woo, “Evasive LWE assumptions: Definitions,
classes, and counterexamples,” in 30th International Conference on the Theory
and Application of Cryptology and Information Security, Kolkata, India, 2024,
vol. 15487, pp. 418–449.'
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.'
mla: 'Brzuska, Chris, et al. “Evasive LWE Assumptions: Definitions, Classes, and Counterexamples.”
30th International Conference on the Theory and Application of Cryptology and
Information Security, vol. 15487, Springer Nature, 2024, pp. 418–49, doi:10.1007/978-981-96-0894-2_14.'
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.
conference:
end_date: 2024-12-13
location: Kolkata, India
name: 'ASIACRYPT: Conference on the Theory and Application of Cryptology and Information
Security'
start_date: 2024-12-09
date_created: 2025-01-05T23:01:56Z
date_published: 2024-12-13T00:00:00Z
date_updated: 2025-09-09T12:00:51Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-981-96-0894-2_14
external_id:
isi:
- '001443890800014'
intvolume: ' 15487'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/2000
month: '12'
oa: 1
oa_version: Preprint
page: 418-449
publication: 30th International Conference on the Theory and Application of Cryptology
and Information Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9789819608935'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Evasive LWE assumptions: Definitions, classes, and counterexamples'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15487
year: '2024'
...