---
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: 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: '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: '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: 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: 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: publisher
OA_type: gold
_id: '18961'
abstract:
- lang: eng
text: "Automated contact tracing (ACT) emerged as a promising measure to curb the
spread of Covid-19. Users enable ACT on their smartphones to automatically record
contacts with other users. If a user tests positive for the disease, they report
their diagnosis to alert their contacts.\r\nDesigning effective ACT protocols
is challenging since they need to be efficient and secure while also ensuring
users' privacy. As ACT protocols necessarily leak some information by design,
defining privacy is difficult. For example, a user cannot deny having met another
user. Ideally, however, the user can plausibly deny everything else, in particular,
when they met. We call this privacy property contact-time deniability.\r\nWhile
some early works discussed contact-time deniability informally, it has received
little attention since then. We investigate deniability from a rigorous, theoretical
point of view and arrive at the following impossibility result:\r\nA decentralized
protocol with unidirectional communication cannot be contact-time deniable and
replay-secure. This holds even if malicious users treat smartphones as black-boxes.\r\n
Unidirectional protocols are usually very efficient and many proposals are unidirectional,
e.g., the widely-deployed Google-Apple Exposure Notifications. So the impossibility
result considerably constrains the design space of efficient, secure, and private
ACT protocols. However, it can also be used as a guide; we discuss several possibilities
to achieve contact-time deniability in practice."
acknowledgement: "We thank Raluca-Georgia Diugan for her initial contributions and
support afterward.\r\nThis research was funded in whole or in part by the Austrian
Science Fund (FWF) 10.55776/F85."
article_processing_charge: No
article_type: original
author:
- 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: 'Günther CU, Pietrzak KZ. Deniability in automated contact tracing: Impossibilities
and possibilities. Proceedings on Privacy Enhancing Technologies. 2024;2024(4):636-648.
doi:10.56553/popets-2024-0134'
apa: 'Günther, C. U., & Pietrzak, K. Z. (2024). Deniability in automated contact
tracing: Impossibilities and possibilities. Proceedings on Privacy Enhancing
Technologies. Bristol, UK/Virtual: Privacy Enhancing Technologies Symposium
Advisory Board. https://doi.org/10.56553/popets-2024-0134'
chicago: 'Günther, Christoph Ullrich, and Krzysztof Z Pietrzak. “Deniability in
Automated Contact Tracing: Impossibilities and Possibilities.” Proceedings
on Privacy Enhancing Technologies. Privacy Enhancing Technologies Symposium
Advisory Board, 2024. https://doi.org/10.56553/popets-2024-0134.'
ieee: 'C. U. Günther and K. Z. Pietrzak, “Deniability in automated contact tracing:
Impossibilities and possibilities,” Proceedings on Privacy Enhancing Technologies,
vol. 2024, no. 4. Privacy Enhancing Technologies Symposium Advisory Board, pp.
636–648, 2024.'
ista: 'Günther CU, Pietrzak KZ. 2024. Deniability in automated contact tracing:
Impossibilities and possibilities. Proceedings on Privacy Enhancing Technologies.
2024(4), 636–648.'
mla: 'Günther, Christoph Ullrich, and Krzysztof Z. Pietrzak. “Deniability in Automated
Contact Tracing: Impossibilities and Possibilities.” Proceedings on Privacy
Enhancing Technologies, vol. 2024, no. 4, Privacy Enhancing Technologies Symposium
Advisory Board, 2024, pp. 636–48, doi:10.56553/popets-2024-0134.'
short: C.U. Günther, K.Z. Pietrzak, Proceedings on Privacy Enhancing Technologies
2024 (2024) 636–648.
conference:
end_date: 2024-07-20
location: Bristol, UK/Virtual
name: 'PETs: Privacy Enhancing Technologies Symposium '
start_date: 2024-07-15
corr_author: '1'
date_created: 2025-01-29T13:39:34Z
date_published: 2024-07-01T00:00:00Z
date_updated: 2025-04-15T08:16:04Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
- _id: GradSch
doi: 10.56553/popets-2024-0134
file:
- access_level: open_access
checksum: 348ed6adcf6ad2f925227bde1758cae6
content_type: application/pdf
creator: dernst
date_created: 2025-01-29T13:44:47Z
date_updated: 2025-01-29T13:44:47Z
file_id: '18962'
file_name: 2024_ProcPrivacyEnhTech_Guenther.pdf
file_size: 611567
relation: main_file
success: 1
file_date_updated: 2025-01-29T13:44:47Z
has_accepted_license: '1'
intvolume: ' 2024'
issue: '4'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 636-648
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: Proceedings on Privacy Enhancing Technologies
publication_identifier:
issn:
- 2299-0984
publication_status: published
publisher: Privacy Enhancing Technologies Symposium Advisory Board
quality_controlled: '1'
status: public
title: 'Deniability in automated contact tracing: Impossibilities and possibilities'
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
volume: 2024
year: '2024'
...
---
_id: '17051'
abstract:
- lang: eng
text: "Memory-hard functions (MHF) are functions whose evaluation provably requires\r\na
lot of memory. While MHFs are an unkeyed primitive, it is natural to consider
the\r\nnotion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling\r\nthe
public parameters one also samples a trapdoor which allows evaluating the\r\nfunction
much cheaper.\r\nBiryukov and Perrin (Asiacrypt’17) were the first to consider
TMHFs and put\r\nforth a candidate TMHF construction called Diodon that is based
on the Scrypt\r\nMHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s
initial hash chain\r\nis replaced by a sequence of squares in a group of unknown
order where the order of\r\nthe group is the trapdoor. For a length n sequence
of squares and a group of order\r\nN, Diodon’s cumulative memory complexity (CMC)
is O(n2log N) without the\r\ntrapdoor and O(n log(n) log(N)2) with knowledge of
it.\r\nWhile Scrypt is proven to be optimally memory-hard in the random oracle\r\nmodel
(Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been\r\nproven
so far. In this work, we fill this gap by rigorously analyzing a specific\r\ninstantiation
of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)\r\nwhich
almost matches the upper bound. Our proof is based Alwen et al.’s lower\r\nbound
on Scrypt’s CMC but requires non-trivial modifications due to the algebraic\r\nstructure
of Diodon. Most importantly, our analysis involves a more elaborate\r\ncompression
argument and a solvability criterion for certain systems of Diophantine\r\nequations."
acknowledgement: We thank the Eurocrypt reviewers for their thorough review and for
pointing out related works. This research was funded in whole or in part by the
Austrian Science Fund (FWF) 10.55776/F85.
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: 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: 'Auerbach B, Günther CU, Pietrzak KZ. Trapdoor memory-hard functions. In: 43rd
Annual International Conference on the Theory and Applications of Cryptographic
Techniques. Vol 14653. Springer Nature; 2024:315-344. doi:10.1007/978-3-031-58734-4_11'
apa: 'Auerbach, B., Günther, C. U., & Pietrzak, K. Z. (2024). Trapdoor memory-hard
functions. In 43rd Annual International Conference on the Theory and Applications
of Cryptographic Techniques (Vol. 14653, pp. 315–344). Zurich, Switzerland:
Springer Nature. https://doi.org/10.1007/978-3-031-58734-4_11'
chicago: Auerbach, Benedikt, Christoph Ullrich Günther, and Krzysztof Z Pietrzak.
“Trapdoor Memory-Hard Functions.” In 43rd Annual International Conference on
the Theory and Applications of Cryptographic Techniques, 14653:315–44. Springer
Nature, 2024. https://doi.org/10.1007/978-3-031-58734-4_11.
ieee: B. Auerbach, C. U. Günther, and K. Z. Pietrzak, “Trapdoor memory-hard functions,”
in 43rd Annual International Conference on the Theory and Applications of Cryptographic
Techniques, Zurich, Switzerland, 2024, vol. 14653, pp. 315–344.
ista: 'Auerbach B, Günther CU, Pietrzak KZ. 2024. Trapdoor memory-hard functions.
43rd Annual International Conference on the Theory and Applications of Cryptographic
Techniques. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS,
vol. 14653, 315–344.'
mla: Auerbach, Benedikt, et al. “Trapdoor Memory-Hard Functions.” 43rd Annual
International Conference on the Theory and Applications of Cryptographic Techniques,
vol. 14653, Springer Nature, 2024, pp. 315–44, doi:10.1007/978-3-031-58734-4_11.
short: B. Auerbach, C.U. Günther, K.Z. Pietrzak, in:, 43rd Annual International
Conference on the Theory and Applications of Cryptographic Techniques, Springer
Nature, 2024, pp. 315–344.
conference:
end_date: 2024-05-30
location: Zurich, Switzerland
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2024-05-26
corr_author: '1'
date_created: 2024-05-26T22:00:58Z
date_published: 2024-05-01T00:00:00Z
date_updated: 2025-09-08T07:35:40Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-031-58734-4_11
external_id:
isi:
- '001274940200011'
intvolume: ' 14653'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2024/312
month: '05'
oa: 1
oa_version: Preprint
page: 315-344
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 43rd Annual International Conference on the Theory and Applications of
Cryptographic Techniques
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031587337'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trapdoor memory-hard functions
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14653
year: '2024'
...
---
_id: '17328'
abstract:
- lang: eng
text: "We study selfish mining attacks in longest-chain blockchains like Bitcoin,
but where the proof of work is replaced with efficient proof systems - like proofs
of stake or proofs of space - and consider the problem of computing an optimal
selfish mining attack which maximizes expected relative revenue of the adversary,
thus minimizing the chain quality. To this end, we propose a novel selfish mining
attack that aims to maximize this objective and formally model the attack as a
Markov decision process (MDP). We then present a formal analysis procedure which
computes an ϵ-tight lower bound on the optimal expected relative revenue in the
MDP and a strategy that achieves this ϵ-tight lower bound, where ϵ > 0 may be
any specified precision. Our analysis is fully automated and provides formal guarantees
on the correctness. We evaluate our selfish mining attack and observe that it
achieves superior expected relative revenue compared to two considered baselines.\r\nIn
concurrent work [Sarenche FC'24] does an automated analysis on selfish mining
in predictable longest-chain blockchains based on efficient proof systems. Predictable
means the randomness for the challenges is fixed for many blocks (as used e.g.,
in Ouroboros), while we consider unpredictable (Bitcoin-like) chains where the
challenge is derived from the previous block."
acknowledgement: "This work was supported in part by the ERC-2020-CoG 863818 (FoRM-SMArt)
grant and the MOE-T2EP20122-0014 (Data-Driven Distributed Algorithms) grant.\r\n"
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Amirali
full_name: Ebrahimzadeh, Amirali
last_name: Ebrahimzadeh
- first_name: Mehrdad
full_name: Karrabi, Mehrdad
id: 67638922-f394-11eb-9cf6-f20423e08757
last_name: Karrabi
- 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: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D. Fully
automated selfish mining analysis in efficient proof systems blockchains. In:
Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed
Computing. Association for Computing Machinery; 2024:268-278. doi:10.1145/3662158.3662769'
apa: 'Chatterjee, K., Ebrahimzadeh, A., Karrabi, M., Pietrzak, K. Z., Yeo, M. X.,
& Zikelic, D. (2024). Fully automated selfish mining analysis in efficient
proof systems blockchains. In Proceedings of the 43rd Annual ACM Symposium
on Principles of Distributed Computing (pp. 268–278). Nantes, France: Association
for Computing Machinery. https://doi.org/10.1145/3662158.3662769'
chicago: Chatterjee, Krishnendu, Amirali Ebrahimzadeh, Mehrdad Karrabi, Krzysztof
Z Pietrzak, Michelle X Yeo, and Dorde Zikelic. “Fully Automated Selfish Mining
Analysis in Efficient Proof Systems Blockchains.” In Proceedings of the 43rd
Annual ACM Symposium on Principles of Distributed Computing, 268–78. Association
for Computing Machinery, 2024. https://doi.org/10.1145/3662158.3662769.
ieee: K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K. Z. Pietrzak, M. X. Yeo, and
D. Zikelic, “Fully automated selfish mining analysis in efficient proof systems
blockchains,” in Proceedings of the 43rd Annual ACM Symposium on Principles
of Distributed Computing, Nantes, France, 2024, pp. 268–278.
ista: 'Chatterjee K, Ebrahimzadeh A, Karrabi M, Pietrzak KZ, Yeo MX, Zikelic D.
2024. Fully automated selfish mining analysis in efficient proof systems blockchains. Proceedings
of the 43rd Annual ACM Symposium on Principles of Distributed Computing. PODC:
Symposium on Principles of Distributed Computing, 268–278.'
mla: Chatterjee, Krishnendu, et al. “Fully Automated Selfish Mining Analysis in
Efficient Proof Systems Blockchains.” Proceedings of the 43rd Annual ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery,
2024, pp. 268–78, doi:10.1145/3662158.3662769.
short: K. Chatterjee, A. Ebrahimzadeh, M. Karrabi, K.Z. Pietrzak, M.X. Yeo, D. Zikelic,
in:, Proceedings of the 43rd Annual ACM Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2024, pp. 268–278.
conference:
end_date: 2024-06-21
location: Nantes, France
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2024-06-17
corr_author: '1'
date_created: 2024-07-28T22:01:10Z
date_published: 2024-06-17T00:00:00Z
date_updated: 2025-04-14T07:52:47Z
day: '17'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1145/3662158.3662769
ec_funded: 1
external_id:
arxiv:
- '2405.04420'
file:
- access_level: open_access
checksum: 6122bd97b42751ff81c452a19970f67d
content_type: application/pdf
creator: dernst
date_created: 2024-07-29T07:18:12Z
date_updated: 2024-07-29T07:18:12Z
file_id: '17334'
file_name: 2024_ACM_Chatterjee.pdf
file_size: 832034
relation: main_file
success: 1
file_date_updated: 2024-07-29T07:18:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: 268-278
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 43rd Annual ACM Symposium on Principles of Distributed
Computing'
publication_identifier:
isbn:
- '9798400706684'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Fully automated selfish mining analysis in efficient proof systems blockchains
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: '2024'
...
---
_id: '18086'
abstract:
- lang: eng
text: "Abstract. Continuous group key agreement (CGKA) allows a group of\r\nusers
to maintain a continuously updated shared key in an asynchronous\r\nsetting where
parties only come online sporadically and their messages\r\nare relayed by an
untrusted server. CGKA captures the basic primitive\r\nunderlying group messaging
schemes.\r\nCurrent solutions including TreeKEM (“Messaging Layer Security”\r\n(MLS)
IETF RFC 9420) cannot handle concurrent requests while retaining low communication
complexity. The exception being CoCoA, which\r\nis concurrent while having extremely
low communication complexity (in\r\ngroups of size n and for m concurrent updates
the communication per\r\nuser is log(n), i.e., independent of m). The main downside
of CoCoA\r\nis that in groups of size n, users might have to do up to log(n) update\r\nrequests
to the server to ensure their (potentially corrupted) key material has been refreshed.\r\nIn
this work we present a “fast healing” concurrent CGKA protocol,\r\nnamed DeCAF,
where users will heal after at most log(t) requests, with\r\nt being the number
of corrupted users. While also suitable for the standard central-server setting,
our protocol is particularly interesting for\r\nrealizing decentralized group
messaging, where protocol messages (add,\r\nremove, update) are being posted on
some append-only data structure\r\nrather than sent to a server. In this setting,
concurrency is crucial once\r\nthe rate of requests exceeds, say, the rate at
which new blocks are added\r\nto a blockchain.\r\nIn the central-server setting,
CoCoA (the only alternative with concurrency, sub-linear communication and basic
post-compromise security)\r\nenjoys much lower download communication. However,
in the decentralized setting – where there is no server which can craft specific
messages\r\nfor different users to reduce their download communication – our protocol\r\nsignificantly
outperforms CoCoA. DeCAF heals in fewer epochs (log(t)\r\nvs. log(n)) while incurring
a similar per epoch per user communication\r\ncost."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- 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: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- 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: 'Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ.
DeCAF: Decentralizable CGKA with fast healing. In: Galdi C, Phan DH, eds. Security
and Cryptography for Networks: 14th International Conference. Vol 14974. Cham:
Springer Nature; 2024:294–313. doi:10.1007/978-3-031-71073-5_14'
apa: 'Alwen, J. F., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G.,
& Pietrzak, K. Z. (2024). DeCAF: Decentralizable CGKA with fast healing. In
C. Galdi & D. H. Phan (Eds.), Security and Cryptography for Networks: 14th
International Conference (Vol. 14974, pp. 294–313). Cham: Springer Nature.
https://doi.org/10.1007/978-3-031-71073-5_14'
chicago: 'Alwen, Joel F, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo
Pascual Perez, and Krzysztof Z Pietrzak. “DeCAF: Decentralizable CGKA with Fast
Healing.” In Security and Cryptography for Networks: 14th International Conference,
edited by Clemente Galdi and Duong Hieu Phan, 14974:294–313. Cham: Springer Nature,
2024. https://doi.org/10.1007/978-3-031-71073-5_14.'
ieee: 'J. F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, and
K. Z. Pietrzak, “DeCAF: Decentralizable CGKA with fast healing,” in Security
and Cryptography for Networks: 14th International Conference, Amalfi, Italy,
2024, vol. 14974, pp. 294–313.'
ista: 'Alwen JF, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ.
2024. DeCAF: Decentralizable CGKA with fast healing. Security and Cryptography
for Networks: 14th International Conference. SCN: Security and Cryptography for
Networks, LNCS, vol. 14974, 294–313.'
mla: 'Alwen, Joel F., et al. “DeCAF: Decentralizable CGKA with Fast Healing.” Security
and Cryptography for Networks: 14th International Conference, edited by Clemente
Galdi and Duong Hieu Phan, vol. 14974, Springer Nature, 2024, pp. 294–313, doi:10.1007/978-3-031-71073-5_14.'
short: 'J.F. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z.
Pietrzak, in:, C. Galdi, D.H. Phan (Eds.), Security and Cryptography for Networks:
14th International Conference, Springer Nature, Cham, 2024, pp. 294–313.'
conference:
end_date: 2024-09-13
location: Amalfi, Italy
name: 'SCN: Security and Cryptography for Networks'
start_date: 2024-09-11
corr_author: '1'
date_created: 2024-09-18T11:35:14Z
date_published: 2024-09-10T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '10'
department:
- _id: GradSch
- _id: KrPi
doi: 10.1007/978-3-031-71073-5_14
editor:
- first_name: Clemente
full_name: Galdi, Clemente
last_name: Galdi
- first_name: Duong Hieu
full_name: Phan, Duong Hieu
last_name: Phan
external_id:
isi:
- '001330408000014'
intvolume: ' 14974'
isi: 1
language:
- iso: eng
month: '09'
oa_version: None
page: 294–313
place: Cham
publication: 'Security and Cryptography for Networks: 14th International Conference'
publication_identifier:
eisbn:
- '9783031710735'
eissn:
- 1611-3349
isbn:
- '9783031710728'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
status: public
title: 'DeCAF: Decentralizable CGKA with fast healing'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14974
year: '2024'
...
---
_id: '14428'
abstract:
- lang: eng
text: "Suppose we have two hash functions h1 and h2, but we trust the security of
only one of them. To mitigate this worry, we wish to build a hash combiner Ch1,h2
which is secure so long as one of the underlying hash functions is. This question
has been well-studied in the regime of collision resistance. In this case, concatenating
the two hash function outputs clearly works. Unfortunately, a long series of works
(Boneh and Boyen, CRYPTO’06; Pietrzak, Eurocrypt’07; Pietrzak, CRYPTO’08) showed
no (noticeably) shorter combiner for collision resistance is possible.\r\nIn this
work, we revisit this pessimistic state of affairs, motivated by the observation
that collision-resistance is insufficient for many interesting applications of
cryptographic hash functions anyway. We argue the right formulation of the “hash
combiner” is to build what we call random oracle (RO) combiners, utilizing stronger
assumptions for stronger constructions.\r\nIndeed, we circumvent the previous
lower bounds for collision resistance by constructing a simple length-preserving
RO combiner C˜h1,h2Z1,Z2(M)=h1(M,Z1)⊕h2(M,Z2),where Z1,Z2\r\n are random salts
of appropriate length. We show that this extra randomness is necessary for RO
combiners, and indeed our construction is somewhat tight with this lower bound.\r\nOn
the negative side, we show that one cannot generically apply the composition theorem
to further replace “monolithic” hash functions h1 and h2 by some simpler indifferentiable
construction (such as the Merkle-Damgård transformation) from smaller components,
such as fixed-length compression functions. Finally, despite this issue, we directly
prove collision resistance of the Merkle-Damgård variant of our combiner, where
h1 and h2 are replaced by iterative Merkle-Damgård hashes applied to a fixed-length
compression function. Thus, we can still subvert the concatenation barrier for
collision-resistance combiners while utilizing practically small fixed-length
components underneath."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Yevgeniy
full_name: Dodis, Yevgeniy
last_name: Dodis
- first_name: Niels
full_name: Ferguson, Niels
last_name: Ferguson
- first_name: Eli
full_name: Goldin, Eli
last_name: Goldin
- first_name: Peter
full_name: Hall, Peter
last_name: Hall
- 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: 'Dodis Y, Ferguson N, Goldin E, Hall P, Pietrzak KZ. Random oracle combiners:
Breaking the concatenation barrier for collision-resistance. In: 43rd Annual
International Cryptology Conference. Vol 14082. Springer Nature; 2023:514-546.
doi:10.1007/978-3-031-38545-2_17'
apa: 'Dodis, Y., Ferguson, N., Goldin, E., Hall, P., & Pietrzak, K. Z. (2023).
Random oracle combiners: Breaking the concatenation barrier for collision-resistance.
In 43rd Annual International Cryptology Conference (Vol. 14082, pp. 514–546).
Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-031-38545-2_17'
chicago: 'Dodis, Yevgeniy, Niels Ferguson, Eli Goldin, Peter Hall, and Krzysztof
Z Pietrzak. “Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance.”
In 43rd Annual International Cryptology Conference, 14082:514–46. Springer
Nature, 2023. https://doi.org/10.1007/978-3-031-38545-2_17.'
ieee: 'Y. Dodis, N. Ferguson, E. Goldin, P. Hall, and K. Z. Pietrzak, “Random oracle
combiners: Breaking the concatenation barrier for collision-resistance,” in 43rd
Annual International Cryptology Conference, Santa Barbara, CA, United States,
2023, vol. 14082, pp. 514–546.'
ista: 'Dodis Y, Ferguson N, Goldin E, Hall P, Pietrzak KZ. 2023. Random oracle combiners:
Breaking the concatenation barrier for collision-resistance. 43rd Annual International
Cryptology Conference. CRYPTO: Advances in Cryptology, LNCS, vol. 14082, 514–546.'
mla: 'Dodis, Yevgeniy, et al. “Random Oracle Combiners: Breaking the Concatenation
Barrier for Collision-Resistance.” 43rd Annual International Cryptology Conference,
vol. 14082, Springer Nature, 2023, pp. 514–46, doi:10.1007/978-3-031-38545-2_17.'
short: Y. Dodis, N. Ferguson, E. Goldin, P. Hall, K.Z. Pietrzak, in:, 43rd Annual
International Cryptology Conference, Springer Nature, 2023, pp. 514–546.
conference:
end_date: 2023-08-24
location: Santa Barbara, CA, United States
name: 'CRYPTO: Advances in Cryptology'
start_date: 2023-08-20
corr_author: '1'
date_created: 2023-10-15T22:01:11Z
date_published: 2023-08-09T00:00:00Z
date_updated: 2025-09-09T13:06:18Z
day: '09'
department:
- _id: KrPi
doi: 10.1007/978-3-031-38545-2_17
external_id:
isi:
- '001314616100017'
intvolume: ' 14082'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1041
month: '08'
oa: 1
oa_version: Preprint
page: 514-546
publication: 43rd Annual International Cryptology Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031385445'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Random oracle combiners: Breaking the concatenation barrier for collision-resistance'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14082
year: '2023'
...
---
_id: '14691'
abstract:
- lang: eng
text: "Continuous Group-Key Agreement (CGKA) allows a group of users to maintain
a shared key. It is the fundamental cryptographic primitive underlying group messaging
schemes and related protocols, most notably TreeKEM, the underlying key agreement
protocol of the Messaging Layer Security (MLS) protocol, a standard for group
messaging by the IETF. CKGA works in an asynchronous setting where parties only
occasionally must come online, and their messages are relayed by an untrusted
server. The most expensive operation provided by CKGA is that which allows for
a user to refresh their key material in order to achieve forward secrecy (old
messages are secure when a user is compromised) and post-compromise security (users
can heal from compromise). One caveat of early CGKA protocols is that these update
operations had to be performed sequentially, with any user wanting to update their
key material having had to receive and process all previous updates. Late versions
of TreeKEM do allow for concurrent updates at the cost of a communication overhead
per update message that is linear in the number of updating parties. This was
shown to be indeed necessary when achieving PCS in just two rounds of communication
by [Bienstock et al. TCC’20].\r\nThe recently proposed protocol CoCoA [Alwen et
al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements
are relaxed, and only a logarithmic number of rounds is required. The natural
question, thus, is whether CoCoA is optimal in this setting.\r\nIn this work we
answer this question, providing a lower bound on the cost (concretely, the amount
of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary
k number of rounds, that shows that CoCoA is very close to optimal. Additionally,
we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification
of it, with a reduced communication cost for certain k.\r\nWe prove our bound
in a combinatorial setting where the state of the protocol progresses in rounds,
and the state of the protocol in each round is captured by a set system, each
set specifying a set of users who share a secret key. We show this combinatorial
model is equivalent to a symbolic model capturing building blocks including PRFs
and public-key encryption, related to the one used by Bienstock et al.\r\nOur
lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of
updates per user the protocol requires to heal. This generalizes the n2 bound
for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1)
efficiency we get for the variants of the CoCoA protocol also introduced in this
paper."
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: 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: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. On the cost of post-compromise
security in concurrent Continuous Group-Key Agreement. In: 21st International
Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:271-300.
doi:10.1007/978-3-031-48621-0_10'
apa: 'Auerbach, B., Cueto Noval, M., Pascual Perez, G., & Pietrzak, K. Z. (2023).
On the cost of post-compromise security in concurrent Continuous Group-Key Agreement.
In 21st International Conference on Theory of Cryptography (Vol. 14371,
pp. 271–300). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_10'
chicago: Auerbach, Benedikt, Miguel Cueto Noval, Guillermo Pascual Perez, and Krzysztof
Z Pietrzak. “On the Cost of Post-Compromise Security in Concurrent Continuous
Group-Key Agreement.” In 21st International Conference on Theory of Cryptography,
14371:271–300. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_10.
ieee: B. Auerbach, M. Cueto Noval, G. Pascual Perez, and K. Z. Pietrzak, “On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement,” in
21st International Conference on Theory of Cryptography, Taipei, Taiwan,
2023, vol. 14371, pp. 271–300.
ista: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement. 21st
International Conference on Theory of Cryptography. TCC: Theory of Cryptography,
LNCS, vol. 14371, 271–300.'
mla: Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent
Continuous Group-Key Agreement.” 21st International Conference on Theory of
Cryptography, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:10.1007/978-3-031-48621-0_10.
short: B. Auerbach, M. Cueto Noval, G. Pascual Perez, K.Z. Pietrzak, in:, 21st International
Conference on Theory of Cryptography, Springer Nature, 2023, pp. 271–300.
conference:
end_date: 2023-12-02
location: Taipei, Taiwan
name: 'TCC: Theory of Cryptography'
start_date: 2023-11-29
corr_author: '1'
date_created: 2023-12-17T23:00:53Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2025-09-09T13:42:16Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48621-0_10
external_id:
isi:
- '001160724400010'
intvolume: ' 14371'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1123
month: '11'
oa: 1
oa_version: Preprint
page: 271-300
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486203'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the cost of post-compromise security in concurrent Continuous Group-Key
Agreement
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14371
year: '2023'
...
---
_id: '13143'
abstract:
- lang: eng
text: "GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching
giant prime numbers, usually of special forms like Mersenne and Proth primes.
The numbers in the current search-space are millions of digits large and the participating
volunteers need to run resource-consuming primality tests. Once a candidate prime
N has been found, the only way for another party to independently verify the primality
of N used to be by repeating the expensive primality test. To avoid the need for
second recomputation of each primality test, these projects have recently adopted
certifying mechanisms that enable efficient verification of performed tests. However,
the mechanisms presently in place only detect benign errors and there is no guarantee
against adversarial behavior: a malicious volunteer can mislead the project to
reject a giant prime as being non-prime.\r\nIn this paper, we propose a practical,
cryptographically-sound mechanism for certifying the non-primality of Proth numbers.
That is, a volunteer can – parallel to running the primality test for N – generate
an efficiently verifiable proof at a little extra cost certifying that N is not
prime. The interactive protocol has statistical soundness and can be made non-interactive
using the Fiat-Shamir heuristic.\r\nOur approach is based on a cryptographic primitive
called Proof of Exponentiation (PoE) which, for a group G, certifies that a tuple
(x,y,T)∈G2×N satisfies x2T=y (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol.
2020). In particular, we show how to adapt Pietrzak’s PoE at a moderate additional
cost to make it a cryptographically-sound certificate of non-primality."
acknowledgement: 'We are grateful to Pavel Atnashev for clarifying via e-mail several
aspects of the primality tests implementated in the PrimeGrid project. Pavel Hubáček
is supported by the Czech Academy of Sciences (RVO 67985840), the Grant Agency of
the Czech Republic under the grant agreement no. 19-27871X, and by the Charles University
project UNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral
Fellowship, ISF grants 484/18 and 1789/19, and ERC StG project SPP: Secrecy Preserving
Proofs.'
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: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- 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, Hubáček P, Kamath C, Pietrzak KZ. Certifying giant nonprimes.
In: Public-Key Cryptography - PKC 2023. Vol 13940. Springer Nature; 2023:530-553.
doi:10.1007/978-3-031-31368-4_19'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., & Pietrzak, K. Z. (2023). Certifying
giant nonprimes. In Public-Key Cryptography - PKC 2023 (Vol. 13940, pp.
530–553). Atlanta, GA, United States: Springer Nature. https://doi.org/10.1007/978-3-031-31368-4_19'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Krzysztof Z Pietrzak.
“Certifying Giant Nonprimes.” In Public-Key Cryptography - PKC 2023, 13940:530–53.
Springer Nature, 2023. https://doi.org/10.1007/978-3-031-31368-4_19.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, and K. Z. Pietrzak, “Certifying giant
nonprimes,” in Public-Key Cryptography - PKC 2023, Atlanta, GA, United
States, 2023, vol. 13940, pp. 530–553.
ista: 'Hoffmann C, Hubáček P, Kamath C, Pietrzak KZ. 2023. Certifying giant nonprimes.
Public-Key Cryptography - PKC 2023. PKC: Public-Key Cryptography, LNCS, vol. 13940,
530–553.'
mla: Hoffmann, Charlotte, et al. “Certifying Giant Nonprimes.” Public-Key Cryptography
- PKC 2023, vol. 13940, Springer Nature, 2023, pp. 530–53, doi:10.1007/978-3-031-31368-4_19.
short: C. Hoffmann, P. Hubáček, C. Kamath, K.Z. Pietrzak, in:, Public-Key Cryptography
- PKC 2023, Springer Nature, 2023, pp. 530–553.
conference:
end_date: 2023-05-10
location: Atlanta, GA, United States
name: 'PKC: Public-Key Cryptography'
start_date: 2023-05-07
corr_author: '1'
date_created: 2023-06-18T22:00:47Z
date_published: 2023-05-02T00:00:00Z
date_updated: 2026-04-07T12:34:30Z
day: '02'
department:
- _id: KrPi
doi: 10.1007/978-3-031-31368-4_19
external_id:
isi:
- '001276519300019'
intvolume: ' 13940'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/238
month: '05'
oa: 1
oa_version: Submitted Version
page: 530-553
publication: Public-Key Cryptography - PKC 2023
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031313677'
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: Certifying giant nonprimes
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13940
year: '2023'
...
---
_id: '12167'
abstract:
- lang: eng
text: "Payment channels effectively move the transaction load off-chain thereby
successfully addressing the inherent scalability problem most cryptocurrencies
face. A major drawback of payment channels is the need to “top up” funds on-chain
when a channel is depleted. Rebalancing was proposed to alleviate this issue,
where parties with depleting channels move their funds along a cycle to replenish
their channels off-chain. Protocols for rebalancing so far either introduce local
solutions or compromise privacy.\r\nIn this work, we present an opt-in rebalancing
protocol that is both private and globally optimal, meaning our protocol maximizes
the total amount of rebalanced funds. We study rebalancing from the framework
of linear programming. To obtain full privacy guarantees, we leverage multi-party
computation in solving the linear program, which is executed by selected participants
to maintain efficiency. Finally, we efficiently decompose the rebalancing solution
into incentive-compatible cycles which conserve user balances when executed atomically."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Georgia
full_name: Avarikioti, Georgia
id: c20482a0-3b89-11eb-9862-88cf6404b88c
last_name: Avarikioti
- 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: Iosif
full_name: Salem, Iosif
last_name: Salem
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Samarth
full_name: Tiwari, Samarth
last_name: Tiwari
- 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 G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. Hide &
Seek: Privacy-preserving rebalancing on payment channel networks. In: Financial
Cryptography and Data Security. Vol 13411. Springer Nature; 2022:358-373.
doi:10.1007/978-3-031-18283-9_17'
apa: 'Avarikioti, G., Pietrzak, K. Z., Salem, I., Schmid, S., Tiwari, S., &
Yeo, M. X. (2022). Hide & Seek: Privacy-preserving rebalancing on payment
channel networks. In Financial Cryptography and Data Security (Vol. 13411,
pp. 358–373). Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_17'
chicago: 'Avarikioti, Georgia, Krzysztof Z Pietrzak, Iosif Salem, Stefan Schmid,
Samarth Tiwari, and Michelle X Yeo. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” In Financial Cryptography and Data Security,
13411:358–73. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_17.'
ieee: 'G. Avarikioti, K. Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. X.
Yeo, “Hide & Seek: Privacy-preserving rebalancing on payment channel networks,”
in Financial Cryptography and Data Security, Grenada, 2022, vol. 13411,
pp. 358–373.'
ista: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. 2022. Hide
& Seek: Privacy-preserving rebalancing on payment channel networks. Financial
Cryptography and Data Security. FC: Financial Cryptography and Data Security,
LNCS, vol. 13411, 358–373.'
mla: 'Avarikioti, Georgia, et al. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” Financial Cryptography and Data Security,
vol. 13411, Springer Nature, 2022, pp. 358–73, doi:10.1007/978-3-031-18283-9_17.'
short: G. Avarikioti, K.Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, M.X. Yeo, in:,
Financial Cryptography and Data Security, Springer Nature, 2022, pp. 358–373.
conference:
end_date: 2022-05-06
location: Grenada
name: 'FC: Financial Cryptography and Data Security'
start_date: 2022-05-02
date_created: 2023-01-12T12:10:38Z
date_published: 2022-10-22T00:00:00Z
date_updated: 2025-09-10T09:48:15Z
day: '22'
department:
- _id: KrPi
doi: 10.1007/978-3-031-18283-9_17
external_id:
arxiv:
- '2110.08848'
isi:
- '001423640200017'
intvolume: ' 13411'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2110.08848
month: '10'
oa: 1
oa_version: Preprint
page: 358-373
publication: Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031182839'
eissn:
- 1611-3349
isbn:
- '9783031182822'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Hide & Seek: Privacy-preserving rebalancing on payment channel networks'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13411
year: '2022'
...
---
_id: '17060'
abstract:
- lang: eng
text: "Payment channel networks (PCNs) are one of the most prominent solutions to
the limited transaction throughput of blockchains. Nevertheless, PCNs suffer themselves
from a throughput limitation due to the capital constraints of their channels.
A similar dependence on high capital is also found in inter-bank payment settlements,
where the so-called netting technique is used to mitigate liquidity demands.\r\nIn
this work, we alleviate this limitation by introducing the notion of transaction
aggregation: instead of executing transactions sequentially through a PCN, we
enable senders to aggregate multiple transactions and execute them simultaneously
to benefit from several amounts that may \"cancel out\". Two direct advantages
of our proposal is the decrease in intermediary fees paid by senders as well as
the obfuscation of the transaction data from the intermediaries.\r\nWe formulate
the transaction aggregation as a computational problem, a generalization of the
Bank Clearing Problem. We present a generic framework for the transaction aggregation
execution, and thereafter we propose Wiser as an implementation of this framework
in a specific hub-based setting. To overcome the NP-hardness of the transaction
aggregation problem, in Wiser we propose a fixed-parameter linear algorithm for
a special case of transaction aggregation as well as the Bank Clearing Problem.
Wiser can also be seen as a modern variant of the Hawala money transfer system,
as well as a decentralized implementation of the overseas remittance service of
Wise."
acknowledgement: "This work was supported partially by ERC Starting Grant QIP–805241,
by the Vienna business agency (Wirtschaftsagentur) through the Vienna Cybersecurity
and Privacy Research Center\r\n(ViSP) and by the Austrian Science Fund (FWF) project
I 4800-N (ADVISE).\r\nThe first author would like to thank Daniel Dadush for suggesting
the use of discrepancy techniques to solve the transaction aggregation problem."
article_processing_charge: Yes (in subscription journal)
arxiv: 1
author:
- first_name: Samarth
full_name: Tiwari, Samarth
last_name: Tiwari
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Zeta
full_name: Avarikioti, Zeta
last_name: Avarikioti
- first_name: Iosif
full_name: Salem, Iosif
last_name: Salem
- 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: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Tiwari S, Yeo MX, Avarikioti Z, Salem I, Pietrzak KZ, Schmid S. Wiser: Increasing
throughput in payment channel networks with transaction aggregation. In: Proceedings
of the 4th ACM Conference on Advances in Financial Technologies. Association
for Computing Machinery; 2022:217-231. doi:10.1145/3558535.3559775'
apa: 'Tiwari, S., Yeo, M. X., Avarikioti, Z., Salem, I., Pietrzak, K. Z., &
Schmid, S. (2022). Wiser: Increasing throughput in payment channel networks with
transaction aggregation. In Proceedings of the 4th ACM Conference on Advances
in Financial Technologies (pp. 217–231). Cambridge, MA, United States: Association
for Computing Machinery. https://doi.org/10.1145/3558535.3559775'
chicago: 'Tiwari, Samarth, Michelle X Yeo, Zeta Avarikioti, Iosif Salem, Krzysztof
Z Pietrzak, and Stefan Schmid. “Wiser: Increasing Throughput in Payment Channel
Networks with Transaction Aggregation.” In Proceedings of the 4th ACM Conference
on Advances in Financial Technologies, 217–31. Association for Computing Machinery,
2022. https://doi.org/10.1145/3558535.3559775.'
ieee: 'S. Tiwari, M. X. Yeo, Z. Avarikioti, I. Salem, K. Z. Pietrzak, and S. Schmid,
“Wiser: Increasing throughput in payment channel networks with transaction aggregation,”
in Proceedings of the 4th ACM Conference on Advances in Financial Technologies,
Cambridge, MA, United States, 2022, pp. 217–231.'
ista: 'Tiwari S, Yeo MX, Avarikioti Z, Salem I, Pietrzak KZ, Schmid S. 2022. Wiser:
Increasing throughput in payment channel networks with transaction aggregation.
Proceedings of the 4th ACM Conference on Advances in Financial Technologies. AFT:
Conference on Advances in Financial Technologies, 217–231.'
mla: 'Tiwari, Samarth, et al. “Wiser: Increasing Throughput in Payment Channel Networks
with Transaction Aggregation.” Proceedings of the 4th ACM Conference on Advances
in Financial Technologies, Association for Computing Machinery, 2022, pp.
217–31, doi:10.1145/3558535.3559775.'
short: S. Tiwari, M.X. Yeo, Z. Avarikioti, I. Salem, K.Z. Pietrzak, S. Schmid, in:,
Proceedings of the 4th ACM Conference on Advances in Financial Technologies, Association
for Computing Machinery, 2022, pp. 217–231.
conference:
end_date: 2022-09-21
location: Cambridge, MA, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2022-09-19
date_created: 2024-05-28T13:58:35Z
date_published: 2022-09-19T00:00:00Z
date_updated: 2025-09-10T09:57:48Z
day: '19'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1145/3558535.3559775
external_id:
arxiv:
- '2205.11597'
isi:
- '001041852800015'
file:
- access_level: open_access
checksum: 54a7d405f8e57dba24728599ca63818c
content_type: application/pdf
creator: dernst
date_created: 2024-08-19T06:45:21Z
date_updated: 2024-08-19T06:45:21Z
file_id: '17439'
file_name: 2022_AFT_Tiwari.pdf
file_size: 574728
relation: main_file
success: 1
file_date_updated: 2024-08-19T06:45:21Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: 217-231
publication: Proceedings of the 4th ACM Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9781450398619'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Wiser: Increasing throughput in payment channel networks with transaction
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: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2022'
...
---
_id: '12176'
abstract:
- lang: eng
text: "A proof of exponentiation (PoE) in a group G of unknown order allows a prover
to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive
has recently found exciting applications in the constructions of verifiable delay
functions and succinct arguments of knowledge. The most practical PoEs only achieve
soundness either under computational assumptions, i.e., they are arguments (Wesolowski,
Journal of Cryptology 2020), or in groups that come with the promise of not having
any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in
general groups of unknown order is due to Block et al. (CRYPTO 2021), and can
be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits
of security, say λ=80, the number of repetitions required (and thus the blow-up
in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound
PoE for the case where the exponent q is the product of all primes up to some
bound B. We show that, in this case, it suffices to run only λ/log(B) parallel
instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to
Block et al. by an order of magnitude. Furthermore, we show that in the known
applications where PoEs are used as a building block such structured exponents
are viable. Finally, we also discuss batching of our PoE, showing that many proofs
(for the same G and q but different x and T) can be batched by adding only a single
element to the proof per additional statement."
acknowledgement: "We would like to thank the authors of [BHR+21] for clarifying several
questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the
Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and
by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by
Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19.
Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part
of this work at Institute of Science and Technology Austria."
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: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- first_name: Karen
full_name: Klein, Karen
last_name: Klein
- 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, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound
proofs of exponentiation in any group. In: Advances in Cryptology – CRYPTO
2022. Vol 13508. Springer Nature; 2022:370-399. doi:10.1007/978-3-031-15979-4_13'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., & Pietrzak, K. Z. (2022).
Practical statistically-sound proofs of exponentiation in any group. In Advances
in Cryptology – CRYPTO 2022 (Vol. 13508, pp. 370–399). Santa Barbara, CA,
United States: Springer Nature. https://doi.org/10.1007/978-3-031-15979-4_13'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof
Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.”
In Advances in Cryptology – CRYPTO 2022, 13508:370–99. Springer Nature,
2022. https://doi.org/10.1007/978-3-031-15979-4_13.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical
statistically-sound proofs of exponentiation in any group,” in Advances in
Cryptology – CRYPTO 2022, Santa Barbara, CA, United States, 2022, vol. 13508,
pp. 370–399.
ista: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound
proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYPTO:
International Cryptology Conference, LNCS, vol. 13508, 370–399.'
mla: Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation
in Any Group.” Advances in Cryptology – CRYPTO 2022, vol. 13508, Springer
Nature, 2022, pp. 370–99, doi:10.1007/978-3-031-15979-4_13.
short: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances
in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.
conference:
end_date: 2022-08-18
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2022-08-15
corr_author: '1'
date_created: 2023-01-12T12:12:07Z
date_published: 2022-10-13T00:00:00Z
date_updated: 2026-04-07T12:34:30Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-3-031-15979-4_13
external_id:
isi:
- '000886792700013'
intvolume: ' 13508'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1021
month: '10'
oa: 1
oa_version: Preprint
page: 370-399
publication: Advances in Cryptology – CRYPTO 2022
publication_identifier:
eisbn:
- '9783031159794'
eissn:
- 1611-3349
isbn:
- '9783031159787'
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: Practical statistically-sound proofs of exponentiation in any group
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13508
year: '2022'
...
---
_id: '11476'
abstract:
- lang: eng
text: "Messaging platforms like Signal are widely deployed and provide strong security
in an asynchronous setting. It is a challenging problem to construct a protocol
with similar security guarantees that can efficiently scale to large groups. A
major bottleneck are the frequent key rotations users need to perform to achieve
post compromise forward security.\r\n\r\nIn current proposals – most notably in
TreeKEM (which is part of the IETF’s Messaging Layer Security (MLS) protocol draft)
– for users in a group of size n to rotate their keys, they must each craft a
message of size log(n) to be broadcast to the group using an (untrusted) delivery
server.\r\n\r\nIn larger groups, having users sequentially rotate their keys requires
too much bandwidth (or takes too long), so variants allowing any T≤n users to
simultaneously rotate their keys in just 2 communication rounds have been suggested
(e.g. “Propose and Commit” by MLS). Unfortunately, 2-round concurrent updates
are either damaging or expensive (or both); i.e. they either result in future
operations being more costly (e.g. via “blanking” or “tainting”) or are costly
themselves requiring Ω(T) communication for each user [Bienstock et al., TCC’20].\r\n\r\nIn
this paper we propose CoCoA; a new scheme that allows for T concurrent updates
that are neither damaging nor costly. That is, they add no cost to future operations
yet they only require Ω(log2(n)) communication per user. To circumvent the [Bienstock
et al.] lower bound, CoCoA increases the number of rounds needed to complete all
updates from 2 up to (at most) log(n); though typically fewer rounds are needed.\r\n\r\nThe
key insight of our protocol is the following: in the (non-concurrent version of)
TreeKEM, a delivery server which gets T concurrent update requests will approve
one and reject the remaining T−1. In contrast, our server attempts to apply all
of them. If more than one user requests to rotate the same key during a round,
the server arbitrarily picks a winner. Surprisingly, we prove that regardless
of how the server chooses the winners, all previously compromised users will recover
after at most log(n) such update rounds.\r\n\r\nTo keep the communication complexity
low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly
forwards packets, but instead actively computes individualized packets tailored
to each user. As the server is untrusted, this change requires us to develop new
mechanisms ensuring robustness of the protocol."
acknowledgement: We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful
feedback on an earlier draft of this paper.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joël
full_name: Alwen, Joël
last_name: Alwen
- 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: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- 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
- first_name: Michael
full_name: Walter, Michael
last_name: Walter
citation:
ama: 'Alwen J, Auerbach B, Cueto Noval M, et al. CoCoA: Concurrent continuous group
key agreement. In: Advances in Cryptology – EUROCRYPT 2022. Vol 13276.
Cham: Springer Nature; 2022:815–844. doi:10.1007/978-3-031-07085-3_28'
apa: 'Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak,
K. Z., & Walter, M. (2022). CoCoA: Concurrent continuous group key agreement.
In Advances in Cryptology – EUROCRYPT 2022 (Vol. 13276, pp. 815–844). Cham:
Springer Nature. https://doi.org/10.1007/978-3-031-07085-3_28'
chicago: 'Alwen, Joël, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo
Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “CoCoA: Concurrent Continuous
Group Key Agreement.” In Advances in Cryptology – EUROCRYPT 2022, 13276:815–844.
Cham: Springer Nature, 2022. https://doi.org/10.1007/978-3-031-07085-3_28.'
ieee: 'J. Alwen et al., “CoCoA: Concurrent continuous group key agreement,”
in Advances in Cryptology – EUROCRYPT 2022, Trondheim, Norway, 2022, vol.
13276, pp. 815–844.'
ista: 'Alwen J, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ,
Walter M. 2022. CoCoA: Concurrent continuous group key agreement. Advances in
Cryptology – EUROCRYPT 2022. EUROCRYPT: Theory and Applications of Cryptology
and Information Security, LNCS, vol. 13276, 815–844.'
mla: 'Alwen, Joël, et al. “CoCoA: Concurrent Continuous Group Key Agreement.” Advances
in Cryptology – EUROCRYPT 2022, vol. 13276, Springer Nature, 2022, pp. 815–844,
doi:10.1007/978-3-031-07085-3_28.'
short: J. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak,
M. Walter, in:, Advances in Cryptology – EUROCRYPT 2022, Springer Nature, Cham,
2022, pp. 815–844.
conference:
end_date: 2022-06-03
location: Trondheim, Norway
name: 'EUROCRYPT: Theory and Applications of Cryptology and Information Security'
start_date: 2022-05-30
corr_author: '1'
date_created: 2022-06-30T16:48:00Z
date_published: 2022-05-25T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '25'
department:
- _id: GradSch
- _id: KrPi
doi: 10.1007/978-3-031-07085-3_28
ec_funded: 1
external_id:
isi:
- '000832305300028'
intvolume: ' 13276'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/251
month: '05'
oa: 1
oa_version: Preprint
page: 815–844
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: Advances in Cryptology – EUROCRYPT 2022
publication_identifier:
eisbn:
- '9783031070853'
eissn:
- 1611-3349
isbn:
- '9783031070846'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'CoCoA: Concurrent continuous group key agreement'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13276
year: '2022'
...
---
_id: '10407'
abstract:
- lang: eng
text: Digital hardware Trojans are integrated circuits whose implementation differ
from the specification in an arbitrary and malicious way. For example, the circuit
can differ from its specified input/output behavior after some fixed number of
queries (known as “time bombs”) or on some particular input (known as “cheat codes”).
To detect such Trojans, countermeasures using multiparty computation (MPC) or
verifiable computation (VC) have been proposed. On a high level, to realize a
circuit with specification F one has more sophisticated circuits F⋄ manufactured
(where F⋄ specifies a MPC or VC of F ), and then embeds these F⋄ ’s into
a master circuit which must be trusted but is relatively simple compared to F
. Those solutions impose a significant overhead as F⋄ is much more complex
than F , also the master circuits are not exactly trivial. In this work, we
show that in restricted settings, where F has no evolving state and is queried
on independent inputs, we can achieve a relaxed security notion using very simple
constructions. In particular, we do not change the specification of the circuit
at all (i.e., F=F⋄ ). Moreover the master circuit basically just queries a subset
of its manufactured circuits and checks if they’re all the same. The security
we achieve guarantees that, if the manufactured circuits are initially tested
on up to T inputs, the master circuit will catch Trojans that try to deviate on
significantly more than a 1/T fraction of the inputs. This bound is optimal for
the type of construction considered, and we provably achieve it using a construction
where 12 instantiations of F need to be embedded into the master. We also discuss
an extremely simple construction with just 2 instantiations for which we conjecture
that it already achieves the optimal bound.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Małgorzata
full_name: Gałązka, Małgorzata
last_name: Gałązka
- first_name: Tomasz
full_name: Lizurej, Tomasz
last_name: Lizurej
- 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: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience
without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:10.1007/978-3-030-90453-1_14'
apa: 'Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z.,
& Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp.
397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC,
United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_14'
chicago: Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej,
Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,”
13043:397–428. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_14.
ieee: 'S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and
M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory
of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp.
397–428.'
ista: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX.
2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference,
LNCS, vol. 13043, 397–428.'
mla: Chakraborty, Suvradip, et al. Trojan-Resilience without Cryptography.
Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:10.1007/978-3-030-90453-1_14.
short: S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X.
Yeo, in:, Springer Nature, 2021, pp. 397–428.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-14T07:22:05Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_14
ec_funded: 1
external_id:
isi:
- '000728364000014'
intvolume: ' 13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1224
month: '11'
oa: 1
oa_version: Preprint
page: 397-428
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trojan-resilience without cryptography
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...
---
_id: '10409'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a SO(w) loss
in security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the
circuit. The design of the strategy relies on separators, a graph-theoretic notion
with connections to circuit complexity. with only a SO(w) loss in security.
For instance, circuits with constant treewidth are as a result adaptively indistinguishable
with only a polynomial loss. This (partially) complements a negative result of
Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that
Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions,
we introduce a new pebble game that abstracts out our security reduction and then
present a pebbling strategy for this game where the number of pebbles used is
roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the
strategy relies on separators, a graph-theoretic notion with connections to circuit
complexity.
acknowledgement: We are grateful to Daniel Wichs for helpful discussions on the landscape
of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021
and TCC 2021 reviewers for their detailed review and suggestions, which helped improve
presentation considerably.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- 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: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th International Conference. Vol 13043. Springer Nature;
2021:486-517. doi:10.1007/978-3-030-90453-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th International Conference (Vol. 13043,
pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th International Conference, 13043:486–517.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th International Conference, Raleigh, NC, United
States, 2021, vol. 13043, pp. 486–517.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS,
vol. 13043, 486–517.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517,
doi:10.1007/978-3-030-90453-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference,
Springer Nature, 2021, pp. 486–517.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-15T08:32:06Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_17
ec_funded: 1
external_id:
isi:
- '000728364000017'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '11'
oa: 1
oa_version: Preprint
page: 486-517
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10044'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On treewidth, separators and Yao’s garbling
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: '13043 '
year: '2021'
...