---
OA_place: publisher
OA_type: hybrid
_id: '22006'
abstract:
- lang: eng
text: Runtime monitoring checks, during execution, whether a partial signal produced
by a hybrid system satisfies its specification. Signal First-Order Logic (SFO)
offers expressive real-time specifications over such signals, but currently comes
only with Boolean semantics and has no tool support. We provide the first robustness-based
quantitative semantics for SFO, enabling the expression and evaluation of rich
real-time properties beyond the scope of existing formalisms such as Signal Temporal
Logic. To enable online monitoring, we identify a past-time fragment of SFO and
give a pastification procedure that transforms bounded-response SFO formulas into
equisatisfiable formulas in this fragment. We then develop an efficient runtime
monitoring algorithm for this past-time fragment and evaluate its performance
on a set of benchmarks, demonstrating the practicality and effectiveness of our
approach. To the best of our knowledge, this is the first publicly available prototype
for online quantitative monitoring of full SFO.
acknowledgement: We thank the anonymous reviewers for their helpful comments. This
work was supported by the European Research Council (ERC) Grants VAMOS (No. 101020093)
and HYPER (No. 101055412), and by the Advanced Research and Invention Agency under
the Safeguarded AI programme (MSAI-PR01-P047).
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Marek
full_name: Chalupa, Marek
id: 87e34708-d6c6-11ec-9f5b-9391e7be2463
last_name: Chalupa
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Naci E
full_name: Sarac, Naci E
id: 8C6B42F8-C8E6-11E9-A03A-F2DCE5697425
last_name: Sarac
- first_name: Zhengqi
full_name: Yu, Zhengqi
id: 20aa2ae8-f2f1-11ed-bbfa-8205053f1342
last_name: Yu
orcid: 0000-0002-4993-773X
citation:
ama: 'Chalupa M, Henzinger TA, Sarac NE, Yu E. Quantitative monitoring of Signal
First-Order logic. In: 27th International Symposium on Formal Methods.
Vol 16557. Springer Nature; 2026:214-233. doi:10.1007/978-3-032-26220-2_11'
apa: 'Chalupa, M., Henzinger, T. A., Sarac, N. E., & Yu, E. (2026). Quantitative
monitoring of Signal First-Order logic. In 27th International Symposium on
Formal Methods (Vol. 16557, pp. 214–233). Tokyo, Japan: Springer Nature. https://doi.org/10.1007/978-3-032-26220-2_11'
chicago: Chalupa, Marek, Thomas A Henzinger, Naci E Sarac, and Emily Yu. “Quantitative
Monitoring of Signal First-Order Logic.” In 27th International Symposium on
Formal Methods, 16557:214–33. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-26220-2_11.
ieee: M. Chalupa, T. A. Henzinger, N. E. Sarac, and E. Yu, “Quantitative monitoring
of Signal First-Order logic,” in 27th International Symposium on Formal Methods,
Tokyo, Japan, 2026, vol. 16557, pp. 214–233.
ista: 'Chalupa M, Henzinger TA, Sarac NE, Yu E. 2026. Quantitative monitoring of Signal
First-Order logic. 27th International Symposium on Formal Methods. FM: Formal
Methods, LNCS, vol. 16557, 214–233.'
mla: Chalupa, Marek, et al. “Quantitative Monitoring of Signal First-Order Logic.”
27th International Symposium on Formal Methods, vol. 16557, Springer Nature,
2026, pp. 214–33, doi:10.1007/978-3-032-26220-2_11.
short: M. Chalupa, T.A. Henzinger, N.E. Sarac, E. Yu, in:, 27th International Symposium
on Formal Methods, Springer Nature, 2026, pp. 214–233.
conference:
end_date: 2026-05-22
location: Tokyo, Japan
name: 'FM: Formal Methods'
start_date: 2026-05-18
das_tickbox: '0'
date_created: 2026-06-14T22:01:44Z
date_published: 2026-05-18T00:00:00Z
date_updated: 2026-06-22T08:21:09Z
day: '18'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-032-26220-2_11
ec_funded: 1
external_id:
arxiv:
- '2603.00728'
file:
- access_level: open_access
checksum: 7055199ecb985e9e2e272f4988827067
content_type: application/pdf
creator: dernst
date_created: 2026-06-22T08:18:41Z
date_updated: 2026-06-22T08:18:41Z
file_id: '22113'
file_name: 2026_LNCS_Chalupa.pdf
file_size: 849237
relation: main_file
success: 1
file_date_updated: 2026-06-22T08:18:41Z
has_accepted_license: '1'
intvolume: ' 16557'
keyword:
- Signal first-order logic
- Robustness-based quantitative semantics
- Online runtime monitoring
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 214-233
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 27th International Symposium on Formal Methods
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032262196'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Quantitative monitoring of Signal First-Order logic
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: 16557
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21042'
abstract:
- lang: eng
text: "Many blockchains such as Ethereum execute all incoming transactions sequentially
significantly limiting the potential throughput. A common approach to scale execution
is parallel execution engines that fully utilize modern multi-core architectures.
Parallel execution is then either done optimistically, by executing transactions
in parallel and detecting conflicts on the fly, or guided, by requiring exhaustive
client transaction hints and scheduling transactions accordingly.\r\n\r\nHowever,
recent studies have shown that the performance of parallel execution engines depends
on the nature of the underlying workload. In fact, in some cases, only a 60% speed-up
compared to sequential execution could be obtained. This is the case, as transactions
that access the same resources must be executed sequentially. For example, if
10% of the transactions in a block access the same resource, the execution cannot
meaningfully scale beyond 10 cores. Therefore, a single popular application can
bottleneck the execution and limit the potential throughput.\r\n\r\nIn this paper,
we introduce Anthemius, a block construction algorithm that optimizes parallel
transaction execution throughput. We evaluate Anthemius exhaustively under a range
of workloads, and show that Anthemius enables the underlying parallel execution
engine to process over twice as many transactions."
acknowledgement: This work was supported by the Austrian Science Fund (FWF) SFB project
SpyCoDe F8502 and the Vienna Science and Technology Fund (WWTF) project SCALE2 CT22-045.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Ray
full_name: Neiheiser, Ray
id: f09651b9-fec0-11ec-b5d8-934aff0e52a4
last_name: Neiheiser
orcid: 0000-0001-7227-8309
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
orcid: 0000-0002-8827-3382
citation:
ama: 'Neiheiser R, Kokoris Kogias E. Anthemius: Efficient and modular block assembly
for concurrent execution. In: 29th International Conference on Financial Cryptography
and Data Security. Vol 15751. Springer Nature; 2026:307-323. doi:10.1007/978-3-032-07024-1_18'
apa: 'Neiheiser, R., & Kokoris Kogias, E. (2026). Anthemius: Efficient and modular
block assembly for concurrent execution. In 29th International Conference on
Financial Cryptography and Data Security (Vol. 15751, pp. 307–323). Miyakojima,
Japan: Springer Nature. https://doi.org/10.1007/978-3-032-07024-1_18'
chicago: 'Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient
and Modular Block Assembly for Concurrent Execution.” In 29th International
Conference on Financial Cryptography and Data Security, 15751:307–23. Springer
Nature, 2026. https://doi.org/10.1007/978-3-032-07024-1_18.'
ieee: 'R. Neiheiser and E. Kokoris Kogias, “Anthemius: Efficient and modular block
assembly for concurrent execution,” in 29th International Conference on Financial
Cryptography and Data Security, Miyakojima, Japan, 2026, vol. 15751, pp. 307–323.'
ista: 'Neiheiser R, Kokoris Kogias E. 2026. Anthemius: Efficient and modular block
assembly for concurrent execution. 29th International Conference on Financial
Cryptography and Data Security. FC: Financial Cryptography and Data Security,
LNCS, vol. 15751, 307–323.'
mla: 'Neiheiser, Ray, and Eleftherios Kokoris Kogias. “Anthemius: Efficient and Modular
Block Assembly for Concurrent Execution.” 29th International Conference on
Financial Cryptography and Data Security, vol. 15751, Springer Nature, 2026,
pp. 307–23, doi:10.1007/978-3-032-07024-1_18.'
short: R. Neiheiser, E. Kokoris Kogias, in:, 29th International Conference on Financial
Cryptography and Data Security, Springer Nature, 2026, pp. 307–323.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
corr_author: '1'
date_created: 2026-01-25T23:01:40Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-02-12T13:39:07Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-032-07024-1_18
external_id:
arxiv:
- '2502.10074'
intvolume: ' 15751'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2502.10074
month: '01'
oa: 1
oa_version: Preprint
page: 307-323
project:
- _id: 34a1b658-11ca-11ed-8bc3-c75229f0241e
grant_number: F8502
name: Interface Theory for Security and Privacy
- _id: 7bdd2f70-9f16-11ee-852c-b7950bc6d277
grant_number: ICT22-045
name: SeCure, privAte, and interoperabLe layEr 2
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070234'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Anthemius: Efficient and modular block assembly for concurrent execution'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15751
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21044'
abstract:
- lang: eng
text: 'Scalability is a crucial requirement for modern large-scale systems, enabling
elasticity and ensuring responsiveness under varying load. While cloud systems
have achieved scalable architectures, blockchain systems remain constrained by
the need to over-provision validator machines to handle peak load. This leads
to resource inefficiency, poor cost scaling, and limits on performance. To address
these challenges, we introduce Pilotfish, the first scale-out transaction execution
engine for blockchains. Pilotfish enables validators to scale horizontally by
distributing transaction execution across multiple worker machines, allowing elasticity
without compromising consistency or determinism. It integrates seamlessly with
the lazy blockchain architecture, completing the missing piece of execution elasticity.
To achieve this, Pilotfish tackles several key challenges: ensuring scalable and
strongly consistent distributed transactions, handling partial crash recovery
with lightweight replication, and maintaining concurrency with a novel versioned-queue
scheduling algorithm. Our evaluation shows that Pilotfish scales linearly up to
at least eight workers per validator for compute-bound workloads, while maintaining
low latency. By solving scalable execution, Pilotfish brings blockchains closer
to achieving end-to-end elasticity, unlocking new possibilities for efficient
and adaptable blockchain systems.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Quentin
full_name: Kniep, Quentin
last_name: Kniep
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
orcid: 0000-0002-8827-3382
- first_name: Alberto
full_name: Sonnino, Alberto
last_name: Sonnino
- first_name: Igor
full_name: Zablotchi, Igor
last_name: Zablotchi
- first_name: Nuda
full_name: Zhang, Nuda
last_name: Zhang
citation:
ama: 'Kniep Q, Kokoris Kogias E, Sonnino A, Zablotchi I, Zhang N. Pilotfish: Distributed
execution for scalable blockchains. In: 29th International Conference on Financial
Cryptography and Data Security. Vol 15751. Springer Nature; 2026:287-306.
doi:10.1007/978-3-032-07024-1_17'
apa: 'Kniep, Q., Kokoris Kogias, E., Sonnino, A., Zablotchi, I., & Zhang, N.
(2026). Pilotfish: Distributed execution for scalable blockchains. In 29th
International Conference on Financial Cryptography and Data Security (Vol.
15751, pp. 287–306). Miyakojima, Japan: Springer Nature. https://doi.org/10.1007/978-3-032-07024-1_17'
chicago: 'Kniep, Quentin, Eleftherios Kokoris Kogias, Alberto Sonnino, Igor Zablotchi,
and Nuda Zhang. “Pilotfish: Distributed Execution for Scalable Blockchains.” In
29th International Conference on Financial Cryptography and Data Security,
15751:287–306. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-07024-1_17.'
ieee: 'Q. Kniep, E. Kokoris Kogias, A. Sonnino, I. Zablotchi, and N. Zhang, “Pilotfish:
Distributed execution for scalable blockchains,” in 29th International Conference
on Financial Cryptography and Data Security, Miyakojima, Japan, 2026, vol.
15751, pp. 287–306.'
ista: 'Kniep Q, Kokoris Kogias E, Sonnino A, Zablotchi I, Zhang N. 2026. Pilotfish:
Distributed execution for scalable blockchains. 29th International Conference
on Financial Cryptography and Data Security. FC: Financial Cryptography and Data
Security, LNCS, vol. 15751, 287–306.'
mla: 'Kniep, Quentin, et al. “Pilotfish: Distributed Execution for Scalable Blockchains.”
29th International Conference on Financial Cryptography and Data Security,
vol. 15751, Springer Nature, 2026, pp. 287–306, doi:10.1007/978-3-032-07024-1_17.'
short: Q. Kniep, E. Kokoris Kogias, A. Sonnino, I. Zablotchi, N. Zhang, in:, 29th
International Conference on Financial Cryptography and Data Security, Springer
Nature, 2026, pp. 287–306.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
date_created: 2026-01-25T23:01:41Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-02-16T07:56:09Z
day: '01'
doi: 10.1007/978-3-032-07024-1_17
external_id:
arxiv:
- '2401.16292'
intvolume: ' 15751'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2401.16292
month: '01'
oa: 1
oa_version: Preprint
page: 287-306
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070234'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Pilotfish: Distributed execution for scalable blockchains'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15751
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21134'
abstract:
- lang: eng
text: "The Nakamoto consensus protocol underlying the Bitcoin blockchain uses proof
of work as a voting mechanism. Honest miners who contribute hashing power towards
securing the chain try to extend the longest chain they are aware of. Despite
its simplicity, Nakamoto consensus achieves meaningful security guarantees assuming
that at any point in time, a majority of the hashing power is controlled by honest
parties. This also holds under “resource variability”, i.e., if the total hashing
power varies greatly over time.\r\nProofs of space (PoSpace) have been suggested
as a more sustainable replacement for proofs of work. Unfortunately, no construction
of a “longest-chain” blockchain based on PoSpace, that is secure under dynamic
availability, is known. In this work, we prove that without additional assumptions
no such protocol exists. We exactly quantify this impossibility result by proving
a bound on the length of the fork required for double spending as a function of
the adversarial capabilities. This bound holds for any chain selection rule, and
we also show a chain selection rule (albeit a very strange one) that almost matches
this bound.\r\nThe Nakamoto consensus protocol underlying the Bitcoin blockchain
uses proof of work as a voting mechanism. Honest miners who contribute hashing
power towards securing the chain try to extend the longest chain they are aware
of. Despite its simplicity, Nakamoto consensus achieves meaningful security guarantees
assuming that at any point in time, a majority of the hashing power is controlled
by honest parties. This also holds under “resource variability”, i.e., if the
total hashing power varies greatly over time.\r\n\r\nProofs of space (PoSpace)
have been suggested as a more sustainable replacement for proofs of work. Unfortunately,
no construction of a “longest-chain” blockchain based on PoSpace, that is secure
under dynamic availability, is known. In this work, we prove that without additional
assumptions no such protocol exists. We exactly quantify this impossibility result
by proving a bound on the length of the fork required for double spending as a
function of the adversarial capabilities. This bound holds for any chain selection
rule, and we also show a chain selection rule (albeit a very strange one) that
almost matches this bound.\r\n\r\nConcretely, we consider a security game in which
the honest parties at any point control 0 > 1\r\n times more space than the adversary.
The adversary can change the honest space by a factor 1+- E with every block (dynamic
availability), and “replotting” the space (which allows answering two challenges
using the same space) takes as much time as p blocks.\r\nWe prove that no matter
what chain selection rule is used, in this game the adversary can create a fork
of length o^2 . p/E that will be picked as the winner by the chain selection rule.\r\nWe
also provide an upper bound that matches the lower bound up to a factor o. There
exists a chain selection rule (albeit a very strange one) which in the above game
requires forks of length at least o . p/E\r\nOur results show the necessity of
additional assumptions to create a secure PoSpace based longest-chain blockchain.
The Chia network in addition to PoSpace uses a verifiable delay function. Our
bounds show that an additional primitive like that is necessary."
acknowledgement: This research was funded in whole or in part by the Austrian Science
Fund (FWF) 10.55776/F85.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Baig MA, Pietrzak KZ. On the (in)security of Proofs-of-space based longest-chain
blockchains. In: 29th International Conference on Financial Cryptography and
Data Security. Vol 15752. Springer Nature; 2026:127-142. doi:10.1007/978-3-032-07035-7_8'
apa: 'Baig, M. A., & Pietrzak, K. Z. (2026). On the (in)security of Proofs-of-space
based longest-chain blockchains. In 29th International Conference on Financial
Cryptography and Data Security (Vol. 15752, pp. 127–142). Miyakojima, Japan:
Springer Nature. https://doi.org/10.1007/978-3-032-07035-7_8'
chicago: Baig, Mirza Ahad, and Krzysztof Z Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” In 29th International Conference on Financial
Cryptography and Data Security, 15752:127–42. Springer Nature, 2026. https://doi.org/10.1007/978-3-032-07035-7_8.
ieee: M. A. Baig and K. Z. Pietrzak, “On the (in)security of Proofs-of-space based
longest-chain blockchains,” in 29th International Conference on Financial Cryptography
and Data Security, Miyakojima, Japan, 2026, vol. 15752, pp. 127–142.
ista: 'Baig MA, Pietrzak KZ. 2026. On the (in)security of Proofs-of-space based
longest-chain blockchains. 29th International Conference on Financial Cryptography
and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 15752,
127–142.'
mla: Baig, Mirza Ahad, and Krzysztof Z. Pietrzak. “On the (in)Security of Proofs-of-Space
Based Longest-Chain Blockchains.” 29th International Conference on Financial
Cryptography and Data Security, vol. 15752, Springer Nature, 2026, pp. 127–42,
doi:10.1007/978-3-032-07035-7_8.
short: M.A. Baig, K.Z. Pietrzak, in:, 29th International Conference on Financial
Cryptography and Data Security, Springer Nature, 2026, pp. 127–142.
conference:
end_date: 2025-04-18
location: Miyakojima, Japan
name: 'FC: Financial Cryptography and Data Security'
start_date: 2025-04-14
corr_author: '1'
date_created: 2026-02-01T23:01:43Z
date_published: 2026-01-01T00:00:00Z
date_updated: 2026-04-15T08:45:18Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-032-07035-7_8
external_id:
arxiv:
- '2505.14891'
intvolume: ' 15752'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2505.14891
month: '01'
oa: 1
oa_version: Preprint
page: 127-142
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 29th International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032070340'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '21651'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: On the (in)security of Proofs-of-space based longest-chain blockchains
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15752
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21135'
abstract:
- lang: eng
text: Three-dimensional (3D) microscopy data is often anisotropic with significantly
lower resolution (up to 8x) along the z axis than along the xy axes. Computationally
generating plausible isotropic resolution from anisotropic imaging data would
benefit the visual analysis of large-scale volumes. This paper proposes niiv,
a self-supervised method for isotropic reconstruction of 3D microscopy data that
can quickly produce images at arbitrary output resolutions. The representation
embeds a learned latent code within a neural field that describes the implicit
higher-resolution isotropic image region. We use an attention-guided latent interpolation
approach, which allows flexible information exchange over a local latent neighborhood.
Under isotropic volume assumptions, we self-supervise this representation on low-/high-resolution
lateral image pairs to reconstruct an isotropic volume from low-resolution axial
images. We evaluate our method on simulated and real anisotropic electron (EM)
and light microscopy (LM) data. Compared to diffusion-based baselines, niiv shows
improved reconstruction quality (+1 dB PSNR) and is over three orders of magnitude
faster (1,000x) to infer. Specifically, niiv reconstructs a 128^3 voxel volume
in 2/10th of a second, renderable at varying (continuous) high resolutions for
display. Our code is available at https://github.com/jakobtroidl/niiv-miccai.
acknowledgement: This work was supported by NIH grants 1U01NS132158 and R01HD104969.
We thank the reviewers for their constructive feedback.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jakob
full_name: Troidl, Jakob
last_name: Troidl
- first_name: Yiqing
full_name: Liang, Yiqing
last_name: Liang
- first_name: Johanna
full_name: Beyer, Johanna
last_name: Beyer
- first_name: Mojtaba
full_name: Tavakoli, Mojtaba
id: 3A0A06F4-F248-11E8-B48F-1D18A9856A87
last_name: Tavakoli
orcid: 0000-0002-7667-6854
- first_name: Johann G
full_name: Danzl, Johann G
id: 42EFD3B6-F248-11E8-B48F-1D18A9856A87
last_name: Danzl
orcid: 0000-0001-8559-3973
- first_name: Markus
full_name: Hadwiger, Markus
last_name: Hadwiger
- first_name: Hanspeter
full_name: Pfister, Hanspeter
last_name: Pfister
- first_name: James
full_name: Tompkin, James
last_name: Tompkin
citation:
ama: 'Troidl J, Liang Y, Beyer J, et al. niiv: Interactive Self-supervised Neural
Implicit Isotropic Volume Reconstruction. In: 1st International Workshop on
Efficient Medical Artificial Intelligence. Vol 16318. Springer Nature; 2026:257-267.
doi:10.1007/978-3-032-13961-0_26'
apa: 'Troidl, J., Liang, Y., Beyer, J., Tavakoli, M., Danzl, J. G., Hadwiger, M.,
… Tompkin, J. (2026). niiv: Interactive Self-supervised Neural Implicit Isotropic
Volume Reconstruction. In 1st International Workshop on Efficient Medical Artificial
Intelligence (Vol. 16318, pp. 257–267). Daejeon, South Korea: Springer Nature.
https://doi.org/10.1007/978-3-032-13961-0_26'
chicago: 'Troidl, Jakob, Yiqing Liang, Johanna Beyer, Mojtaba Tavakoli, Johann G
Danzl, Markus Hadwiger, Hanspeter Pfister, and James Tompkin. “Niiv: Interactive
Self-Supervised Neural Implicit Isotropic Volume Reconstruction.” In 1st International
Workshop on Efficient Medical Artificial Intelligence, 16318:257–67. Springer
Nature, 2026. https://doi.org/10.1007/978-3-032-13961-0_26.'
ieee: 'J. Troidl et al., “niiv: Interactive Self-supervised Neural Implicit
Isotropic Volume Reconstruction,” in 1st International Workshop on Efficient
Medical Artificial Intelligence, Daejeon, South Korea, 2026, vol. 16318, pp.
257–267.'
ista: 'Troidl J, Liang Y, Beyer J, Tavakoli M, Danzl JG, Hadwiger M, Pfister H,
Tompkin J. 2026. niiv: Interactive Self-supervised Neural Implicit Isotropic Volume
Reconstruction. 1st International Workshop on Efficient Medical Artificial Intelligence.
EMA4MICCAI: Efficient Medical Artificial Intelligence, LNCS, vol. 16318, 257–267.'
mla: 'Troidl, Jakob, et al. “Niiv: Interactive Self-Supervised Neural Implicit Isotropic
Volume Reconstruction.” 1st International Workshop on Efficient Medical Artificial
Intelligence, vol. 16318, Springer Nature, 2026, pp. 257–67, doi:10.1007/978-3-032-13961-0_26.'
short: J. Troidl, Y. Liang, J. Beyer, M. Tavakoli, J.G. Danzl, M. Hadwiger, H. Pfister,
J. Tompkin, in:, 1st International Workshop on Efficient Medical Artificial Intelligence,
Springer Nature, 2026, pp. 257–267.
conference:
end_date: 2025-09-23
location: Daejeon, South Korea
name: 'EMA4MICCAI: Efficient Medical Artificial Intelligence'
start_date: 2025-09-23
date_created: 2026-02-01T23:01:44Z
date_published: 2026-01-03T00:00:00Z
date_updated: 2026-02-16T08:50:50Z
day: '03'
department:
- _id: JoDa
doi: 10.1007/978-3-032-13961-0_26
intvolume: ' 16318'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1101/2024.09.07.611785
month: '01'
oa: 1
oa_version: Preprint
page: 257-267
publication: 1st International Workshop on Efficient Medical Artificial Intelligence
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032139603'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: software
url: https://github.com/jakobtroidl/niiv-miccai
scopus_import: '1'
status: public
title: 'niiv: Interactive Self-supervised Neural Implicit Isotropic Volume Reconstruction'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16318
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21374'
abstract:
- lang: eng
text: "Let . S be a set of distinct points in general position in the\r\nEuclidean
plane. A plane Hamiltonian path on . S is a crossing-free geometric path such
that every point of .S is a vertex of the path. It is\r\nknown that, if. S is
sufficiently large, there exist three edge-disjoint plane\r\nHamiltonian paths
on . S. In this paper we study an edge-constrained\r\nversion of the problem of
finding Hamiltonian paths on a point set. We\r\nfirst consider the problem of
finding a single plane Hamiltonian path . π\r\nwith endpoints .s, t ∈ S and constraints
given by a segment . ab, where\r\n.a, b ∈ S. We consider the following scenarios:
(i) .ab ∈ π; (ii) .ab π. We\r\ncharacterize those quintuples . S, a, b, s, t for
which . π exists. Secondly,\r\nwe consider the problem of finding two plane Hamiltonian
paths . π1, π2\r\non a set . S with constraints given by a segment . ab, where
.a, b ∈ S. We\r\nconsider the following scenarios: (i) .π1 and .π2 share no edges
and .ab is\r\nan edge of . π1; (ii) .π1 and .π2 share no edges and none of them
includes\r\n.ab as an edge; (iii) both .π1 and .π2 include .ab as an edge and
share no\r\nother edges. In all cases, we characterize those triples . S, a, b
for which\r\n.π1 and .π2 exist."
acknowledgement: "We thank the organizers of the HOMONOLO 2024 workshop in Nová Louka,
Czech Republic, for the fruitful atmosphere where the research on this project was
initiated.\r\n\r\nT. Antić, A. Džuklevski, J. Kratochvíl and M. Saumell received
funding from GAČR grant 23–04949X, T.A and A.Dž were additionally supported by GAUK
grant SVV–2025–260822. G. Liotta was supported in part by MUR of Italy, PRIN Project
no. 2022TS4Y3N – EXPAND and PON Project ARS01_00540. J. Fiala was in part supported
by GAČR grant 25-16847S."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Todor
full_name: Antić, Todor
last_name: Antić
- first_name: Aleksa
full_name: Džuklevski, Aleksa
last_name: Džuklevski
- first_name: Jiří
full_name: Fiala, Jiří
last_name: Fiala
- first_name: Jan
full_name: Kratochvíl, Jan
last_name: Kratochvíl
- first_name: Giuseppe
full_name: Liotta, Giuseppe
last_name: Liotta
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
- first_name: Maria
full_name: Saumell, Maria
last_name: Saumell
- first_name: Johannes
full_name: Zink, Johannes
last_name: Zink
citation:
ama: 'Antić T, Džuklevski A, Fiala J, et al. Edge-constrained Hamiltonian paths
on a point set. In: 51st International Conference on Current Trends in Theory
and Practice of Computer Science. Vol 16448. Springer Nature; 2026:532-546.
doi:10.1007/978-3-032-17801-5_39'
apa: 'Antić, T., Džuklevski, A., Fiala, J., Kratochvíl, J., Liotta, G., Saghafian,
M., … Zink, J. (2026). Edge-constrained Hamiltonian paths on a point set. In 51st
International Conference on Current Trends in Theory and Practice of Computer
Science (Vol. 16448, pp. 532–546). Krakow, Poland: Springer Nature. https://doi.org/10.1007/978-3-032-17801-5_39'
chicago: Antić, Todor, Aleksa Džuklevski, Jiří Fiala, Jan Kratochvíl, Giuseppe Liotta,
Morteza Saghafian, Maria Saumell, and Johannes Zink. “Edge-Constrained Hamiltonian
Paths on a Point Set.” In 51st International Conference on Current Trends in
Theory and Practice of Computer Science, 16448:532–46. Springer Nature, 2026.
https://doi.org/10.1007/978-3-032-17801-5_39.
ieee: T. Antić et al., “Edge-constrained Hamiltonian paths on a point set,”
in 51st International Conference on Current Trends in Theory and Practice of
Computer Science, Krakow, Poland, 2026, vol. 16448, pp. 532–546.
ista: 'Antić T, Džuklevski A, Fiala J, Kratochvíl J, Liotta G, Saghafian M, Saumell
M, Zink J. 2026. Edge-constrained Hamiltonian paths on a point set. 51st International
Conference on Current Trends in Theory and Practice of Computer Science. SOFSEM:
Conference on Current Trends in Theory and Practice of Computer Science, LNCS,
vol. 16448, 532–546.'
mla: Antić, Todor, et al. “Edge-Constrained Hamiltonian Paths on a Point Set.” 51st
International Conference on Current Trends in Theory and Practice of Computer
Science, vol. 16448, Springer Nature, 2026, pp. 532–46, doi:10.1007/978-3-032-17801-5_39.
short: T. Antić, A. Džuklevski, J. Fiala, J. Kratochvíl, G. Liotta, M. Saghafian,
M. Saumell, J. Zink, in:, 51st International Conference on Current Trends in Theory
and Practice of Computer Science, Springer Nature, 2026, pp. 532–546.
conference:
end_date: 2026-02-13
location: Krakow, Poland
name: 'SOFSEM: Conference on Current Trends in Theory and Practice of Computer Science'
start_date: 2026-02-09
date_created: 2026-03-01T23:01:40Z
date_published: 2026-02-13T00:00:00Z
date_updated: 2026-03-02T08:49:20Z
day: '13'
department:
- _id: HeEd
doi: 10.1007/978-3-032-17801-5_39
external_id:
arxiv:
- '2511.22526'
intvolume: ' 16448'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2511.22526
month: '02'
oa: 1
oa_version: Preprint
page: 532-546
publication: 51st International Conference on Current Trends in Theory and Practice
of Computer Science
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032178008'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Edge-constrained Hamiltonian paths on a point set
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16448
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '21410'
abstract:
- lang: eng
text: Given a finite set of red and blue points in R^d, the MST-ratio is defined
as the total length of the Euclidean minimum spanning trees of the red points
and the blue points, divided by the length of the Euclidean minimum spanning tree
of their union. The MST-ratio has recently gained attention due to its direct
interpretation in topological models for studying point sets with applications
in spatial biology. The maximum MST-ratio of a point set is the maximum MST-ratio
over all proper colorings of its points by red and blue. We prove that finding
the maximum MST-ratio of a given point set is NP-hard when the dimension is part
of the input. Moreover, we present a quadratic-time 3-approximation algorithm
for this problem. As part of the proof, we show that in any metric space, the
maximum MST-ratio is smaller than 3. Furthermore, we study the average MST-ratio
over all colorings of a set of n points. We show that this average is always at
least n-2/n-1, and for n random points uniformly distributed in a d-dimensional
unit cube, the average tends to (math formular) in expectation as n approaches
infinity.
acknowledgement: "A. J. Ameli—Supported by the project COALESCE (ERC grant no. 853234).\r\nM.
Saghafian—Partially supported by the European Research Council (ERC), grant no.
788183, and by the Wittgenstein Prize, Austrian Science Fund (FWF), grant no. Z
342-N31."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Afrouz
full_name: Jabal Ameli, Afrouz
last_name: Jabal Ameli
- first_name: Faezeh
full_name: Motiei, Faezeh
last_name: Motiei
- first_name: Morteza
full_name: Saghafian, Morteza
id: f86f7148-b140-11ec-9577-95435b8df824
last_name: Saghafian
citation:
ama: 'Jabal Ameli A, Motiei F, Saghafian M. On the MST-ratio: Theoretical bounds
and complexity of finding the maximum. In: 20th International Conference and
Workshops on Algorithms and Computation. Vol 16444. Springer Nature; 2026:386-401.
doi:10.1007/978-981-95-7127-7_26'
apa: 'Jabal Ameli, A., Motiei, F., & Saghafian, M. (2026). On the MST-ratio:
Theoretical bounds and complexity of finding the maximum. In 20th International
Conference and Workshops on Algorithms and Computation (Vol. 16444, pp. 386–401).
Perugia, Italy: Springer Nature. https://doi.org/10.1007/978-981-95-7127-7_26'
chicago: 'Jabal Ameli, Afrouz, Faezeh Motiei, and Morteza Saghafian. “On the MST-Ratio:
Theoretical Bounds and Complexity of Finding the Maximum.” In 20th International
Conference and Workshops on Algorithms and Computation, 16444:386–401. Springer
Nature, 2026. https://doi.org/10.1007/978-981-95-7127-7_26.'
ieee: 'A. Jabal Ameli, F. Motiei, and M. Saghafian, “On the MST-ratio: Theoretical
bounds and complexity of finding the maximum,” in 20th International Conference
and Workshops on Algorithms and Computation, Perugia, Italy, 2026, vol. 16444,
pp. 386–401.'
ista: 'Jabal Ameli A, Motiei F, Saghafian M. 2026. On the MST-ratio: Theoretical
bounds and complexity of finding the maximum. 20th International Conference and
Workshops on Algorithms and Computation. WALCOM: International Conference and
Workshops on Algorithms and Computation, LNCS, vol. 16444, 386–401.'
mla: 'Jabal Ameli, Afrouz, et al. “On the MST-Ratio: Theoretical Bounds and Complexity
of Finding the Maximum.” 20th International Conference and Workshops on Algorithms
and Computation, vol. 16444, Springer Nature, 2026, pp. 386–401, doi:10.1007/978-981-95-7127-7_26.'
short: A. Jabal Ameli, F. Motiei, M. Saghafian, in:, 20th International Conference
and Workshops on Algorithms and Computation, Springer Nature, 2026, pp. 386–401.
conference:
end_date: 2026-03-06
location: Perugia, Italy
name: 'WALCOM: International Conference and Workshops on Algorithms and Computation'
start_date: 2026-03-04
date_created: 2026-03-08T23:01:45Z
date_published: 2026-02-14T00:00:00Z
date_updated: 2026-03-09T10:25:41Z
day: '14'
department:
- _id: HeEd
doi: 10.1007/978-981-95-7127-7_26
ec_funded: 1
external_id:
arxiv:
- '2409.11079'
intvolume: ' 16444'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2409.11079
month: '02'
oa: 1
oa_version: Preprint
page: 386-401
project:
- _id: 266A2E9E-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '788183'
name: Alpha Shape Theory Extended
- _id: 268116B8-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z00342
name: Mathematics, Computer Science
publication: 20th International Conference and Workshops on Algorithms and Computation
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9789819571260'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'On the MST-ratio: Theoretical bounds and complexity of finding the maximum'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16444
year: '2026'
...
---
OA_place: repository
OA_type: green
_id: '20844'
abstract:
- lang: eng
text: "We introduce and construct a new proof system called Non-interactive Arguments
of Knowledge or Space (NArKoS), where a space-bounded prover can convince a verifier
they know a secret, while having access to sufficient space allows one to forge
indistinguishable proofs without the secret.\r\nAn application of NArKoS are space-deniable
proofs, which are proofs of knowledge (say for authentication in access control)
that are sound when executed by a lightweight device like a smart-card or an RFID
chip that cannot have much storage, but are deniable (in the strong sense of online
deniability) as the verifier, like a card reader, can efficiently forge such proofs.\r\nWe
construct NArKoS in the random oracle model using an OR-proof combining a sigma
protocol (for the proof of knowledge of the secret) with a new proof system called
simulatable Proof of Transient Space (simPoTS). We give two different constructions
of simPoTS, one based on labelling graphs with high pebbling complexity, a technique
used in the construction of memory-hard functions and proofs of space, and a more
practical construction based on the verifiable space-hard functions from TCC’24
where a prover must compute a root of a sparse polynomial. In both cases, the
main challenge is making the proofs efficiently simulatable."
acknowledgement: "Jesko Dujmovic: Funded by the European Union (ERC, LACONIC, 101041207).
Views and opinions expressed are however those of the author(s) only and do not
necessarily reflect those of the European Union or the European Research Council.
Neither the European Union nor the granting authority can be held responsible for
them.\r\nChristoph U. Günther and Krzysztof Pietrzak: This research was funded in
whole or in part by the Austrian Science Fund (FWF) 10.55776/F85. For open access
purposes, the author has applied a CC BY public copyright license to any author-accepted
manuscript version arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Jesko
full_name: Dujmovic, Jesko
last_name: Dujmovic
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Dujmovic J, Günther CU, Pietrzak KZ. Space-deniable proofs. In: 23rd International
Conference on Theory of Cryptography. Vol 16271. Springer Nature; 2025:171-202.
doi:10.1007/978-3-032-12290-2_6'
apa: 'Dujmovic, J., Günther, C. U., & Pietrzak, K. Z. (2025). Space-deniable
proofs. In 23rd International Conference on Theory of Cryptography (Vol.
16271, pp. 171–202). Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_6'
chicago: Dujmovic, Jesko, Christoph Ullrich Günther, and Krzysztof Z Pietrzak. “Space-Deniable
Proofs.” In 23rd International Conference on Theory of Cryptography, 16271:171–202.
Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_6.
ieee: J. Dujmovic, C. U. Günther, and K. Z. Pietrzak, “Space-deniable proofs,” in
23rd International Conference on Theory of Cryptography, Aarhus, Denmark,
2025, vol. 16271, pp. 171–202.
ista: 'Dujmovic J, Günther CU, Pietrzak KZ. 2025. Space-deniable proofs. 23rd International
Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
16271, 171–202.'
mla: Dujmovic, Jesko, et al. “Space-Deniable Proofs.” 23rd International Conference
on Theory of Cryptography, vol. 16271, Springer Nature, 2025, pp. 171–202,
doi:10.1007/978-3-032-12290-2_6.
short: J. Dujmovic, C.U. Günther, K.Z. Pietrzak, in:, 23rd International Conference
on Theory of Cryptography, Springer Nature, 2025, pp. 171–202.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:33Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:44:16Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_6
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1723
month: '12'
oa: 1
oa_version: Preprint
page: 171-202
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Space-deniable proofs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20845'
abstract:
- lang: eng
text: "We develop new attacks against the Evasive LWE family of assumptions, in
both the public and private-coin regime. To the best of our knowledge, ours are
the first attacks against Evasive LWE in the public-coin regime, for any instantiation
from the family. Our attacks are summarized below.\r\n\r\nPublic-Coin Attacks.\r\n1.The
recent work by Hseih, Lin and Luo [17] constructed the first Attribute Based Encryption
(ABE) for unbounded depth circuits by relying on the “circular” evasive LWE assumption.
This assumption has been popularly considered as a safe, public-coin instance
of Evasive LWE in contrast to its “private-coin” cousins (for instance, see [10,
11]).\r\nWe provide the first attack against this assumption, challenging the
widely held belief that this is a public-coin assumption.\r\n2. We demonstrate
a counter-example against vanilla public-coin evasive LWE by Wee [26] in an unnatural
parameter regime. Our attack crucially relies on the error in the pre-condition
being larger than the error in the post-condition, necessitating a refinement
of the assumption.\r\n\r\nPrivate-Coin Attacks.\r\n1. The recent work by Agrawal,
Kumari and Yamada [2] constructed the first functional encryption scheme for pseudorandom
functionalities (PRFE) and extended this to obfuscation for pseudorandom functionalities
(PRIO) [4] by relying on private-coin evasive LWE. We provide a new attack against
the assumption stated in the first posting of their work (subsequently refined
to avoid these attacks).\r\n2. The recent work by Branco et al. [8] (concurrently
to [4]) provides a construction of obfuscation for pseudorandom functionalities
by relying on private-coin evasive LWE. We provide a new attack against their
stated assumption.\r\n3. Branco et al. [8] showed that there exist contrived,
“self-referential” classes of pseudorandom functionalities for which pseudorandom
obfuscation cannot exist. We extend their techniques to develop an analogous result
for pseudorandom functional encryption.\r\n\r\nWhile Evasive LWE was developed
to specifically avoid “zeroizing attacks”, our work shows that in certain settings,
such attacks can still apply."
acknowledgement: "We thank Rachel Lin for expressing concern about the applicability
of “HJL-style” attacks [15] on the construction in [2] during a talk by the first
author about [2]. This was the starting point of the investigation that led us to
develop the attack in [5, Sec 4.1]. The first author also thanks Hoeteck Wee for
sharing his rationale for introducing evasive LWE.\r\nThe first author is supported
by the CyStar center of excellence, the VHAR faculty chair, and the C3iHub fellowship.
The third author thanks Cystar, IIT Madras, for supporting a visit to IIT Madras
during which the collaboration was initiated. The 4th author is partly supported
by JST CREST Grant Number JPMJCR22M1."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Shweta
full_name: Agrawal, Shweta
last_name: Agrawal
- first_name: Anuja
full_name: Modi, Anuja
last_name: Modi
- first_name: Anshu
full_name: Yadav, Anshu
id: dc8f1524-403e-11ee-bf07-9649ad996e21
last_name: Yadav
- first_name: Shota
full_name: Yamada, Shota
last_name: Yamada
citation:
ama: 'Agrawal S, Modi A, Yadav A, Yamada S. Zeroizing attacks against evasive and circular
evasive LWE. In: 23rd International Conference on Theory of Cryptography.
Vol 16269. Springer Nature; 2025:259-290. doi:10.1007/978-3-032-12293-3_9'
apa: 'Agrawal, S., Modi, A., Yadav, A., & Yamada, S. (2025). Zeroizing attacks
against evasive and circular evasive LWE. In 23rd International Conference
on Theory of Cryptography (Vol. 16269, pp. 259–290). Aarhus, Denmark: Springer
Nature. https://doi.org/10.1007/978-3-032-12293-3_9'
chicago: Agrawal, Shweta, Anuja Modi, Anshu Yadav, and Shota Yamada. “Zeroizing
Attacks against Evasive and Circular Evasive LWE.” In 23rd International Conference
on Theory of Cryptography, 16269:259–90. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12293-3_9.
ieee: S. Agrawal, A. Modi, A. Yadav, and S. Yamada, “Zeroizing attacks against evasive
and circular evasive LWE,” in 23rd International Conference on Theory of Cryptography,
Aarhus, Denmark, 2025, vol. 16269, pp. 259–290.
ista: 'Agrawal S, Modi A, Yadav A, Yamada S. 2025. Zeroizing attacks against evasive
and circular evasive LWE. 23rd International Conference on Theory of Cryptography.
TCC: Theory of Cryptography, LNCS, vol. 16269, 259–290.'
mla: Agrawal, Shweta, et al. “Zeroizing Attacks against Evasive and Circular Evasive
LWE.” 23rd International Conference on Theory of Cryptography, vol. 16269,
Springer Nature, 2025, pp. 259–90, doi:10.1007/978-3-032-12293-3_9.
short: S. Agrawal, A. Modi, A. Yadav, S. Yamada, in:, 23rd International Conference
on Theory of Cryptography, Springer Nature, 2025, pp. 259–290.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
date_created: 2025-12-21T23:01:33Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:51:13Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12293-3_9
intvolume: ' 16269'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/375
month: '12'
oa: 1
oa_version: Preprint
page: 259-290
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122926'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Zeroizing attacks against evasive and circular evasive LWE
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16269
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '20846'
abstract:
- lang: eng
text: "CVRFs are PRFs that unify the properties of verifiable and constrained PRFs.
Since they were introduced concurrently by Fuchsbauer and Chandran-Raghuraman-Vinayagamurthy
in 2014, it has been an open problem to construct CVRFs without using heavy machinery
such as multilinear maps, obfuscation or functional encryption.\r\nWe solve this
problem by constructing a prefix-constrained verifiable PRF that does not rely
on the aforementioned assumptions. Essentially, our construction is a verifiable
version of the Goldreich-Goldwasser-Micali PRF. To achieve verifiability we leverage
degree-2 algebraic PRGs and bilinear groups. In short, proofs consist of intermediate
values of the Goldreich-Goldwasser-Micali PRF raised to the exponents of group
elements. These outputs can be verified using pairings since the underlying PRG
is of degree 2.\r\nWe prove the selective security of our construction under the
Decisional Square Diffie-Hellman (DSDH) assumption and a new assumption, which
we dub recursive Decisional Diffie-Hellman (recursive DDH).\r\nWe prove the soundness
of recursive DDH in the generic group model assuming the hardness of the Multivariate
Quadratic (MQ) problem and a new variant thereof, which we call MQ+.\r\nLast,
in terms of applications, we observe that our CVRF is also an exponent (C)VRF
in the plain model. Exponent VRFs were recently introduced by Boneh et al. (Eurocrypt’25)
with various applications to threshold cryptography in mind. In addition to that,
we give further applications for prefix-CVRFs in the blockchain setting, namely,
stake-pooling and compressible randomness beacons."
acknowledgement: "We thank Jonas Steinbach and Gertjan De Mulder for helpful discussions
on BIP 32, Dennis Hofheinz and Julia Kastner for helpful discussions on early prototypes
of our CVRF, and Klaus Kraßnitzer for running pairing benchmarks on his MacBook
Pro.\r\nChristoph U. Günther: This research was funded in whole or in part by the
Austrian Science Fund (FWF) 10.55776/F85. For open access purposes, the author has
applied a CC BY public copyright license to any author-accepted manuscript version
arising from this submission."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Brandt, Nicholas
last_name: Brandt
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Christoph Ullrich
full_name: Günther, Christoph Ullrich
id: ec98511c-eb8e-11eb-b029-edd25d7271a1
last_name: Günther
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
- first_name: Stella
full_name: Wohnig, Stella
last_name: Wohnig
citation:
ama: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. Constrained verifiable
random functions without obfuscation and friends. In: 23rd International Conference
on Theory of Cryptography. Vol 16271. Springer Nature; 2025:478-511. doi:10.1007/978-3-032-12290-2_16'
apa: 'Brandt, N., Cueto Noval, M., Günther, C. U., Ünal, A., & Wohnig, S. (2025).
Constrained verifiable random functions without obfuscation and friends. In 23rd
International Conference on Theory of Cryptography (Vol. 16271, pp. 478–511).
Aarhus, Denmark: Springer Nature. https://doi.org/10.1007/978-3-032-12290-2_16'
chicago: Brandt, Nicholas, Miguel Cueto Noval, Christoph Ullrich Günther, Akin Ünal,
and Stella Wohnig. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” In 23rd International Conference on Theory of Cryptography,
16271:478–511. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-12290-2_16.
ieee: N. Brandt, M. Cueto Noval, C. U. Günther, A. Ünal, and S. Wohnig, “Constrained
verifiable random functions without obfuscation and friends,” in 23rd International
Conference on Theory of Cryptography, Aarhus, Denmark, 2025, vol. 16271, pp.
478–511.
ista: 'Brandt N, Cueto Noval M, Günther CU, Ünal A, Wohnig S. 2025. Constrained
verifiable random functions without obfuscation and friends. 23rd International
Conference on Theory of Cryptography. TCC: Theory of Cryptography, LNCS, vol.
16271, 478–511.'
mla: Brandt, Nicholas, et al. “Constrained Verifiable Random Functions without Obfuscation
and Friends.” 23rd International Conference on Theory of Cryptography,
vol. 16271, Springer Nature, 2025, pp. 478–511, doi:10.1007/978-3-032-12290-2_16.
short: N. Brandt, M. Cueto Noval, C.U. Günther, A. Ünal, S. Wohnig, in:, 23rd International
Conference on Theory of Cryptography, Springer Nature, 2025, pp. 478–511.
conference:
end_date: 2025-12-05
location: Aarhus, Denmark
name: 'TCC: Theory of Cryptography'
start_date: 2025-12-01
corr_author: '1'
date_created: 2025-12-21T23:01:34Z
date_published: 2025-12-05T00:00:00Z
date_updated: 2025-12-29T11:11:29Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-032-12290-2_16
intvolume: ' 16271'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1045
month: '12'
oa: 1
oa_version: Preprint
page: 478-511
project:
- _id: 34a34d57-11ca-11ed-8bc3-a2688a8724e1
grant_number: F8509
name: Security and Privacy by Design for Complex Systems
publication: 23rd International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783032122896'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Constrained verifiable random functions without obfuscation and friends
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16271
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21090'
abstract:
- lang: eng
text: Fairness in AI is traditionally studied as a static property evaluated once,
over a fixed dataset. However, real-world AI systems operate sequentially, with
outcomes and environments evolving over time. This paper proposes a framework
for analysing fairness as a runtime property. Using a minimal yet expressive model
based on sequences of coin tosses with possibly evolving biases, we study the
problems of monitoring and enforcing fairness expressed in either toss outcomes
or coin biases. Since there is no one-size-fits-all solution for either problem,
we provide a summary of monitoring and enforcement strategies, parametrised by
environment dynamics, prediction horizon, and confidence thresholds. For both
problems, we present general results under simple or minimal assumptions. We survey
existing solutions for the monitoring problem for Markovian and additive dynamics,
and existing solutions for the enforcement problem in static settings with known
dynamics.
acknowledgement: 'This work is supported by the European Research Council under Grant
No.: ERC-2020-AdG 101020093.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Filip
full_name: Cano Cordoba, Filip
id: 708cad98-e86a-11ef-8098-bdae2d7c6af1
last_name: Cano Cordoba
orcid: 0000-0002-0783-904X
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Konstantin
full_name: Kueffner, Konstantin
id: 8121a2d0-dc85-11ea-9058-af578f3b4515
last_name: Kueffner
orcid: 0000-0001-8974-2542
citation:
ama: 'Cano Cordoba F, Henzinger TA, Kueffner K. Algorithmic fairness: A runtime
perspective. In: 25th International Conference on Runtime Verification.
Vol 16087. Springer Nature; 2025:1-21. doi:10.1007/978-3-032-05435-7_1'
apa: 'Cano Cordoba, F., Henzinger, T. A., & Kueffner, K. (2025). Algorithmic
fairness: A runtime perspective. In 25th International Conference on Runtime
Verification (Vol. 16087, pp. 1–21). Graz, Austria: Springer Nature. https://doi.org/10.1007/978-3-032-05435-7_1'
chicago: 'Cano Cordoba, Filip, Thomas A Henzinger, and Konstantin Kueffner. “Algorithmic
Fairness: A Runtime Perspective.” In 25th International Conference on Runtime
Verification, 16087:1–21. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-05435-7_1.'
ieee: 'F. Cano Cordoba, T. A. Henzinger, and K. Kueffner, “Algorithmic fairness:
A runtime perspective,” in 25th International Conference on Runtime Verification,
Graz, Austria, 2025, vol. 16087, pp. 1–21.'
ista: 'Cano Cordoba F, Henzinger TA, Kueffner K. 2025. Algorithmic fairness: A runtime
perspective. 25th International Conference on Runtime Verification. RV: Runtime
Verification, LNCS, vol. 16087, 1–21.'
mla: 'Cano Cordoba, Filip, et al. “Algorithmic Fairness: A Runtime Perspective.”
25th International Conference on Runtime Verification, vol. 16087, Springer
Nature, 2025, pp. 1–21, doi:10.1007/978-3-032-05435-7_1.'
short: F. Cano Cordoba, T.A. Henzinger, K. Kueffner, in:, 25th International Conference
on Runtime Verification, Springer Nature, 2025, pp. 1–21.
conference:
end_date: 2025-09-19
location: Graz, Austria
name: 'RV: Runtime Verification'
start_date: 2025-09-15
corr_author: '1'
date_created: 2026-01-29T16:01:41Z
date_published: 2025-09-13T00:00:00Z
date_updated: 2026-02-16T11:57:00Z
day: '13'
department:
- _id: ToHe
doi: 10.1007/978-3-032-05435-7_1
ec_funded: 1
external_id:
arxiv:
- '2507.20711'
intvolume: ' 16087'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2507.20711
month: '09'
oa: 1
oa_version: Preprint
page: 1-21
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 25th International Conference on Runtime Verification
publication_identifier:
eisbn:
- '9783032054357'
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Algorithmic fairness: A runtime perspective'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16087
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21091'
abstract:
- lang: eng
text: Neural certificates have emerged as a powerful tool in cyber-physical systems
control, providing witnesses of correctness. These certificates, such as barrier
functions, often learned alongside control policies, once verified, serve as mathematical
proofs of system safety. However, traditional formal verification of their defining
conditions typically faces scalability challenges due to exhaustive state-space
exploration. To address this challenge, we propose a lightweight runtime monitoring
framework that integrates real-time verification and does not require access to
the underlying control policy. Our monitor observes the system during deployment
and performs on-the-fly verification of the certificate over a lookahead region
to ensure safety within a finite prediction horizon. We instantiate this framework
for ReLU-based control barrier functions and demonstrate its practical effectiveness
in a case study. Our approach enables timely detection of safety violations and
incorrect certificates with minimal overhead, providing an effective but lightweight
alternative to the static verification of the certificates.
acknowledgement: 'This work is supported by the European Research Council under Grant
No.: ERC-2020-AdG 101020093.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Konstantin
full_name: Kueffner, Konstantin
id: 8121a2d0-dc85-11ea-9058-af578f3b4515
last_name: Kueffner
orcid: 0000-0001-8974-2542
- first_name: Zhengqi
full_name: Yu, Zhengqi
id: 20aa2ae8-f2f1-11ed-bbfa-8205053f1342
last_name: Yu
orcid: 0000-0002-4993-773X
citation:
ama: 'Henzinger TA, Kueffner K, Yu E. Formal verification of neural certificates
done dynamically. In: 25th International Conference on Runtime Verification.
Vol 16087. Springer Nature; 2025:54-72. doi:10.1007/978-3-032-05435-7_4'
apa: 'Henzinger, T. A., Kueffner, K., & Yu, E. (2025). Formal verification of
neural certificates done dynamically. In 25th International Conference on Runtime
Verification (Vol. 16087, pp. 54–72). Graz, Austria: Springer Nature. https://doi.org/10.1007/978-3-032-05435-7_4'
chicago: Henzinger, Thomas A, Konstantin Kueffner, and Emily Yu. “Formal Verification
of Neural Certificates Done Dynamically.” In 25th International Conference
on Runtime Verification, 16087:54–72. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-05435-7_4.
ieee: T. A. Henzinger, K. Kueffner, and E. Yu, “Formal verification of neural certificates
done dynamically,” in 25th International Conference on Runtime Verification,
Graz, Austria, 2025, vol. 16087, pp. 54–72.
ista: 'Henzinger TA, Kueffner K, Yu E. 2025. Formal verification of neural certificates
done dynamically. 25th International Conference on Runtime Verification. RV: Runtime
Verification, LNCS, vol. 16087, 54–72.'
mla: Henzinger, Thomas A., et al. “Formal Verification of Neural Certificates Done
Dynamically.” 25th International Conference on Runtime Verification, vol.
16087, Springer Nature, 2025, pp. 54–72, doi:10.1007/978-3-032-05435-7_4.
short: T.A. Henzinger, K. Kueffner, E. Yu, in:, 25th International Conference on
Runtime Verification, Springer Nature, 2025, pp. 54–72.
conference:
end_date: 2025-09-19
location: Graz, Austria
name: 'RV: Runtime Verification'
start_date: 2025-09-15
corr_author: '1'
date_created: 2026-01-29T16:03:01Z
date_published: 2025-09-13T00:00:00Z
date_updated: 2026-02-16T11:53:25Z
day: '13'
department:
- _id: ToHe
doi: 10.1007/978-3-032-05435-7_4
ec_funded: 1
external_id:
arxiv:
- '2507.11987'
intvolume: ' 16087'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2507.11987
month: '09'
oa: 1
oa_version: Preprint
page: 54-72
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 25th International Conference on Runtime Verification
publication_identifier:
eisbn:
- '9783032054357'
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Formal verification of neural certificates done dynamically
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16087
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21092'
abstract:
- lang: eng
text: Formal verification provides assurances that a probabilistic system satisfies
its specification—conditioned on the system model being aligned with reality.
We propose alignment monitoring to watch that this assumption is justified. We
consider a probabilistic model well aligned if it accurately predicts the behaviour
of an uncertain system in advance. An alignment score measures this by quantifying
the similarity between the model’s predicted and the system’s (unknown) actual
distributions. An alignment monitor observes the system at runtime; at each point
in time it uses the current state and the model to predict the next state. After
the next state is observed, the monitor updates the verdict, which is a high-probability
interval estimate for the true alignment score. We utilize tools from sequential
forecasting to construct our alignment monitors. Besides a monitor for measuring
the expected alignment score, we introduce a differential alignment monitor, designed
for comparing two models, and a weighted alignment monitor, which permits task-specific
alignment monitoring. We evaluate our monitors experimentally on the PRISM benchmark
suite. They are fast, memory-efficient, and detect misalignment early.
acknowledgement: 'This work is supported by the European Research Council under Grant
No.: ERC-2020-AdG 101020093.'
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Konstantin
full_name: Kueffner, Konstantin
id: 8121a2d0-dc85-11ea-9058-af578f3b4515
last_name: Kueffner
orcid: 0000-0001-8974-2542
- first_name: Vasu
full_name: Singh, Vasu
id: 4DAE2708-F248-11E8-B48F-1D18A9856A87
last_name: Singh
- first_name: I
full_name: Sun, I
last_name: Sun
citation:
ama: 'Henzinger TA, Kueffner K, Singh V, Sun I. Alignment monitoring. In: 25th
International Conference on Runtime Verification. Vol 16087. Springer Nature;
2025:140-159. doi:10.1007/978-3-032-05435-7_9'
apa: 'Henzinger, T. A., Kueffner, K., Singh, V., & Sun, I. (2025). Alignment
monitoring. In 25th International Conference on Runtime Verification (Vol.
16087, pp. 140–159). Graz, Austria: Springer Nature. https://doi.org/10.1007/978-3-032-05435-7_9'
chicago: Henzinger, Thomas A, Konstantin Kueffner, Vasu Singh, and I Sun. “Alignment
Monitoring.” In 25th International Conference on Runtime Verification,
16087:140–59. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-05435-7_9.
ieee: T. A. Henzinger, K. Kueffner, V. Singh, and I. Sun, “Alignment monitoring,”
in 25th International Conference on Runtime Verification, Graz, Austria,
2025, vol. 16087, pp. 140–159.
ista: 'Henzinger TA, Kueffner K, Singh V, Sun I. 2025. Alignment monitoring. 25th
International Conference on Runtime Verification. RV: Runtime Verification, LNCS,
vol. 16087, 140–159.'
mla: Henzinger, Thomas A., et al. “Alignment Monitoring.” 25th International
Conference on Runtime Verification, vol. 16087, Springer Nature, 2025, pp.
140–59, doi:10.1007/978-3-032-05435-7_9.
short: T.A. Henzinger, K. Kueffner, V. Singh, I. Sun, in:, 25th International Conference
on Runtime Verification, Springer Nature, 2025, pp. 140–159.
conference:
end_date: 2025-09-19
location: Graz, Austria
name: 'RV: Runtime Verification'
start_date: 2025-09-15
corr_author: '1'
date_created: 2026-01-29T16:03:43Z
date_published: 2025-09-13T00:00:00Z
date_updated: 2026-02-16T11:56:38Z
day: '13'
department:
- _id: ToHe
doi: 10.1007/978-3-032-05435-7_9
ec_funded: 1
external_id:
arxiv:
- '2508.00021'
intvolume: ' 16087'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2508.00021
month: '09'
oa: 1
oa_version: Preprint
page: 140-159
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 25th International Conference on Runtime Verification
publication_identifier:
eisbn:
- '9783032054357'
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Alignment monitoring
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16087
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21093'
abstract:
- lang: eng
text: We propose a monitoring approach for hyperproperties where the system’s observations
range over infinite domains. The specifications are given as formulas of symbolic
hypernode logic, an extension of earlier versions of hypernode logic that supports
events with data. We demonstrate how to translate terms of symbolic hypernode
logic into multi-tape symbolic transducers and we present a monitoring algorithm
for universally quantified formulas that is based on this translation. We evaluate
our approach against the previous approach for monitoring hypernode logic, and
we also compare it to other monitors for hyperproperties.
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093 and
in part by the FWF-2022-SFB F8502 (SPyCoDe).
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Marek
full_name: Chalupa, Marek
id: 87e34708-d6c6-11ec-9f5b-9391e7be2463
last_name: Chalupa
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
- first_name: Ana A
full_name: Oliveira da Costa, Ana A
id: 8b282559-50b0-11ef-861e-d6ace0d92e9b
last_name: Oliveira da Costa
citation:
ama: 'Chalupa M, Henzinger TA, Oliveira da Costa AA. Monitoring hypernode logic
over infinite domains. In: 25th International Conference on Runtime Verification.
Vol 16087. Springer Nature; 2025:417-437. doi:10.1007/978-3-032-05435-7_23'
apa: 'Chalupa, M., Henzinger, T. A., & Oliveira da Costa, A. A. (2025). Monitoring
hypernode logic over infinite domains. In 25th International Conference on
Runtime Verification (Vol. 16087, pp. 417–437). Graz, Austria: Springer Nature.
https://doi.org/10.1007/978-3-032-05435-7_23'
chicago: Chalupa, Marek, Thomas A Henzinger, and Ana A Oliveira da Costa. “Monitoring
Hypernode Logic over Infinite Domains.” In 25th International Conference on
Runtime Verification, 16087:417–37. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-05435-7_23.
ieee: M. Chalupa, T. A. Henzinger, and A. A. Oliveira da Costa, “Monitoring hypernode
logic over infinite domains,” in 25th International Conference on Runtime Verification,
Graz, Austria, 2025, vol. 16087, pp. 417–437.
ista: 'Chalupa M, Henzinger TA, Oliveira da Costa AA. 2025. Monitoring hypernode
logic over infinite domains. 25th International Conference on Runtime Verification.
RV: Runtime Verification, LNCS, vol. 16087, 417–437.'
mla: Chalupa, Marek, et al. “Monitoring Hypernode Logic over Infinite Domains.”
25th International Conference on Runtime Verification, vol. 16087, Springer
Nature, 2025, pp. 417–37, doi:10.1007/978-3-032-05435-7_23.
short: M. Chalupa, T.A. Henzinger, A.A. Oliveira da Costa, in:, 25th International
Conference on Runtime Verification, Springer Nature, 2025, pp. 417–437.
conference:
end_date: 2025-09-19
location: Graz, Austria
name: 'RV: Runtime Verification'
start_date: 2025-09-15
corr_author: '1'
date_created: 2026-01-29T16:04:31Z
date_published: 2025-09-13T00:00:00Z
date_updated: 2026-02-16T11:59:20Z
day: '13'
department:
- _id: ToHe
doi: 10.1007/978-3-032-05435-7_23
ec_funded: 1
external_id:
arxiv:
- '2508.02301'
intvolume: ' 16087'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2508.02301
month: '09'
oa: 1
oa_version: Preprint
page: 417-437
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: 34a1b658-11ca-11ed-8bc3-c75229f0241e
grant_number: F8502
name: Interface Theory for Security and Privacy
publication: 25th International Conference on Runtime Verification
publication_identifier:
eisbn:
- '9783032054357'
eissn:
- 1611-3349
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: Monitoring hypernode logic over infinite domains
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16087
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21262'
abstract:
- lang: eng
text: "Continuous Group Key Agreement (CGKA) is the primitive underlying secure
group messaging. It allows a large group of N users to maintain a shared secret
key that is frequently rotated by the\r\ngroup members in order to achieve forward
secrecy and post compromise security. The group messaging scheme Messaging Layer
Security (MLS) standardized by the IETF makes use of a CGKA called TreeKEM which
arranges the N group members in a binary tree. Here, each node is associated with
a public-key, each user is assigned one of the leaves, and a user knows the corresponding
secret keys from their leaf to the root. To update the key material known to them,
a user must just replace keys at log(N) nodes, which requires them to create and
upload log(N) ciphertexts. Such updates must be processed sequentially by all
users, which for large groups is impractical. To allow for concurrent updates,
TreeKEM uses the “propose and commit” paradigm, where multiple users can concurrently
propose to update (by just sampling a fresh leaf key), and a single user can then
commit to all proposals at once. Unfortunately, this process destroys the binary
tree structure as the tree gets pruned and some nodes must be “blanked” at the
cost of increasing the in-degree of others, which makes the commit operation,
as well as, future commits more costly. In the worst case, the update cost (in
terms of uploaded ciphertexts) per user can grow from log(N) to Ω(N). In this
work we provide two main contributions. First, we show that MLS’ communication
complexity is bad not only in the worst case but also if the proposers and committers
are chosen at random: even if there’s just one update proposal for every commit
the expected cost is already over √N, and it approaches N as this ratio changes
towards more proposals. Our second contribution is a new variant of propose and
commit for\r\nTreeKEM which for moderate amounts of update proposals per commit
provably achieves an update cost of Θ(log(N)) assuming the proposers and committers
are chosen at random."
acknowledgement: B. Auerbach and B. Erol—Conducted part of this work at ISTA.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Boran
full_name: Erol, Boran
last_name: Erol
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. Continuous group-key agreement:
Concurrent updates without pruning. In: 45th Annual International Cryptology
Conference. Vol 16007. Springer Nature; 2025:141-172. doi:10.1007/978-3-032-01913-4_5'
apa: 'Auerbach, B., Cueto Noval, M., Erol, B., & Pietrzak, K. Z. (2025). Continuous
group-key agreement: Concurrent updates without pruning. In 45th Annual International
Cryptology Conference (Vol. 16007, pp. 141–172). Santa Barbara, CA, United
States: Springer Nature. https://doi.org/10.1007/978-3-032-01913-4_5'
chicago: 'Auerbach, Benedikt, Miguel Cueto Noval, Boran Erol, and Krzysztof Z Pietrzak.
“Continuous Group-Key Agreement: Concurrent Updates without Pruning.” In 45th
Annual International Cryptology Conference, 16007:141–72. Springer Nature,
2025. https://doi.org/10.1007/978-3-032-01913-4_5.'
ieee: 'B. Auerbach, M. Cueto Noval, B. Erol, and K. Z. Pietrzak, “Continuous group-key
agreement: Concurrent updates without pruning,” in 45th Annual International
Cryptology Conference, Santa Barbara, CA, United States, 2025, vol. 16007,
pp. 141–172.'
ista: 'Auerbach B, Cueto Noval M, Erol B, Pietrzak KZ. 2025. Continuous group-key
agreement: Concurrent updates without pruning. 45th Annual International Cryptology
Conference. CRYPTO: International Cryptology Conference, LNCS, vol. 16007, 141–172.'
mla: 'Auerbach, Benedikt, et al. “Continuous Group-Key Agreement: Concurrent Updates
without Pruning.” 45th Annual International Cryptology Conference, vol.
16007, Springer Nature, 2025, pp. 141–72, doi:10.1007/978-3-032-01913-4_5.'
short: B. Auerbach, M. Cueto Noval, B. Erol, K.Z. Pietrzak, in:, 45th Annual International
Cryptology Conference, Springer Nature, 2025, pp. 141–172.
conference:
end_date: 2025-08-21
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2025-08-17
date_created: 2026-02-17T07:41:04Z
date_published: 2025-08-17T00:00:00Z
date_updated: 2026-02-18T07:36:42Z
day: '17'
department:
- _id: KrPi
doi: 10.1007/978-3-032-01913-4_5
intvolume: ' 16007'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/1035
month: '08'
oa: 1
oa_version: Preprint
page: 141-172
publication: 45th Annual International Cryptology Conference
publication_identifier:
eisbn:
- '9783032019134'
eissn:
- 1611-3349
isbn:
- '9783032019127'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Continuous group-key agreement: Concurrent updates without pruning'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16007
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '21323'
abstract:
- lang: eng
text: We present a unifying framework for proving the knowledge-soundness of KZG-like
polynomial commitment schemes, encompassing both univariate and multivariate variants.
By conceptualizing the proof technique of Lipmaa, Parisella, and Siim for the
univariate KZG scheme (EUROCRYPT 2024), we present tools and falsifiable hardness
assumptions that permit black-box extraction of the multivariate KZG scheme. Central
to our approach is the notion of a canonical Proof-of-Knowledge of a Polynomial
(PoKoP) of a polynomial commitment scheme, which we use to capture the extractability
notion required in constructions of practical zk-SNARKs. We further present an
explicit polynomial decomposition lemma for multivariate polynomials, enabling
a more direct analysis of interpolating extractors and bridging the gap between
univariate and multivariate commitments. Our results provide the first standard-model
proofs of extractability for the multivariate KZG scheme and many of its variants
under falsifiable assumptions.
acknowledgement: Juraj Belohorec, Pavel Hubáček, and Kristýna Mašková were partially
supported by the Academy of Sciences of the Czech Republic (RVO 67985840), Czech
Science Foundation GAČR grant No. 25-16311S, and by Zircuit. Pavel Dvořák was supported
by Czech Science Foundation GAČR grant No. 22-14872O. Juraj Belohorec and Kristýna
Mašková were supported by the grant SVV–2025–260822.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Juraj
full_name: Belohorec, Juraj
last_name: Belohorec
- first_name: Pavel
full_name: Dvořák, Pavel
last_name: Dvořák
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Kristýna
full_name: Mašková, Kristýna
last_name: Mašková
- first_name: Martin
full_name: Pastyřík, Martin
last_name: Pastyřík
citation:
ama: 'Belohorec J, Dvořák P, Hoffmann C, Hubáček P, Mašková K, Pastyřík M. On extractability
of the KZG family of polynomial commitment schemes. In: 45th Annual International
Cryptology Conference. Vol 16005. Springer Nature; 2025:584-616. doi:10.1007/978-3-032-01887-8_19'
apa: 'Belohorec, J., Dvořák, P., Hoffmann, C., Hubáček, P., Mašková, K., & Pastyřík,
M. (2025). On extractability of the KZG family of polynomial commitment schemes.
In 45th Annual International Cryptology Conference (Vol. 16005, pp. 584–616).
Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-032-01887-8_19'
chicago: Belohorec, Juraj, Pavel Dvořák, Charlotte Hoffmann, Pavel Hubáček, Kristýna
Mašková, and Martin Pastyřík. “On Extractability of the KZG Family of Polynomial
Commitment Schemes.” In 45th Annual International Cryptology Conference,
16005:584–616. Springer Nature, 2025. https://doi.org/10.1007/978-3-032-01887-8_19.
ieee: J. Belohorec, P. Dvořák, C. Hoffmann, P. Hubáček, K. Mašková, and M. Pastyřík,
“On extractability of the KZG family of polynomial commitment schemes,” in 45th
Annual International Cryptology Conference, Santa Barbara, CA, United States,
2025, vol. 16005, pp. 584–616.
ista: 'Belohorec J, Dvořák P, Hoffmann C, Hubáček P, Mašková K, Pastyřík M. 2025.
On extractability of the KZG family of polynomial commitment schemes. 45th Annual
International Cryptology Conference. CRYPTO: International Cryptology Conference,
LNCS, vol. 16005, 584–616.'
mla: Belohorec, Juraj, et al. “On Extractability of the KZG Family of Polynomial
Commitment Schemes.” 45th Annual International Cryptology Conference, vol.
16005, Springer Nature, 2025, pp. 584–616, doi:10.1007/978-3-032-01887-8_19.
short: J. Belohorec, P. Dvořák, C. Hoffmann, P. Hubáček, K. Mašková, M. Pastyřík,
in:, 45th Annual International Cryptology Conference, Springer Nature, 2025, pp.
584–616.
conference:
end_date: 2025-08-221
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2025-08-17
date_created: 2026-02-18T10:59:58Z
date_published: 2025-08-17T00:00:00Z
date_updated: 2026-02-19T07:50:33Z
day: '17'
department:
- _id: KrPi
doi: 10.1007/978-3-032-01887-8_19
intvolume: ' 16005'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/514
month: '08'
oa: 1
oa_version: Preprint
page: 584-616
publication: 45th Annual International Cryptology Conference
publication_identifier:
eisbn:
- '9783032018878'
eissn:
- 1611-3349
isbn:
- '9783032018861'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: On extractability of the KZG family of polynomial commitment schemes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 16005
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19375'
abstract:
- lang: eng
text: "Despite the advances in probabilistic model checking, the scalability of
the verification methods remains limited. In particular, the state space often
becomes extremely large when instantiating parameterized Markov decision processes
(MDPs) even with moderate values. Synthesizing policies for such huge MDPs is
beyond the reach of available tools. We propose a learning-based approach to obtain
a reasonable policy for such huge MDPs.\r\n\r\nThe idea is to generalize optimal
policies obtained by model-checking small instances to larger ones using decision-tree
learning. Consequently, our method bypasses the need for explicit state-space
exploration of large models, providing a practical solution to the state-space
explosion problem. We demonstrate the efficacy of our approach by performing extensive
experimentation on the relevant models from the quantitative verification benchmark
set. The experimental results indicate that our policies perform well, even when
the size of the model is orders of magnitude beyond the reach of state-of-the-art
analysis tools."
acknowledgement: This research was funded in part by the DFG project 427755713 GOPro,
the DFG GRK 2428 (ConVeY), the MUNI Award in Science and Humanities (MUNI/I/1757/2021)
of the Grant Agency of Masaryk University, and the EU under MSCA grant agreement
101034413 (IST-BRIDGE).
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Muqsit
full_name: Azeem, Muqsit
last_name: Azeem
- first_name: Debraj
full_name: Chakraborty, Debraj
last_name: Chakraborty
- first_name: Sudeep
full_name: Kanav, Sudeep
last_name: Kanav
- first_name: Jan
full_name: Kretinsky, Jan
id: 44CEF464-F248-11E8-B48F-1D18A9856A87
last_name: Kretinsky
orcid: 0000-0002-8122-2881
- first_name: Mohammadsadegh
full_name: Mohagheghi, Mohammadsadegh
last_name: Mohagheghi
- first_name: Stefanie
full_name: Mohr, Stefanie
last_name: Mohr
- first_name: Maximilian
full_name: Weininger, Maximilian
id: 02ab0197-cc70-11ed-ab61-918e71f56881
last_name: Weininger
citation:
ama: 'Azeem M, Chakraborty D, Kanav S, et al. 1–2–3–Go! Policy synthesis for parameterized
Markov decision processes via decision-tree learning and generalization. In: 26th
International Conference on Verification, Model Checking, and Abstract Interpretation.
Vol 15530. Springer Nature; 2025:97-120. doi:10.1007/978-3-031-82703-7_5'
apa: 'Azeem, M., Chakraborty, D., Kanav, S., Kretinsky, J., Mohagheghi, M., Mohr,
S., & Weininger, M. (2025). 1–2–3–Go! Policy synthesis for parameterized Markov
decision processes via decision-tree learning and generalization. In 26th International
Conference on Verification, Model Checking, and Abstract Interpretation (Vol.
15530, pp. 97–120). Denver, CO, United States: Springer Nature. https://doi.org/10.1007/978-3-031-82703-7_5'
chicago: Azeem, Muqsit, Debraj Chakraborty, Sudeep Kanav, Jan Kretinsky, Mohammadsadegh
Mohagheghi, Stefanie Mohr, and Maximilian Weininger. “1–2–3–Go! Policy Synthesis
for Parameterized Markov Decision Processes via Decision-Tree Learning and Generalization.”
In 26th International Conference on Verification, Model Checking, and Abstract
Interpretation, 15530:97–120. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-82703-7_5.
ieee: M. Azeem et al., “1–2–3–Go! Policy synthesis for parameterized Markov
decision processes via decision-tree learning and generalization,” in 26th
International Conference on Verification, Model Checking, and Abstract Interpretation,
Denver, CO, United States, 2025, vol. 15530, pp. 97–120.
ista: 'Azeem M, Chakraborty D, Kanav S, Kretinsky J, Mohagheghi M, Mohr S, Weininger
M. 2025. 1–2–3–Go! Policy synthesis for parameterized Markov decision processes
via decision-tree learning and generalization. 26th International Conference on
Verification, Model Checking, and Abstract Interpretation. VMCAI: Verification,
Model Checking, and Abstract Interpretation, LNCS, vol. 15530, 97–120.'
mla: Azeem, Muqsit, et al. “1–2–3–Go! Policy Synthesis for Parameterized Markov
Decision Processes via Decision-Tree Learning and Generalization.” 26th International
Conference on Verification, Model Checking, and Abstract Interpretation, vol.
15530, Springer Nature, 2025, pp. 97–120, doi:10.1007/978-3-031-82703-7_5.
short: M. Azeem, D. Chakraborty, S. Kanav, J. Kretinsky, M. Mohagheghi, S. Mohr,
M. Weininger, in:, 26th International Conference on Verification, Model Checking,
and Abstract Interpretation, Springer Nature, 2025, pp. 97–120.
conference:
end_date: 2025-01-21
location: Denver, CO, United States
name: 'VMCAI: Verification, Model Checking, and Abstract Interpretation'
start_date: 2025-01-20
date_created: 2025-03-09T23:01:29Z
date_published: 2025-01-23T00:00:00Z
date_updated: 2025-09-30T10:46:54Z
day: '23'
department:
- _id: KrCh
doi: 10.1007/978-3-031-82703-7_5
ec_funded: 1
external_id:
arxiv:
- '2410.18293'
isi:
- '001446577100005'
intvolume: ' 15530'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2410.18293
month: '01'
oa: 1
oa_version: Preprint
page: 97-120
project:
- _id: fc2ed2f7-9c52-11eb-aca3-c01059dda49c
call_identifier: H2020
grant_number: '101034413'
name: 'IST-BRIDGE: International postdoctoral program'
publication: 26th International Conference on Verification, Model Checking, and Abstract
Interpretation
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031827020'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 1–2–3–Go! Policy synthesis for parameterized Markov decision processes via decision-tree
learning and generalization
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15530
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19445'
abstract:
- lang: eng
text: "In reconfiguration, we are given two solutions to a graph problem, such as
Vertex Cover or Dominating Set, with each solution represented by a placement
of tokens on vertices of the graph. Our task is to reconfigure one into the other
using small steps while ensuring the intermediate configurations of tokens are
also valid solutions. The two commonly studied settings are Token Jumping and
Token Sliding, which allows moving a single token to an arbitrary or an adjacent
vertex, respectively.\r\n\r\nWe introduce new rules that generalize Token Jumping,
parameterized by the number of tokens allowed to move at once and by the maximum
distance of each move. Our main contribution is identifying minimal rules that
allow reconfiguring any possible given solution into any other for Independent
Set, Vertex Cover, and Dominating Set. For each minimal rule, we also provide
an efficient algorithm that finds a corresponding reconfiguration sequence.\r\n\r\nWe
further focus on the rule that allows each token to move to an adjacent vertex
in a single step. This natural variant turns out to be the minimal rule that guarantees
reconfigurability for Vertex Cover. We determine the computational complexity
of deciding whether a (shortest) reconfiguration sequence exists under this rule
for the three studied problems. While reachability for Vertex Cover is shown to
be in P, finding a shortest sequence is shown to be NP-complete. For Independent
Set and Dominating Set, even reachability is shown to be PSPACE-complete."
acknowledgement: J. M. Křišťan acknowledges the support of the Czech Science Foundation
Grant No. 24-12046S. This work was supported by the Grant Agency of the Czech Technical
University in Prague, grant No. SGS23/205/OHK3/3T/18. J. Svoboda acknowledges the
support of the ERC CoG 863818 (ForM-SMArt) grant.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Jan Matyáš
full_name: Křišťan, Jan Matyáš
last_name: Křišťan
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
citation:
ama: 'Křišťan JM, Svoboda J. Reconfiguration using generalized token jumping. In:
19th International Conference and Workshops on Algorithms and Computation.
Vol 15411. Springer Nature; 2025:244-265. doi:10.1007/978-981-96-2845-2_16'
apa: 'Křišťan, J. M., & Svoboda, J. (2025). Reconfiguration using generalized
token jumping. In 19th International Conference and Workshops on Algorithms
and Computation (Vol. 15411, pp. 244–265). Chengdu, China: Springer Nature.
https://doi.org/10.1007/978-981-96-2845-2_16'
chicago: Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized
Token Jumping.” In 19th International Conference and Workshops on Algorithms
and Computation, 15411:244–65. Springer Nature, 2025. https://doi.org/10.1007/978-981-96-2845-2_16.
ieee: J. M. Křišťan and J. Svoboda, “Reconfiguration using generalized token jumping,”
in 19th International Conference and Workshops on Algorithms and Computation,
Chengdu, China, 2025, vol. 15411, pp. 244–265.
ista: 'Křišťan JM, Svoboda J. 2025. Reconfiguration using generalized token jumping.
19th International Conference and Workshops on Algorithms and Computation. WALCOM:
International Conference and Workshops on Algorithms and Computation, LNCS, vol.
15411, 244–265.'
mla: Křišťan, Jan Matyáš, and Jakub Svoboda. “Reconfiguration Using Generalized
Token Jumping.” 19th International Conference and Workshops on Algorithms and
Computation, vol. 15411, Springer Nature, 2025, pp. 244–65, doi:10.1007/978-981-96-2845-2_16.
short: J.M. Křišťan, J. Svoboda, in:, 19th International Conference and Workshops
on Algorithms and Computation, Springer Nature, 2025, pp. 244–265.
conference:
end_date: 2025-03-02
location: Chengdu, China
name: 'WALCOM: International Conference and Workshops on Algorithms and Computation'
start_date: 2025-02-28
date_created: 2025-03-23T23:01:27Z
date_published: 2025-02-20T00:00:00Z
date_updated: 2025-09-30T11:14:33Z
day: '20'
department:
- _id: KrCh
doi: 10.1007/978-981-96-2845-2_16
ec_funded: 1
external_id:
arxiv:
- '2411.12582'
isi:
- '001537885900016'
intvolume: ' 15411'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2411.12582
month: '02'
oa: 1
oa_version: Preprint
page: 244-265
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 19th International Conference and Workshops on Algorithms and Computation
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9789819628445'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reconfiguration using generalized token jumping
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 15411
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19600'
abstract:
- lang: eng
text: In this work, we explore route discovery in private payment channel networks.
We first determine what “ideal" privacy for a routing protocol means in this setting.
We observe that protocols achieving this strong privacy definition exist by leveraging
Multi-Party Computation but they are inherently inefficient as they must involve
the entire network. We then present protocols with weaker privacy guarantees but
much better efficiency (involving only a small fraction of the nodes). The core
idea is that both sender and receiver gossip a message which propagates through
the network, and the moment any node in the network receives both messages, a
path is found. In our first protocol the message is always sent to all neighbouring
nodes with a delay proportional to the fees of that edge. In our second protocol
the message is only sent to one neighbour chosen randomly with a probability proportional
to its degree. We additionally propose a more realistic notion of privacy in order
to measure the privacy leakage of our protocols in practice. Our realistic notion
of privacy challenges an adversary that join the network with a fixed budget to
create channels to guess the sender and receiver of a transaction upon receiving
messages from our protocols. Simulations of our protocols on the Lightning network
topology (for random transactions and uniform fees) show that 1) forming edges
with high degree nodes is a more effective attack strategy for the adversary,
2) there is a tradeoff between the number of nodes involved in our protocols (privacy)
and the optimality of the discovered path, and 3) our protocols involve a very
small fraction of the network on average.
acknowledgement: This work was supported in part by the ERC CoG 863818 (ForM-SMArt),
Austrian Science Fund (FWF) 10.55776/COE12, and MOE-T2EP20122-0014 (Data-Driven
Distributed Algorithms) grants.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Zeta
full_name: Avarikioti, Zeta
last_name: Avarikioti
- first_name: Mahsa
full_name: Bastankhah, Mahsa
last_name: Bastankhah
- first_name: Mohammad Ali
full_name: Maddah-Ali, Mohammad Ali
last_name: Maddah-Ali
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX.
Route discovery in private payment channel networks. In: Computer Security.
ESORICS 2024 International Workshops. Vol 15263. Springer Nature; 2025:207-223.
doi:10.1007/978-3-031-82349-7_15'
apa: 'Avarikioti, Z., Bastankhah, M., Maddah-Ali, M. A., Pietrzak, K. Z., Svoboda,
J., & Yeo, M. X. (2025). Route discovery in private payment channel networks.
In Computer Security. ESORICS 2024 International Workshops (Vol. 15263,
pp. 207–223). Bydgoszcz, Poland: Springer Nature. https://doi.org/10.1007/978-3-031-82349-7_15'
chicago: Avarikioti, Zeta, Mahsa Bastankhah, Mohammad Ali Maddah-Ali, Krzysztof
Z Pietrzak, Jakub Svoboda, and Michelle X Yeo. “Route Discovery in Private Payment
Channel Networks.” In Computer Security. ESORICS 2024 International Workshops,
15263:207–23. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-82349-7_15.
ieee: Z. Avarikioti, M. Bastankhah, M. A. Maddah-Ali, K. Z. Pietrzak, J. Svoboda,
and M. X. Yeo, “Route discovery in private payment channel networks,” in Computer
Security. ESORICS 2024 International Workshops, Bydgoszcz, Poland, 2025, vol.
15263, pp. 207–223.
ista: 'Avarikioti Z, Bastankhah M, Maddah-Ali MA, Pietrzak KZ, Svoboda J, Yeo MX.
2025. Route discovery in private payment channel networks. Computer Security.
ESORICS 2024 International Workshops. ESORICS: European Symposium on Research
in Computer Security, LNCS, vol. 15263, 207–223.'
mla: Avarikioti, Zeta, et al. “Route Discovery in Private Payment Channel Networks.”
Computer Security. ESORICS 2024 International Workshops, vol. 15263, Springer
Nature, 2025, pp. 207–23, doi:10.1007/978-3-031-82349-7_15.
short: Z. Avarikioti, M. Bastankhah, M.A. Maddah-Ali, K.Z. Pietrzak, J. Svoboda,
M.X. Yeo, in:, Computer Security. ESORICS 2024 International Workshops, Springer
Nature, 2025, pp. 207–223.
conference:
end_date: 2024-09-20
location: Bydgoszcz, Poland
name: 'ESORICS: European Symposium on Research in Computer Security'
start_date: 2024-09-16
date_created: 2025-04-20T22:01:28Z
date_published: 2025-04-01T00:00:00Z
date_updated: 2025-11-05T07:52:35Z
day: '01'
department:
- _id: KrPi
- _id: KrCh
doi: 10.1007/978-3-031-82349-7_15
ec_funded: 1
intvolume: ' 15263'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1539
month: '04'
oa: 1
oa_version: Submitted Version
page: 207-223
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: Computer Security. ESORICS 2024 International Workshops
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031823480'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Route discovery in private payment channel networks
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15263
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19712'
abstract:
- lang: eng
text: "We study recent algebraic attacks (Briaud-Øygarden EC’23) on the Regular
Syndrome Decoding (RSD) problem and the assumptions underlying the correctness
of their attacks’ complexity estimates. By relating these assumptions to interesting
algebraic-combinatorial problems, we prove that they do not hold in full generality.
However, we show that they are (asymptotically) true for most parameter sets,
supporting the soundness of algebraic attacks on RSD. Further, we prove—without
any heuristics or assumptions—that RSD can be broken in polynomial time whenever
the number of error blocks times the square of the size of error blocks is larger
than 2 times the square of the dimension of the code.\r\nAdditionally, we use
our methodology to attack a variant of the Learning With Errors problem where
each error term lies in a fixed set of constant size. We prove that this problem
can be broken in polynomial time, given a sufficient number of samples. This result
improves on the seminal work by Arora and Ge (ICALP’11), as the attack’s time
complexity is independent of the LWE modulus."
acknowledgement: We thank Pierre Briaud and Morten Øygarden for helpful discussions
on algebraic attacks on RSD, and the EC reviewers for helpful comments.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Simon-Philipp
full_name: Merz, Simon-Philipp
last_name: Merz
- first_name: Patrick
full_name: Stählin, Patrick
last_name: Stählin
- first_name: Akin
full_name: Ünal, Akin
id: f6b56fb6-dc63-11ee-9dbf-f6780863a85a
last_name: Ünal
orcid: 0000-0002-8929-0221
citation:
ama: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. On the soundness of algebraic
attacks against code-based assumptions. In: 44th Annual International Conference
on the Theory and Applications of Cryptographic Techniques. Vol 15606. Springer
Nature; 2025:385-415. doi:10.1007/978-3-031-91095-1_14'
apa: 'Cueto Noval, M., Merz, S.-P., Stählin, P., & Ünal, A. (2025). On the soundness
of algebraic attacks against code-based assumptions. In 44th Annual International
Conference on the Theory and Applications of Cryptographic Techniques (Vol.
15606, pp. 385–415). Madrid, Spain: Springer Nature. https://doi.org/10.1007/978-3-031-91095-1_14'
chicago: Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal.
“On the Soundness of Algebraic Attacks against Code-Based Assumptions.” In 44th
Annual International Conference on the Theory and Applications of Cryptographic
Techniques, 15606:385–415. Springer Nature, 2025. https://doi.org/10.1007/978-3-031-91095-1_14.
ieee: M. Cueto Noval, S.-P. Merz, P. Stählin, and A. Ünal, “On the soundness of algebraic
attacks against code-based assumptions,” in 44th Annual International Conference
on the Theory and Applications of Cryptographic Techniques, Madrid, Spain,
2025, vol. 15606, pp. 385–415.
ista: 'Cueto Noval M, Merz S-P, Stählin P, Ünal A. 2025. On the soundness of algebraic
attacks against code-based assumptions. 44th Annual International Conference on
the Theory and Applications of Cryptographic Techniques. EUROCRYPT: International
Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
15606, 385–415.'
mla: Cueto Noval, Miguel, et al. “On the Soundness of Algebraic Attacks against
Code-Based Assumptions.” 44th Annual International Conference on the Theory
and Applications of Cryptographic Techniques, vol. 15606, Springer Nature,
2025, pp. 385–415, doi:10.1007/978-3-031-91095-1_14.
short: M. Cueto Noval, S.-P. Merz, P. Stählin, A. Ünal, in:, 44th Annual International
Conference on the Theory and Applications of Cryptographic Techniques, Springer
Nature, 2025, pp. 385–415.
conference:
end_date: 2025-05-08
location: Madrid, Spain
name: 'EUROCRYPT: International Conference on the Theory and Applications of Cryptographic
Techniques'
start_date: 2025-05-04
corr_author: '1'
date_created: 2025-05-19T14:15:01Z
date_published: 2025-04-28T00:00:00Z
date_updated: 2025-05-28T06:12:39Z
day: '28'
department:
- _id: KrPi
doi: 10.1007/978-3-031-91095-1_14
intvolume: ' 15606'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://www.research-collection.ethz.ch/handle/20.500.11850/732894
month: '04'
oa: 1
oa_version: Submitted Version
page: 385-415
publication: 44th Annual International Conference on the Theory and Applications of
Cryptographic Techniques
publication_identifier:
eisbn:
- '9783031910951'
eissn:
- 1611-3349
isbn:
- '9783031910944'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the soundness of algebraic attacks against code-based assumptions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 15606
year: '2025'
...