---
_id: '14456'
abstract:
- lang: eng
text: In this paper, we present novel algorithms that efficiently compute a shortest
reconfiguration sequence between two given dominating sets in trees and interval
graphs under the TOKEN SLIDING model. In this problem, a graph is provided along
with its two dominating sets, which can be imagined as tokens placed on vertices.
The objective is to find a shortest sequence of dominating sets that transforms
one set into the other, with each set in the sequence resulting from sliding a
single token in the previous set. While identifying any sequence has been well
studied, our work presents the first polynomial algorithms for this optimization
variant in the context of dominating sets.
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. Shortest dominating set reconfiguration under token
sliding. In: 24th International Symposium on Fundamentals of Computation Theory.
Vol 14292. Springer Nature; 2023:333-347. doi:10.1007/978-3-031-43587-4_24'
apa: 'Křišťan, J. M., & Svoboda, J. (2023). Shortest dominating set reconfiguration
under token sliding. In 24th International Symposium on Fundamentals of Computation
Theory (Vol. 14292, pp. 333–347). Trier, Germany: Springer Nature. https://doi.org/10.1007/978-3-031-43587-4_24'
chicago: Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration
under Token Sliding.” In 24th International Symposium on Fundamentals of Computation
Theory, 14292:333–47. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-43587-4_24.
ieee: J. M. Křišťan and J. Svoboda, “Shortest dominating set reconfiguration under
token sliding,” in 24th International Symposium on Fundamentals of Computation
Theory, Trier, Germany, 2023, vol. 14292, pp. 333–347.
ista: 'Křišťan JM, Svoboda J. 2023. Shortest dominating set reconfiguration under
token sliding. 24th International Symposium on Fundamentals of Computation Theory.
FCT: Fundamentals of Computation Theory, LNCS, vol. 14292, 333–347.'
mla: Křišťan, Jan Matyáš, and Jakub Svoboda. “Shortest Dominating Set Reconfiguration
under Token Sliding.” 24th International Symposium on Fundamentals of Computation
Theory, vol. 14292, Springer Nature, 2023, pp. 333–47, doi:10.1007/978-3-031-43587-4_24.
short: J.M. Křišťan, J. Svoboda, in:, 24th International Symposium on Fundamentals
of Computation Theory, Springer Nature, 2023, pp. 333–347.
conference:
end_date: 2023-09-21
location: Trier, Germany
name: 'FCT: Fundamentals of Computation Theory'
start_date: 2023-09-18
date_created: 2023-10-29T23:01:16Z
date_published: 2023-09-21T00:00:00Z
date_updated: 2024-01-22T08:10:49Z
day: '21'
department:
- _id: KrCh
doi: 10.1007/978-3-031-43587-4_24
external_id:
arxiv:
- '2307.10847'
intvolume: ' 14292'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2307.10847
month: '09'
oa: 1
oa_version: Preprint
page: 333-347
publication: 24th International Symposium on Fundamentals of Computation Theory
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031435867'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
link:
- relation: erratum
url: https://doi.org/10.1007/978-3-031-43587-4_31
scopus_import: '1'
status: public
title: Shortest dominating set reconfiguration under token sliding
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14292
year: '2023'
...
---
_id: '14457'
abstract:
- lang: eng
text: "Threshold secret sharing allows a dealer to split a secret s into n shares,
such that any t shares allow for reconstructing s, but no t-1 shares reveal any
information about s. Leakage-resilient secret sharing requires that the secret
remains hidden, even when an adversary additionally obtains a limited amount of
leakage from every share. Benhamouda et al. (CRYPTO’18) proved that Shamir’s secret
sharing scheme is one bit leakage-resilient for reconstruction threshold t≥0.85n
and conjectured that the same holds for t = c.n for any constant 0≤c≤1. Nielsen
and Simkin (EUROCRYPT’20) showed that this is the best one can hope for by proving
that Shamir’s scheme is not secure against one-bit leakage when t0c.n/log(n).\r\nIn
this work, we strengthen the lower bound of Nielsen and Simkin. We consider noisy
leakage-resilience, where a random subset of leakages is replaced by uniformly
random noise. We prove a lower bound for Shamir’s secret sharing, similar to that
of Nielsen and Simkin, which holds even when a constant fraction of leakages is
replaced by random noise. To this end, we first prove a lower bound on the share
size of any noisy-leakage-resilient sharing scheme. We then use this lower bound
to show that there exist universal constants c1, c2, such that for sufficiently
large n it holds that Shamir’s secret sharing scheme is not noisy-leakage-resilient
for t≤c1.n/log(n), even when a c2 fraction of leakages are replaced by random
noise.\r\n\r\n\r\n\r\n"
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Mark
full_name: Simkin, Mark
last_name: Simkin
citation:
ama: 'Hoffmann C, Simkin M. Stronger lower bounds for leakage-resilient secret sharing.
In: 8th International Conference on Cryptology and Information Security in
Latin America. Vol 14168. Springer Nature; 2023:215-228. doi:10.1007/978-3-031-44469-2_11'
apa: 'Hoffmann, C., & Simkin, M. (2023). Stronger lower bounds for leakage-resilient
secret sharing. In 8th International Conference on Cryptology and Information
Security in Latin America (Vol. 14168, pp. 215–228). Quito, Ecuador: Springer
Nature. https://doi.org/10.1007/978-3-031-44469-2_11'
chicago: Hoffmann, Charlotte, and Mark Simkin. “Stronger Lower Bounds for Leakage-Resilient
Secret Sharing.” In 8th International Conference on Cryptology and Information
Security in Latin America, 14168:215–28. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-44469-2_11.
ieee: C. Hoffmann and M. Simkin, “Stronger lower bounds for leakage-resilient secret
sharing,” in 8th International Conference on Cryptology and Information Security
in Latin America, Quito, Ecuador, 2023, vol. 14168, pp. 215–228.
ista: 'Hoffmann C, Simkin M. 2023. Stronger lower bounds for leakage-resilient secret
sharing. 8th International Conference on Cryptology and Information Security in
Latin America. LATINCRYPT: Conference on Cryptology and Information Security in
Latin America, LNCS, vol. 14168, 215–228.'
mla: Hoffmann, Charlotte, and Mark Simkin. “Stronger Lower Bounds for Leakage-Resilient
Secret Sharing.” 8th International Conference on Cryptology and Information
Security in Latin America, vol. 14168, Springer Nature, 2023, pp. 215–28,
doi:10.1007/978-3-031-44469-2_11.
short: C. Hoffmann, M. Simkin, in:, 8th International Conference on Cryptology and
Information Security in Latin America, Springer Nature, 2023, pp. 215–228.
conference:
end_date: 2023-10-06
location: Quito, Ecuador
name: 'LATINCRYPT: Conference on Cryptology and Information Security in Latin America'
start_date: 2023-10-03
date_created: 2023-10-29T23:01:16Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2023-10-31T11:43:12Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-031-44469-2_11
intvolume: ' 14168'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1017
month: '10'
oa: 1
oa_version: Preprint
page: 215-228
publication: 8th International Conference on Cryptology and Information Security in
Latin America
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031444685'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Stronger lower bounds for leakage-resilient secret sharing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14168
year: '2023'
...
---
_id: '14559'
abstract:
- lang: eng
text: We consider the problem of learning control policies in discrete-time stochastic
systems which guarantee that the system stabilizes within some specified stabilization
region with probability 1. Our approach is based on the novel notion of stabilizing
ranking supermartingales (sRSMs) that we introduce in this work. Our sRSMs overcome
the limitation of methods proposed in previous works whose applicability is restricted
to systems in which the stabilizing region cannot be left once entered under any
control policy. We present a learning procedure that learns a control policy together
with an sRSM that formally certifies probability 1 stability, both learned as
neural networks. We show that this procedure can also be adapted to formally verifying
that, under a given Lipschitz continuous control policy, the stochastic system
stabilizes within some stabilizing region with probability 1. Our experimental
evaluation shows that our learning procedure can successfully learn provably stabilizing
policies in practice.
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093, ERC
CoG 863818 (FoRM-SMArt) and the European Union’s Horizon 2020 research and innovation
programme under the Marie Skłodowska-Curie Grant Agreement No. 665385.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Matin
full_name: Ansaripour, Matin
last_name: Ansaripour
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- 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: Mathias
full_name: Lechner, Mathias
id: 3DC22916-F248-11E8-B48F-1D18A9856A87
last_name: Lechner
- first_name: Dorde
full_name: Zikelic, Dorde
id: 294AA7A6-F248-11E8-B48F-1D18A9856A87
last_name: Zikelic
orcid: 0000-0002-4681-1699
citation:
ama: 'Ansaripour M, Chatterjee K, Henzinger TA, Lechner M, Zikelic D. Learning provably
stabilizing neural controllers for discrete-time stochastic systems. In: 21st
International Symposium on Automated Technology for Verification and Analysis.
Vol 14215. Springer Nature; 2023:357-379. doi:10.1007/978-3-031-45329-8_17'
apa: 'Ansaripour, M., Chatterjee, K., Henzinger, T. A., Lechner, M., & Zikelic,
D. (2023). Learning provably stabilizing neural controllers for discrete-time
stochastic systems. In 21st International Symposium on Automated Technology
for Verification and Analysis (Vol. 14215, pp. 357–379). Singapore, Singapore:
Springer Nature. https://doi.org/10.1007/978-3-031-45329-8_17'
chicago: Ansaripour, Matin, Krishnendu Chatterjee, Thomas A Henzinger, Mathias Lechner,
and Dorde Zikelic. “Learning Provably Stabilizing Neural Controllers for Discrete-Time
Stochastic Systems.” In 21st International Symposium on Automated Technology
for Verification and Analysis, 14215:357–79. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-45329-8_17.
ieee: M. Ansaripour, K. Chatterjee, T. A. Henzinger, M. Lechner, and D. Zikelic,
“Learning provably stabilizing neural controllers for discrete-time stochastic
systems,” in 21st International Symposium on Automated Technology for Verification
and Analysis, Singapore, Singapore, 2023, vol. 14215, pp. 357–379.
ista: 'Ansaripour M, Chatterjee K, Henzinger TA, Lechner M, Zikelic D. 2023. Learning
provably stabilizing neural controllers for discrete-time stochastic systems.
21st International Symposium on Automated Technology for Verification and Analysis.
ATVA: Automated Technology for Verification and Analysis, LNCS, vol. 14215, 357–379.'
mla: Ansaripour, Matin, et al. “Learning Provably Stabilizing Neural Controllers
for Discrete-Time Stochastic Systems.” 21st International Symposium on Automated
Technology for Verification and Analysis, vol. 14215, Springer Nature, 2023,
pp. 357–79, doi:10.1007/978-3-031-45329-8_17.
short: M. Ansaripour, K. Chatterjee, T.A. Henzinger, M. Lechner, D. Zikelic, in:,
21st International Symposium on Automated Technology for Verification and Analysis,
Springer Nature, 2023, pp. 357–379.
conference:
end_date: 2023-10-27
location: Singapore, Singapore
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2023-10-24
date_created: 2023-11-19T23:00:56Z
date_published: 2023-10-22T00:00:00Z
date_updated: 2025-07-14T09:09:59Z
day: '22'
department:
- _id: ToHe
- _id: KrCh
doi: 10.1007/978-3-031-45329-8_17
ec_funded: 1
intvolume: ' 14215'
language:
- iso: eng
month: '10'
oa_version: None
page: 357-379
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: 21st International Symposium on Automated Technology for Verification
and Analysis
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031453281'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Learning provably stabilizing neural controllers for discrete-time stochastic
systems
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14215
year: '2023'
...
---
_id: '14691'
abstract:
- lang: eng
text: "Continuous Group-Key Agreement (CGKA) allows a group of users to maintain
a shared key. It is the fundamental cryptographic primitive underlying group messaging
schemes and related protocols, most notably TreeKEM, the underlying key agreement
protocol of the Messaging Layer Security (MLS) protocol, a standard for group
messaging by the IETF. CKGA works in an asynchronous setting where parties only
occasionally must come online, and their messages are relayed by an untrusted
server. The most expensive operation provided by CKGA is that which allows for
a user to refresh their key material in order to achieve forward secrecy (old
messages are secure when a user is compromised) and post-compromise security (users
can heal from compromise). One caveat of early CGKA protocols is that these update
operations had to be performed sequentially, with any user wanting to update their
key material having had to receive and process all previous updates. Late versions
of TreeKEM do allow for concurrent updates at the cost of a communication overhead
per update message that is linear in the number of updating parties. This was
shown to be indeed necessary when achieving PCS in just two rounds of communication
by [Bienstock et al. TCC’20].\r\nThe recently proposed protocol CoCoA [Alwen et
al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements
are relaxed, and only a logarithmic number of rounds is required. The natural
question, thus, is whether CoCoA is optimal in this setting.\r\nIn this work we
answer this question, providing a lower bound on the cost (concretely, the amount
of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary
k number of rounds, that shows that CoCoA is very close to optimal. Additionally,
we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification
of it, with a reduced communication cost for certain k.\r\nWe prove our bound
in a combinatorial setting where the state of the protocol progresses in rounds,
and the state of the protocol in each round is captured by a set system, each
set specifying a set of users who share a secret key. We show this combinatorial
model is equivalent to a symbolic model capturing building blocks including PRFs
and public-key encryption, related to the one used by Bienstock et al.\r\nOur
lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of
updates per user the protocol requires to heal. This generalizes the n2 bound
for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1)
efficiency we get for the variants of the CoCoA protocol also introduced in this
paper."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. On the cost of post-compromise
security in concurrent Continuous Group-Key Agreement. In: 21st International
Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:271-300.
doi:10.1007/978-3-031-48621-0_10'
apa: 'Auerbach, B., Cueto Noval, M., Pascual Perez, G., & Pietrzak, K. Z. (2023).
On the cost of post-compromise security in concurrent Continuous Group-Key Agreement.
In 21st International Conference on Theory of Cryptography (Vol. 14371,
pp. 271–300). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_10'
chicago: Auerbach, Benedikt, Miguel Cueto Noval, Guillermo Pascual Perez, and Krzysztof
Z Pietrzak. “On the Cost of Post-Compromise Security in Concurrent Continuous
Group-Key Agreement.” In 21st International Conference on Theory of Cryptography,
14371:271–300. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_10.
ieee: B. Auerbach, M. Cueto Noval, G. Pascual Perez, and K. Z. Pietrzak, “On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement,” in
21st International Conference on Theory of Cryptography, Taipei, Taiwan,
2023, vol. 14371, pp. 271–300.
ista: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement. 21st
International Conference on Theory of Cryptography. TCC: Theory of Cryptography,
LNCS, vol. 14371, 271–300.'
mla: Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent
Continuous Group-Key Agreement.” 21st International Conference on Theory of
Cryptography, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:10.1007/978-3-031-48621-0_10.
short: B. Auerbach, M. Cueto Noval, G. Pascual Perez, K.Z. Pietrzak, in:, 21st International
Conference on Theory of Cryptography, Springer Nature, 2023, pp. 271–300.
conference:
end_date: 2023-12-02
location: Taipei, Taiwan
name: 'TCC: Theory of Cryptography'
start_date: 2023-11-29
date_created: 2023-12-17T23:00:53Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2023-12-18T08:36:51Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48621-0_10
intvolume: ' 14371'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1123
month: '11'
oa: 1
oa_version: Preprint
page: 271-300
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486203'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the cost of post-compromise security in concurrent Continuous Group-Key
Agreement
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14371
year: '2023'
...
---
_id: '14692'
abstract:
- lang: eng
text: "The generic-group model (GGM) aims to capture algorithms working over groups
of prime order that only rely on the group operation, but do not exploit any additional
structure given by the concrete implementation of the group. In it, it is possible
to prove information-theoretic lower bounds on the hardness of problems like the
discrete logarithm (DL) or computational Diffie-Hellman (CDH). Thus, since its
introduction, it has served as a valuable tool to assess the concrete security
provided by cryptographic schemes based on such problems. A work on the related
algebraic-group model (AGM) introduced a method, used by many subsequent works,
to adapt GGM lower bounds for one problem to another, by means of conceptually
simple reductions.\r\nIn this work, we propose an alternative approach to extend
GGM bounds from one problem to another. Following an idea by Yun [EC15], we show
that, in the GGM, the security of a large class of problems can be reduced to
that of geometric search-problems. By reducing the security of the resulting geometric-search
problems to variants of the search-by-hypersurface problem, for which information
theoretic lower bounds exist, we give alternative proofs of several results that
used the AGM approach.\r\nThe main advantage of our approach is that our reduction
from geometric search-problems works, as well, for the GGM with preprocessing
(more precisely the bit-fixing GGM introduced by Coretti, Dodis and Guo [Crypto18]).
As a consequence, this opens up the possibility of transferring preprocessing
GGM bounds from one problem to another, also by means of simple reductions. Concretely,
we prove novel preprocessing bounds on the hardness of the d-strong discrete logarithm,
the d-strong Diffie-Hellman inversion, and multi-instance CDH problems, as well
as a large class of Uber assumptions. Additionally, our approach applies to Shoup’s
GGM without additional restrictions on the query behavior of the adversary, while
the recent works of Zhang, Zhou, and Katz [AC22] and Zhandry [Crypto22] highlight
that this is not the case for the AGM approach."
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: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
citation:
ama: 'Auerbach B, Hoffmann C, Pascual Perez G. Generic-group lower bounds via reductions
between geometric-search problems: With and without preprocessing. In: 21st
International Conference on Theory of Cryptography. Vol 14371. Springer Nature;
2023:301-330. doi:10.1007/978-3-031-48621-0_11'
apa: 'Auerbach, B., Hoffmann, C., & Pascual Perez, G. (2023). Generic-group
lower bounds via reductions between geometric-search problems: With and without
preprocessing. In 21st International Conference on Theory of Cryptography
(Vol. 14371, pp. 301–330). Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_11'
chicago: 'Auerbach, Benedikt, Charlotte Hoffmann, and Guillermo Pascual Perez. “Generic-Group
Lower Bounds via Reductions between Geometric-Search Problems: With and without
Preprocessing.” In 21st International Conference on Theory of Cryptography,
14371:301–30. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_11.'
ieee: 'B. Auerbach, C. Hoffmann, and G. Pascual Perez, “Generic-group lower bounds
via reductions between geometric-search problems: With and without preprocessing,”
in 21st International Conference on Theory of Cryptography, 2023, vol.
14371, pp. 301–330.'
ista: 'Auerbach B, Hoffmann C, Pascual Perez G. 2023. Generic-group lower bounds
via reductions between geometric-search problems: With and without preprocessing.
21st International Conference on Theory of Cryptography. , LNCS, vol. 14371, 301–330.'
mla: 'Auerbach, Benedikt, et al. “Generic-Group Lower Bounds via Reductions between
Geometric-Search Problems: With and without Preprocessing.” 21st International
Conference on Theory of Cryptography, vol. 14371, Springer Nature, 2023, pp.
301–30, doi:10.1007/978-3-031-48621-0_11.'
short: B. Auerbach, C. Hoffmann, G. Pascual Perez, in:, 21st International Conference
on Theory of Cryptography, Springer Nature, 2023, pp. 301–330.
date_created: 2023-12-17T23:00:54Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2023-12-18T09:17:03Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48621-0_11
intvolume: ' 14371'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/808
month: '11'
oa: 1
oa_version: Preprint
page: 301-330
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486203'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Generic-group lower bounds via reductions between geometric-search problems:
With and without preprocessing'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14371
year: '2023'
...
---
_id: '14693'
abstract:
- lang: eng
text: "Lucas sequences are constant-recursive integer sequences with a long history
of applications in cryptography, both in the design of cryptographic schemes and
cryptanalysis. In this work, we study the sequential hardness of computing Lucas
sequences over an RSA modulus.\r\nFirst, we show that modular Lucas sequences
are at least as sequentially hard as the classical delay function given by iterated
modular squaring proposed by Rivest, Shamir, and Wagner (MIT Tech. Rep. 1996)
in the context of time-lock puzzles. Moreover, there is no obvious reduction in
the other direction, which suggests that the assumption of sequential hardness
of modular Lucas sequences is strictly weaker than that of iterated modular squaring.
In other words, the sequential hardness of modular Lucas sequences might hold
even in the case of an algorithmic improvement violating the sequential hardness
of iterated modular squaring.\r\nSecond, we demonstrate the feasibility of constructing
practically-efficient verifiable delay functions based on the sequential hardness
of modular Lucas sequences. Our construction builds on the work of Pietrzak (ITCS
2019) by leveraging the intrinsic connection between the problem of computing
modular Lucas sequences and exponentiation in an appropriate extension field."
acknowledgement: "Home Theory of Cryptography Conference paper\r\n(Verifiable) Delay
Functions from Lucas Sequences\r\nDownload book PDF\r\nDownload book EPUB\r\nSimilar
content being viewed by others\r\n\r\nSlider with three content items shown per
slide. Use the Previous and Next buttons to navigate the slides or the slide controller
buttons at the end to navigate through each slide.\r\nPrevious slide\r\nGeneric-Group
Delay Functions Require Hidden-Order Groups\r\nChapter© 2020\r\n\r\nShifted powers
in Lucas–Lehmer sequences\r\nArticle30 January 2019\r\n\r\nA New Class of Trapdoor
Verifiable Delay Functions\r\nChapter© 2023\r\n\r\nWeak Pseudoprimality Associated
with the Generalized Lucas Sequences\r\nChapter© 2022\r\n\r\nOn the Security of
Time-Lock Puzzles and Timed Commitments\r\nChapter© 2020\r\n\r\nGeneration of full
cycles by a composition of NLFSRs\r\nArticle08 March 2014\r\n\r\nCryptographically
Strong de Bruijn Sequences with Large Periods\r\nChapter© 2013\r\n\r\nOpen Problems
on With-Carry Sequence Generators\r\nChapter© 2014\r\n\r\nGenerically Speeding-Up
Repeated Squaring Is Equivalent to Factoring: Sharp Thresholds for All Generic-Ring
Delay Functions\r\nChapter© 2020\r\n\r\nNext slide\r\nGo to slide 1\r\nGo to slide
2\r\nGo to slide 3\r\n(Verifiable) Delay Functions from Lucas Sequences\r\nCharlotte
Hoffmann, Pavel Hubáček, Chethan Kamath & Tomáš Krňák \r\nConference paper\r\nFirst
Online: 27 November 2023\r\n83 Accesses\r\n\r\nPart of the Lecture Notes in Computer
Science book series (LNCS,volume 14372)\r\n\r\nAbstract\r\nLucas sequences are constant-recursive
integer sequences with a long history of applications in cryptography, both in the
design of cryptographic schemes and cryptanalysis. In this work, we study the sequential
hardness of computing Lucas sequences over an RSA modulus.\r\n\r\nFirst, we show
that modular Lucas sequences are at least as sequentially hard as the classical
delay function given by iterated modular squaring proposed by Rivest, Shamir, and
Wagner (MIT Tech. Rep. 1996) in the context of time-lock puzzles. Moreover, there
is no obvious reduction in the other direction, which suggests that the assumption
of sequential hardness of modular Lucas sequences is strictly weaker than that of
iterated modular squaring. In other words, the sequential hardness of modular Lucas
sequences might hold even in the case of an algorithmic improvement violating the
sequential hardness of iterated modular squaring.\r\n\r\nSecond, we demonstrate
the feasibility of constructing practically-efficient verifiable delay functions
based on the sequential hardness of modular Lucas sequences. Our construction builds
on the work of Pietrzak (ITCS 2019) by leveraging the intrinsic connection between
the problem of computing modular Lucas sequences and exponentiation in an appropriate
extension field.\r\n\r\nKeywords\r\nDelay functions\r\nVerifiable delay functions\r\nLucas
sequences\r\nDownload conference paper PDF\r\n\r\n1 Introduction\r\nA verifiable
delay function (VDF) \r\n is a function that satisfies two properties. First, it
is a delay function, which means it must take a prescribed (wall) time T to compute
f, irrespective of the amount of parallelism available. Second, it should be possible
for anyone to quickly verify – say, given a short proof \r\n – the value of the
function (even without resorting to parallelism), where by quickly we mean that
the verification time should be independent of or significantly smaller than T (e.g.,
logarithmic in T). If we drop either of the two requirements, then the primitive
turns out trivial to construct. For instance, for an appropriately chosen hash function
h, the delay function \r\n defined by T-times iterated hashing of the input is a
natural heuristic for an inherently sequential task which, however, seems hard to
verify more efficiently than by recomputing. On the other hand, the identity function
\r\n is trivial to verify but also easily computable. Designing a simple function
satisfying the two properties simultaneously proved to be a nontrivial task.\r\n\r\nThe
notion of VDFs was introduced in [31] and later formalised in [9]. In principle,
since the task of constructing a VDF reduces to the task of incrementally-verifiable
computation [9, 53], constructions of VDFs could leverage succinct non-interactive
arguments of knowledge (SNARKs): take any sequentially-hard function f (for instance,
iterated hashing) as the delay function and then use the SNARK on top of it as the
mechanism for verifying the computation of the delay function. However, as discussed
in [9], the resulting construction is not quite practical since we would rely on
a general-purpose machinery of SNARKs with significant overhead.\r\n\r\nEfficient
VDFs via Algebraic Delay Functions. VDFs have recently found interesting applications
in design of blockchains [17], randomness beacons [43, 51], proofs of data replication
[9], or short-lived zero-knowledge proofs and signatures [3]. Since efficiency is
an important factor there, this has resulted in a flurry of constructions of VDFs
that are tailored with application and practicality in mind. They rely on more algebraic,
structured delay functions that often involve iterating an atomic operation so that
one can resort to custom proof systems to achieve verifiability. These constructions
involve a range of algebraic settings like the RSA or class groups [5, 8, 25, 42,
55], permutation polynomials over finite fields [9], isogenies of elliptic curves
[21, 52] and, very recently, lattices [15, 28]. The constructions in [42, 55] are
arguably the most practical and the mechanism that underlies their delay function
is the same: carry out iterated squaring in groups of unknown order, like RSA groups
[47] or class groups [12]. What distinguishes these two proposals is the way verification
is carried out, i.e., how the underlying “proof of exponentiation” works: while
Pietrzak [42] resorts to an LFKN-style recursive proof system [35], Wesolowski [55]
uses a clever linear decomposition of the exponent.\r\n\r\nIterated Modular Squaring
and Sequentiality. The delay function that underlies the VDFs in [5, 25, 42, 55]
is the same, and its security relies on the conjectured sequential hardness of iterated
squaring in a group of unknown order (suggested in the context of time-lock puzzles
by Rivest, Shamir, and Wagner [48]). Given that the practically efficient VDFs all
rely on the above single delay function, an immediate open problem is to identify
additional sources of sequential hardness that are structured enough to support
practically efficient verifiability.\r\n\r\n1.1 Our Approach to (Verifiable) Delay
Functions\r\nIn this work, we study an alternative source of sequential hardness
in the algebraic setting and use it to construct efficient verifiable delay functions.
The sequentiality of our delay function relies on an atomic operation that is related
to the computation of so-called Lucas sequences [29, 34, 57], explained next.\r\n\r\nLucas
Sequences. A Lucas sequence is a constant-recursive integer sequence that satisfies
the recurrence relation\r\n\r\nfor integers P and Q.Footnote1 Specifically, the
Lucas sequences of integers \r\n and \r\n of the first and second type (respectively)
are defined recursively as\r\n\r\nwith \r\n, and\r\n\r\nwith \r\n.\r\n\r\nThese
sequences can be alternatively defined by the characteristic polynomial \r\n. Specifically,
given the discriminant \r\n of the characteristic polynomial, one can alternatively
compute the above sequences by performing operations in the extension field\r\n\r\nusing
the identities\r\n\r\nwhere \r\n and its conjugate \r\n are roots of the characteristic
polynomial. Since conjugation and exponentiation commute in the extension field
(i.e., \r\n), computing the i-th terms of the two Lucas sequences over integers
reduces to computing \r\n in the extension field, and vice versa.\r\n\r\nThe intrinsic
connection between computing the terms in the Lucas sequences and that of exponentiation
in the extension has been leveraged to provide alternative instantiations of public-key
encryption schemes like RSA and ElGamal in terms of Lucas sequences [7, 30]. However,
as we explain later, the corresponding underlying computational hardness assumptions
are not necessarily equivalent.\r\n\r\nOverview of Our Delay Function. The delay
function in [5, 25, 42, 55] is defined as the iterated squaring base x in a (safe)
RSA groupFootnote2 modulo N:\r\n\r\nOur delay function is its analogue in the setting
of Lucas sequences:\r\n\r\nAs mentioned above, computing \r\n can be carried out
equivalently in the extension field \r\n using the known relationship to roots of
the characteristic polynomial of the Lucas sequence. Thus, the delay function can
be alternatively defined as\r\n\r\nNote that the atomic operation of our delay function
is “doubling” the index of an element of the Lucas sequence modulo N (i.e., \r\n)
or, equivalently, squaring in the extension field \r\n (as opposed to squaring in
\r\n). Using the representation of \r\n as \r\n, squaring in \r\n can be expressed
as a combination of squaring, multiplication and addition modulo N, since\r\n\r\n(1)\r\nSince
\r\n is a group of unknown order (provided the factorization of N is kept secret),
iterated squaring remains hard here. In fact, we show in Sect. 3.2 that iterated
squaring in \r\n is at least as hard as iterated squaring for RSA moduli N. Moreover,
we conjecture in Conjecture 1 that it is, in fact, strictly harder (also see discussion
below on advantages of our approach).\r\n\r\nVerifying Modular Lucas Sequence. To
obtain a VDF, we need to show how to efficiently verify our delay function. To this
end, we show how to adapt the interactive proof of exponentiation from [42] to our
setting, which then – via the Fiat-Shamir Transform [22] – yields the non-interactive
verification algorithm.Footnote3 Thus, our main result is stated informally below.\r\n\r\nTheorem
1\r\n(Informally stated, see Theorem 2). Assuming sequential hardness of modular
Lucas sequence, there exists statistically-sound VDF in the random-oracle model.\r\n\r\nHowever,
the modification of Pietrzak’s protocol is not trivial and we have to overcome several
hurdles that we face in this task, which we elaborate on in Sect. 1.2. We conclude
this section with discussions about our results.\r\n\r\nAdvantage of Our Approach.
Our main advantage is the reliance on a potentially weaker (sequential) hardness
assumption while maintaining efficiency: we show in Sect. 3.2 that modular Lucas
sequences are at least as sequentially-hard as the classical delay function given
by iterated modular squaring [48]. Despite the linear recursive structure of Lucas
sequences, there is no obvious reduction in the other direction, which suggests
that the assumption of sequential hardness of modular Lucas sequences is strictly
weaker than that of iterated modular squaring (Conjecture 1). In other words, the
sequential hardness of modular Lucas sequences might hold even in the case of an
algorithmic improvement violating the sequential hardness of iterated modular squaring.
Even though both assumptions need the group order to be hidden, we believe that
there is need for a nuanced analysis of sequential hardness assumptions in hidden
order groups, especially because all current delay functions that provide sufficient
structure for applications are based on iterated modular squaring. If the iterated
modular squaring assumption is broken, our delay function is currently the only
practical alternative in the RSA group.\r\n\r\nDelay Functions in Idealised Models.
Recent works studied the relationship of group-theoretic (verifiable) delay functions
to the hardness of factoring in idealised models such as the algebraic group model
and the generic ring model [27, 50]. In the generic ring model, Rotem and Segev
[50] showed the equivalence of straight-line delay functions in the RSA setting
and factoring. Our construction gives rise to a straight-line delay function and,
by their result, its sequentiality is equivalent to factoring for generic algorithms.
However, their result holds only in the generic ring model and leaves the relationship
between the two assumptions unresolved in the standard model.\r\n\r\nCompare this
with the status of the RSA assumption and factoring. On one hand, we know that in
the generic ring model, RSA and factoring are equivalent [2]. Yet, it is possible
to rule out certain classes of reductions from factoring to RSA in the standard
model [11]. Most importantly, despite the equivalence in the generic ring model,
there is currently no reduction from factoring to RSA in the standard model and
it remains one of the major open problems in number theory related to cryptography
since the introduction of the RSA assumption.\r\n\r\nIn summary, speeding up iterated
squaring by a non-generic algorithm could be possible (necessarily exploiting the
representations of ring elements modulo N), while such an algorithm may not lead
to a speed-up in the computation of modular Lucas sequences despite the result of
Rotem and Segev [50].\r\n\r\n1.2 Technical Overview\r\nPietrzak’s VDF. Let \r\n
be an RSA modulus where p and q are safe primes and let x be a random element from
\r\n. At its core, Pietrzak’s VDF relies on the interactive protocol for the statement\r\n\r\n“(N,
x, y, T) satisfies \r\n”.\r\n\r\nThe protocol is recursive and, in a round-by-round
fashion, reduces the claim to a smaller statement by halving the time parameter.
To be precise, in each round, the (honest) prover sends the “midpoint” \r\n of the
current statement to the verifier and they together reduce the statement to\r\n\r\n“\r\n
satisfies \r\n”,\r\n\r\nwhere \r\n and \r\n for a random challenge r. This is continued
till \r\n is obtained at which point the verifier simply checks whether \r\n using
a single modular squaring.\r\n\r\nSince the challenges r are public, the protocol
can be compiled into a non-interactive one using the Fiat-Shamir transform [22]
and this yields a means to verify the delay function\r\n\r\nIt is worth pointing
out that the choice of safe primes is crucial for proving soundness: in case the
group has easy-to-find elements of small order then it becomes easy to break soundness
(see, e.g., [10]).\r\n\r\nAdapting Pietrzak’s Protocol to Lucas Sequences. For a
modulus \r\n and integers \r\n, recall that our delay function is defined as\r\n\r\nor
equivalently\r\n\r\nfor the discriminant \r\n of the characteristic polynomial \r\n.
Towards building a verification algorithm for this delay function, the natural first
step is to design an interactive protocol for the statement\r\n\r\n“(N, P, Q, y,
T) satisfies \r\n.”\r\n\r\nIt turns out that the interactive protocol from [42]
can be adapted for this purpose. However, we encounter two technicalities in this
process.\r\n\r\nDealing with elements of small order. The main problem that we face
while designing our protocol is avoiding elements of small order. In the case of
[42], this was accomplished by moving to the setting of signed quadratic residues
[26] in which the sub-groups are all of large order. It is not clear whether a corresponding
object exists for our algebraic setting. However, in an earlier draft of Pietrzak’s
protocol [41], this problem was dealt with in a different manner: the prover sends
a square root of \r\n, from which the original \r\n can be recovered easily (by
squaring it) with a guarantee that the result lies in a group of quadratic residues
\r\n. Notice that the prover knows the square root of \r\n, because it is just a
previous term in the sequence he computed.\r\n\r\nIn our setting, we cannot simply
ask for the square root of the midpoint as the subgroup of \r\n we effectively work
in has a different structure. Nevertheless, we can use a similar approach: for an
appropriately chosen small a, we provide an a-th root of \r\n (instead of \r\n itself)
to the prover in the beginning of the protocol. The prover then computes the whole
sequence for \r\n. In the end, he has the a-th root of every term of the original
sequence and he can recover any element of the original sequence by raising to the
a-th power.\r\n\r\nSampling strong modulus. The second technicality is related to
the first one. In order to ensure that we can use the above trick, we require a
modulus where the small subgroups are reasonably small not only in the group \r\n
but also in the extension \r\n. Thus the traditional sampling algorithms that are
used to sample strong primes (e.g., [46]) are not sufficient for our purposes. However,
sampling strong primes that suit our criteria can still be carried out efficiently
as we show in the full version.\r\n\r\nComparing Our Technique with [8, 25]. The
VDFs in [8, 25] are also inspired by [42] and, hence, faced the same problem of
low-order elements. In [8], this is dealt with by amplifying the soundness at the
cost of parallel repetition and hence larger proofs and extra computation. In [25],
the number of repetitions of [8] is reduced significantly by introducing the following
technique: The exponent of the initial instance is reduced by some parameter \r\n
and at the end of an interactive phase, the verifier performs final exponentiation
with \r\n, thereby weeding out potential false low-order elements in the claim.
This technique differs from the approach taken in our work in the following ways:
The technique from [25] works in arbitrary groups but it requires the parameter
\r\n to be large and of a specific form. In particular, the VDF becomes more efficient
when \r\n is larger than \r\n. In our protocol, we work in RSA groups whose modulus
is the product of primes that satisfy certain conditions depending on a. This enables
us to choose a parameter a that is smaller than a statistical security parameter
and thereby makes the final exponentiation performed by the verifier much more efficient.
Further, a can be any natural number, while \r\n must be set as powers of all small
prime numbers up a certain bound in [25].\r\n\r\n1.3 More Related Work\r\nTimed
Primitives. The notion of VDFs was introduced in [31] and later formalised in [9].
VDFs are closely related to the notions of time-lock puzzles [48] and proofs of
sequential work [36]. Roughly speaking, a time-lock puzzle is a delay function that
additionally allows efficient sampling of the output via a trapdoor. A proof of
sequential work, on the other hand, is a delay “multi-function”, in the sense that
the output is not necessarily unique. Constructions of time-lock puzzles are rare
[6, 38, 48], and there are known limitations: e.g., that it cannot exist in the
random-oracle model [36]. However, we know how to construct proofs of sequential
work in the random-oracle model [1, 16, 19, 36].\r\n\r\nSince VDFs have found several
applications, e.g., in the design of resource-efficient blockchains [17], randomness
beacons [43, 51] and proof of data replication [9], there have been several constructions.
Among them, the most notable are the iterated-squaring based construction from [8,
25, 42, 55], the permutation-polynomial based construction from [9], the isogenies-based
construction from [13, 21, 52] and the construction from lattice problems [15, 28].
The constructions in [42, 55] are quite practical (see the survey [10]) and the
VDF deployed in the cryptocurrency Chia is basically their construction adapted
to the algebraic setting of class groups [17]. This is arguably the closest work
to ours. On the other hand, the constructions from [21, 52], which work in the algebraic
setting of isogenies of elliptic curves where no analogue of square and multiply
is known, simply rely on “exponentiation”. Although, these constructions provide
a certain form of quantum resistance, they are presently far from efficient. Freitag
et al. [23] constructed VDFs from any sequentially hard function and polynomial
hardness of learning with errors, the first from standard assumptions. The works
of Cini, Lai, and Malavolta [15, 28] constructed the first VDF from lattice-based
assumptions and conjectured it to be post-quantum secure.\r\n\r\nSeveral variants
of VDFs have also been proposed. A VDF is said to be unique if the proof that is
used for verification is unique [42]. Recently, Choudhuri et al. [5] constructed
unique VDFs from the sequential hardness of iterated squaring in any RSA group and
polynomial hardness of LWE. A VDF is tight [18] if the gap between simply computing
the function and computing it with a proof is small. Yet another extension is a
continuous VDF [20]. The feasibility of time-lock puzzles and proofs of sequential
works were recently extended to VDFs. It was shown [50] that the latter requirement,
i.e., working in a group of unknown order, is inherent in a black-box sense. It
was shown in [18, 37] that there are barriers to constructing tight VDFs in the
random-oracle model.\r\n\r\nVDFs also have surprising connection to complexity theory
[14, 20, 33].\r\n\r\nWork Related to Lucas Sequences. Lucas sequences have long
been studied in the context of number theory: see for example [45] or [44] for a
survey of its applications to number theory. Its earliest application to cryptography
can be traced to the \r\n factoring algorithm [56]. Constructive applications were
found later thanks to the parallels with exponentiation. Several encryption and
signature schemes were proposed, most notably the LUC family of encryption and signatures
[30, 39]. It was later shown that some of these schemes can be broken or that the
advantages it claimed were not present [7]. Other applications can be found in [32].\r\n\r\n2
Preliminaries\r\n2.1 Interactive Proof Systems\r\nInteractive Protocols. An interactive
protocol consists of a pair \r\n of interactive Turing machines that are run on
a common input \r\n. The first machine \r\n is the prover and is computationally
unbounded. The second machine \r\n is the verifier and is probabilistic polynomial-time.\r\n\r\nIn
an \r\n-round (i.e., \r\n-message) interactive protocol, in each round \r\n, first
\r\n sends a message \r\n to \r\n and then \r\n sends a message \r\n to \r\n, where
\r\n is a finite alphabet. At the end of the interaction, \r\n runs a (deterministic)
Turing machine on input \r\n. The interactive protocol is public-coin if \r\n is
a uniformly distributed random string in \r\n.\r\n\r\nInteractive Proof Systems.
The notion of an interactive proof for a language L is due to Goldwasser, Micali
and Rackoff [24].\r\n\r\nDefinition 1\r\nFor a function \r\n, an interactive protocol
\r\n is an \r\n-statistically-sound interactive proof system for L if:\r\n\r\nCompleteness:
For every \r\n, if \r\n interacts with \r\n on common input \r\n, then \r\n accepts
with probability 1.\r\n\r\nSoundness: For every \r\n and every (computationally-unbounded)
cheating prover strategy \r\n, the verifier \r\n accepts when interacting with \r\n
with probability less than \r\n, where \r\n is called the soundness error.\r\n\r\n2.2
Verifiable Delay Functions\r\nWe adapt the definition of verifiable delay functions
from [9] but we decouple the verifiability and sequentiality properties for clarity
of exposition of our results. First, we present the definition of a delay function.\r\n\r\nDefinition
2\r\nA delay function \r\n consists of a triple of algorithms with the following
syntax:\r\n\r\n:\r\n\r\nOn input a security parameter \r\n, the algorithm \r\n outputs
public parameters \r\n.\r\n\r\n:\r\n\r\nOn input public parameters \r\n and a time
parameter \r\n, the algorithm \r\n outputs a challenge x.\r\n\r\n:\r\n\r\nOn input
a challenge pair (x, T), the (deterministic) algorithm \r\n outputs the value y
of the delay function in time T.\r\n\r\nThe security property required of a delay
function is sequential hardness as defined below.\r\n\r\nDefinition 3\r\n(Sequentiality).
We say that a delay function \r\n satisfies the sequentiality property, if there
exists an \r\n such that for all \r\n and for every adversary \r\n, where \r\n uses
\r\n processors and runs in time \r\n, there exists a negligible function \r\n such
that\r\n\r\nfigure a\r\nA few remarks about our definition of sequentiality are
in order:\r\n\r\n1.\r\nWe require computing \r\n to be hard in less than T sequential
steps even using any polynomially-bounded amount of parallelism and precomputation.
Note that it is necessary to bound the amount of parallelism, as an adversary could
otherwise break the underlying hardness assumption (e.g. hardness of factorization).
Analogously, T should be polynomial in \r\n as, otherwise, breaking the underlying
hardness assumptions becomes easier than computing \r\n itself for large values
of T.\r\n\r\n2.\r\nAnother issue is what bound on the number of sequential steps
of the adversary should one impose. For example, the delay function based on T repeated
modular squarings can be computed in sequential time \r\n using polynomial parallelism
[4]. Thus, one cannot simply bound the sequential time of the adversary by o(T).
Similarly to [38], we adapt the \r\n bound for \r\n which, in particular, is asymptotically
smaller than \r\n.\r\n\r\n3.\r\nWithout loss of generality, we assume that the size
of \r\n is at least linear in n and the adversary A does not have to get the unary
representation of the security parameter \r\n as its input.\r\n\r\nThe definition
of verifiable delay function extends a delay function with the possibility to compute
publicly-verifiable proofs of correctness of the output value.\r\n\r\nDefinition
4\r\nA delay function \r\n is a verifiable delay function if it is equipped with
two additional algorithms \r\n and \r\n with the following syntax:\r\n\r\n:\r\n\r\nOn
input public parameters and a challenge pair (x, T), the \r\n algorithm outputs
\r\n, where \r\n is a proof that the output y is the output of \r\n.\r\n\r\n:\r\n\r\nOn
input public parameters, a challenge pair (x, T), and an output/proof pair \r\n,
the (deterministic) algorithm \r\n outputs either \r\n or \r\n.\r\n\r\nIn addition
to sequentiality (inherited from the underlying delay function), the \r\n and \r\n
algorithms must together satisfy correctness and (statistical) soundness as defined
below.\r\n\r\nDefinition 5\r\n(Correctness). A verifiable delay function \r\n is
correct if for all \r\n\r\nfigure b\r\nDefinition 6\r\n(Statistical soundness).
A verifiable delay function \r\n is statistically sound if for every (computationally
unbounded) malicious prover \r\n there exists a negligible function \r\n such that
for all \r\n\r\nfigure c\r\n3 Delay Functions from Lucas Sequences\r\nIn this section,
we propose a delay function based on Lucas sequences and prove its sequentiality
assuming that iterated squaring in a group of unknown order is sequential (Sect.
3.1). Further, we conjecture (Sect. 3.2) that our delay function candidate is even
more robust than its predecessor proposed by Rivest, Shamir, and Wagner [48]. Finally,
we turn our delay function candidate into a verifiable delay function (Sect. 4).\r\n\r\n3.1
The Atomic Operation\r\nOur delay function is based on subsequences of Lucas sequences,
whose indexes are powers of two. Below, we use \r\n to denote the set of non-negative
integers.\r\n\r\nDefinition 7\r\nFor integers \r\n, the Lucas sequences \r\n and
\r\n are defined for all \r\n as\r\n\r\nwith \r\n and \r\n, and\r\n\r\nwith \r\n
and \r\n.\r\n\r\nWe define subsequences \r\n, respectively \r\n, of \r\n, respectively
\r\n for all \r\n as\r\n\r\n(2)\r\nAlthough the value of \r\n depends on parameters
(P, Q), we omit (P, Q) from the notation because these parameters will be always
obvious from the context.\r\n\r\nThe underlying atomic operation for our delay function
is\r\n\r\nThere are several ways to compute \r\n in T sequential steps, and we describe
two of them below.\r\n\r\nAn Approach Based on Squaring in a Suitable Extension
Ring. To compute the value \r\n, we can use the extension ring \r\n, where \r\n
is the discriminant of the characteristic polynomial \r\n of the Lucas sequence.
The characteristic polynomial f(z) has a root \r\n, and it is known that, for all
\r\n, it holds that\r\n\r\nThus, by iterated squaring of \r\n, we can compute terms
of our target subsequences. To get a better understanding of squaring in the extension
ring, consider the representation of the root \r\n for some \r\n. Then,\r\n\r\nThen,
the atomic operation of our delay function can be interpreted as \r\n, defined for
all \r\n as\r\n\r\n(3)\r\nAn Approach Based on Known Identities. Many useful identities
for members of modular Lucas sequences are known, such as\r\n\r\n(4)\r\nSetting
\r\n we get\r\n\r\n(5)\r\nThe above identities are not hard to derive (see, e.g.,
Lemma 12.5 in [40]). Indexes are doubled on each of application of the identities
in Eq. (5), and, thus, for \r\n, we define an auxiliary sequence \r\n by \r\n. Using
the identities in Eq. (5), we get recursive equations\r\n\r\n(6)\r\nThen, the atomic
operation of our delay function can be interpreted as \r\n, defined for all \r\n
as\r\n\r\n(7)\r\nAfter a closer inspection, the reader may have an intuition that
an auxiliary sequence \r\n, which introduces a third state variable, is redundant.
This intuition is indeed right. In fact, there is another easily derivable identity\r\n\r\n(8)\r\nwhich
can be found, e.g., as Lemma 12.2 in [40]. On the other hand, Eq. (8) is quite interesting
because it allows us to compute large powers of an element \r\n using two Lucas
sequences. We use this fact in the security reduction in Sect. 3.2. Our construction
of a delay function, denoted \r\n, is given in Fig. 1.\r\n\r\nFig. 1.\r\nfigure
1\r\nOur delay function candidate \r\n based on a modular Lucas sequence.\r\n\r\nFull
size image\r\nOn the Discriminant D. Notice that whenever D is a quadratic residue
modulo N, the value \r\n is an element of \r\n and hence \r\n. By definition, LCS.Gen
generates a parameter D that is a quadratic residue with probability 1/4, so it
might seem that in one fourth of the cases there is another approach to compute
\r\n: find the element \r\n and then perform n sequential squarings in the group
\r\n. However, it is well known that finding square roots of uniform elements in
\r\n is equivalent to factoring the modulus N, so this approach is not feasible.
We can therefore omit any restrictions on the discriminant D in the definition of
our delay function LCS.\r\n\r\n3.2 Reduction from RSW Delay Function\r\nIn order
to prove the sequentiality property (Definition 3) of our candidate \r\n, we rely
on the standard conjecture of the sequentiality of the \r\n time-lock puzzles, implicitly
stated in [48] as the underlying hardness assumption.\r\n\r\nDefinition 8\r\n(\r\n
delay function). The \r\n delay function is defined as follows:\r\n\r\n: Samples
two n-bit primes p and q and outputs \r\n.\r\n\r\n: Outputs an x sampled from the
uniform distribution on \r\n.\r\n\r\n: Outputs \r\n.\r\n\r\nTheorem 2\r\nIf the
\r\n delay function has the sequentiality property, then the \r\n delay function
has the sequentiality property.\r\n\r\nProof\r\nSuppose there exists an adversary
\r\n who contradicts the sequentiality of \r\n, where \r\n is a precomputation algorithm
and \r\n is an online algorithm. We construct an adversary \r\n who contradicts
the sequentiality of \r\n as follows:\r\n\r\nThe algorithm \r\n is defined identically
to the algorithm \r\n.\r\n\r\nOn input \r\n, \r\n picks a P from the uniform distribution
on \r\n, sets\r\n\r\nand it runs \r\n to compute \r\n. The algorithm \r\n computes
\r\n using the identity in Eq. (8).\r\n\r\nNote that the input distribution for
the algorithm \r\n produced by \r\n differs from the one produced by \r\n, because
the \r\n generator samples Q from the uniform distribution on \r\n (instead of \r\n).
However, this is not a problem since the size of \r\n is negligible compared to
the size of \r\n, so the statistical distance between the distribution of D produced
by \r\n and the distribution of D sampled by \r\n is negligible in the security
parameter. Thus, except for a negligible multiplicative loss, the adversary \r\n
attains the same success probability of breaking the sequentiality of \r\n as the
probability of \r\n breaking the sequentiality of \r\n – a contradiction to the
assumption of the theorem. \r\n\r\nWe believe that the converse implication to
Theorem 2 is not true, i.e., that breaking the sequentiality of \r\n does not necessarily
imply breaking the sequentiality of \r\n. Below, we state it as a conjecture.\r\n\r\nConjecture
1\r\nSequentiality of \r\n cannot be reduced to sequentiality of \r\n.\r\n\r\nOne
reason why the above conjecture might be true is that, while the \r\n delay function
is based solely only on multiplication in the group \r\n, our \r\n delay function
uses the full arithmetic (addition and multiplication) of the commutative ring \r\n.\r\n\r\nOne
way to support the conjecture would be to construct an algorithm that speeds up
iterated squaring but is not immediately applicable to Lucas sequences. By [49]
we know that this cannot be achieved by a generic algorithm. A non-generic algorithm
that solves iterated squaring in time \r\n is presented in [4]. The main tool of
their construction is the Explicit Chinese Remainder Theorem modulo N. However,
a similiar theorem exists also for univariate polynomial rings, which suggests that
a similar speed-up can be obtained for our delay function by adapting the techniques
in [4] to our setting.\r\n\r\n4 VDF from Lucas Sequences\r\nIn Sect. 3.1 we saw
different ways of computing the atomic operation of the delay function. Computing
\r\n in the extension field seems to be the more natural and time and space effective
approach. Furthermore, writing the atomic operation \r\n as \r\n is very clear,
and, thus, we follow this approach throughout the rest of the paper.\r\n\r\n4.1
Structure of \r\nTo construct a VDF based on Lucas sequences, we use an algebraic
extension\r\n\r\n(9)\r\nwhere N is an RSA modulus and \r\n. In this section, we
describe the structure of the algebraic extension given in Expression (9). Based
on our understanding of the structure of the above algebraic extension, we can conclude
that using modulus N composed of safe primes (i.e., for all prime factors p of N,
\r\n has a large prime divisor) is necessary but not sufficient condition for security
of our construction. We specify some sufficient conditions on factors of N in the
subsequent Sect. 4.2.\r\n\r\nFirst, we introduce some simplifying notation for quotient
rings.\r\n\r\nDefinition 9\r\nFor \r\n and \r\n, we denote by \r\n the quotient
ring \r\n, where (m, f(x)) denotes the ideal of the ring \r\n generated by m and
f(x).\r\n\r\nObservation 1, below, allows us to restrict our analysis only to the
structure of \r\n for prime \r\n.\r\n\r\nObservation 1\r\nLet \r\n be distinct primes,
\r\n and \r\n. Then\r\n\r\nProof\r\nUsing the Chinese reminder theorem, we get\r\n\r\nas
claimed. \r\n\r\nThe following lemma characterizes the structure of \r\n with
respect to the discriminant of f. We use \r\n to denote the standard Legendre symbol.\r\n\r\nLemma
1\r\nLet \r\n and \r\n be a polynomial of degree 2 with the discriminant D. Then\r\n\r\nProof\r\nWe
consider each case separately:\r\n\r\nIf \r\n, then f(x) is irreducible over \r\n
and \r\n is a field with \r\n elements. Since \r\n is a finite field, \r\n is cyclic
and contains \r\n elements.\r\n\r\nIf \r\n, then \r\n and f has some double root
\r\n and it can be written as \r\n for some \r\n. Since the ring \r\n is isomorphic
to the ring \r\n (consider the isomorphism \r\n), we can restrict ourselves to describing
the structure of \r\n.\r\n\r\nWe will prove that the function \r\n,\r\n\r\nis an
isomorphism. First, the polynomial \r\n is invertible if and only if \r\n (inverse
is \r\n). For the choice \r\n, we have\r\n\r\nThus \r\n is onto. Second, \r\n is,
in fact, a bijection, because\r\n\r\n(10)\r\nFinally, \r\n is a homomorphism, because\r\n\r\nIf
\r\n, then f(x) has two roots \r\n. We have an isomorphism\r\n\r\nand \r\n. \r\n\r\n4.2
Strong Groups and Strong Primes\r\nTo achieve the verifiability property of our
construction, we need \r\n to contain a strong subgroup (defined next) of order
asymptotically linear in p. We remark that our definition of strong primes is stronger
than the one by Rivest and Silverman [46].\r\n\r\nDefinition 10\r\n(Strong groups).
For \r\n, we say that a non-trivial group \r\n is \r\n-strong, if the order of each
non-trivial subgroup of \r\n is greater than \r\n.\r\n\r\nObservation 2\r\nIf \r\n
and \r\n are \r\n-strong groups, then \r\n is a \r\n-strong group.\r\n\r\nIt can
be seen from Lemma 1 that \r\n always contains groups of small order (e.g. \r\n).
To avoid these, we descend into the subgroup of a-th powers of elements of \r\n.
Below, we introduce the corresponding notation.\r\n\r\nDefinition 11\r\nFor an Abelian
group \r\n and \r\n, we define the subgroup \r\n of \r\n in the multiplicative notation
and \r\n in the additive notation.\r\n\r\nFurther, we show in Lemma 2 below that
\r\n-strong primality (defined next) is a sufficient condition for \r\n to be a
\r\n-strong group.\r\n\r\nDefinition 12\r\n(Strong primes). Let \r\n and \r\n. We
say that p is a \r\n-strong prime, if \r\n and there exists \r\n, \r\n, such that
\r\n and every prime factor of W is greater than \r\n.\r\n\r\nSince a is a public
parameter in our setup, super-polynomial a could reveal partial information about
the factorization of N. However, we could allow a to be polynomial in \r\n while
maintaining hardness of factoring N.Footnote4 For the sake of simplicity of Definition
12, we rather use stronger condition \r\n. The following simple observation will
be useful for proving Lemma 2.\r\n\r\nObservation 3\r\nFor \r\n.\r\n\r\nLemma 2\r\nLet
p be a \r\n-strong prime and \r\n be a quadratic polynomial. Then, \r\n is a \r\n-strong
group.\r\n\r\nProof\r\nFrom definition of the strong primes, there exists \r\n,
whose factors are bigger than \r\n and \r\n. We denote \r\n a factor of W. Applying
Observation 3 to Lemma 1, we get\r\n\r\nIn particular, we used above the fact that
Observation 2 implies that \r\n as explained next. Since \r\n, all divisors of \r\n
are divisors of aW. By definition of a and W in Definition 12, we also have that
\r\n, which implies that any factor of \r\n divides either a or W, but not both.
When we divide \r\n by all the common divisors with a, only the common divisors
with W are left, which implies \r\n. The proof of the lemma is now completed by
Observation 2.\r\n\r\nCorollary 1\r\nLet p be a \r\n-strong prime, q be a \r\n-strong
prime, \r\n, \r\n, \r\n and \r\n. Then \r\n is \r\n-strong.\r\n\r\n4.3 Our Interactive
Protocol\r\nOur interactive protocol is formally described in Fig. 3. To understand
this protocol, we first recall the outline of Pietrzak’s interactive protocol from
Sect. 1.2 and then highlight the hurdles. Let \r\n be an RSA modulus where p and
q are strong primes and let x be a random element from \r\n. The interactive protocol
in [42] allows a prover to convince the verifier of the statement\r\n\r\n“(N, x,
y, T) satisfies \r\n”.\r\n\r\nThe protocol is recursive and in a round-by-round
fashion reduces the claim to a smaller statement by halving the time parameter.
To be precise, in each round the (honest) prover sends the “midpoint” \r\n of the
current statement to the verifier and they together reduce the statement to\r\n\r\n“\r\n
satisfies \r\n”,\r\n\r\nwhere \r\n and \r\n for a random challenge r. This is continued
until \r\n is obtained at which point the verifier simply checks whether \r\n.\r\n\r\nThe
main problem, we face while designing our protocol is ensuring that the verifier
can check whether \r\n sent by prover lies in an appropriate subgroup of \r\n. In
the first draft of Pietrzak’s protocol [41], prover sends a square root of \r\n,
from which the original \r\n can be recovered easily (by simply squaring it) with
a guarantee, that the result lies in a group of quadratic residues \r\n. Notice
that the prover knows the square root of \r\n, because it is just a previous term
in the sequence he computed.\r\n\r\nUsing Pietrzak’s protocol directly for our delay
function would require computing a-th roots in RSA group for some arbitrary a. Since
this is a computationally hard problem, we cannot use the same trick. In fact, the
VDF construction of Wesolowski [54] is based on similar hardness assumption.\r\n\r\nWhile
Pietrzak shifted from \r\n to the group of signed quadratic residues \r\n in his
following paper [42] to get unique proofs, we resort to his old idea of ‘squaring
a square root’ and generalise it.\r\n\r\nThe high level idea is simple. First, on
input \r\n, prover computes the sequence \r\n. Next, during the protocol, verifier
maps all elements sent by the prover by homomorphism\r\n\r\n(11)\r\ninto the target
strong group \r\n. This process is illustrated in Fig. 2. Notice that the equality
\r\n for the original sequence implies the equality \r\n for the mapped sequence
\r\n.\r\n\r\nFig. 2.\r\nfigure 2\r\nIllustration of our computation of the iterated
squaring using the a-th root of \r\n. Horizontal arrows are \r\n and diagonal arrows
are \r\n.\r\n\r\nFull size image\r\nRestriction to Elements of \r\n. Mapping Eq.
(11) introduces a new technical difficulty. Since \r\n is not injective, we narrow
the domain inputs, for which the output of our VDF is verifiable, from \r\n to \r\n.
Furthermore, the only way to verify that a certain x is an element of \r\n is to
get an a-th root of x and raise it to the ath power. So we have to represent elements
of \r\n by elements of \r\n anyway. To resolve these two issues, we introduce a
non-unique representation of elements of \r\n.\r\n\r\nDefinition 13\r\nFor \r\n
and \r\n, we denote \r\n (an element of \r\n) by [x]. Since this representation
of \r\n is not unique, we define an equality relation by\r\n\r\nWe will denote by
tilde () the elements that were already powered to the a by a verifier (i.e. ).
Thus tilded variables verifiably belong to the target group \r\n.\r\n\r\nIn the
following text, the goal of the brackets notation in Definition 13 is to distinguish
places where the equality means the equality of elements of \r\n from those places,
where the equality holds up to \r\n. A reader can also see the notation in Definition
13 as a concrete representation of elements of a factor group \r\n.\r\n\r\nOur security
reduction 2 required the delay function to operate everywhere on \r\n. This is not
a problem if the \r\n algorithm is modified to output the set \r\n.\r\n\r\nFig.
3.\r\nfigure 3\r\nOur Interactive Protocol for \r\n.\r\n\r\nFull size image\r\n4.4
Security\r\nRecall here that \r\n is \r\n-strong group, so there exist\r\n\r\n and
\r\n such that\r\n\r\n(12)\r\nDefinition 14\r\nFor \r\n and \r\n, we define \r\n
as i-th coordinate of \r\n, where \r\n is the isomorphism given by Eq. (12).\r\n\r\nLemma
3\r\nLet \r\n and \r\n. If \r\n, then\r\n\r\n\t(13)\r\nProof\r\nFix \r\n, \r\n and
y. Let some \r\n satisfy\r\n\r\n(14)\r\nUsing notation from Definition 14, we rewrite
Eq. (14) as a set of equations\r\n\r\nFor every \r\n, by reordering the terms, the
j-th equation becomes\r\n\r\n(15)\r\nIf \r\n, then \r\n. Further for every \r\n.
It follows that \r\n. Putting these two equations together gives us \r\n, which
contradicts our assumption \r\n.\r\n\r\nIt follows that there exists \r\n such that\r\n\r\n(16)\r\nThereafter
there exists \r\n such that \r\n divides \r\n and\r\n\r\n(17)\r\nFurthermore, from
Eq. (15), \r\n divides \r\n. Finally, dividing eq. Eq. (15) by \r\n, we get that
r is determined uniquely (\r\n),\r\n\r\nUsing the fact that \r\n, this uniqueness
of r upper bounds number of \r\n, such that Eq. (14) holds, to one. It follows that
the probability that Eq. (14) holds for r chosen randomly from the uniform distribution
over \r\n is less than \r\n. \r\n\r\nCorollary 2\r\nThe halving protocol will
turn an invalid input tuple (i.e. \r\n) into a valid output tuple (i.e. \r\n) with
probability less than \r\n.\r\n\r\nTheorem 3\r\nFor any computationally unbounded
prover who submits anything other than \r\n such that \r\n in phase 2 of the protocol,
the soundness error is upper-bounded by \r\n\r\nProof\r\nIn each round of the protocol,
T decreases to \r\n. It follows that the number of rounds of the halving protocol
before reaching \r\n is upper bounded by \r\n.\r\n\r\nIf the verifier accepts the
solution tuple \r\n in the last round, then the equality \r\n must hold. It follows
that the initial inequality must have turned into equality in some round of the
halving protocol. By Lemma 3, the probability of this event is bounded by \r\n.
Finally, using the union bound for all rounds, we obtain the upper bound (\r\n.
\ \r\n\r\n4.5 Our VDF\r\nAnalogously to the VDF of Pietrzak [42], we compile our
public-coin interactive proof given in Fig. 3 into a VDF using the Fiat-Shamir heuristic.
The complete construction is given in Fig. 4. For ease of exposition, we assume
that the time parameter T is always a power of two.\r\n\r\nFig. 4.\r\nfigure 4\r\n
based on Lucas sequences\r\n\r\nFull size image\r\nAs discussed in Sect. 4.3, it
is crucial for the security of the protocol that the prover computes a sequence
of powers of the a-th root of the challenge and the resulting value (as well as
the intermediate values) received from the prover is lifted to the appropriate group
by raising it to the a-th power. We use the tilde notation in Fig. 4 in order to
denote elements on the sequence relative to the a-th root.\r\n\r\nNote that, by
the construction, the output of our VDF is the \r\n-th power of the root of the
characteristic polynomial for Lucas sequence with parameters P and Q. Therefore,
the value of the delay function implicitly corresponds to the \r\n-th term of the
Lucas sequence.\r\n\r\nTheorem 4\r\nLet \r\n be the statistical security parameter.
The \r\n VDF defined in Fig. 4 is correct and statistically-sound with a negligible
soundness error if \r\n is modelled as a random oracle, against any adversary that
makes \r\n oracle queries.\r\n\r\nProof\r\nThe correctness follows directly by construction.\r\n\r\nTo
prove its statistical soundness, we proceed in a similar way to [42]. We cannot
apply Fiat-Shamir transformation directly, because our protocol does not have constant
number of rounds, thus we use Fiat-Shamir heuristic to each round separately.\r\n\r\nFirst,
we use a random oracle as the \r\n function. Second, if a malicious prover computed
a proof accepted by verifier for some tuple \r\n such that\r\n\r\n(19)\r\nthen he
must have succeeded in turning inequality from Eq. (19) into equality in some round.
By Lemma 3, probability of such a flipping is bounded by \r\n. Every such an attempt
requires one query to random oracle. Using a union bound, it follows that the probability
that a malicious prover who made q queries to random oracle succeeds in flipping
initial inequality into equality in some round is upper-bounded by \r\n.\r\n\r\nSince
q is \r\n, \r\n is a negligible function and thus the soundness error is negligible.
\ \r\n\r\nNotes\r\n1.\r\nNote that integer sequences like Fibonacci numbers and
Mersenne numbers are special cases of Lucas sequences.\r\n\r\n2.\r\nThe choice of
modulus N is said to be safe if \r\n for safe primes \r\n and \r\n, where \r\n and
\r\n are also prime.\r\n\r\n3.\r\nFurther, using the ideas from [14, 20], it is
possible to construct so-called continuous VDFs from Lucas sequences.\r\n\r\n4.\r\nSince
we set a to be at most polynomial in \r\n, its is possible to go over all possible
candidate values for a in time polynomial in \r\n. Thus, any algorithm that could
factor N using the knowledge of a can be efficiently simulated even without the
knowledge of a.\r\n\r\nReferences\r\nAbusalah, H., Kamath, C., Klein, K., Pietrzak,
K., Walter, M.: Reversible proofs of sequential work. In: Ishai, Y., Rijmen, V.
(eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 277–291. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_10\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nAggarwal, D., Maurer, U.: Breaking RSA generically
is equivalent to factoring. IEEE Trans. Inf. Theory 62(11), 6251–6259 (2016). https://doi.org/10.1109/TIT.2016.2594197\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nArun, A., Bonneau,
J., Clark, J.: Short-lived zero-knowledge proofs and signatures. In: Agrawal, S.,
Lin, D. (eds.) Advances in Cryptology – ASIACRYPT 2022. Lecture Notes in Computer
Science, vol. 13793, pp. 487–516. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_17\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBernstein, D., Sorenson, J.: Modular exponentiation
via the explicit Chinese remainder theorem. Math. Comput. 76, 443–454 (2007). https://doi.org/10.1090/S0025-5718-06-01849-7\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nBitansky, N., et
al.: PPAD is as hard as LWE and iterated squaring. IACR Cryptol. ePrint Arch., p.
1072 (2022)\r\n\r\nGoogle Scholar\r\n \r\n\r\nBitansky, N., Goldwasser, S., Jain,
A., Paneth, O., Vaikuntanathan, V., Waters, B.: Time-lock puzzles from randomized
encodings. In: ITCS, pp. 345–356. ACM (2016)\r\n\r\nGoogle Scholar\r\n \r\n\r\nBleichenbacher,
D., Bosma, W., Lenstra, A.K.: Some remarks on Lucas-based cryptosystems. In: Coppersmith,
D. (ed.) CRYPTO 1995. LNCS, vol. 963, pp. 386–396. Springer, Heidelberg (1995).
https://doi.org/10.1007/3-540-44750-4_31\r\n\r\nCrossRef\r\n \r\nGoogle Scholar\r\n
\r\n\r\nBlock, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Time- and
space-efficient arguments from groups of unknown order. In: Malkin, T., Peikert,
C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 123–152. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_5\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBoneh, D., Bonneau, J., Bünz, B., Fisch, B.: Verifiable
delay functions. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991,
pp. 757–788. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_25\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBoneh, D., Bünz, B., Fisch, B.: A survey of two verifiable
delay functions. IACR Cryptol. ePrint Arch. 2018, 712 (2018)\r\n\r\nMATH\r\n \r\nGoogle
Scholar\r\n \r\n\r\nBoneh, D., Venkatesan, R.: Breaking RSA may not be equivalent
to factoring. In: Nyberg, K. (ed.) Advances in Cryptology - EUROCRYPT ’98. Lecture
Notes in Computer Science, vol. 1403, pp. 59–71. Springer, Cham (1998). https://doi.org/10.1007/BFb0054117\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nBuchmann, J., Williams, H.C.: A key-exchange system
based on imaginary quadratic fields. J. Cryptol. 1(2), 107–118 (1988). https://doi.org/10.1007/BF02351719\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nChavez-Saab, J.,
Rodríguez-Henríquez, F., Tibouchi, M.: Verifiable Isogeny walks: towards an isogeny-based
postquantum VDF. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203,
pp. 441–460. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-99277-4_21\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nChoudhuri, A.R., Hubáček, P., Kamath, C., Pietrzak,
K., Rosen, A., Rothblum, G.N.: PPAD-hardness via iterated squaring modulo a composite.
IACR Cryptol. ePrint Arch. 2019, 667 (2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nCini,
V., Lai, R.W.F., Malavolta, G.: Lattice-based succinct arguments from vanishing
polynomials. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology -
CRYPTO 2023. Lecture Notes in Computer Science, pp. 72–105. Springer Nature Switzerland,
Cham (2023). https://doi.org/10.1007/978-3-031-38545-2_3\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nCohen, B., Pietrzak, K.: Simple proofs of sequential work. In:
Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 451–467.
Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_15\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nCohen, B., Pietrzak, K.: The Chia network blockchain.
Technical report, Chia Network (2019). https://www.chia.net/assets/ChiaGreenPaper.pdf.
Accessed 29 July 2022\r\n\r\nDöttling, N., Garg, S., Malavolta, G., Vasudevan, P.N.:
Tight verifiable delay functions. In: Galdi, C., Kolesnikov, V. (eds.) SCN 2020.
LNCS, vol. 12238, pp. 65–84. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-57990-6_4\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nDöttling, N., Lai, R.W.F., Malavolta, G.: Incremental
proofs of sequential work. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS,
vol. 11477, pp. 292–323. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_11\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nEphraim, N., Freitag, C., Komargodski, I., Pass,
R.: Continuous verifiable delay functions. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT
2020. LNCS, vol. 12107, pp. 125–154. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_5\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nDe Feo, L., Masson, S., Petit, C., Sanso, A.: Verifiable
delay functions from supersingular isogenies and pairings. In: Galbraith, S.D.,
Moriai, S. (eds.) ASIACRYPT 2019. LNCS, vol. 11921, pp. 248–277. Springer, Cham
(2019). https://doi.org/10.1007/978-3-030-34578-5_10\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nFiat, A., Shamir, A.: How to prove yourself: practical solutions
to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS,
vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nFreitag, C., Pass, R., Sirkin, N.: Parallelizable
delegation from LWE. IACR Cryptol. ePrint Arch., p. 1025 (2022)\r\n\r\nGoogle Scholar\r\n
\r\n\r\nGoldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive
proof systems. SIAM J. Comput. 18(1), 186–208 (1989)\r\n\r\nCrossRef\r\n \r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nHoffmann, C., Hubáček, P., Kamath, C.,
Klein, K., Pietrzak, K.: Practical statistically sound proofs of exponentiation
in any group. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology – CRYPTO
2022. Lecture Notes in Computer Science, vol. 13508, pp. 1–30. Springer, Cham (2022).
https://doi.org/10.1007/978-3-031-15979-4_13\r\n\r\nCrossRef\r\n \r\nMATH\r\n \r\nGoogle
Scholar\r\n \r\n\r\nHofheinz, D., Kiltz, E.: The group of signed quadratic residues
and applications. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 637–653.
Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03356-8_37\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nKatz, J., Loss, J., Xu, J.: On the security of time-lock
puzzles and timed commitments. In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part
III. LNCS, vol. 12552, pp. 390–413. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64381-2_14\r\n\r\nCrossRef\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nLai, R.W.F., Malavolta, G.: Lattice-based
timed cryptography. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology
- CRYPTO 2023. Lecture Notes in Computer Science, pp. 782–804. Springer Nature Switzerland,
Cham (2023). https://doi.org/10.1007/978-3-031-38554-4_25\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nLehmer, D.H.: An extended theory of Lucas’ functions. Ann. Math.
31(3), 419–448 (1930). https://www.jstor.org/stable/1968235\r\n\r\nLennon, M.J.J.,
Smith, P.J.: LUC: A new public key system. In: Douglas, E.G. (ed.) Ninth IFIP Symposium
on Computer Security, pp. 103–117. Elsevier Science Publishers (1993)\r\n\r\nGoogle
Scholar\r\n \r\n\r\nLenstra, A.K., Wesolowski, B.: Trustworthy public randomness
with sloth, unicorn, and trx. IJACT 3(4), 330–343 (2017)\r\n\r\nCrossRef\r\n \r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nLipmaa, H.: On Diophantine complexity
and statistical zero-knowledge arguments. In: Laih, C.-S. (ed.) ASIACRYPT 2003.
LNCS, vol. 2894, pp. 398–415. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-40061-5_26\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nLombardi, A., Vaikuntanathan, V.: Fiat-Shamir for
repeated squaring with applications to PPAD-hardness and VDFs. In: Micciancio, D.,
Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 632–651. Springer, Cham
(2020). https://doi.org/10.1007/978-3-030-56877-1_22\r\n\r\nCrossRef\r\n \r\nGoogle
Scholar\r\n \r\n\r\nLucas, E.: Théorie des fonctions numériques simplement périodiques.
Am. J. Math. 1(4), 289–321 (1878). https://www.jstor.org/stable/2369373\r\n\r\nLund,
C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof
systems. J. ACM 39(4), 859–868 (1992)\r\n\r\nCrossRef\r\n \r\nMathSciNet\r\n \r\nMATH\r\n
\r\nGoogle Scholar\r\n \r\n\r\nMahmoody, M., Moran, T., Vadhan, S.P.: Publicly verifiable
proofs of sequential work. In: ITCS, pp. 373–388. ACM (2013)\r\n\r\nGoogle Scholar\r\n
\r\n\r\nMahmoody, M., Smith, C., Wu, D.J.: A note on the (Im)possibility of verifiable
delay functions in the random oracle model. IACR Cryptol. ePrint Arch. 2019, 663
(2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nMalavolta, G., Thyagarajan, S.A.K.: Homomorphic
time-lock puzzles and applications. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO
2019. LNCS, vol. 11692, pp. 620–649. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_22\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nMüller, W.B., Nöbauer, W.: Some remarks on public-key
cryptosystems. Studia Sci. Math. Hungar. 16, 71–76 (1981)\r\n\r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nBressoud, D.M.: Factorization and primality
testing. Math. Comput. 56(193), 400 (1991)\r\n\r\nCrossRef\r\n \r\nGoogle Scholar\r\n
\r\n\r\nPietrzak, K.: Simple verifiable delay functions. IACR Cryptol. ePrint Arch.
2018, 627 (2018). https://eprint.iacr.org/2018/627/20180720:081000\r\n\r\nPietrzak,
K.: Simple verifiable delay functions. In: ITCS. LIPIcs, vol. 124, pp. 1–15. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik (2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nRabin,
M.O.: Transaction protection by beacons. J. Comput. Syst. Sci. 27(2), 256–267 (1983)\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nRibenboim, P.: My
Numbers, My Friends: Popular Lectures on Number Theory. Springer-Verlag, New York
(2000)\r\n\r\nCrossRef\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nRiesel, H.:
Prime Numbers and Computer Methods for Factorization, Progress in Mathematics, vol.
57. Birkhäuser, Basel (1985)\r\n\r\nCrossRef\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n
\r\n\r\nRivest, R., Silverman, R.: Are ’strong’ primes needed for RSA. Cryptology
ePrint Archive, Report 2001/007 (2001). https://eprint.iacr.org/2001/007\r\n\r\nRivest,
R.L., Shamir, A., Adleman, L.M.: A method for obtaining digital signatures and public-key
cryptosystems (reprint). Commun. ACM 26(1), 96–99 (1983)\r\n\r\nCrossRef\r\n \r\nMATH\r\n
\r\nGoogle Scholar\r\n \r\n\r\nRivest, R.L., Shamir, A., Wagner, D.A.: Time-lock
puzzles and timed-release crypto. Technical report, Massachusetts Institute of Technology
(1996)\r\n\r\nGoogle Scholar\r\n \r\n\r\nRotem, L., Segev, G.: Generically speeding-up
repeated squaring is equivalent to factoring: sharp thresholds for all generic-ring
delay functions. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol.
12172, pp. 481–509. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_17\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nRotem, L., Segev, G., Shahaf, I.: Generic-group delay
functions require hidden-order groups. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT
2020. LNCS, vol. 12107, pp. 155–180. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_6\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nSchindler, P., Judmayer, A., Hittmeir, M., Stifter,
N., Weippl, E.R.: RandRunner: distributed randomness from trapdoor VDFs with strong
uniqueness. In: 28th Annual Network and Distributed System Security Symposium, NDSS
2021, virtually, 21–25 February 2021. The Internet Society (2021)\r\n\r\nGoogle
Scholar\r\n \r\n\r\nShani, B.: A note on isogeny-based hybrid verifiable delay functions.
IACR Cryptol. ePrint Arch. 2019, 205 (2019)\r\n\r\nGoogle Scholar\r\n \r\n\r\nValiant,
P.: Incrementally verifiable computation or proofs of knowledge imply time/space
efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer,
Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_1\r\n\r\nCrossRef\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nWesolowski, B.: Efficient verifiable
delay functions. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11478,
pp. 379–407. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17659-4_13\r\n\r\nCrossRef\r\n
\r\nGoogle Scholar\r\n \r\n\r\nWesolowski, B.: Efficient verifiable delay functions.
J. Cryptol. 33(4), 2113–2147 (2020). https://doi.org/10.1007/s00145-020-09364-x\r\n\r\nCrossRef\r\n
\r\nMathSciNet\r\n \r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nWilliams, H.C.: A
\r\n method of factoring. Math. Comput. 39(159), 225–234 (1982)\r\n\r\nMathSciNet\r\n
\r\nMATH\r\n \r\nGoogle Scholar\r\n \r\n\r\nWilliams, H.C.: Édouard lucas and primality
testing. Math. Gaz. 83, 173 (1999)\r\n\r\nCrossRef\r\n \r\nGoogle Scholar\r\n \r\n\r\nDownload
references\r\n\r\nAcknowledgements\r\nWe thank Krzysztof Pietrzak and Alon Rosen
for several fruitful discussions about this work and the anonymous reviewers of
SCN 2022 and TCC 2023 for valuable suggestions.\r\n\r\nPavel Hubáček is supported
by the Czech Academy of Sciences (RVO 67985840), by the Grant Agency of the Czech
Republic under the grant agreement no. 19-27871X, and by the Charles University
project UNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral
Fellowship, by the European Research Council (ERC) under the European Union’s Horizon
Europe research and innovation programme (grant agreement No. 101042417, acronym
SPP), and by ISF grant 1789/19."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- first_name: Tomáš
full_name: Krňák, Tomáš
last_name: Krňák
citation:
ama: 'Hoffmann C, Hubáček P, Kamath C, Krňák T. (Verifiable) delay functions from
Lucas sequences. In: 21st International Conference on Theory of Cryptography.
Vol 14372. Springer Nature; 2023:336-362. doi:10.1007/978-3-031-48624-1_13'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., & Krňák, T. (2023). (Verifiable)
delay functions from Lucas sequences. In 21st International Conference on Theory
of Cryptography (Vol. 14372, pp. 336–362). Taipei, Taiwan: Springer Nature.
https://doi.org/10.1007/978-3-031-48624-1_13'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Tomáš Krňák. “(Verifiable)
Delay Functions from Lucas Sequences.” In 21st International Conference on
Theory of Cryptography, 14372:336–62. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48624-1_13.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, and T. Krňák, “(Verifiable) delay functions
from Lucas sequences,” in 21st International Conference on Theory of Cryptography,
Taipei, Taiwan, 2023, vol. 14372, pp. 336–362.
ista: 'Hoffmann C, Hubáček P, Kamath C, Krňák T. 2023. (Verifiable) delay functions
from Lucas sequences. 21st International Conference on Theory of Cryptography.
TCC: Theory of Cryptography, LNCS, vol. 14372, 336–362.'
mla: Hoffmann, Charlotte, et al. “(Verifiable) Delay Functions from Lucas Sequences.”
21st International Conference on Theory of Cryptography, vol. 14372, Springer
Nature, 2023, pp. 336–62, doi:10.1007/978-3-031-48624-1_13.
short: C. Hoffmann, P. Hubáček, C. Kamath, T. Krňák, in:, 21st International Conference
on Theory of Cryptography, Springer Nature, 2023, pp. 336–362.
conference:
end_date: 2023-12-02
location: Taipei, Taiwan
name: 'TCC: Theory of Cryptography'
start_date: 2023-11-29
date_created: 2023-12-17T23:00:54Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2023-12-18T09:00:00Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48624-1_13
intvolume: ' 14372'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1404
month: '11'
oa: 1
oa_version: Preprint
page: 336-362
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486234'
issn:
- 0302-9743
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: (Verifiable) delay functions from Lucas sequences
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14372
year: '2023'
...
---
_id: '14736'
abstract:
- lang: eng
text: Payment channel networks (PCNs) are a promising technology to improve the
scalability of cryptocurrencies. PCNs, however, face the challenge that the frequent
usage of certain routes may deplete channels in one direction, and hence prevent
further transactions. In order to reap the full potential of PCNs, recharging
and rebalancing mechanisms are required to provision channels, as well as an admission
control logic to decide which transactions to reject in case capacity is insufficient.
This paper presents a formal model of this optimisation problem. In particular,
we consider an online algorithms perspective, where transactions arrive over time
in an unpredictable manner. Our main contributions are competitive online algorithms
which come with provable guarantees over time. We empirically evaluate our algorithms
on randomly generated transactions to compare the average performance of our algorithms
to our theoretical bounds. We also show how this model and approach differs from
related problems in classic communication networks.
acknowledgement: Supported by the German Federal Ministry of Education and Research
(BMBF), grant 16KISK020K (6G-RIC), 2021–2025, and ERC CoG 863818 (ForM-SMArt).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Mahsa
full_name: Bastankhah, Mahsa
last_name: Bastankhah
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Mohammad Ali
full_name: Maddah-Ali, Mohammad Ali
last_name: Maddah-Ali
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. R2:
Boosting liquidity in payment channel networks with online admission control.
In: 27th International Conference on Financial Cryptography and Data Security.
Vol 13950. Springer Nature; 2023:309-325. doi:10.1007/978-3-031-47754-6_18'
apa: 'Bastankhah, M., Chatterjee, K., Maddah-Ali, M. A., Schmid, S., Svoboda, J.,
& Yeo, M. X. (2023). R2: Boosting liquidity in payment channel networks with online
admission control. In 27th International Conference on Financial Cryptography
and Data Security (Vol. 13950, pp. 309–325). Bol, Brac, Croatia: Springer
Nature. https://doi.org/10.1007/978-3-031-47754-6_18'
chicago: 'Bastankhah, Mahsa, Krishnendu Chatterjee, Mohammad Ali Maddah-Ali, Stefan
Schmid, Jakub Svoboda, and Michelle X Yeo. “R2: Boosting Liquidity in Payment
Channel Networks with Online Admission Control.” In 27th International Conference
on Financial Cryptography and Data Security, 13950:309–25. Springer Nature,
2023. https://doi.org/10.1007/978-3-031-47754-6_18.'
ieee: 'M. Bastankhah, K. Chatterjee, M. A. Maddah-Ali, S. Schmid, J. Svoboda, and
M. X. Yeo, “R2: Boosting liquidity in payment channel networks with online admission
control,” in 27th International Conference on Financial Cryptography and Data
Security, Bol, Brac, Croatia, 2023, vol. 13950, pp. 309–325.'
ista: 'Bastankhah M, Chatterjee K, Maddah-Ali MA, Schmid S, Svoboda J, Yeo MX. 2023.
R2: Boosting liquidity in payment channel networks with online admission control.
27th International Conference on Financial Cryptography and Data Security. FC:
Financial Cryptography and Data Security, LNCS, vol. 13950, 309–325.'
mla: 'Bastankhah, Mahsa, et al. “R2: Boosting Liquidity in Payment Channel Networks
with Online Admission Control.” 27th International Conference on Financial
Cryptography and Data Security, vol. 13950, Springer Nature, 2023, pp. 309–25,
doi:10.1007/978-3-031-47754-6_18.'
short: M. Bastankhah, K. Chatterjee, M.A. Maddah-Ali, S. Schmid, J. Svoboda, M.X.
Yeo, in:, 27th International Conference on Financial Cryptography and Data Security,
Springer Nature, 2023, pp. 309–325.
conference:
end_date: 2023-05-05
location: Bol, Brac, Croatia
name: 'FC: Financial Cryptography and Data Security'
start_date: 2023-05-01
date_created: 2024-01-08T09:30:22Z
date_published: 2023-12-01T00:00:00Z
date_updated: 2025-07-14T09:10:01Z
day: '01'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1007/978-3-031-47754-6_18
ec_funded: 1
intvolume: ' 13950'
language:
- iso: eng
month: '12'
oa_version: None
page: 309-325
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
publication: 27th International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031477546'
eissn:
- 1611-3349
isbn:
- '9783031477539'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'R2: Boosting liquidity in payment channel networks with online admission control'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13950
year: '2023'
...
---
_id: '14744'
abstract:
- lang: eng
text: "Sharding distributed ledgers is a promising on-chain solution for scaling
blockchains but lacks formal grounds, nurturing skepticism on whether such complex
systems can scale blockchains securely. We fill this gap by introducing the first
formal framework as well as a roadmap to robust sharding. In particular, we first
define the properties sharded distributed ledgers should fulfill. We build upon
and extend the Bitcoin backbone protocol by defining consistency and scalability.
Consistency encompasses the need for atomic execution of cross-shard transactions
to preserve safety, whereas scalability encapsulates the speedup a sharded system
can gain in comparison to a non-sharded system.\r\nUsing our model, we explore
the limitations of sharding. We show that a sharded ledger with n participants
cannot scale under a fully adaptive adversary, but it can scale up to m shards
where n=c'm log m, under an epoch-adaptive adversary; the constant c' encompasses
the trade-off between security and scalability. This is possible only if the sharded
ledgers create succinct proofs of the valid state updates at every epoch. We leverage
our results to identify the sufficient components for robust sharding, which we
incorporate in a protocol abstraction termed Divide & Scale. To demonstrate the
power of our framework, we analyze the most prominent sharded blockchains (Elastico,
Monoxide, OmniLedger, RapidChain) and pinpoint where they fail to meet the desired
properties."
acknowledgement: The work was partially supported by the Austrian Science Fund (FWF)
through the project CoRaF (grant agreement 2020388).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Zeta
full_name: Avarikioti, Zeta
last_name: Avarikioti
- first_name: Antoine
full_name: Desjardins, Antoine
id: 06d0c166-aec1-11ee-a7c0-b96e840a602b
last_name: Desjardins
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Roger
full_name: Wattenhofer, Roger
last_name: Wattenhofer
citation:
ama: 'Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. Divide &
Scale: Formalization and roadmap to robust sharding. In: 30th International
Colloquium on Structural Information and Communication Complexity. Vol 13892.
Springer Nature; 2023:199-245. doi:10.1007/978-3-031-32733-9_10'
apa: 'Avarikioti, Z., Desjardins, A., Kokoris Kogias, E., & Wattenhofer, R.
(2023). Divide & Scale: Formalization and roadmap to robust sharding. In 30th
International Colloquium on Structural Information and Communication Complexity
(Vol. 13892, pp. 199–245). Alcalá de Henares, Spain: Springer Nature. https://doi.org/10.1007/978-3-031-32733-9_10'
chicago: 'Avarikioti, Zeta, Antoine Desjardins, Eleftherios Kokoris Kogias, and
Roger Wattenhofer. “Divide & Scale: Formalization and Roadmap to Robust Sharding.”
In 30th International Colloquium on Structural Information and Communication
Complexity, 13892:199–245. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-32733-9_10.'
ieee: 'Z. Avarikioti, A. Desjardins, E. Kokoris Kogias, and R. Wattenhofer, “Divide
& Scale: Formalization and roadmap to robust sharding,” in 30th International
Colloquium on Structural Information and Communication Complexity, Alcalá
de Henares, Spain, 2023, vol. 13892, pp. 199–245.'
ista: 'Avarikioti Z, Desjardins A, Kokoris Kogias E, Wattenhofer R. 2023. Divide
& Scale: Formalization and roadmap to robust sharding. 30th International
Colloquium on Structural Information and Communication Complexity. SIROCCO: Structural
Information and Communication Complexity, LNCS, vol. 13892, 199–245.'
mla: 'Avarikioti, Zeta, et al. “Divide & Scale: Formalization and Roadmap to Robust
Sharding.” 30th International Colloquium on Structural Information and Communication
Complexity, vol. 13892, Springer Nature, 2023, pp. 199–245, doi:10.1007/978-3-031-32733-9_10.'
short: Z. Avarikioti, A. Desjardins, E. Kokoris Kogias, R. Wattenhofer, in:, 30th
International Colloquium on Structural Information and Communication Complexity,
Springer Nature, 2023, pp. 199–245.
conference:
end_date: 2023-06-09
location: Alcalá de Henares, Spain
name: 'SIROCCO: Structural Information and Communication Complexity'
start_date: 2023-06-06
date_created: 2024-01-08T12:56:46Z
date_published: 2023-06-01T00:00:00Z
date_updated: 2024-01-09T07:40:57Z
day: '01'
department:
- _id: ElKo
doi: 10.1007/978-3-031-32733-9_10
intvolume: ' 13892'
language:
- iso: eng
month: '06'
oa_version: None
page: 199-245
publication: 30th International Colloquium on Structural Information and Communication
Complexity
publication_identifier:
eisbn:
- '9783031327339'
eissn:
- 1611-3349
isbn:
- '9783031327322'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Divide & Scale: Formalization and roadmap to robust sharding'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13892
year: '2023'
...
---
_id: '14758'
abstract:
- lang: eng
text: 'We present a flexible and efficient toolchain to symbolically solve (standard)
Rabin games, fair-adversarial Rabin games, and 2 1/2 license type-player Rabin
games. To our best knowledge, our tools are the first ones to be able to solve
these problems. Furthermore, using these flexible game solvers as a back-end,
we implemented a tool for computing correct-by-construction controllers for stochastic
dynamical systems under LTL specifications. Our implementations use the recent
theoretical result that all of these games can be solved using the same symbolic
fixpoint algorithm but utilizing different, domain specific calculations of the
involved predecessor operators. The main feature of our toolchain is the utilization
of two programming abstractions: one to separate the symbolic fixpoint computations
from the predecessor calculations, and another one to allow the integration of
different BDD libraries as back-ends. In particular, we employ a multi-threaded
execution of the fixpoint algorithm by using the multi-threaded BDD library Sylvan,
which leads to enormous computational savings.'
acknowledgement: 'Authors ordered alphabetically. R. Majumdar and A.-K. Schmuck are
partially supported by DFG project 389792660 TRR 248-CPEC. A.-K. Schmuck is additionally
funded through DFG project (SCHM 3541/1-1). K. Mallik is supported by the ERC project
ERC-2020-AdG 101020093. M. Rychlicki is supported by the EPSRC project EP/V00252X/1.
S. Soudjani is supported by the following projects: EPSRC EP/V043676/1, EIC 101070802,
and ERC 101089047.'
alternative_title:
- LNCS
article_processing_charge: Yes (in subscription journal)
author:
- first_name: Rupak
full_name: Majumdar, Rupak
last_name: Majumdar
- first_name: Kaushik
full_name: Mallik, Kaushik
id: 0834ff3c-6d72-11ec-94e0-b5b0a4fb8598
last_name: Mallik
orcid: 0000-0001-9864-7475
- first_name: Mateusz
full_name: Rychlicki, Mateusz
last_name: Rychlicki
- first_name: Anne-Kathrin
full_name: Schmuck, Anne-Kathrin
last_name: Schmuck
- first_name: Sadegh
full_name: Soudjani, Sadegh
last_name: Soudjani
citation:
ama: 'Majumdar R, Mallik K, Rychlicki M, Schmuck A-K, Soudjani S. A flexible toolchain
for symbolic rabin games under fair and stochastic uncertainties. In: 35th
International Conference on Computer Aided Verification. Vol 13966. Springer
Nature; 2023:3-15. doi:10.1007/978-3-031-37709-9_1'
apa: 'Majumdar, R., Mallik, K., Rychlicki, M., Schmuck, A.-K., & Soudjani, S.
(2023). A flexible toolchain for symbolic rabin games under fair and stochastic
uncertainties. In 35th International Conference on Computer Aided Verification
(Vol. 13966, pp. 3–15). Paris, France: Springer Nature. https://doi.org/10.1007/978-3-031-37709-9_1'
chicago: Majumdar, Rupak, Kaushik Mallik, Mateusz Rychlicki, Anne-Kathrin Schmuck,
and Sadegh Soudjani. “A Flexible Toolchain for Symbolic Rabin Games under Fair
and Stochastic Uncertainties.” In 35th International Conference on Computer
Aided Verification, 13966:3–15. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-37709-9_1.
ieee: R. Majumdar, K. Mallik, M. Rychlicki, A.-K. Schmuck, and S. Soudjani, “A flexible
toolchain for symbolic rabin games under fair and stochastic uncertainties,” in
35th International Conference on Computer Aided Verification, Paris, France,
2023, vol. 13966, pp. 3–15.
ista: 'Majumdar R, Mallik K, Rychlicki M, Schmuck A-K, Soudjani S. 2023. A flexible
toolchain for symbolic rabin games under fair and stochastic uncertainties. 35th
International Conference on Computer Aided Verification. CAV: Computer Aided Verification,
LNCS, vol. 13966, 3–15.'
mla: Majumdar, Rupak, et al. “A Flexible Toolchain for Symbolic Rabin Games under
Fair and Stochastic Uncertainties.” 35th International Conference on Computer
Aided Verification, vol. 13966, Springer Nature, 2023, pp. 3–15, doi:10.1007/978-3-031-37709-9_1.
short: R. Majumdar, K. Mallik, M. Rychlicki, A.-K. Schmuck, S. Soudjani, in:, 35th
International Conference on Computer Aided Verification, Springer Nature, 2023,
pp. 3–15.
conference:
end_date: 2023-07-22
location: Paris, France
name: 'CAV: Computer Aided Verification'
start_date: 2023-07-17
date_created: 2024-01-08T13:18:00Z
date_published: 2023-07-16T00:00:00Z
date_updated: 2024-02-27T07:39:51Z
day: '16'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-031-37709-9_1
ec_funded: 1
file:
- access_level: open_access
checksum: 1a361d83db0244fd32c03b544c294b5a
content_type: application/pdf
creator: dernst
date_created: 2024-01-09T10:01:07Z
date_updated: 2024-01-09T10:01:07Z
file_id: '14765'
file_name: 2023_LNCSCAV_Majumdar.pdf
file_size: 405147
relation: main_file
success: 1
file_date_updated: 2024-01-09T10:01:07Z
has_accepted_license: '1'
intvolume: ' 13966'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 3-15
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 35th International Conference on Computer Aided Verification
publication_identifier:
eisbn:
- '9783031377099'
eissn:
- 1611-3349
isbn:
- '9783031377082'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '14994'
relation: research_data
status: public
scopus_import: '1'
status: public
title: A flexible toolchain for symbolic rabin games under fair and stochastic uncertainties
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: 13966
year: '2023'
...
---
_id: '12167'
abstract:
- lang: eng
text: "Payment channels effectively move the transaction load off-chain thereby
successfully addressing the inherent scalability problem most cryptocurrencies
face. A major drawback of payment channels is the need to “top up” funds on-chain
when a channel is depleted. Rebalancing was proposed to alleviate this issue,
where parties with depleting channels move their funds along a cycle to replenish
their channels off-chain. Protocols for rebalancing so far either introduce local
solutions or compromise privacy.\r\nIn this work, we present an opt-in rebalancing
protocol that is both private and globally optimal, meaning our protocol maximizes
the total amount of rebalanced funds. We study rebalancing from the framework
of linear programming. To obtain full privacy guarantees, we leverage multi-party
computation in solving the linear program, which is executed by selected participants
to maintain efficiency. Finally, we efficiently decompose the rebalancing solution
into incentive-compatible cycles which conserve user balances when executed atomically."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Georgia
full_name: Avarikioti, Georgia
id: c20482a0-3b89-11eb-9862-88cf6404b88c
last_name: Avarikioti
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Iosif
full_name: Salem, Iosif
last_name: Salem
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Samarth
full_name: Tiwari, Samarth
last_name: Tiwari
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
citation:
ama: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. Hide &
Seek: Privacy-preserving rebalancing on payment channel networks. In: Financial
Cryptography and Data Security. Vol 13411. Springer Nature; 2022:358-373.
doi:10.1007/978-3-031-18283-9_17'
apa: 'Avarikioti, G., Pietrzak, K. Z., Salem, I., Schmid, S., Tiwari, S., &
Yeo, M. X. (2022). Hide & Seek: Privacy-preserving rebalancing on payment
channel networks. In Financial Cryptography and Data Security (Vol. 13411,
pp. 358–373). Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_17'
chicago: 'Avarikioti, Georgia, Krzysztof Z Pietrzak, Iosif Salem, Stefan Schmid,
Samarth Tiwari, and Michelle X Yeo. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” In Financial Cryptography and Data Security,
13411:358–73. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_17.'
ieee: 'G. Avarikioti, K. Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. X.
Yeo, “Hide & Seek: Privacy-preserving rebalancing on payment channel networks,”
in Financial Cryptography and Data Security, Grenada, 2022, vol. 13411,
pp. 358–373.'
ista: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. 2022. Hide
& Seek: Privacy-preserving rebalancing on payment channel networks. Financial
Cryptography and Data Security. FC: Financial Cryptography and Data Security,
LNCS, vol. 13411, 358–373.'
mla: 'Avarikioti, Georgia, et al. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” Financial Cryptography and Data Security,
vol. 13411, Springer Nature, 2022, pp. 358–73, doi:10.1007/978-3-031-18283-9_17.'
short: G. Avarikioti, K.Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, M.X. Yeo, in:,
Financial Cryptography and Data Security, Springer Nature, 2022, pp. 358–373.
conference:
end_date: 2022-05-06
location: Grenada
name: 'FC: Financial Cryptography and Data Security'
start_date: 2022-05-02
date_created: 2023-01-12T12:10:38Z
date_published: 2022-10-22T00:00:00Z
date_updated: 2023-09-05T15:10:57Z
day: '22'
department:
- _id: KrPi
doi: 10.1007/978-3-031-18283-9_17
external_id:
arxiv:
- '2110.08848'
intvolume: ' 13411'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2110.08848
month: '10'
oa: 1
oa_version: Preprint
page: 358-373
publication: Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031182839'
eissn:
- 1611-3349
isbn:
- '9783031182822'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Hide & Seek: Privacy-preserving rebalancing on payment channel networks'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13411
year: '2022'
...
---
_id: '12168'
abstract:
- lang: eng
text: "Advances in blockchains have influenced the State-Machine-Replication (SMR)
world and many state-of-the-art blockchain-SMR solutions are based on two pillars:
Chaining and Leader-rotation. A predetermined round-robin mechanism used for Leader-rotation,
however, has an undesirable behavior: crashed parties become designated leaders
infinitely often, slowing down overall system performance. In this paper, we provide
a new Leader-Aware SMR framework that, among other desirable properties, formalizes
a Leader-utilization requirement that bounds the number of rounds whose leaders
are faulty in crash-only executions.\r\nWe introduce Carousel, a novel, reputation-based
Leader-rotation solution to achieve Leader-Aware SMR. The challenge in adaptive
Leader-rotation is that it cannot rely on consensus to determine a leader, since
consensus itself needs a leader. Carousel uses the available on-chain information
to determine a leader locally and achieves Liveness despite this difficulty. A
HotStuff implementation fitted with Carousel demonstrates drastic performance
improvements: it increases throughput over 2x in faultless settings and provided
a 20x throughput increase and 5x latency reduction in the presence of faults."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Shir
full_name: Cohen, Shir
last_name: Cohen
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Zekun
full_name: Li, Zekun
last_name: Li
- first_name: Dahlia
full_name: Malkhi, Dahlia
last_name: Malkhi
- first_name: Alberto
full_name: Sonnino, Alberto
last_name: Sonnino
- first_name: Alexander
full_name: Spiegelman, Alexander
last_name: Spiegelman
citation:
ama: 'Cohen S, Gelashvili R, Kokoris Kogias E, et al. Be aware of your leaders.
In: International Conference on Financial Cryptography and Data Security.
Vol 13411. Springer Nature; 2022:279-295. doi:10.1007/978-3-031-18283-9_13'
apa: 'Cohen, S., Gelashvili, R., Kokoris Kogias, E., Li, Z., Malkhi, D., Sonnino,
A., & Spiegelman, A. (2022). Be aware of your leaders. In International
Conference on Financial Cryptography and Data Security (Vol. 13411, pp. 279–295).
Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_13'
chicago: Cohen, Shir, Rati Gelashvili, Eleftherios Kokoris Kogias, Zekun Li, Dahlia
Malkhi, Alberto Sonnino, and Alexander Spiegelman. “Be Aware of Your Leaders.”
In International Conference on Financial Cryptography and Data Security,
13411:279–95. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_13.
ieee: S. Cohen et al., “Be aware of your leaders,” in International Conference
on Financial Cryptography and Data Security, Grenada, 2022, vol. 13411, pp.
279–295.
ista: 'Cohen S, Gelashvili R, Kokoris Kogias E, Li Z, Malkhi D, Sonnino A, Spiegelman
A. 2022. Be aware of your leaders. International Conference on Financial Cryptography
and Data Security. FC: Financial Cryptography and Data Security, LNCS, vol. 13411,
279–295.'
mla: Cohen, Shir, et al. “Be Aware of Your Leaders.” International Conference
on Financial Cryptography and Data Security, vol. 13411, Springer Nature,
2022, pp. 279–95, doi:10.1007/978-3-031-18283-9_13.
short: S. Cohen, R. Gelashvili, E. Kokoris Kogias, Z. Li, D. Malkhi, A. Sonnino,
A. Spiegelman, in:, International Conference on Financial Cryptography and Data
Security, Springer Nature, 2022, pp. 279–295.
conference:
end_date: 2022-05-06
location: Grenada
name: 'FC: Financial Cryptography and Data Security'
start_date: 2022-05-02
date_created: 2023-01-12T12:10:49Z
date_published: 2022-10-22T00:00:00Z
date_updated: 2023-09-05T15:11:35Z
day: '22'
department:
- _id: ElKo
doi: 10.1007/978-3-031-18283-9_13
external_id:
arxiv:
- '2110.00960'
intvolume: ' 13411'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2110.00960
month: '10'
oa: 1
oa_version: Preprint
page: 279-295
publication: International Conference on Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031182839'
eissn:
- 1611-3349
isbn:
- '9783031182822'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Be aware of your leaders
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13411
year: '2022'
...
---
_id: '12170'
abstract:
- lang: eng
text: We present PET, a specialized and highly optimized framework for partial exploration
on probabilistic systems. Over the last decade, several significant advances in
the analysis of Markov decision processes employed partial exploration. In a nutshell,
this idea allows to focus computation on specific parts of the system, guided
by heuristics, while maintaining correctness. In particular, only relevant parts
of the system are constructed on demand, which in turn potentially allows to omit
constructing large parts of the system. Depending on the model, this leads to
dramatic speed-ups, in extreme cases even up to an arbitrary factor. PET unifies
several previous implementations and provides a flexible framework to easily implement
partial exploration for many further problems. Our experimental evaluation shows
significant improvements compared to the previous implementations while vastly
reducing the overhead required to add support for additional properties.
acknowledgement: We thank Pranav Ashok and Maximilian Weininger for their contributions
to spiritual predecessors of PET as well as motivating the initial development of
this tool.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Tobias
full_name: Meggendorfer, Tobias
id: b21b0c15-30a2-11eb-80dc-f13ca25802e1
last_name: Meggendorfer
orcid: 0000-0002-1712-2165
citation:
ama: 'Meggendorfer T. PET – A partial exploration tool for probabilistic verification.
In: 20th International Symposium on Automated Technology for Verification and
Analysis. Vol 13505. Springer Nature; 2022:320-326. doi:10.1007/978-3-031-19992-9_20'
apa: 'Meggendorfer, T. (2022). PET – A partial exploration tool for probabilistic
verification. In 20th International Symposium on Automated Technology for Verification
and Analysis (Vol. 13505, pp. 320–326). Virtual: Springer Nature. https://doi.org/10.1007/978-3-031-19992-9_20'
chicago: Meggendorfer, Tobias. “PET – A Partial Exploration Tool for Probabilistic
Verification.” In 20th International Symposium on Automated Technology for
Verification and Analysis, 13505:320–26. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-19992-9_20.
ieee: T. Meggendorfer, “PET – A partial exploration tool for probabilistic verification,”
in 20th International Symposium on Automated Technology for Verification and
Analysis, Virtual, 2022, vol. 13505, pp. 320–326.
ista: 'Meggendorfer T. 2022. PET – A partial exploration tool for probabilistic
verification. 20th International Symposium on Automated Technology for Verification
and Analysis. ATVA: Automated Technology for Verification and Analysis, LNCS,
vol. 13505, 320–326.'
mla: Meggendorfer, Tobias. “PET – A Partial Exploration Tool for Probabilistic Verification.”
20th International Symposium on Automated Technology for Verification and Analysis,
vol. 13505, Springer Nature, 2022, pp. 320–26, doi:10.1007/978-3-031-19992-9_20.
short: T. Meggendorfer, in:, 20th International Symposium on Automated Technology
for Verification and Analysis, Springer Nature, 2022, pp. 320–326.
conference:
end_date: 2022-10-28
location: Virtual
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2022-10-25
date_created: 2023-01-12T12:11:07Z
date_published: 2022-10-21T00:00:00Z
date_updated: 2023-09-05T15:11:51Z
day: '21'
department:
- _id: KrCh
doi: 10.1007/978-3-031-19992-9_20
intvolume: ' 13505'
language:
- iso: eng
month: '10'
oa_version: None
page: 320-326
publication: 20th International Symposium on Automated Technology for Verification
and Analysis
publication_identifier:
eisbn:
- '9783031199929'
eissn:
- 1611-3349
isbn:
- '9783031199912'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: PET – A partial exploration tool for probabilistic verification
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13505
year: '2022'
...
---
_id: '12171'
abstract:
- lang: eng
text: 'We propose an algorithmic approach for synthesizing linear hybrid automata
from time-series data. Unlike existing approaches, our approach provides a whole
family of models with the same discrete structure but different dynamics. Each
model in the family is guaranteed to capture the input data up to a precision
error ε, in the following sense: For each time series, the model contains an execution
that is ε-close to the data points. Our construction allows to effectively choose
a model from this family with minimal precision error ε. We demonstrate the algorithm’s
efficiency and its ability to find precise models in two case studies.'
acknowledgement: This work was supported in part by the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie grant agreement
no. 847635, by the ERC-2020-AdG 101020093, by DIREC - Digital Research Centre Denmark,
and by the Villum Investigator Grant S4OS.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Miriam
full_name: Garcia Soto, Miriam
id: 4B3207F6-F248-11E8-B48F-1D18A9856A87
last_name: Garcia Soto
orcid: 0000-0003-2936-5719
- 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: Christian
full_name: Schilling, Christian
id: 3A2F4DCE-F248-11E8-B48F-1D18A9856A87
last_name: Schilling
orcid: 0000-0003-3658-1065
citation:
ama: 'Garcia Soto M, Henzinger TA, Schilling C. Synthesis of parametric hybrid automata
from time series. In: 20th International Symposium on Automated Technology
for Verification and Analysis. Vol 13505. Springer Nature; 2022:337-353. doi:10.1007/978-3-031-19992-9_22'
apa: 'Garcia Soto, M., Henzinger, T. A., & Schilling, C. (2022). Synthesis of parametric
hybrid automata from time series. In 20th International Symposium on Automated
Technology for Verification and Analysis (Vol. 13505, pp. 337–353). Virtual:
Springer Nature. https://doi.org/10.1007/978-3-031-19992-9_22'
chicago: Garcia Soto, Miriam, Thomas A Henzinger, and Christian Schilling. “Synthesis
of Parametric Hybrid Automata from Time Series.” In 20th International Symposium
on Automated Technology for Verification and Analysis, 13505:337–53. Springer
Nature, 2022. https://doi.org/10.1007/978-3-031-19992-9_22.
ieee: M. Garcia Soto, T. A. Henzinger, and C. Schilling, “Synthesis of parametric
hybrid automata from time series,” in 20th International Symposium on Automated
Technology for Verification and Analysis, Virtual, 2022, vol. 13505, pp. 337–353.
ista: 'Garcia Soto M, Henzinger TA, Schilling C. 2022. Synthesis of parametric hybrid
automata from time series. 20th International Symposium on Automated Technology
for Verification and Analysis. ATVA: Automated Technology for Verification and
Analysis, LNCS, vol. 13505, 337–353.'
mla: Garcia Soto, Miriam, et al. “Synthesis of Parametric Hybrid Automata from Time
Series.” 20th International Symposium on Automated Technology for Verification
and Analysis, vol. 13505, Springer Nature, 2022, pp. 337–53, doi:10.1007/978-3-031-19992-9_22.
short: M. Garcia Soto, T.A. Henzinger, C. Schilling, in:, 20th International Symposium
on Automated Technology for Verification and Analysis, Springer Nature, 2022,
pp. 337–353.
conference:
end_date: 2022-10-28
location: Virtual
name: 'ATVA: Automated Technology for Verification and Analysis'
start_date: 2022-10-25
date_created: 2023-01-12T12:11:16Z
date_published: 2022-10-21T00:00:00Z
date_updated: 2023-02-13T09:27:55Z
day: '21'
department:
- _id: ToHe
doi: 10.1007/978-3-031-19992-9_22
ec_funded: 1
external_id:
arxiv:
- '2208.06383'
intvolume: ' 13505'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2208.06383
month: '10'
oa: 1
oa_version: Preprint
page: 337-353
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 20th International Symposium on Automated Technology for Verification
and Analysis
publication_identifier:
eisbn:
- '9783031199929'
eissn:
- 1611-3349
isbn:
- '9783031199912'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Synthesis of parametric hybrid automata from time series
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13505
year: '2022'
...
---
_id: '12175'
abstract:
- lang: eng
text: An automaton is history-deterministic (HD) if one can safely resolve its non-deterministic
choices on the fly. In a recent paper, Henzinger, Lehtinen and Totzke studied
this in the context of Timed Automata [9], where it was conjectured that the class
of timed ω-languages recognised by HD-timed automata strictly extends that of
deterministic ones. We provide a proof for this fact.
acknowledgement: This work was supported in part by the ERC-2020-AdG 101020093, the
EPSRC project EP/V025848/1, and the EPSRC project EP/X017796/1.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sougata
full_name: Bose, Sougata
last_name: Bose
- 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: Karoliina
full_name: Lehtinen, Karoliina
last_name: Lehtinen
- first_name: Sven
full_name: Schewe, Sven
last_name: Schewe
- first_name: Patrick
full_name: Totzke, Patrick
last_name: Totzke
citation:
ama: 'Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. History-deterministic
timed automata are not determinizable. In: 16th International Conference on
Reachability Problems. Vol 13608. Springer Nature; 2022:67-76. doi:10.1007/978-3-031-19135-0_5'
apa: 'Bose, S., Henzinger, T. A., Lehtinen, K., Schewe, S., & Totzke, P. (2022).
History-deterministic timed automata are not determinizable. In 16th International
Conference on Reachability Problems (Vol. 13608, pp. 67–76). Kaiserslautern,
Germany: Springer Nature. https://doi.org/10.1007/978-3-031-19135-0_5'
chicago: Bose, Sougata, Thomas A Henzinger, Karoliina Lehtinen, Sven Schewe, and
Patrick Totzke. “History-Deterministic Timed Automata Are Not Determinizable.”
In 16th International Conference on Reachability Problems, 13608:67–76.
Springer Nature, 2022. https://doi.org/10.1007/978-3-031-19135-0_5.
ieee: S. Bose, T. A. Henzinger, K. Lehtinen, S. Schewe, and P. Totzke, “History-deterministic
timed automata are not determinizable,” in 16th International Conference on
Reachability Problems, Kaiserslautern, Germany, 2022, vol. 13608, pp. 67–76.
ista: 'Bose S, Henzinger TA, Lehtinen K, Schewe S, Totzke P. 2022. History-deterministic
timed automata are not determinizable. 16th International Conference on Reachability
Problems. RC: Reachability Problems, LNCS, vol. 13608, 67–76.'
mla: Bose, Sougata, et al. “History-Deterministic Timed Automata Are Not Determinizable.”
16th International Conference on Reachability Problems, vol. 13608, Springer
Nature, 2022, pp. 67–76, doi:10.1007/978-3-031-19135-0_5.
short: S. Bose, T.A. Henzinger, K. Lehtinen, S. Schewe, P. Totzke, in:, 16th International
Conference on Reachability Problems, Springer Nature, 2022, pp. 67–76.
conference:
end_date: 2022-10-21
location: Kaiserslautern, Germany
name: 'RC: Reachability Problems'
start_date: 2022-10-17
date_created: 2023-01-12T12:11:57Z
date_published: 2022-10-12T00:00:00Z
date_updated: 2023-09-05T15:12:08Z
day: '12'
department:
- _id: ToHe
doi: 10.1007/978-3-031-19135-0_5
ec_funded: 1
intvolume: ' 13608'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://hal.science/hal-03849398/
month: '10'
oa: 1
oa_version: Preprint
page: 67-76
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: 16th International Conference on Reachability Problems
publication_identifier:
eisbn:
- '9783031191350'
eissn:
- 1611-3349
isbn:
- '9783031191343'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: History-deterministic timed automata are not determinizable
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13608
year: '2022'
...
---
_id: '12176'
abstract:
- lang: eng
text: "A proof of exponentiation (PoE) in a group G of unknown order allows a prover
to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive
has recently found exciting applications in the constructions of verifiable delay
functions and succinct arguments of knowledge. The most practical PoEs only achieve
soundness either under computational assumptions, i.e., they are arguments (Wesolowski,
Journal of Cryptology 2020), or in groups that come with the promise of not having
any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in
general groups of unknown order is due to Block et al. (CRYPTO 2021), and can
be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits
of security, say λ=80, the number of repetitions required (and thus the blow-up
in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound
PoE for the case where the exponent q is the product of all primes up to some
bound B. We show that, in this case, it suffices to run only λ/log(B) parallel
instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to
Block et al. by an order of magnitude. Furthermore, we show that in the known
applications where PoEs are used as a building block such structured exponents
are viable. Finally, we also discuss batching of our PoE, showing that many proofs
(for the same G and q but different x and T) can be batched by adding only a single
element to the proof per additional statement."
acknowledgement: "We would like to thank the authors of [BHR+21] for clarifying several
questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the
Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and
by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by
Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19.
Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part
of this work at Institute of Science and Technology Austria."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- first_name: Karen
full_name: Klein, Karen
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound
proofs of exponentiation in any group. In: Advances in Cryptology – CRYPTO
2022. Vol 13508. Springer Nature; 2022:370-399. doi:10.1007/978-3-031-15979-4_13'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., & Pietrzak, K. Z. (2022).
Practical statistically-sound proofs of exponentiation in any group. In Advances
in Cryptology – CRYPTO 2022 (Vol. 13508, pp. 370–399). Santa Barbara, CA,
United States: Springer Nature. https://doi.org/10.1007/978-3-031-15979-4_13'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof
Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.”
In Advances in Cryptology – CRYPTO 2022, 13508:370–99. Springer Nature,
2022. https://doi.org/10.1007/978-3-031-15979-4_13.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical
statistically-sound proofs of exponentiation in any group,” in Advances in
Cryptology – CRYPTO 2022, Santa Barbara, CA, United States, 2022, vol. 13508,
pp. 370–399.
ista: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound
proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYYPTO:
International Cryptology Conference, LNCS, vol. 13508, 370–399.'
mla: Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation
in Any Group.” Advances in Cryptology – CRYPTO 2022, vol. 13508, Springer
Nature, 2022, pp. 370–99, doi:10.1007/978-3-031-15979-4_13.
short: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances
in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.
conference:
end_date: 2022-08-18
location: Santa Barbara, CA, United States
name: 'CRYYPTO: International Cryptology Conference'
start_date: 2022-08-15
date_created: 2023-01-12T12:12:07Z
date_published: 2022-10-13T00:00:00Z
date_updated: 2023-09-05T15:12:27Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-3-031-15979-4_13
external_id:
isi:
- '000886792700013'
intvolume: ' 13508'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1021
month: '10'
oa: 1
oa_version: Preprint
page: 370-399
publication: Advances in Cryptology – CRYPTO 2022
publication_identifier:
eisbn:
- '9783031159794'
eissn:
- 1611-3349
isbn:
- '9783031159787'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical statistically-sound proofs of exponentiation in any group
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13508
year: '2022'
...
---
_id: '12298'
abstract:
- lang: eng
text: 'Existing committee-based Byzantine state machine replication (SMR) protocols,
typically deployed in production blockchains, face a clear trade-off: (1) they
either achieve linear communication cost in the steady state, but sacrifice liveness
during periods of asynchrony, or (2) they are robust (progress with probability
one) but pay quadratic communication cost. We believe this trade-off is unwarranted
since existing linear protocols still have asymptotic quadratic cost in the worst
case. We design Ditto, a Byzantine SMR protocol that enjoys the best of both worlds:
optimal communication on and off the steady state (linear and quadratic, respectively)
and progress guarantee under asynchrony and DDoS attacks. We achieve this by replacing
the view-synchronization of partially synchronous protocols with an asynchronous
fallback mechanism at no extra asymptotic cost. Specifically, we start from HotStuff,
a state-of-the-art linear protocol, and gradually build Ditto. As a separate contribution
and an intermediate step, we design a 2-chain version of HotStuff, Jolteon, which
leverages a quadratic view-change mechanism to reduce the latency of the standard
3-chain HotStuff. We implement and experimentally evaluate all our systems to
prove that breaking the robustness-efficiency trade-off is in the realm of practicality.'
acknowledgement: We thank our shepherd Aniket Kate and the anonymous reviewers at
FC 2022 for their helpful feedback. This work is supported by the Novi team at Facebook.
We also thank the Novi Research and Engineering teams for valuable feedback, and
in particular Mathieu Baudet, Andrey Chursin, George Danezis, Zekun Li, and Dahlia
Malkhi for discussions that shaped this work.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Rati
full_name: Gelashvili, Rati
last_name: Gelashvili
- first_name: Eleftherios
full_name: Kokoris Kogias, Eleftherios
id: f5983044-d7ef-11ea-ac6d-fd1430a26d30
last_name: Kokoris Kogias
- first_name: Alberto
full_name: Sonnino, Alberto
last_name: Sonnino
- first_name: Alexander
full_name: Spiegelman, Alexander
last_name: Spiegelman
- first_name: Zhuolun
full_name: Xiang, Zhuolun
last_name: Xiang
citation:
ama: 'Gelashvili R, Kokoris Kogias E, Sonnino A, Spiegelman A, Xiang Z. Jolteon
and ditto: Network-adaptive efficient consensus with asynchronous fallback. In:
Financial Cryptography and Data Security. Vol 13411. Springer Nature; 2022:296-315.
doi:10.1007/978-3-031-18283-9_14'
apa: 'Gelashvili, R., Kokoris Kogias, E., Sonnino, A., Spiegelman, A., & Xiang,
Z. (2022). Jolteon and ditto: Network-adaptive efficient consensus with asynchronous
fallback. In Financial Cryptography and Data Security (Vol. 13411, pp.
296–315). Radisson Grenada Beach Resort, Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_14'
chicago: 'Gelashvili, Rati, Eleftherios Kokoris Kogias, Alberto Sonnino, Alexander
Spiegelman, and Zhuolun Xiang. “Jolteon and Ditto: Network-Adaptive Efficient
Consensus with Asynchronous Fallback.” In Financial Cryptography and Data Security,
13411:296–315. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_14.'
ieee: 'R. Gelashvili, E. Kokoris Kogias, A. Sonnino, A. Spiegelman, and Z. Xiang,
“Jolteon and ditto: Network-adaptive efficient consensus with asynchronous fallback,”
in Financial Cryptography and Data Security, Radisson Grenada Beach Resort,
Grenada, 2022, vol. 13411, pp. 296–315.'
ista: 'Gelashvili R, Kokoris Kogias E, Sonnino A, Spiegelman A, Xiang Z. 2022. Jolteon
and ditto: Network-adaptive efficient consensus with asynchronous fallback. Financial
Cryptography and Data Security. FC: Financial Cryptography, LNCS, vol. 13411,
296–315.'
mla: 'Gelashvili, Rati, et al. “Jolteon and Ditto: Network-Adaptive Efficient Consensus
with Asynchronous Fallback.” Financial Cryptography and Data Security,
vol. 13411, Springer Nature, 2022, pp. 296–315, doi:10.1007/978-3-031-18283-9_14.'
short: R. Gelashvili, E. Kokoris Kogias, A. Sonnino, A. Spiegelman, Z. Xiang, in:,
Financial Cryptography and Data Security, Springer Nature, 2022, pp. 296–315.
conference:
end_date: 2022-05-06
location: Radisson Grenada Beach Resort, Grenada
name: 'FC: Financial Cryptography'
start_date: 2022-05-02
date_created: 2023-01-16T10:05:51Z
date_published: 2022-10-22T00:00:00Z
date_updated: 2023-09-05T15:13:17Z
day: '22'
department:
- _id: ElKo
doi: 10.1007/978-3-031-18283-9_14
external_id:
arxiv:
- '2106.10362'
intvolume: ' 13411'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2106.10362'
month: '10'
oa: 1
oa_version: Preprint
page: 296-315
publication: Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031182839'
eissn:
- 1611-3349
isbn:
- '9783031182822'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Jolteon and ditto: Network-adaptive efficient consensus with asynchronous
fallback'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13411
year: '2022'
...
---
_id: '12302'
abstract:
- lang: eng
text: 'We propose a novel algorithm to decide the language inclusion between (nondeterministic)
Büchi automata, a PSPACE-complete problem. Our approach, like others before, leverage
a notion of quasiorder to prune the search for a counterexample by discarding
candidates which are subsumed by others for the quasiorder. Discarded candidates
are guaranteed to not compromise the completeness of the algorithm. The novelty
of our work lies in the quasiorder used to discard candidates. We introduce FORQs
(family of right quasiorders) that we obtain by adapting the notion of family
of right congruences put forward by Maler and Staiger in 1993. We define a FORQ-based
inclusion algorithm which we prove correct and instantiate it for a specific FORQ,
called the structural FORQ, induced by the Büchi automaton to the right of the
inclusion sign. The resulting implementation, called FORKLIFT, scales up better
than the state-of-the-art on a variety of benchmarks including benchmarks from
program verification and theorem proving for word combinatorics. Artifact: https://doi.org/10.5281/zenodo.6552870'
acknowledgement: This work was partially funded by the ESF Investing in your future,
the Madrid regional project S2018/TCS-4339 BLOQUES, the Spanish project PGC2018-102210-B-I00
BOSCO, the Ramón y Cajal fellowship RYC-2016-20281, and the ERC grant PR1001ERC02.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Kyveli
full_name: Doveri, Kyveli
last_name: Doveri
- first_name: Pierre
full_name: Ganty, Pierre
last_name: Ganty
- first_name: Nicolas Adrien
full_name: Mazzocchi, Nicolas Adrien
id: b26baa86-3308-11ec-87b0-8990f34baa85
last_name: Mazzocchi
citation:
ama: 'Doveri K, Ganty P, Mazzocchi NA. FORQ-based language inclusion formal testing.
In: Computer Aided Verification. Vol 13372. Springer Nature; 2022:109-129.
doi:10.1007/978-3-031-13188-2_6'
apa: 'Doveri, K., Ganty, P., & Mazzocchi, N. A. (2022). FORQ-based language
inclusion formal testing. In Computer Aided Verification (Vol. 13372, pp.
109–129). Haifa, Israel: Springer Nature. https://doi.org/10.1007/978-3-031-13188-2_6'
chicago: Doveri, Kyveli, Pierre Ganty, and Nicolas Adrien Mazzocchi. “FORQ-Based
Language Inclusion Formal Testing.” In Computer Aided Verification, 13372:109–29.
Springer Nature, 2022. https://doi.org/10.1007/978-3-031-13188-2_6.
ieee: K. Doveri, P. Ganty, and N. A. Mazzocchi, “FORQ-based language inclusion formal
testing,” in Computer Aided Verification, Haifa, Israel, 2022, vol. 13372,
pp. 109–129.
ista: 'Doveri K, Ganty P, Mazzocchi NA. 2022. FORQ-based language inclusion formal
testing. Computer Aided Verification. CAV: Computer Aided Verification, LNCS,
vol. 13372, 109–129.'
mla: Doveri, Kyveli, et al. “FORQ-Based Language Inclusion Formal Testing.” Computer
Aided Verification, vol. 13372, Springer Nature, 2022, pp. 109–29, doi:10.1007/978-3-031-13188-2_6.
short: K. Doveri, P. Ganty, N.A. Mazzocchi, in:, Computer Aided Verification, Springer
Nature, 2022, pp. 109–129.
conference:
end_date: 2022-08-10
location: Haifa, Israel
name: 'CAV: Computer Aided Verification'
start_date: 2022-08-07
date_created: 2023-01-16T10:06:31Z
date_published: 2022-08-06T00:00:00Z
date_updated: 2023-09-05T15:13:36Z
day: '06'
ddc:
- '000'
department:
- _id: ToHe
doi: 10.1007/978-3-031-13188-2_6
ec_funded: 1
external_id:
arxiv:
- '2207.13549'
isi:
- '000870310500006'
file:
- access_level: open_access
checksum: edc363b1be5447a09063e115c247918a
content_type: application/pdf
creator: dernst
date_created: 2023-01-30T12:51:02Z
date_updated: 2023-01-30T12:51:02Z
file_id: '12465'
file_name: 2022_LNCS_Doveri.pdf
file_size: 497682
relation: main_file
success: 1
file_date_updated: 2023-01-30T12:51:02Z
has_accepted_license: '1'
intvolume: ' 13372'
isi: 1
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
page: 109-129
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
call_identifier: H2020
grant_number: '101020093'
name: Vigilant Algorithmic Monitoring of Software
publication: Computer Aided Verification
publication_identifier:
eisbn:
- '9783031131882'
eissn:
- 1611-3349
isbn:
- '9783031131875'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: FORQ-based language inclusion formal testing
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13372
year: '2022'
...
---
_id: '12516'
abstract:
- lang: eng
text: "The homogeneous continuous LWE (hCLWE) problem is to distinguish samples
of a specific high-dimensional Gaussian mixture from standard normal samples.
It was shown to be at least as hard as Learning with Errors, but no reduction
in the other direction is currently known.\r\nWe present four new public-key encryption
schemes based on the hardness of hCLWE, with varying tradeoffs between decryption
and security errors, and different discretization techniques. Our schemes yield
a polynomial-time algorithm for solving hCLWE using a Statistical Zero-Knowledge
oracle."
acknowledgement: "We are grateful to Devika Sharma and Luca Trevisan for their insight
and advice and to an anonymous reviewer for helpful comments.\r\n\r\nThis work was
supported by the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (Grant agreement No. 101019547). The first
author was additionally supported by RGC GRF CUHK14209920 and the fourth author
was additionally supported by ISF grant No. 1399/17, project PROMETHEUS (Grant 780701),
and Cariplo CRYPTONOMEX grant."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Andrej
full_name: Bogdanov, Andrej
last_name: Bogdanov
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
- first_name: Alon
full_name: Rosen, Alon
last_name: Rosen
citation:
ama: 'Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. Public-Key Encryption from Homogeneous
CLWE. In: Theory of Cryptography. Vol 13748. Springer Nature; 2022:565-592.
doi:10.1007/978-3-031-22365-5_20'
apa: 'Bogdanov, A., Cueto Noval, M., Hoffmann, C., & Rosen, A. (2022). Public-Key
Encryption from Homogeneous CLWE. In Theory of Cryptography (Vol. 13748,
pp. 565–592). Chicago, IL, United States: Springer Nature. https://doi.org/10.1007/978-3-031-22365-5_20'
chicago: Bogdanov, Andrej, Miguel Cueto Noval, Charlotte Hoffmann, and Alon Rosen.
“Public-Key Encryption from Homogeneous CLWE.” In Theory of Cryptography,
13748:565–92. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-22365-5_20.
ieee: A. Bogdanov, M. Cueto Noval, C. Hoffmann, and A. Rosen, “Public-Key Encryption
from Homogeneous CLWE,” in Theory of Cryptography, Chicago, IL, United
States, 2022, vol. 13748, pp. 565–592.
ista: 'Bogdanov A, Cueto Noval M, Hoffmann C, Rosen A. 2022. Public-Key Encryption
from Homogeneous CLWE. Theory of Cryptography. TCC: Theory of Cryptography, LNCS,
vol. 13748, 565–592.'
mla: Bogdanov, Andrej, et al. “Public-Key Encryption from Homogeneous CLWE.” Theory
of Cryptography, vol. 13748, Springer Nature, 2022, pp. 565–92, doi:10.1007/978-3-031-22365-5_20.
short: A. Bogdanov, M. Cueto Noval, C. Hoffmann, A. Rosen, in:, Theory of Cryptography,
Springer Nature, 2022, pp. 565–592.
conference:
end_date: 2022-11-10
location: Chicago, IL, United States
name: 'TCC: Theory of Cryptography'
start_date: 2022-11-07
date_created: 2023-02-05T23:01:00Z
date_published: 2022-12-21T00:00:00Z
date_updated: 2023-08-04T10:39:30Z
day: '21'
department:
- _id: KrPi
doi: 10.1007/978-3-031-22365-5_20
external_id:
isi:
- '000921318200020'
intvolume: ' 13748'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/093
month: '12'
oa: 1
oa_version: Preprint
page: 565-592
publication: Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031223648'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Public-Key Encryption from Homogeneous CLWE
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13748
year: '2022'
...
---
_id: '10891'
abstract:
- lang: eng
text: We present a formal framework for the online black-box monitoring of software
using monitors with quantitative verdict functions. Quantitative verdict functions
have several advantages. First, quantitative monitors can be approximate, i.e.,
the value of the verdict function does not need to correspond exactly to the value
of the property under observation. Second, quantitative monitors can be quantified
universally, i.e., for every possible observed behavior, the monitor tries to
make the best effort to estimate the value of the property under observation.
Third, quantitative monitors can watch boolean as well as quantitative properties,
such as average response time. Fourth, quantitative monitors can use non-finite-state
resources, such as counters. As a consequence, quantitative monitors can be compared
according to how many resources they use (e.g., the number of counters) and how
precisely they approximate the property under observation. This allows for a rich
spectrum of cost-precision trade-offs in monitoring software.
acknowledgement: The formal framework for quantitative monitoring which is presented
in this invited talk was defined jointly with N. Ege Saraç at LICS 2021. This work
was supported in part by the Wittgenstein Award Z211-N23 of the Austrian Science
Fund.
article_processing_charge: No
author:
- first_name: Thomas A
full_name: Henzinger, Thomas A
id: 40876CD8-F248-11E8-B48F-1D18A9856A87
last_name: Henzinger
orcid: 0000-0002-2985-7724
citation:
ama: 'Henzinger TA. Quantitative monitoring of software. In: Software Verification.
Vol 13124. LNCS. Springer Nature; 2022:3-6. doi:10.1007/978-3-030-95561-8_1'
apa: 'Henzinger, T. A. (2022). Quantitative monitoring of software. In Software
Verification (Vol. 13124, pp. 3–6). New Haven, CT, United States: Springer
Nature. https://doi.org/10.1007/978-3-030-95561-8_1'
chicago: Henzinger, Thomas A. “Quantitative Monitoring of Software.” In Software
Verification, 13124:3–6. LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-030-95561-8_1.
ieee: T. A. Henzinger, “Quantitative monitoring of software,” in Software Verification,
New Haven, CT, United States, 2022, vol. 13124, pp. 3–6.
ista: 'Henzinger TA. 2022. Quantitative monitoring of software. Software Verification.
NSV: Numerical Software VerificationLNCS vol. 13124, 3–6.'
mla: Henzinger, Thomas A. “Quantitative Monitoring of Software.” Software Verification,
vol. 13124, Springer Nature, 2022, pp. 3–6, doi:10.1007/978-3-030-95561-8_1.
short: T.A. Henzinger, in:, Software Verification, Springer Nature, 2022, pp. 3–6.
conference:
end_date: 2021-10-19
location: New Haven, CT, United States
name: 'NSV: Numerical Software Verification'
start_date: 2021-10-18
date_created: 2022-03-20T23:01:40Z
date_published: 2022-02-22T00:00:00Z
date_updated: 2023-08-03T06:11:55Z
day: '22'
department:
- _id: ToHe
doi: 10.1007/978-3-030-95561-8_1
external_id:
isi:
- '000771713200001'
intvolume: ' 13124'
isi: 1
language:
- iso: eng
month: '02'
oa_version: None
page: 3-6
project:
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
call_identifier: FWF
grant_number: Z211
name: The Wittgenstein Prize
publication: Software Verification
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030955601'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Quantitative monitoring of software
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13124
year: '2022'
...
---
_id: '11185'
abstract:
- lang: eng
text: Bundling crossings is a strategy which can enhance the readability of graph
drawings. In this paper we consider bundlings for families of pseudosegments,
i.e., simple curves such that any two have share at most one point at which they
cross. Our main result is that there is a polynomial-time algorithm to compute
an 8-approximation of the bundled crossing number of such instances (up to adding
a term depending on the facial structure). This 8-approximation also holds for
bundlings of good drawings of graphs. In the special case of circular drawings
the approximation factor is 8 (no extra term), this improves upon the 10-approximation
of Fink et al. [6]. We also show how to compute a 92-approximation when the intersection
graph of the pseudosegments is bipartite.
acknowledgement: This work was initiated during the Workshop on Geometric Graphs in
November 2019 in Strobl, Austria. We would like to thank Oswin Aichholzer, Fabian
Klute, Man-Kwun Chiu, Martin Balko, Pavel Valtr for their avid discussions during
the workshop. The first author has received funding from the European Union’s Horizon
2020 research and innovation programme under the Marie Sklodowska Curie grant agreement
No 754411. The second author has been supported by the German Research Foundation
DFG Project FE 340/12-1.
article_processing_charge: No
arxiv: 1
author:
- first_name: Alan M
full_name: Arroyo Guevara, Alan M
id: 3207FDC6-F248-11E8-B48F-1D18A9856A87
last_name: Arroyo Guevara
orcid: 0000-0003-2401-8670
- first_name: Stefan
full_name: Felsner, Stefan
last_name: Felsner
citation:
ama: 'Arroyo Guevara AM, Felsner S. Approximating the bundled crossing number. In:
WALCOM 2022: Algorithms and Computation. Vol 13174. LNCS. Springer Nature;
2022:383-395. doi:10.1007/978-3-030-96731-4_31'
apa: 'Arroyo Guevara, A. M., & Felsner, S. (2022). Approximating the bundled
crossing number. In WALCOM 2022: Algorithms and Computation (Vol. 13174,
pp. 383–395). Jember, Indonesia: Springer Nature. https://doi.org/10.1007/978-3-030-96731-4_31'
chicago: 'Arroyo Guevara, Alan M, and Stefan Felsner. “Approximating the Bundled
Crossing Number.” In WALCOM 2022: Algorithms and Computation, 13174:383–95.
LNCS. Springer Nature, 2022. https://doi.org/10.1007/978-3-030-96731-4_31.'
ieee: 'A. M. Arroyo Guevara and S. Felsner, “Approximating the bundled crossing
number,” in WALCOM 2022: Algorithms and Computation, Jember, Indonesia,
2022, vol. 13174, pp. 383–395.'
ista: 'Arroyo Guevara AM, Felsner S. 2022. Approximating the bundled crossing number.
WALCOM 2022: Algorithms and Computation. WALCOM: Algorithms and ComputationLNCS
vol. 13174, 383–395.'
mla: 'Arroyo Guevara, Alan M., and Stefan Felsner. “Approximating the Bundled Crossing
Number.” WALCOM 2022: Algorithms and Computation, vol. 13174, Springer
Nature, 2022, pp. 383–95, doi:10.1007/978-3-030-96731-4_31.'
short: 'A.M. Arroyo Guevara, S. Felsner, in:, WALCOM 2022: Algorithms and Computation,
Springer Nature, 2022, pp. 383–395.'
conference:
end_date: 2022-03-26
location: Jember, Indonesia
name: 'WALCOM: Algorithms and Computation'
start_date: 2022-03-24
date_created: 2022-04-17T22:01:47Z
date_published: 2022-03-16T00:00:00Z
date_updated: 2023-09-25T10:56:10Z
day: '16'
department:
- _id: UlWa
doi: 10.1007/978-3-030-96731-4_31
ec_funded: 1
external_id:
arxiv:
- '2109.14892'
intvolume: ' 13174'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: ' https://doi.org/10.48550/arXiv.2109.14892'
month: '03'
oa: 1
oa_version: Preprint
page: 383-395
project:
- _id: 260C2330-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '754411'
name: ISTplus - Postdoctoral Fellowships
publication: 'WALCOM 2022: Algorithms and Computation'
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030967307'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '13969'
relation: later_version
status: public
scopus_import: '1'
series_title: LNCS
status: public
title: Approximating the bundled crossing number
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13174
year: '2022'
...