---
OA_place: publisher
_id: '21651'
abstract:
- lang: eng
text: "Blockchains enable distributed consensus in permissionless settings, where
participants\r\nare unknown, dynamically changing, and do not trust each other.
While Bitcoin,\r\nbased on Proof-of-Work (PoW), was the first protocol in this
model, significant\r\nresearch has focused on permissionless protocols using alternative
physical resources,\r\nspecifically Proof-of-Space (PoSpace) and Verifiable Delay
Functions (VDFs). This\r\nthesis investigates the theoretical limits and design
space of longest-chain protocols in\r\nthe fully permissionless and dynamically
available settings using these three resources.\r\nFirst, we address the feasibility
of blockchains relying solely on storage as a resource.\r\nWe prove a fundamental
impossibility result: there exists no secure longest-chain\r\nprotocol based exclusively
on Proof-of-Space in the fully permissionless or dynamically\r\navailable settings.
Further, we quantify the adversarial capabilities required to execute\r\na double-spend
attack. Our result formally justifies the necessity of coupling PoSpace\r\nwith
time-dependent primitives (such as VDFs) or to move to less permissive settings\r\n(quasi-permissionless
or permissioned) to ensure security.\r\nSecond, we generalize Nakamoto-like heaviest
chain consensus to protocols utilizing\r\ncombinations of multiple physical resources.
We analyze chain selection rules governed\r\nby a weight function Γ(S, V,W), which
assigns weight to blocks based on recorded\r\nSpace (S), VDF speed (V ), and Work
(W). We provide a complete classification\r\nof secure weight functions, proving
that a weight function is secure against private\r\ndouble-spend attacks if and
only if it is homogeneous in the timed resources (V,W)\r\nand sub-homogeneous
in S. This framework unifies existing protocols like Bitcoin and\r\nChia under
a single theoretical model and provides a powerful tool for designing new\r\nlongest-chain
blockchains from a mix of physical resources."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
citation:
ama: Baig MA. On secure chain selection rules from physical resources in a permissionless
setting. 2026. doi:10.15479/AT-ISTA-21651
apa: Baig, M. A. (2026). On secure chain selection rules from physical resources
in a permissionless setting. Institute of Science and Technology Austria.
https://doi.org/10.15479/AT-ISTA-21651
chicago: Baig, Mirza Ahad. “On Secure Chain Selection Rules from Physical Resources
in a Permissionless Setting.” Institute of Science and Technology Austria, 2026.
https://doi.org/10.15479/AT-ISTA-21651.
ieee: M. A. Baig, “On secure chain selection rules from physical resources in a
permissionless setting,” Institute of Science and Technology Austria, 2026.
ista: Baig MA. 2026. On secure chain selection rules from physical resources in
a permissionless setting. Institute of Science and Technology Austria.
mla: Baig, Mirza Ahad. On Secure Chain Selection Rules from Physical Resources
in a Permissionless Setting. Institute of Science and Technology Austria,
2026, doi:10.15479/AT-ISTA-21651.
short: M.A. Baig, On Secure Chain Selection Rules from Physical Resources in a Permissionless
Setting, Institute of Science and Technology Austria, 2026.
corr_author: '1'
date_created: 2026-04-02T09:31:34Z
date_published: 2026-03-04T00:00:00Z
date_updated: 2026-04-15T08:45:19Z
day: '04'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-21651
file:
- access_level: closed
checksum: c3986dba90653dac97adba662ebff238
content_type: application/x-zip-compressed
creator: mbaig
date_created: 2026-04-03T17:28:48Z
date_updated: 2026-04-13T08:24:13Z
file_id: '21655'
file_name: PhD-Thesis-Mirza-Ahad-Baig - Library Submission.zip
file_size: 139353434
relation: source_file
- access_level: open_access
checksum: 292a5989262521f7c145a109d1f348cb
content_type: application/pdf
creator: mbaig
date_created: 2026-04-03T17:29:30Z
date_updated: 2026-04-15T07:37:25Z
file_id: '21656'
file_name: 2026_Baig_Mirza_Ahad_Thesis.pdf
file_size: 1942037
relation: main_file
file_date_updated: 2026-04-15T07:37:25Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by-nc-sa/4.0/
month: '03'
oa: 1
oa_version: Published Version
publication_identifier:
isbn:
- 978-3-99078-078-7
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '21134'
relation: part_of_dissertation
status: public
- id: '20587'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On secure chain selection rules from physical resources in a permissionless
setting
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: publisher
_id: '20920'
abstract:
- lang: eng
text: "Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18)
are functions that require a prescribed number of sequential steps T to evaluate,
yet their output can be verified in time much faster than T. Since their introduction,
VDFs have gained a lot of attention due to their applications in blockchain protocols,
randomness beacons, timestamping and deniability. This thesis explores the theory
and applications of VDFs, focusing on enhancing their soundness, efficiency and
practicality.\r\n\r\nThe only practical VDFs known to date are based on repeated
squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T).\r\nThe
iterated squaring assumption states that, for a random group element x, the result
of VDF cannot be computed significantly faster than performing T sequential squarings
if the group order is unknown. To make the result verifiable a prover can compute
a proof of exponentiation (PoE) \\pi. Given \\pi, the output of VDF can be verified
in time much less than T.\r\n\r\nWe first present new constructions of statistically
sound proofs of exponentiation, which are an important building block in the construction
of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness
means that the proofs remain secure against computationally unbounded adversaries,
in particular, it remains secure even when the group order is known. We thereby
address limitations in previous PoE protocols which either required (non-standard)
hardness assumptions or a lot of parallel repetitions. Our construction significantly
reduces the proof size of statistically sound PoEs that allow for a structured
exponent, which leads to better efficiency of SNARKs and other applications.\r\n\r\nSecondly,
we introduce improved batching techniques for PoEs, which allow multiple proofs
to be aggregated and verified with minimal overhead. These protocols optimize
communication and computation complexity in large-scale blockchain environments
and enable scalable remote benchmarking of parallel computation resources.\r\n\r\nWe
then construct VDFs with enhanced properties such as zero-knowledge and watermarkability.
It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable
new cryptographic primitives called short-lived proofs and signatures. The validity
of such proofs and signatures expires after a predefined amount of time T, i.e.,
they are deniable after time T. Our constructions improve upon the constructions
by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably
weaker assumptions).\r\n\r\nFinally, we apply PoEs in the realm of primality testing,
providing cryptographically sound proofs of non-primality for large Proth numbers.
This work gives a surprising application of VDFs in the area of computational
number theory.\r\n\r\nTogether, our contributions advance both the theoretical
foundations and the real-world usability of VDFs in general and in particular
of PoEs, making them more adaptable and secure for current and emerging cryptographic
applications."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
citation:
ama: Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:10.15479/AT-ISTA-20920
apa: Hoffmann, C. (2025). Theory and applications of verifiable delay functions.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20920
chicago: Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.”
Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20920.
ieee: C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute
of Science and Technology Austria, 2025.
ista: Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute
of Science and Technology Austria.
mla: Hoffmann, Charlotte. Theory and Applications of Verifiable Delay Functions.
Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20920.
short: C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute
of Science and Technology Austria, 2025.
corr_author: '1'
date_created: 2026-01-02T10:46:47Z
date_published: 2025-12-31T00:00:00Z
date_updated: 2026-07-06T13:15:27Z
day: '31'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-20920
file:
- access_level: closed
checksum: 8a099fbf54963bd0be38f7ce73658682
content_type: application/x-zip-compressed
creator: choffman
date_created: 2026-01-02T10:39:16Z
date_updated: 2026-01-02T10:39:16Z
file_id: '20921'
file_name: 2025_Hoffmann_Charlotte_Source.zip
file_size: 8355494
relation: source_file
- access_level: open_access
checksum: 9521c07bfb2bb5b14a49c09fcfc96474
content_type: application/pdf
creator: choffman
date_created: 2026-01-02T10:39:26Z
date_updated: 2026-01-02T10:39:26Z
file_id: '20922'
file_name: 2025_Hoffmann_Charlotte_Thesis.pdf
file_size: 2258804
relation: main_file
success: 1
file_date_updated: 2026-01-02T10:39:26Z
has_accepted_license: '1'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Published Version
page: '116'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '13143'
relation: part_of_dissertation
status: public
- id: '12176'
relation: part_of_dissertation
status: public
- id: '20556'
relation: earlier_version
status: public
- id: '19778'
relation: part_of_dissertation
status: public
- id: '20701'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: Theory and applications of verifiable delay functions
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
OA_place: publisher
_id: '20556'
abstract:
- lang: eng
text: "Verifiable Delay Functions (VDFs) introduced by Boneh et al. (CRYPTO'18)
are functions that require a prescribed number of sequential steps T to evaluate,
yet their output can be verified in time much faster than T. Since their introduction,
VDFs have gained a lot of attention due to their applications in blockchain protocols,
randomness beacons, timestamping and deniability. This thesis explores the theory
and applications of VDFs, focusing on enhancing their soundness, efficiency and
practicality.\r\n\r\nThe only practical VDFs known to date are based on repeated
squaring in hidden order groups. Consider the function VDF(x,T)=x^(2^T).\r\nThe
iterated squaring assumption states that, for a random group element x, the result
of VDF cannot be computed significantly faster than performing T sequential squarings
if the group order is unknown. To make the result verifiable a prover can compute
a proof of exponentiation (PoE) \\pi. Given \\pi, the output of VDF can be verified
in time much less than T.\r\n\r\nWe first present new constructions of statistically
sound proofs of exponentiation, which are an important building block in the construction
of SNARKs (Succinct Non-Interactive Argument of Knowledge). Statistical soundness
means that the proofs remain secure against computationally unbounded adversaries,
in particular, it remains secure even when the group order is known. We thereby
address limitations in previous PoE protocols which either required (non-standard)
hardness assumptions or a lot of parallel repetitions. Our construction significantly
reduces the proof size of statistically sound PoEs that allow for a structured
exponent, which leads to better efficiency of SNARKs and other applications.\r\n\r\nSecondly,
we introduce improved batching techniques for PoEs, which allow multiple proofs
to be aggregated and verified with minimal overhead. These protocols optimize
communication and computation complexity in large-scale blockchain environments
and enable scalable remote benchmarking of parallel computation resources.\r\n\r\nWe
then construct VDFs with enhanced properties such as zero-knowledge and watermarkability.
It was shown by Arun, Bonneau and Clark (ASIACRYPT'22) that these features enable
new cryptographic primitives called short-lived proofs and signatures. The validity
of such proofs and signatures expires after a predefined amount of time T, i.e.,
they are deniable after time T. Our constructions improve upon the constructions
by Arun, Bonneau and Clark in several dimensions (faster forging times, arguably
weaker assumptions).\r\n\r\nFinally, we apply PoEs in the realm of primality testing,
providing cryptographically sound proofs of non-primality for large Proth numbers.
This work gives a surprising application of VDFs in the area of computational
number theory.\r\n\r\nTogether, our contributions advance both the theoretical
foundations and the real-world usability of VDFs in general and in particular
of PoEs, making them more adaptable and secure for current and emerging cryptographic
applications."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
citation:
ama: Hoffmann C. Theory and applications of verifiable delay functions. 2025. doi:10.15479/AT-ISTA-20556
apa: Hoffmann, C. (2025). Theory and applications of verifiable delay functions.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT-ISTA-20556
chicago: Hoffmann, Charlotte. “Theory and Applications of Verifiable Delay Functions.”
Institute of Science and Technology Austria, 2025. https://doi.org/10.15479/AT-ISTA-20556.
ieee: C. Hoffmann, “Theory and applications of verifiable delay functions,” Institute
of Science and Technology Austria, 2025.
ista: Hoffmann C. 2025. Theory and applications of verifiable delay functions. Institute
of Science and Technology Austria.
mla: Hoffmann, Charlotte. Theory and Applications of Verifiable Delay Functions.
Institute of Science and Technology Austria, 2025, doi:10.15479/AT-ISTA-20556.
short: C. Hoffmann, Theory and Applications of Verifiable Delay Functions, Institute
of Science and Technology Austria, 2025.
corr_author: '1'
date_created: 2025-10-27T14:16:56Z
date_published: 2025-10-31T00:00:00Z
date_updated: 2026-07-06T13:15:27Z
day: '31'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/AT-ISTA-20556
file:
- access_level: closed
checksum: 1fffa4e2c33dd0b9f883d615504a2858
content_type: application/pdf
creator: choffman
date_created: 2025-10-28T14:33:03Z
date_updated: 2026-01-08T14:11:39Z
file_id: '20573'
file_name: 2025_Hoffmann_Charlotte_Thesis.pdf
file_size: 2259304
relation: main_file
- access_level: closed
checksum: 076ea98a1f0a86c3bbc990b6b9460dc2
content_type: application/x-zip-compressed
creator: choffman
date_created: 2025-10-28T14:35:06Z
date_updated: 2025-11-11T09:34:54Z
file_id: '20574'
file_name: 2025_Hoffmann_Charlotte_Source.zip
file_size: 9987633
relation: source_file
file_date_updated: 2026-01-08T14:11:39Z
has_accepted_license: '1'
language:
- iso: eng
month: '10'
oa_version: Published Version
page: '116'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '13143'
relation: part_of_dissertation
status: public
- id: '12176'
relation: part_of_dissertation
status: public
- id: '20920'
relation: later_version
status: public
- id: '19778'
relation: part_of_dissertation
status: public
- id: '20701'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: Theory and applications of verifiable delay functions
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2025'
...
---
OA_place: publisher
_id: '18088'
abstract:
- lang: eng
text: "Instant messaging applications like Whatsapp, Signal or Telegram have become
ubiquitous in today's society.\r\nMany of them provide not only end-to-end encryption,
but also security guarantees even when the key material gets compromised.\r\nThese
are achieved through frequent key update performed by users.\r\nIn particular,
the compromise of a group key should preserve confidentiality of previously exchanged
messages (forward secrecy), and a subsequent key update will ensure security for
future ones (post-compromise security).\r\nThough great protocols for one-on-one
communication have been known for some time, the design of ones that scale efficiently
for larger groups while achieving akin security guarantees is a hard problem.\r\nA
great deal of research has been aimed at this topic, much of it under the umbrella
of the Messaging Layer Security (MLS) working group at the IETF. \r\nStarted in
2018, this joint effort by academics and industry culminated in 2023 with the
publication of the first standard for secure group messaging [IETF, RFC9420].\r\n\r\nAt
the core of secure group messaging is a cryptographic primitive termed Continuous
Group Key Agreement, or CGKA [Alwen et al. 2021], that essentially allows a changing
group of users to agree on a common key with the added functionality security
against compromises is achieved by users asynchronously issuing a key update.
In this thesis we contribute to the understanding of CGKA across different angles.\r\nFirst,
we present a new technique to effect dynamic operations in groups, i.e., add or
remove members, that can be more efficient that the one employed by MLS in certain
settings.\r\nConsidering the setting of users belonging to multiple overlapping
groups, we then show lowerbounds on the communication cost of constructions that
leverage said overlap, at the same time showing protocols that are asymptotically
optimal and efficient for practical settings, respectively. Along the way, we
show that the communication cost of key updates in MLS is average-cost optimal.\r\nAn
important feature in CGKA protocols, particularly for big groups, is the possibility
of executing several group operations concurrently. While later versions of MLS
support this, they do at the cost of worsening the communication efficiency of
future group operations.\r\nIn this thesis we introduce two new protocols that
permit concurrency without any negative effect on efficiency. Our protocols circumvent
previously existing lower bounds by satisfying a new notion of post-compromise
security that only asks for security to be re-established after a certain number
of key updates have taken place. While this can be slower than MLS in terms of
rounds of communication, we show that it leads to more efficient overall communication.
\r\nAdditionally, we introduce a new technique that allows group members to decrease
the information they need to store and download, which makes one of our protocols
enjoy much lower download cost than any other existing CGKA constructions. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
citation:
ama: Pascual Perez G. On the efficiency and security of secure group messaging.
2024. doi:10.15479/at:ista:18088
apa: Pascual Perez, G. (2024). On the efficiency and security of secure group
messaging. Institute of Science and Technology Austria. https://doi.org/10.15479/at:ista:18088
chicago: Pascual Perez, Guillermo. “On the Efficiency and Security of Secure Group
Messaging.” Institute of Science and Technology Austria, 2024. https://doi.org/10.15479/at:ista:18088.
ieee: G. Pascual Perez, “On the efficiency and security of secure group messaging,”
Institute of Science and Technology Austria, 2024.
ista: Pascual Perez G. 2024. On the efficiency and security of secure group messaging.
Institute of Science and Technology Austria.
mla: Pascual Perez, Guillermo. On the Efficiency and Security of Secure Group
Messaging. Institute of Science and Technology Austria, 2024, doi:10.15479/at:ista:18088.
short: G. Pascual Perez, On the Efficiency and Security of Secure Group Messaging,
Institute of Science and Technology Austria, 2024.
corr_author: '1'
date_created: 2024-09-18T12:59:49Z
date_published: 2024-09-18T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '18'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrPi
- _id: GradSch
doi: 10.15479/at:ista:18088
ec_funded: 1
file:
- access_level: closed
checksum: ce0dca715b3df48e52e2e891b6ac1bc5
content_type: application/x-zip-compressed
creator: gpascual
date_created: 2024-09-19T12:35:38Z
date_updated: 2024-09-19T12:35:38Z
file_id: '18099'
file_name: thesis_bundle.zip
file_size: 11917734
relation: source_file
- access_level: open_access
checksum: 4a2c72e90f1a0ef2a13cff800f8d1265
content_type: application/pdf
creator: gpascual
date_created: 2024-09-19T12:36:08Z
date_updated: 2024-09-19T12:36:08Z
file_id: '18100'
file_name: thesis_gpasper.pdf
file_size: 2729427
relation: main_file
file_date_updated: 2024-09-19T12:36:08Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '239'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10408'
relation: part_of_dissertation
status: public
- id: '11476'
relation: part_of_dissertation
status: public
- id: '18086'
relation: part_of_dissertation
status: public
- id: '10049'
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 the efficiency and security of secure group messaging
tmp:
image: /images/cc_by_nc_sa.png
legal_code_url: https://creativecommons.org/licenses/by-nc-sa/4.0/legalcode
name: Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International (CC
BY-NC-SA 4.0)
short: CC BY-NC-SA (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2024'
...
---
OA_place: publisher
_id: '14506'
abstract:
- lang: eng
text: "Payment channel networks are a promising approach to improve the scalability
bottleneck\r\nof cryptocurrencies. Two design principles behind payment channel
networks are\r\nefficiency and privacy. Payment channel networks improve efficiency
by allowing users\r\nto transact in a peer-to-peer fashion along multi-hop routes
in the network, avoiding\r\nthe lengthy process of consensus on the blockchain.
Transacting over payment channel\r\nnetworks also improves privacy as these transactions
are not broadcast to the blockchain.\r\nDespite the influx of recent protocols
built on top of payment channel networks and\r\ntheir analysis, a common shortcoming
of many of these protocols is that they typically\r\nfocus only on either improving
efficiency or privacy, but not both. Another limitation\r\non the efficiency front
is that the models used to model actions, costs and utilities of\r\nusers are
limited or come with unrealistic assumptions.\r\nThis thesis aims to address some
of the shortcomings of recent protocols and algorithms\r\non payment channel networks,
particularly in their privacy and efficiency aspects. We\r\nfirst present a payment
route discovery protocol based on hub labelling and private\r\ninformation retrieval
that hides the route query and is also efficient. We then present\r\na rebalancing
protocol that formulates the rebalancing problem as a linear program\r\nand solves
the linear program using multiparty computation so as to hide the channel\r\nbalances.
The rebalancing solution as output by our protocol is also globally optimal.\r\nWe
go on to develop more realistic models of the action space, costs, and utilities
of\r\nboth existing and new users that want to join the network. In each of these
settings,\r\nwe also develop algorithms to optimise the utility of these users
with good guarantees\r\non the approximation and competitive ratios."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- 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: Yeo MX. Advances in efficiency and privacy in payment channel network analysis.
2023. doi:10.15479/14506
apa: Yeo, M. X. (2023). Advances in efficiency and privacy in payment channel
network analysis. Institute of Science and Technology Austria. https://doi.org/10.15479/14506
chicago: Yeo, Michelle X. “Advances in Efficiency and Privacy in Payment Channel
Network Analysis.” Institute of Science and Technology Austria, 2023. https://doi.org/10.15479/14506.
ieee: M. X. Yeo, “Advances in efficiency and privacy in payment channel network
analysis,” Institute of Science and Technology Austria, 2023.
ista: Yeo MX. 2023. Advances in efficiency and privacy in payment channel network
analysis. Institute of Science and Technology Austria.
mla: Yeo, Michelle X. Advances in Efficiency and Privacy in Payment Channel Network
Analysis. Institute of Science and Technology Austria, 2023, doi:10.15479/14506.
short: M.X. Yeo, Advances in Efficiency and Privacy in Payment Channel Network Analysis,
Institute of Science and Technology Austria, 2023.
corr_author: '1'
date_created: 2023-11-10T08:10:43Z
date_published: 2023-11-10T00:00:00Z
date_updated: 2026-04-07T13:29:45Z
day: '10'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/14506
ec_funded: 1
file:
- access_level: closed
checksum: 521c72818d720a52b377207b2ee87b6a
content_type: application/x-zip-compressed
creator: cchlebak
date_created: 2023-11-23T10:29:55Z
date_updated: 2023-11-23T10:29:55Z
file_id: '14598'
file_name: thesis_yeo.zip
file_size: 3037720
relation: source_file
- access_level: open_access
checksum: 0ed5d16899687aecf13d843c9878c9f2
content_type: application/pdf
creator: cchlebak
date_created: 2023-11-23T10:30:08Z
date_updated: 2023-11-23T10:30:08Z
file_id: '14599'
file_name: thesis_yeo.pdf
file_size: 2717256
relation: main_file
success: 1
file_date_updated: 2023-11-23T10:30:08Z
has_accepted_license: '1'
language:
- iso: eng
month: '11'
oa: 1
oa_version: Published Version
page: '162'
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '13238'
relation: part_of_dissertation
status: deleted
- id: '9969'
relation: part_of_dissertation
status: public
- id: '14490'
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: Advances in efficiency and privacy in payment channel network analysis
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2023'
...
---
OA_place: publisher
_id: '10035'
abstract:
- lang: eng
text: 'Many security definitions come in two flavors: a stronger “adaptive” flavor,
where the adversary can arbitrarily make various choices during the course of
the attack, and a weaker “selective” flavor where the adversary must commit to
some or all of their choices a-priori. For example, in the context of identity-based
encryption, selective security requires the adversary to decide on the identity
of the attacked party at the very beginning of the game whereas adaptive security
allows the attacker to first see the master public key and some secret keys before
making this choice. Often, it appears to be much easier to achieve selective security
than it is to achieve adaptive security. A series of several recent works shows
how to cleverly achieve adaptive security in several such scenarios including
generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and
Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition
that they share a common technique, the connection was never made precise. In
this work we present a new framework (published at Crypto ’17 [JKK+17a]) that
connects all of these works and allows us to present them in a unified and simplified
fashion. Having the framework in place, we show how to achieve adaptive security
for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the
first adaptive security proofs for continuous group key agreement protocols (published
at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that
currently used proof techniques cannot lead to significantly better security guarantees
for "graph-building" games (published at TCC ’21 [KKPW21a]). These games cover
generalized selective decryption, as well as the security of prominent constructions
for constrained PRFs, continuous group key agreement, and proxy re-encryption.
Finally, we revisit the adaptive security of Yao’s garbled circuits and extend
the analysis of Jafargholi and Wichs in two directions: While they prove adaptive
security only for a modified construction with increased online complexity, we
provide the first positive results for the original construction by Yao (published
at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi
and Wichs are essentially optimal by showing that no black-box reduction can provide
a significantly better security bound (published at Crypto ’21 [KKPW21c]).'
acknowledgement: "I want to acknowledge the funding by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
citation:
ama: Klein K. On the adaptive security of graph-based games. 2021. doi:10.15479/at:ista:10035
apa: Klein, K. (2021). On the adaptive security of graph-based games. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:10035
chicago: Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute
of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10035.
ieee: K. Klein, “On the adaptive security of graph-based games,” Institute of Science
and Technology Austria, 2021.
ista: Klein K. 2021. On the adaptive security of graph-based games. Institute of
Science and Technology Austria.
mla: Klein, Karen. On the Adaptive Security of Graph-Based Games. Institute
of Science and Technology Austria, 2021, doi:10.15479/at:ista:10035.
short: K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science
and Technology Austria, 2021.
corr_author: '1'
date_created: 2021-09-23T07:31:44Z
date_published: 2021-09-23T00:00:00Z
date_updated: 2026-07-06T13:16:17Z
day: '23'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/at:ista:10035
ec_funded: 1
file:
- access_level: open_access
checksum: 73a44345c683e81f3e765efbf86fdcc5
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-04T12:22:33Z
date_updated: 2021-10-04T12:22:33Z
file_id: '10082'
file_name: thesis_pdfa.pdf
file_size: 2104726
relation: main_file
success: 1
- access_level: closed
checksum: 7b80df30a0e686c3ef6a56d4e1c59e29
content_type: application/x-zip-compressed
creator: cchlebak
date_created: 2021-10-05T07:04:37Z
date_updated: 2022-03-10T12:15:18Z
file_id: '10085'
file_name: thesis_final (1).zip
file_size: 9538359
relation: source_file
file_date_updated: 2022-03-10T12:15:18Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '276'
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10041'
relation: part_of_dissertation
status: public
- id: '10049'
relation: part_of_dissertation
status: public
- id: '637'
relation: part_of_dissertation
status: public
- id: '6430'
relation: part_of_dissertation
status: public
- id: '10044'
relation: part_of_dissertation
status: public
- id: '10048'
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 the adaptive security of graph-based games
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: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2021'
...
---
OA_place: publisher
_id: '7896'
abstract:
- lang: eng
text: "A search problem lies in the complexity class FNP if a solution to the given
instance of the problem can be verified efficiently. The complexity class TFNP
consists of all search problems in FNP that are total in the sense that a solution
is guaranteed to exist. TFNP contains a host of interesting problems from fields
such as algorithmic game theory, computational topology, number theory and combinatorics.
Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead,
one studies its syntactic subclasses which are defined based on the combinatorial
principle used to argue totality. Of particular interest is the subclass PPAD,
which contains important problems\r\nlike computing Nash equilibrium for bimatrix
games and computational counterparts of several fixed-point theorems as complete.
In the thesis, we undertake the study of averagecase hardness of TFNP, and in
particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness
of PPAD before a series of recent results showed how to achieve it using a cryptographic
primitive called program obfuscation.\r\nHowever, it is currently not known how
to construct program obfuscation from standard cryptographic assumptions. Therefore,
it is desirable to relax the assumption under which average-case hardness of PPAD
can be shown. In the thesis we take a step in this direction. First, we show that
assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to
factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average
in the random-oracle model. Then we strengthen this result to show that the average-case
hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform,
a well-known technique used to compile a public-coin interactive protocol into
a non-interactive one. As a corollary, we obtain average-case hardness for PPAD
in the random-oracle model assuming the worst-case hardness of #SAT. Moreover,
the above results can all be strengthened to obtain average-case hardness for
the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable
procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable,
we mean that every intermediate state of the computation includes a proof of its
correctness, and the proof can be updated and verified in polynomial time. Previous
constructions of such procedures relied on strong, non-standard assumptions. Instead,
we introduce a technique called recursive proof-merging to obtain the same from
weaker assumptions. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
citation:
ama: Kamath Hosdurg C. On the average-case hardness of total search problems. 2020.
doi:10.15479/AT:ISTA:7896
apa: Kamath Hosdurg, C. (2020). On the average-case hardness of total search
problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896
chicago: Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search
Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.
ieee: C. Kamath Hosdurg, “On the average-case hardness of total search problems,”
Institute of Science and Technology Austria, 2020.
ista: Kamath Hosdurg C. 2020. On the average-case hardness of total search problems.
Institute of Science and Technology Austria.
mla: Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.
short: C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems,
Institute of Science and Technology Austria, 2020.
corr_author: '1'
date_created: 2020-05-26T14:08:55Z
date_published: 2020-05-25T00:00:00Z
date_updated: 2026-04-08T07:24:42Z
day: '25'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrPi
doi: 10.15479/AT:ISTA:7896
ec_funded: 1
file:
- access_level: open_access
checksum: b39e2e1c376f5819b823fb7077491c64
content_type: application/pdf
creator: dernst
date_created: 2020-05-26T14:08:13Z
date_updated: 2020-07-14T12:48:04Z
file_id: '7897'
file_name: 2020_Thesis_Kamath.pdf
file_size: 1622742
relation: main_file
- access_level: closed
checksum: 8b26ba729c1a85ac6bea775f5d73cdc7
content_type: application/x-zip-compressed
creator: dernst
date_created: 2020-05-26T14:08:23Z
date_updated: 2020-07-14T12:48:04Z
file_id: '7898'
file_name: Thesis_Kamath.zip
file_size: 15301529
relation: source_file
file_date_updated: 2020-07-14T12:48:04Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '126'
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6677'
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 the average-case hardness of total search problems
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: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2020'
...
---
OA_place: publisher
_id: '83'
abstract:
- lang: eng
text: "A proof system is a protocol between a prover and a verifier over a common
input in which an honest prover convinces the verifier of the validity of true
statements. Motivated by the success of decentralized cryptocurrencies, exemplified
by Bitcoin, the focus of this thesis will be on proof systems which found applications
in some sustainable alternatives to Bitcoin, such as the Spacemint and Chia cryptocurrencies.
In particular, we focus on proofs of space and proofs of sequential work.\r\nProofs
of space (PoSpace) were suggested as more ecological, economical, and egalitarian
alternative to the energy-wasteful proof-of-work mining of Bitcoin. However, the
state-of-the-art constructions of PoSpace are based on sophisticated graph pebbling
lower bounds, and are therefore complex. Moreover, when these PoSpace are used
in cryptocurrencies like Spacemint, miners can only start mining after ensuring
that a commitment to their space is already added in a special transaction to
the blockchain. Proofs of sequential work (PoSW) are proof systems in which a
prover, upon receiving a statement x and a time parameter T, computes a proof
which convinces the verifier that T time units had passed since x was received.
Whereas Spacemint assumes synchrony to retain some interesting Bitcoin dynamics,
Chia requires PoSW with unique proofs, i.e., PoSW in which it is hard to come
up with more than one accepting proof for any true statement. In this thesis we
construct simple and practically-efficient PoSpace and PoSW. When using our PoSpace
in cryptocurrencies, miners can start mining on the fly, like in Bitcoin, and
unlike current constructions of PoSW, which either achieve efficient verification
of sequential work, or faster-than-recomputing verification of correctness of
proofs, but not both at the same time, ours achieve the best of these two worlds."
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Hamza M
full_name: Abusalah, Hamza M
id: 40297222-F248-11E8-B48F-1D18A9856A87
last_name: Abusalah
citation:
ama: Abusalah HM. Proof systems for sustainable decentralized cryptocurrencies.
2018. doi:10.15479/AT:ISTA:TH_1046
apa: Abusalah, H. M. (2018). Proof systems for sustainable decentralized cryptocurrencies.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:TH_1046
chicago: Abusalah, Hamza M. “Proof Systems for Sustainable Decentralized Cryptocurrencies.”
Institute of Science and Technology Austria, 2018. https://doi.org/10.15479/AT:ISTA:TH_1046.
ieee: H. M. Abusalah, “Proof systems for sustainable decentralized cryptocurrencies,”
Institute of Science and Technology Austria, 2018.
ista: Abusalah HM. 2018. Proof systems for sustainable decentralized cryptocurrencies.
Institute of Science and Technology Austria.
mla: Abusalah, Hamza M. Proof Systems for Sustainable Decentralized Cryptocurrencies.
Institute of Science and Technology Austria, 2018, doi:10.15479/AT:ISTA:TH_1046.
short: H.M. Abusalah, Proof Systems for Sustainable Decentralized Cryptocurrencies,
Institute of Science and Technology Austria, 2018.
corr_author: '1'
date_created: 2018-12-11T11:44:32Z
date_published: 2018-09-05T00:00:00Z
date_updated: 2026-04-08T14:10:22Z
day: '05'
ddc:
- '004'
degree_awarded: PhD
department:
- _id: KrPi
doi: 10.15479/AT:ISTA:TH_1046
ec_funded: 1
file:
- access_level: open_access
checksum: c4b5f7d111755d1396787f41886fc674
content_type: application/pdf
creator: dernst
date_created: 2019-04-09T06:43:41Z
date_updated: 2020-07-14T12:48:11Z
file_id: '6245'
file_name: 2018_Thesis_Abusalah.pdf
file_size: 876241
relation: main_file
- access_level: closed
checksum: 0f382ac56b471c48fd907d63eb87dafe
content_type: application/x-gzip
creator: dernst
date_created: 2019-04-09T06:43:41Z
date_updated: 2020-07-14T12:48:11Z
file_id: '6246'
file_name: 2018_Thesis_Abusalah_source.tar.gz
file_size: 2029190
relation: source_file
file_date_updated: 2020-07-14T12:48:11Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '59'
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '7971'
pubrep_id: '1046'
related_material:
record:
- id: '559'
relation: part_of_dissertation
status: public
- id: '1236'
relation: part_of_dissertation
status: public
- id: '1235'
relation: part_of_dissertation
status: public
- id: '1229'
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: Proof systems for sustainable decentralized cryptocurrencies
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2018'
...