---
OA_place: repository
OA_type: green
_id: '21134'
abstract:
- lang: eng
text: "The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof
of work as a voting mechanism. Honest miners who contribute hashing power towards
securing the chain try to extend the longest chain they are aware of. Despite
its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming
that at any point in time, a majority of the hashing power is controlled by honest
parties. This also holds under “resource variability”, i.e., if the total hashing
power varies greatly over time.\r\nProofs of space (PoSpace) have been suggested
as a more sustainable replacement for proofs of work. Unfortunately, no construction
of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic
availability, is known. In this work, we prove that without additional assumptions
no such protocol exists. We exactly quantify this impossibility result by proving
a bound on the length of the fork required for double spending as a function of
the adversarial capabilities. This bound holds for any chain selection rule, and
we also show a chain selection rule (albeit a very strange one) that almost matches
this bound.\r\nThe Nakamoto consensus protocol underlying the Bitcoin blockchain
uses proof of work as a voting mechanism. Honest miners who contribute hashing
power towards securing the chain try to extend the longest chain they are aware
of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees
assuming that at any point in time, a majority of the hashing power is controlled
by honest parties. This also holds under “resource variability”, i.e., if the
total hashing power varies greatly over time.\r\n\r\nProofs of space (PoSpace)
have been suggested as a more sustainable replacement for proofs of work. Unfortunately,
no construction of a “longest-chain” blockchain based on PoSpace, that is secure
under dynamic availability, is known. In this work, we prove that without additional
assumptions no such protocol exists. We exactly quantify this impossibility result
by proving a bound on the length of the fork required for double spending as a
function of the adversarial capabilities. This bound holds for any chain selection
rule, and we also show a chain selection rule (albeit a very strange one) that
almost matches this bound.\r\n\r\nConcretely, we consider a security game in which
the honest parties at any point control 0 > 1\r\n times more space than the adversary.
The adversary can change the honest space by a factor 1+- E with every block (dynamic
availability), and “replotting” the space (which allows answering two challenges
using the same space) takes as much time as p blocks.\r\nWe prove that no matter
what chain selection rule is used, in this game the adversary can create a fork
of length o^2 . p/E that will be picked as the winner by the chain selection rule.\r\nWe
also provide an upper bound that matches the lower bound up to a factor o. There
exists a chain selection rule (albeit a very strange one) which in the above game
requires forks of length at least o . p/E\r\nOur results show the necessity of
additional assumptions to create a secure PoSpace based longest-chain blockchain.
The Chia network in addition to PoSpace uses a verifiable delay function. Our
bounds show that an additional primitive like that is necessary."
acknowledgement: This research was funded in whole or in part by the Austrian Science
Fund (FWF) 10.55776/F85.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain
blockchains. In: 29th International Conference on Financial Cryptography and
Data Security. Vol 15752. Springer Nature; 2026:127-142. doi:10.1007/978-3-032-07035-7_8'
apa: 'Baig, M. A., & Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space
based longest-chain blockchains. In 29th International Conference on Financial
Cryptography and Data Security (Vol. 15752, pp. 127–142). Miyakojima, Japan:
Springer Nature. https://doi.org/10.1007/978-3-032-07035-7_8'
chicago: Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” In 29th International Conference on Financial
Cryptography and Data Security, 15752:127–42. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-07035-7_8.
ieee: M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based
longest-chain blockchains,” in 29th International Conference on Financial Cryptography
and Data Security, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142.
ista: 'Baig MA, Pietrzak KZ. 2026. On the (in)security of Proofs-of-space based
longest-chain blockchains. 29th International Conference on Financial Cryptography
and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15752,
127–142.'
mla: Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” 29th International Conference on Financial
Cryptography and Data Security, vol. 15752, Springer Nature, 2026, pp. 127–42,
doi:10.1007/978-3-032-07035-7_8.
short: M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial
Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
corr_author: '1'
date_created: 2026-02-01T23:01:43Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-032-07035-7_8
external_id:
arxiv:
- '2505.14891'
intvolume: ' 15752'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.14891
month: '01'
oa: 1
oa_version: Preprint
page: 127-142
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070340'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: On the (in)security of Proofs-of-space based longest-chain blockchains
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15752
year: '2026'
...
---
OA_place: publisher
_id: '21651'
abstract:
- lang: eng
text: "Blockchains enable distributed consensus in permissionless settings, where
participants\r\nare unknown, dynamically changing, and do not trust each other.
While Bitcoin,\r\nbased on Proof-of-Work (PoW), was the first protocol in this
model, significant\r\nresearch has focused on permissionless protocols using alternative
physical resources,\r\nspecifically Proof-of-Space (PoSpace) and Verifiable Delay
Functions (VDFs). This\r\nthesis investigates the theoretical limits and design
space of longest-chain protocols in\r\nthe fully permissionless and dynamically
available settings using these three resources.\r\nFirst, we address the feasibility
of blockchains relying solely on storage as a resource.\r\nWe prove a fundamental
impossibility result: there exists no secure longest-chain\r\nprotocol based exclusively
on Proof-of-Space in the fully permissionless or dynamically\r\navailable settings.
Further, we quantify the adversarial capabilities required to execute\r\na double-spend
attack. Our result formally justifies the necessity of coupling PoSpace\r\nwith
time-dependent primitives (such as VDFs) or to move to less permissive settings\r\n(quasi-permissionless
or permissioned) to ensure security.\r\nSecond, we generalize Nakamoto-like heaviest
chain consensus to protocols utilizing\r\ncombinations of multiple physical resources.
We analyze chain selection rules governed\r\nby a weight function Γ(S, V,W), which
assigns weight to blocks based on recorded\r\nSpace (S), VDF speed (V ), and Work
(W). We provide a complete classification\r\nof secure weight functions, proving
that a weight function is secure against private\r\ndouble-spend attacks if and
only if it is homogeneous in the timed resources (V,W)\r\nand sub-homogeneous
in S. This framework unifies existing protocols like Bitcoin and\r\nChia under
a single theoretical model and provides a powerful tool for designing new\r\nlongest-chain
blockchains from a mix of physical resources."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
citation:
ama: Baig MA. On secure chain selection rules from physical resources in a permissionless
setting. 2026. doi:10.15479/AT-ISTA-21651
apa: Baig, M. A. (2026). On secure chain selection rules from physical resources
in a permissionless setting. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT-ISTA-21651
chicago: Baig, Mirza Ahad. “On Secure Chain Selection Rules from Physical Resources
in a Permissionless Setting.” Institute of Science and Technology Austria, 2026.
https://doi.org/10.15479/AT-ISTA-21651.
ieee: M. A. Baig, “On secure chain selection rules from physical resources in a
permissionless setting,” Institute of Science and Technology Austria, 2026.
ista: Baig MA. 2026. On secure chain selection rules from physical resources in
a permissionless setting. Institute of Science and Technology Austria.
mla: Baig, Mirza Ahad. On Secure Chain Selection Rules from Physical Resources
in a Permissionless Setting. Institute of Science and Technology Austria,
2026, doi:10.15479/AT-ISTA-21651.
short: M.A. Baig, On Secure Chain Selection Rules from Physical Resources in a Permissionless
Setting, Institute of Science and Technology Austria, 2026.
corr_author: '1'
date_created: 2026-04-02T09:31:34Z
date_published: 2026-03-04T00:00:00Z
date_updated: 2026-04-15T08:45:19Z
day: '04'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-21651
file:
- access_level: closed
checksum: c3986dba90653dac97adba662ebff238
content_type: application/x-zip-compressed
creator: mbaig
date_created: 2026-04-03T17:28:48Z
date_updated: 2026-04-13T08:24:13Z
file_id: '21655'
file_name: PhD-Thesis-Mirza-Ahad-Baig - Library Submission.zip
file_size: 139353434
relation: source_file
- access_level: open_access
checksum: 292a5989262521f7c145a109d1f348cb
content_type: application/pdf
creator: mbaig
date_created: 2026-04-03T17:29:30Z
date_updated: 2026-04-15T07:37:25Z
file_id: '21656'
file_name: 2026_Baig_Mirza_Ahad_Thesis.pdf
file_size: 1942037
relation: main_file
file_date_updated: 2026-04-15T07:37:25Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '03'
oa: 1
oa_version: Published Version
publication_identifier:
isbn:
- 978-3-99078-078-7
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '21134'
relation: part_of_dissertation
status: public
- id: '20587'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On secure chain selection rules from physical resources in a permissionless
setting
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '19738'
abstract:
- lang: eng
text: "Garbling is a fundamental cryptographic primitive, with numerous theoretical
and practical applications. Since the first construction by Yao (FOCS’82, ’86),
a line of work has concerned itself with reducing the communication and computational
complexity of that construction. One of the most efficient garbling schemes presently
is the ‘Half Gates’ scheme by Zahur, Rosulek, and Evans (Eurocrypt’15). Despite
its widespread adoption, the provable security of this scheme has been based on
assumptions whose only instantiations are in idealized models. For example, in
their original paper, Zahur, Rosulek, and Evans showed that hash functions satisfying
a notion called circular correlation robustness (CCR) suffice for this task, and
then proved that CCR secure hash functions can be instantiated in the random permutation
model.\r\nIn this work, we show how to securely instantiate the Half Gates scheme
in the standard model. To this end, we first show how this scheme can be securely
instantiated given a (family of) weak CCR hash function, a notion that we introduce.
Furthermore, we show how a weak CCR hash function can be used to securely instantiate
other efficient garbling schemes, namely the ones by Rosulek and Roy (Crypto’21)
and Heath (Eurocrypt’24). Thus we believe this notion to be of independent interest.\r\nFinally,
we construct such weak CCR hash functions using indistinguishability obfuscation
and one-way functions. The security proof of this construction constitutes our
main technical contribution. While our construction is not practical, it serves
as a proof of concept supporting the soundness of these garbling schemes, which
we regard to be particularly important given the recent initiative by NIST to
standardize garbling, and the optimizations in Half Gates being potentially adopted."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Anasuya
full_name: Acharya, Anasuya
last_name: Acharya
- first_name: Karen
full_name: Azari, Karen
last_name: Azari
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Dennis
full_name: Hofheinz, Dennis
last_name: Hofheinz
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
citation:
ama: 'Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. Securely instantiating
‘Half Gates’ garbling in the standard model. In: 28th IACR International Conference
on Practice and Theory of Public-Key Cryptography. Vol 15677. Springer Nature;
2025:37-75. doi:10.1007/978-3-031-91829-2_2'
apa: 'Acharya, A., Azari, K., Baig, M. A., Hofheinz, D., & Kamath, C. (2025).
Securely instantiating ‘Half Gates’ garbling in the standard model. In 28th
IACR International Conference on Practice and Theory of Public-Key Cryptography
(Vol. 15677, pp. 37–75). Roros, Norway: Springer Nature. https://doi.org/10.1007/978-3-031-91829-2_2'
chicago: Acharya, Anasuya, Karen Azari, Mirza Ahad Baig, Dennis Hofheinz, and Chethan
Kamath. “Securely Instantiating ‘Half Gates’ Garbling in the Standard Model.”
In 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography, 15677:37–75. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-91829-2_2.
ieee: A. Acharya, K. Azari, M. A. Baig, D. Hofheinz, and C. Kamath, “Securely instantiating
‘Half Gates’ garbling in the standard model,” in 28th IACR International Conference
on Practice and Theory of Public-Key Cryptography, Roros, Norway, 2025, vol.
15677, pp. 37–75.
ista: 'Acharya A, Azari K, Baig MA, Hofheinz D, Kamath C. 2025. Securely instantiating
‘Half Gates’ garbling in the standard model. 28th IACR International Conference
on Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography,
LNCS, vol. 15677, 37–75.'
mla: Acharya, Anasuya, et al. “Securely Instantiating ‘Half Gates’ Garbling in the Standard
Model.” 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography, vol. 15677, Springer Nature, 2025, pp. 37–75, doi:10.1007/978-3-031-91829-2_2.
short: A. Acharya, K. Azari, M.A. Baig, D. Hofheinz, C. Kamath, in:, 28th IACR International
Conference on Practice and Theory of Public-Key Cryptography, Springer Nature,
2025, pp. 37–75.
conference:
end_date: 2025-05-15
location: Roros, Norway
name: 'PKC: Public-Key Cryptography'
start_date: 2025-05-12
date_created: 2025-05-25T22:17:02Z
date_published: 2025-05-05T00:00:00Z
date_updated: 2025-06-02T07:01:45Z
day: '05'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-031-91829-2_2
intvolume: ' 15677'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/281
month: '05'
oa: 1
oa_version: Preprint
page: 37-75
publication: 28th IACR International Conference on Practice and Theory of Public-Key
Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031918285'
issn:
- 0302-9743
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Securely instantiating ‘Half Gates’ garbling in the standard model
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15677
year: '2025'
...
---
OA_place: 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
license: https://creativecommons.org/licenses/by/4.0/
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: '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'
...
---
_id: '12164'
abstract:
- lang: eng
text: 'A shared-memory counter is a widely-used and well-studied concurrent object.
It supports two operations: An Inc operation that increases its value by 1 and
a Read operation that returns its current value. In Jayanti et al (SIAM J Comput,
30(2), 2000), Jayanti, Tan and Toueg proved a linear lower bound on the worst-case
step complexity of obstruction-free implementations, from read-write registers,
of a large class of shared objects that includes counters. The lower bound leaves
open the question of finding counter implementations with sub-linear amortized
step complexity. In this work, we address this gap. We show that n-process, wait-free
and linearizable counters can be implemented from read-write registers with O(log2n)
amortized step complexity. This is the first counter algorithm from read-write
registers that provides sub-linear amortized step complexity in executions of
arbitrary length. Since a logarithmic lower bound on the amortized step complexity
of obstruction-free counter implementations exists, our upper bound is within
a logarithmic factor of the optimal. The worst-case step complexity of the construction
remains linear, which is optimal. This is obtained thanks to a new max register
construction with O(logn) amortized step complexity in executions of arbitrary
length in which the value stored in the register does not grow too quickly. We
then leverage an existing counter algorithm by Aspnes, Attiya and Censor-Hillel
[1] in which we “plug” our max register implementation to show that it remains
linearizable while achieving O(log2n) amortized step complexity.'
acknowledgement: A preliminary version of this work appeared in DISC’19. Mirza Ahad
Baig, Alessia Milani and Corentin Travers are supported by ANR projects Descartes
and FREDDA. Mirza Ahad Baig is supported by UMI Relax. Danny Hendler is supported
by the Israel Science Foundation (Grants 380/18 and 1425/22).
article_processing_charge: No
article_type: original
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Danny
full_name: Hendler, Danny
last_name: Hendler
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: Baig MA, Hendler D, Milani A, Travers C. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 2023;36:29-43. doi:10.1007/s00446-022-00439-5
apa: Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2023). Long-lived
counters with polylogarithmic amortized step complexity. Distributed Computing.
Springer Nature. https://doi.org/10.1007/s00446-022-00439-5
chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
“Long-Lived Counters with Polylogarithmic Amortized Step Complexity.” Distributed
Computing. Springer Nature, 2023. https://doi.org/10.1007/s00446-022-00439-5.
ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived counters with
polylogarithmic amortized step complexity,” Distributed Computing, vol.
36. Springer Nature, pp. 29–43, 2023.
ista: Baig MA, Hendler D, Milani A, Travers C. 2023. Long-lived counters with polylogarithmic
amortized step complexity. Distributed Computing. 36, 29–43.
mla: Baig, Mirza Ahad, et al. “Long-Lived Counters with Polylogarithmic Amortized
Step Complexity.” Distributed Computing, vol. 36, Springer Nature, 2023,
pp. 29–43, doi:10.1007/s00446-022-00439-5.
short: M.A. Baig, D. Hendler, A. Milani, C. Travers, Distributed Computing 36 (2023)
29–43.
date_created: 2023-01-12T12:10:08Z
date_published: 2023-03-01T00:00:00Z
date_updated: 2023-08-16T08:39:36Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00446-022-00439-5
external_id:
isi:
- '000890138700001'
intvolume: ' 36'
isi: 1
keyword:
- Computational Theory and Mathematics
- Computer Networks and Communications
- Hardware and Architecture
- Theoretical Computer Science
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://drops.dagstuhl.de/opus/volltexte/2019/11310/
month: '03'
oa: 1
oa_version: Preprint
page: 29-43
publication: Distributed Computing
publication_identifier:
eissn:
- 1432-0452
issn:
- 0178-2770
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived counters with polylogarithmic amortized step complexity
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 36
year: '2023'
...
---
_id: '10408'
abstract:
- lang: eng
text: 'Key trees are often the best solution in terms of transmission cost and storage
requirements for managing keys in a setting where a group needs to share a secret
key, while being able to efficiently rotate the key material of users (in order
to recover from a potential compromise, or to add or remove users). Applications
include multicast encryption protocols like LKH (Logical Key Hierarchies) or group
messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced)
binary tree, where each node is identified with a key: leaf nodes hold users’
secret keys while the root is the shared group key. For a group of size N, each
user just holds log(N) keys (the keys on the path from its leaf to the root)
and its entire key material can be rotated by broadcasting 2log(N) ciphertexts
(encrypting each fresh key on the path under the keys of its parents). In this
work we consider the natural setting where we have many groups with partially
overlapping sets of users, and ask if we can find solutions where the cost of
rotating a key is better than in the trivial one where we have a separate key
tree for each group. We show that in an asymptotic setting (where the number m
of groups is fixed while the number N of users grows) there exist more general
key graphs whose cost converges to the cost of a single group, thus saving a factor
linear in the number of groups over the trivial solution. As our asymptotic “solution”
converges very slowly and performs poorly on concrete examples, we propose an
algorithm that uses a natural heuristic to compute a key graph for any given group
structure. Our algorithm combines two greedy algorithms, and is thus very efficient:
it first converts the group structure into a “lattice graph”, which is then turned
into a key graph by repeatedly applying the algorithm for constructing a Huffman
code. To better understand how far our proposal is from an optimal solution, we
prove lower bounds on the update cost of continuous group-key agreement and multicast
encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom
generators, and secret sharing as building blocks.'
acknowledgement: B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by
ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the
ERC under the European Union’s Horizon 2020 research and innovation programme (682815
- TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No. 665385; Michael Walter conducted part of this work at IST Austria, funded by
the ERC under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).
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: 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: 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
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management
for overlapping groups. In: 19th International Conference. Vol 13044. Springer
Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8'
apa: 'Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual
Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for
overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253).
Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8'
chicago: 'Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval,
Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter.
“Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th
International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.'
ieee: 'J. F. Alwen et al., “Grafting key trees: Efficient key management
for overlapping groups,” in 19th International Conference, Raleigh, NC,
United States, 2021, vol. 13044, pp. 222–253.'
ista: 'Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak
KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping
groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol.
13044, 222–253.'
mla: 'Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping
Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021,
pp. 222–53, doi:10.1007/978-3-030-90456-2_8.'
short: J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual
Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer
Nature, 2021, pp. 222–253.
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:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90456-2_8
ec_funded: 1
external_id:
isi:
- '000728363700008'
intvolume: ' 13044'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1158
month: '11'
oa: 1
oa_version: Preprint
page: 222-253
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: 19th International Conference
publication_identifier:
eisbn:
- 978-3-030-90456-2
eissn:
- 1611-3349
isbn:
- 9-783-0309-0455-5
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: 'Grafting key trees: Efficient key management for overlapping groups'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13044
year: '2021'
...
---
_id: '8382'
abstract:
- lang: eng
text: We present the first deterministic wait-free long-lived snapshot algorithm,
using only read and write operations, that guarantees polylogarithmic amortized
step complexity in all executions. This is the first non-blocking snapshot algorithm,
using reads and writes only, that has sub-linear amortized step complexity in
executions of arbitrary length. The key to our construction is a novel implementation
of a 2-component max array object which may be of independent interest.
article_processing_charge: No
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Danny
full_name: Hendler, Danny
last_name: Hendler
- first_name: Alessia
full_name: Milani, Alessia
last_name: Milani
- first_name: Corentin
full_name: Travers, Corentin
last_name: Travers
citation:
ama: 'Baig MA, Hendler D, Milani A, Travers C. Long-lived snapshots with polylogarithmic
amortized step complexity. In: Proceedings of the 39th Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2020:31-40.
doi:10.1145/3382734.3406005'
apa: 'Baig, M. A., Hendler, D., Milani, A., & Travers, C. (2020). Long-lived
snapshots with polylogarithmic amortized step complexity. In Proceedings of
the 39th Symposium on Principles of Distributed Computing (pp. 31–40). Virtual,
Italy: Association for Computing Machinery. https://doi.org/10.1145/3382734.3406005'
chicago: Baig, Mirza Ahad, Danny Hendler, Alessia Milani, and Corentin Travers.
“Long-Lived Snapshots with Polylogarithmic Amortized Step Complexity.” In Proceedings
of the 39th Symposium on Principles of Distributed Computing, 31–40. Association
for Computing Machinery, 2020. https://doi.org/10.1145/3382734.3406005.
ieee: M. A. Baig, D. Hendler, A. Milani, and C. Travers, “Long-lived snapshots with
polylogarithmic amortized step complexity,” in Proceedings of the 39th Symposium
on Principles of Distributed Computing, Virtual, Italy, 2020, pp. 31–40.
ista: 'Baig MA, Hendler D, Milani A, Travers C. 2020. Long-lived snapshots with
polylogarithmic amortized step complexity. Proceedings of the 39th Symposium on
Principles of Distributed Computing. PODC: Principles of Distributed Computing,
31–40.'
mla: Baig, Mirza Ahad, et al. “Long-Lived Snapshots with Polylogarithmic Amortized
Step Complexity.” Proceedings of the 39th Symposium on Principles of Distributed
Computing, Association for Computing Machinery, 2020, pp. 31–40, doi:10.1145/3382734.3406005.
short: M.A. Baig, D. Hendler, A. Milani, C. Travers, in:, Proceedings of the 39th
Symposium on Principles of Distributed Computing, Association for Computing Machinery,
2020, pp. 31–40.
conference:
end_date: 2020-08-07
location: Virtual, Italy
name: 'PODC: Principles of Distributed Computing'
start_date: 2020-08-03
date_created: 2020-09-13T22:01:17Z
date_published: 2020-07-31T00:00:00Z
date_updated: 2025-09-10T10:25:23Z
day: '31'
doi: 10.1145/3382734.3406005
external_id:
isi:
- '001436693500004'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.archives-ouvertes.fr/hal-02860087/document
month: '07'
oa: 1
oa_version: Preprint
page: 31-40
publication: Proceedings of the 39th Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9781450375825'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: Long-lived snapshots with polylogarithmic amortized step complexity
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2020'
...