---
_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: 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: Cryptology and Information Security in Latin America'
start_date: 2023-10-03
corr_author: '1'
date_created: 2023-10-29T23:01:16Z
date_published: 2023-10-01T00:00:00Z
date_updated: 2025-09-09T13:09:21Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-031-44469-2_11
external_id:
isi:
- '001157041900011'
intvolume: ' 14168'
isi: 1
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 14168
year: '2023'
...
---
_id: '11476'
abstract:
- lang: eng
text: "Messaging platforms like Signal are widely deployed and provide strong security
in an asynchronous setting. It is a challenging problem to construct a protocol
with similar security guarantees that can efficiently scale to large groups. A
major bottleneck are the frequent key rotations users need to perform to achieve
post compromise forward security.\r\n\r\nIn current proposals – most notably in
TreeKEM (which is part of the IETF’s Messaging Layer Security (MLS) protocol draft)
– for users in a group of size n to rotate their keys, they must each craft a
message of size log(n) to be broadcast to the group using an (untrusted) delivery
server.\r\n\r\nIn larger groups, having users sequentially rotate their keys requires
too much bandwidth (or takes too long), so variants allowing any T≤n users to
simultaneously rotate their keys in just 2 communication rounds have been suggested
(e.g. “Propose and Commit” by MLS). Unfortunately, 2-round concurrent updates
are either damaging or expensive (or both); i.e. they either result in future
operations being more costly (e.g. via “blanking” or “tainting”) or are costly
themselves requiring Ω(T) communication for each user [Bienstock et al., TCC’20].\r\n\r\nIn
this paper we propose CoCoA; a new scheme that allows for T concurrent updates
that are neither damaging nor costly. That is, they add no cost to future operations
yet they only require Ω(log2(n)) communication per user. To circumvent the [Bienstock
et al.] lower bound, CoCoA increases the number of rounds needed to complete all
updates from 2 up to (at most) log(n); though typically fewer rounds are needed.\r\n\r\nThe
key insight of our protocol is the following: in the (non-concurrent version of)
TreeKEM, a delivery server which gets T concurrent update requests will approve
one and reject the remaining T−1. In contrast, our server attempts to apply all
of them. If more than one user requests to rotate the same key during a round,
the server arbitrarily picks a winner. Surprisingly, we prove that regardless
of how the server chooses the winners, all previously compromised users will recover
after at most log(n) such update rounds.\r\n\r\nTo keep the communication complexity
low, CoCoA is a server-aided CGKA. That is, the delivery server no longer blindly
forwards packets, but instead actively computes individualized packets tailored
to each user. As the server is untrusted, this change requires us to develop new
mechanisms ensuring robustness of the protocol."
acknowledgement: We thank Marta Mularczyk and Yiannis Tselekounis for their very helpful
feedback on an earlier draft of this paper.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joël
full_name: Alwen, Joël
last_name: Alwen
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
last_name: Walter
citation:
ama: 'Alwen J, Auerbach B, Cueto Noval M, et al. CoCoA: Concurrent continuous group
key agreement. In: Advances in Cryptology – EUROCRYPT 2022. Vol 13276.
Cham: Springer Nature; 2022:815–844. doi:10.1007/978-3-031-07085-3_28'
apa: 'Alwen, J., Auerbach, B., Cueto Noval, M., Klein, K., Pascual Perez, G., Pietrzak,
K. Z., & Walter, M. (2022). CoCoA: Concurrent continuous group key agreement.
In Advances in Cryptology – EUROCRYPT 2022 (Vol. 13276, pp. 815–844). Cham:
Springer Nature. https://doi.org/10.1007/978-3-031-07085-3_28'
chicago: 'Alwen, Joël, Benedikt Auerbach, Miguel Cueto Noval, Karen Klein, Guillermo
Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter. “CoCoA: Concurrent Continuous
Group Key Agreement.” In Advances in Cryptology – EUROCRYPT 2022, 13276:815–844.
Cham: Springer Nature, 2022. https://doi.org/10.1007/978-3-031-07085-3_28.'
ieee: 'J. Alwen et al., “CoCoA: Concurrent continuous group key agreement,”
in Advances in Cryptology – EUROCRYPT 2022, Trondheim, Norway, 2022, vol.
13276, pp. 815–844.'
ista: 'Alwen J, Auerbach B, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak KZ,
Walter M. 2022. CoCoA: Concurrent continuous group key agreement. Advances in
Cryptology – EUROCRYPT 2022. EUROCRYPT: Theory and Applications of Cryptology
and Information Security, LNCS, vol. 13276, 815–844.'
mla: 'Alwen, Joël, et al. “CoCoA: Concurrent Continuous Group Key Agreement.” Advances
in Cryptology – EUROCRYPT 2022, vol. 13276, Springer Nature, 2022, pp. 815–844,
doi:10.1007/978-3-031-07085-3_28.'
short: J. Alwen, B. Auerbach, M. Cueto Noval, K. Klein, G. Pascual Perez, K.Z. Pietrzak,
M. Walter, in:, Advances in Cryptology – EUROCRYPT 2022, Springer Nature, Cham,
2022, pp. 815–844.
conference:
end_date: 2022-06-03
location: Trondheim, Norway
name: 'EUROCRYPT: Theory and Applications of Cryptology and Information Security'
start_date: 2022-05-30
corr_author: '1'
date_created: 2022-06-30T16:48:00Z
date_published: 2022-05-25T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '25'
department:
- _id: GradSch
- _id: KrPi
doi: 10.1007/978-3-031-07085-3_28
ec_funded: 1
external_id:
isi:
- '000832305300028'
intvolume: ' 13276'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/251
month: '05'
oa: 1
oa_version: Preprint
page: 815–844
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: Advances in Cryptology – EUROCRYPT 2022
publication_identifier:
eisbn:
- '9783031070853'
eissn:
- 1611-3349
isbn:
- '9783031070846'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'CoCoA: Concurrent continuous group key agreement'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13276
year: '2022'
...
---
_id: '12167'
abstract:
- lang: eng
text: "Payment channels effectively move the transaction load off-chain thereby
successfully addressing the inherent scalability problem most cryptocurrencies
face. A major drawback of payment channels is the need to “top up” funds on-chain
when a channel is depleted. Rebalancing was proposed to alleviate this issue,
where parties with depleting channels move their funds along a cycle to replenish
their channels off-chain. Protocols for rebalancing so far either introduce local
solutions or compromise privacy.\r\nIn this work, we present an opt-in rebalancing
protocol that is both private and globally optimal, meaning our protocol maximizes
the total amount of rebalanced funds. We study rebalancing from the framework
of linear programming. To obtain full privacy guarantees, we leverage multi-party
computation in solving the linear program, which is executed by selected participants
to maintain efficiency. Finally, we efficiently decompose the rebalancing solution
into incentive-compatible cycles which conserve user balances when executed atomically."
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Georgia
full_name: Avarikioti, Georgia
id: c20482a0-3b89-11eb-9862-88cf6404b88c
last_name: Avarikioti
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Iosif
full_name: Salem, Iosif
last_name: Salem
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Samarth
full_name: Tiwari, Samarth
last_name: Tiwari
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. Hide &
Seek: Privacy-preserving rebalancing on payment channel networks. In: Financial
Cryptography and Data Security. Vol 13411. Springer Nature; 2022:358-373.
doi:10.1007/978-3-031-18283-9_17'
apa: 'Avarikioti, G., Pietrzak, K. Z., Salem, I., Schmid, S., Tiwari, S., &
Yeo, M. X. (2022). Hide & Seek: Privacy-preserving rebalancing on payment
channel networks. In Financial Cryptography and Data Security (Vol. 13411,
pp. 358–373). Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_17'
chicago: 'Avarikioti, Georgia, Krzysztof Z Pietrzak, Iosif Salem, Stefan Schmid,
Samarth Tiwari, and Michelle X Yeo. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” In Financial Cryptography and Data Security,
13411:358–73. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_17.'
ieee: 'G. Avarikioti, K. Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. X.
Yeo, “Hide & Seek: Privacy-preserving rebalancing on payment channel networks,”
in Financial Cryptography and Data Security, Grenada, 2022, vol. 13411,
pp. 358–373.'
ista: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. 2022. Hide
& Seek: Privacy-preserving rebalancing on payment channel networks. Financial
Cryptography and Data Security. FC: Financial Cryptography and Data Security,
LNCS, vol. 13411, 358–373.'
mla: 'Avarikioti, Georgia, et al. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” Financial Cryptography and Data Security,
vol. 13411, Springer Nature, 2022, pp. 358–73, doi:10.1007/978-3-031-18283-9_17.'
short: G. Avarikioti, K.Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, M.X. Yeo, in:,
Financial Cryptography and Data Security, Springer Nature, 2022, pp. 358–373.
conference:
end_date: 2022-05-06
location: Grenada
name: 'FC: Financial Cryptography and Data Security'
start_date: 2022-05-02
date_created: 2023-01-12T12:10:38Z
date_published: 2022-10-22T00:00:00Z
date_updated: 2025-09-10T09:48:15Z
day: '22'
department:
- _id: KrPi
doi: 10.1007/978-3-031-18283-9_17
external_id:
arxiv:
- '2110.08848'
isi:
- '001423640200017'
intvolume: ' 13411'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2110.08848
month: '10'
oa: 1
oa_version: Preprint
page: 358-373
publication: Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031182839'
eissn:
- 1611-3349
isbn:
- '9783031182822'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Hide & Seek: Privacy-preserving rebalancing on payment channel networks'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 13411
year: '2022'
...
---
_id: '12176'
abstract:
- lang: eng
text: "A proof of exponentiation (PoE) in a group G of unknown order allows a prover
to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive
has recently found exciting applications in the constructions of verifiable delay
functions and succinct arguments of knowledge. The most practical PoEs only achieve
soundness either under computational assumptions, i.e., they are arguments (Wesolowski,
Journal of Cryptology 2020), or in groups that come with the promise of not having
any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in
general groups of unknown order is due to Block et al. (CRYPTO 2021), and can
be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits
of security, say λ=80, the number of repetitions required (and thus the blow-up
in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound
PoE for the case where the exponent q is the product of all primes up to some
bound B. We show that, in this case, it suffices to run only λ/log(B) parallel
instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to
Block et al. by an order of magnitude. Furthermore, we show that in the known
applications where PoEs are used as a building block such structured exponents
are viable. Finally, we also discuss batching of our PoE, showing that many proofs
(for the same G and q but different x and T) can be batched by adding only a single
element to the proof per additional statement."
acknowledgement: "We would like to thank the authors of [BHR+21] for clarifying several
questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the
Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and
by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by
Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19.
Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part
of this work at Institute of Science and Technology Austria."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- first_name: Karen
full_name: Klein, Karen
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound
proofs of exponentiation in any group. In: Advances in Cryptology – CRYPTO
2022. Vol 13508. Springer Nature; 2022:370-399. doi:10.1007/978-3-031-15979-4_13'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., & Pietrzak, K. Z. (2022).
Practical statistically-sound proofs of exponentiation in any group. In Advances
in Cryptology – CRYPTO 2022 (Vol. 13508, pp. 370–399). Santa Barbara, CA,
United States: Springer Nature. https://doi.org/10.1007/978-3-031-15979-4_13'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof
Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.”
In Advances in Cryptology – CRYPTO 2022, 13508:370–99. Springer Nature,
2022. https://doi.org/10.1007/978-3-031-15979-4_13.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical
statistically-sound proofs of exponentiation in any group,” in Advances in
Cryptology – CRYPTO 2022, Santa Barbara, CA, United States, 2022, vol. 13508,
pp. 370–399.
ista: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound
proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYPTO:
International Cryptology Conference, LNCS, vol. 13508, 370–399.'
mla: Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation
in Any Group.” Advances in Cryptology – CRYPTO 2022, vol. 13508, Springer
Nature, 2022, pp. 370–99, doi:10.1007/978-3-031-15979-4_13.
short: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances
in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.
conference:
end_date: 2022-08-18
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2022-08-15
corr_author: '1'
date_created: 2023-01-12T12:12:07Z
date_published: 2022-10-13T00:00:00Z
date_updated: 2026-04-07T12:34:30Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-3-031-15979-4_13
external_id:
isi:
- '000886792700013'
intvolume: ' 13508'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1021
month: '10'
oa: 1
oa_version: Preprint
page: 370-399
publication: Advances in Cryptology – CRYPTO 2022
publication_identifier:
eisbn:
- '9783031159794'
eissn:
- 1611-3349
isbn:
- '9783031159787'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '20920'
relation: dissertation_contains
status: public
- id: '20556'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Practical statistically-sound proofs of exponentiation in any group
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13508
year: '2022'
...
---
_id: '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
orcid: 0000-0002-2505-4246
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- 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
corr_author: '1'
date_created: 2023-02-05T23:01:00Z
date_published: 2022-12-21T00:00:00Z
date_updated: 2024-10-09T21:04:05Z
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: '17060'
abstract:
- lang: eng
text: "Payment channel networks (PCNs) are one of the most prominent solutions to
the limited transaction throughput of blockchains. Nevertheless, PCNs suffer themselves
from a throughput limitation due to the capital constraints of their channels.
A similar dependence on high capital is also found in inter-bank payment settlements,
where the so-called netting technique is used to mitigate liquidity demands.\r\nIn
this work, we alleviate this limitation by introducing the notion of transaction
aggregation: instead of executing transactions sequentially through a PCN, we
enable senders to aggregate multiple transactions and execute them simultaneously
to benefit from several amounts that may \"cancel out\". Two direct advantages
of our proposal is the decrease in intermediary fees paid by senders as well as
the obfuscation of the transaction data from the intermediaries.\r\nWe formulate
the transaction aggregation as a computational problem, a generalization of the
Bank Clearing Problem. We present a generic framework for the transaction aggregation
execution, and thereafter we propose Wiser as an implementation of this framework
in a specific hub-based setting. To overcome the NP-hardness of the transaction
aggregation problem, in Wiser we propose a fixed-parameter linear algorithm for
a special case of transaction aggregation as well as the Bank Clearing Problem.
Wiser can also be seen as a modern variant of the Hawala money transfer system,
as well as a decentralized implementation of the overseas remittance service of
Wise."
acknowledgement: "This work was supported partially by ERC Starting Grant QIP–805241,
by the Vienna business agency (Wirtschaftsagentur) through the Vienna Cybersecurity
and Privacy Research Center\r\n(ViSP) and by the Austrian Science Fund (FWF) project
I 4800-N (ADVISE).\r\nThe first author would like to thank Daniel Dadush for suggesting
the use of discrepancy techniques to solve the transaction aggregation problem."
article_processing_charge: Yes (in subscription journal)
arxiv: 1
author:
- first_name: Samarth
full_name: Tiwari, Samarth
last_name: Tiwari
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Zeta
full_name: Avarikioti, Zeta
last_name: Avarikioti
- first_name: Iosif
full_name: Salem, Iosif
last_name: Salem
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'Tiwari S, Yeo MX, Avarikioti Z, Salem I, Pietrzak KZ, Schmid S. Wiser: Increasing
throughput in payment channel networks with transaction aggregation. In: Proceedings
of the 4th ACM Conference on Advances in Financial Technologies. Association
for Computing Machinery; 2022:217-231. doi:10.1145/3558535.3559775'
apa: 'Tiwari, S., Yeo, M. X., Avarikioti, Z., Salem, I., Pietrzak, K. Z., &
Schmid, S. (2022). Wiser: Increasing throughput in payment channel networks with
transaction aggregation. In Proceedings of the 4th ACM Conference on Advances
in Financial Technologies (pp. 217–231). Cambridge, MA, United States: Association
for Computing Machinery. https://doi.org/10.1145/3558535.3559775'
chicago: 'Tiwari, Samarth, Michelle X Yeo, Zeta Avarikioti, Iosif Salem, Krzysztof
Z Pietrzak, and Stefan Schmid. “Wiser: Increasing Throughput in Payment Channel
Networks with Transaction Aggregation.” In Proceedings of the 4th ACM Conference
on Advances in Financial Technologies, 217–31. Association for Computing Machinery,
2022. https://doi.org/10.1145/3558535.3559775.'
ieee: 'S. Tiwari, M. X. Yeo, Z. Avarikioti, I. Salem, K. Z. Pietrzak, and S. Schmid,
“Wiser: Increasing throughput in payment channel networks with transaction aggregation,”
in Proceedings of the 4th ACM Conference on Advances in Financial Technologies,
Cambridge, MA, United States, 2022, pp. 217–231.'
ista: 'Tiwari S, Yeo MX, Avarikioti Z, Salem I, Pietrzak KZ, Schmid S. 2022. Wiser:
Increasing throughput in payment channel networks with transaction aggregation.
Proceedings of the 4th ACM Conference on Advances in Financial Technologies. AFT:
Conference on Advances in Financial Technologies, 217–231.'
mla: 'Tiwari, Samarth, et al. “Wiser: Increasing Throughput in Payment Channel Networks
with Transaction Aggregation.” Proceedings of the 4th ACM Conference on Advances
in Financial Technologies, Association for Computing Machinery, 2022, pp.
217–31, doi:10.1145/3558535.3559775.'
short: S. Tiwari, M.X. Yeo, Z. Avarikioti, I. Salem, K.Z. Pietrzak, S. Schmid, in:,
Proceedings of the 4th ACM Conference on Advances in Financial Technologies, Association
for Computing Machinery, 2022, pp. 217–231.
conference:
end_date: 2022-09-21
location: Cambridge, MA, United States
name: 'AFT: Conference on Advances in Financial Technologies'
start_date: 2022-09-19
date_created: 2024-05-28T13:58:35Z
date_published: 2022-09-19T00:00:00Z
date_updated: 2025-09-10T09:57:48Z
day: '19'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1145/3558535.3559775
external_id:
arxiv:
- '2205.11597'
isi:
- '001041852800015'
file:
- access_level: open_access
checksum: 54a7d405f8e57dba24728599ca63818c
content_type: application/pdf
creator: dernst
date_created: 2024-08-19T06:45:21Z
date_updated: 2024-08-19T06:45:21Z
file_id: '17439'
file_name: 2022_AFT_Tiwari.pdf
file_size: 574728
relation: main_file
success: 1
file_date_updated: 2024-08-19T06:45:21Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: 217-231
publication: Proceedings of the 4th ACM Conference on Advances in Financial Technologies
publication_identifier:
isbn:
- '9781450398619'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Wiser: Increasing throughput in payment channel networks with transaction
aggregation'
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2022'
...
---
OA_place: publisher
_id: '10035'
abstract:
- lang: eng
text: 'Many security definitions come in two flavors: a stronger “adaptive” flavor,
where the adversary can arbitrarily make various choices during the course of
the attack, and a weaker “selective” flavor where the adversary must commit to
some or all of their choices a-priori. For example, in the context of identity-based
encryption, selective security requires the adversary to decide on the identity
of the attacked party at the very beginning of the game whereas adaptive security
allows the attacker to first see the master public key and some secret keys before
making this choice. Often, it appears to be much easier to achieve selective security
than it is to achieve adaptive security. A series of several recent works shows
how to cleverly achieve adaptive security in several such scenarios including
generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and
Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition
that they share a common technique, the connection was never made precise. In
this work we present a new framework (published at Crypto ’17 [JKK+17a]) that
connects all of these works and allows us to present them in a unified and simplified
fashion. Having the framework in place, we show how to achieve adaptive security
for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the
first adaptive security proofs for continuous group key agreement protocols (published
at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that
currently used proof techniques cannot lead to significantly better security guarantees
for "graph-building" games (published at TCC ’21 [KKPW21a]). These games cover
generalized selective decryption, as well as the security of prominent constructions
for constrained PRFs, continuous group key agreement, and proxy re-encryption.
Finally, we revisit the adaptive security of Yao’s garbled circuits and extend
the analysis of Jafargholi and Wichs in two directions: While they prove adaptive
security only for a modified construction with increased online complexity, we
provide the first positive results for the original construction by Yao (published
at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi
and Wichs are essentially optimal by showing that no black-box reduction can provide
a significantly better security bound (published at Crypto ’21 [KKPW21c]).'
acknowledgement: "I want to acknowledge the funding by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
citation:
ama: Klein K. On the adaptive security of graph-based games. 2021. doi:10.15479/at:ista:10035
apa: Klein, K. (2021). On the adaptive security of graph-based games. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:10035
chicago: Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute
of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10035.
ieee: K. Klein, “On the adaptive security of graph-based games,” Institute of Science
and Technology Austria, 2021.
ista: Klein K. 2021. On the adaptive security of graph-based games. Institute of
Science and Technology Austria.
mla: Klein, Karen. On the Adaptive Security of Graph-Based Games. Institute
of Science and Technology Austria, 2021, doi:10.15479/at:ista:10035.
short: K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science
and Technology Austria, 2021.
corr_author: '1'
date_created: 2021-09-23T07:31:44Z
date_published: 2021-09-23T00:00:00Z
date_updated: 2026-04-16T09:52:03Z
day: '23'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/at:ista:10035
ec_funded: 1
file:
- access_level: open_access
checksum: 73a44345c683e81f3e765efbf86fdcc5
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-04T12:22:33Z
date_updated: 2021-10-04T12:22:33Z
file_id: '10082'
file_name: thesis_pdfa.pdf
file_size: 2104726
relation: main_file
success: 1
- access_level: closed
checksum: 7b80df30a0e686c3ef6a56d4e1c59e29
content_type: application/x-zip-compressed
creator: cchlebak
date_created: 2021-10-05T07:04:37Z
date_updated: 2022-03-10T12:15:18Z
file_id: '10085'
file_name: thesis_final (1).zip
file_size: 9538359
relation: source_file
file_date_updated: 2022-03-10T12:15:18Z
has_accepted_license: '1'
language:
- iso: eng
month: '09'
oa: 1
oa_version: Published Version
page: '276'
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10044'
relation: part_of_dissertation
status: public
- id: '10048'
relation: part_of_dissertation
status: public
- id: '10041'
relation: part_of_dissertation
status: public
- id: '10049'
relation: part_of_dissertation
status: public
- id: '637'
relation: part_of_dissertation
status: public
- id: '6430'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On the adaptive security of graph-based games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2021'
...
---
_id: '10041'
abstract:
- lang: eng
text: Yao’s garbling scheme is one of the most fundamental cryptographic constructions.
Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security
in the selective setting where the adversary chooses the challenge inputs before
seeing the garbled circuit assuming secure symmetric-key encryption (and hence
one-way functions). This was followed by results, both positive and negative,
concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto
2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility
argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s
scheme (where the output mapping is sent in the online phase, together with the
garbled input) that circumvents this negative result, and proved that it is adaptively
secure, at least for shallow circuits. In particular, they showed that for the
class of circuits of depth δ , the loss in security is at most exponential in δ
. The above results all concern the simulation-based notion of security. In this
work, we show that the upper bound of Jafargholi and Wichs is basically optimal
in a strong sense. As our main result, we show that there exists a family of Boolean
circuits, one for each depth δ∈N , such that any black-box reduction proving
the adaptive indistinguishability of the natural adaptation of Yao’s scheme from
any symmetric-key encryption has to lose a factor that is exponential in δ√
. Since indistinguishability is a weaker notion than simulation, our bound also
applies to adaptive simulation. To establish our results, we build on the recent
approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction
with oracle separations to prove fine-grained lower bounds on loss in cryptographic
security.
acknowledgement: We would like to thank the anonymous reviewers of Crypto’21 whose
detailed comments helped us considerably improve the presentation of the paper.
alternative_title:
- LCNS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security
of Yao’s Garbling. In: 41st Annual International Cryptology Conference, Part
II . Vol 12826. Cham: Springer Nature; 2021:486-515. doi:10.1007/978-3-030-84245-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Wichs, D. (2021). Limits
on the Adaptive Security of Yao’s Garbling. In 41st Annual International Cryptology
Conference, Part II (Vol. 12826, pp. 486–515). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-84245-1_17'
chicago: 'Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel
Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In 41st Annual
International Cryptology Conference, Part II , 12826:486–515. Cham: Springer
Nature, 2021. https://doi.org/10.1007/978-3-030-84245-1_17.'
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the
Adaptive Security of Yao’s Garbling,” in 41st Annual International Cryptology
Conference, Part II , Virtual, 2021, vol. 12826, pp. 486–515.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive
Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part
II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.'
mla: Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.”
41st Annual International Cryptology Conference, Part II , vol. 12826,
Springer Nature, 2021, pp. 486–515, doi:10.1007/978-3-030-84245-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International
Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.
conference:
end_date: 2021-08-20
location: Virtual
name: 'CRYPTO: Annual International Cryptology Conference'
start_date: 2021-08-16
date_created: 2021-09-23T14:06:15Z
date_published: 2021-08-11T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-84245-1_17
ec_funded: 1
external_id:
isi:
- '000696697800017'
intvolume: ' 12826'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/945
month: '08'
oa: 1
oa_version: Preprint
page: 486-515
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '41st Annual International Cryptology Conference, Part II '
publication_identifier:
eisbn:
- 978-3-030-84245-1
eissn:
- 1611-3349
isbn:
- 978-3-030-84244-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Limits on the Adaptive Security of Yao’s Garbling
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12826
year: '2021'
...
---
_id: '10044'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in
security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit.
The design of the strategy relies on separators, a graph-theoretic notion with
connections to circuit complexity.
acknowledgement: 'We would like to thank Daniel Wichs for helpful discussions on the
landscape of adaptive security of Yao’s garbling. '
article_number: 2021/926
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th Theory of Cryptography Conference 2021. International
Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th Theory of Cryptography Conference 2021.
Raleigh, NC, United States: International Association for Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th Theory of Cryptography Conference 2021, Raleigh,
NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography
Conference, 2021/926.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th Theory of Cryptography Conference 2021, 2021/926, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography
Conference 2021, International Association for Cryptologic Research, 2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-09-24T12:01:34Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '08'
department:
- _id: KrPi
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10409'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: On treewidth, separators and Yao's garbling
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10048'
abstract:
- lang: eng
text: "The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower\r\nbounds
that almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and\r\nbroadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.\r\n"
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th Theory of Cryptography
Conference 2021. Raleigh, NC, United States: International Association for
Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory
of Cryptography Conference 2021. International Association for Cryptologic
Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th Theory of Cryptography Conference 2021,
Raleigh, NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC:
Theory of Cryptography Conference.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th Theory of Cryptography Conference 2021, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of
Cryptography Conference 2021, International Association for Cryptologic Research,
2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-09-27T12:52:05Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '08'
department:
- _id: KrPi
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '07'
oa: 1
oa_version: Preprint
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10410'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10049'
abstract:
- lang: eng
text: While messaging systems with strong security guarantees are widely used in
practice, designing a protocol that scales efficiently to large groups and enjoys
similar security guarantees remains largely open. The two existing proposals to
date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer
Security Protocol, draft). TreeKEM is the currently considered candidate by the
IETF MLS working group, but dynamic group operations (i.e. adding and removing
users) can cause efficiency issues. In this paper we formalize and analyze a variant
of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying
TTKEM was suggested by Millican (MLS mailing list, February 2018). This version
is more efficient than TreeKEM for some natural distributions of group operations,
we quantify this through simulations.Our second contribution is two security proofs
for TTKEM which establish post compromise and forward secrecy even against adaptive
attackers. The security loss (to the underlying PKE) in the Random Oracle Model
is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs
can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like
protocol establishing tight security against an adversary who can adaptively choose
the sequence of operations was known. We also are the first to prove (or even
formalize) active security where the server can arbitrarily deviate from the protocol
specification. Proving fully active security – where also the users can arbitrarily
deviate – remains open.
acknowledgement: The first three authors contributed equally to this work. Funded
by the European Research Council (ERC) under the European Union’s Horizon2020 research
and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No.665385.
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Margarita
full_name: Capretto, Margarita
last_name: Capretto
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- 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: 'Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. In: 2021 IEEE
Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035'
apa: 'Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M.,
Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively
and actively secure continuous group key agreement. In 2021 IEEE Symposium
on Security and Privacy (pp. 268–284). San Francisco, CA, United States:
IEEE. https://doi.org/10.1109/sp40001.2021.00035'
chicago: 'Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath
Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo,
Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively
and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium
on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.'
ieee: 'K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively
secure continuous group key agreement,” in 2021 IEEE Symposium on Security
and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.'
ista: 'Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval
M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium
on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.'
mla: 'Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively
Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and
Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.'
short: K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M.
Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium
on Security and Privacy , IEEE, 2021, pp. 268–284.
conference:
end_date: 2021-05-27
location: San Francisco, CA, United States
name: 'SP: Symposium on Security and Privacy'
start_date: 2021-05-24
corr_author: '1'
date_created: 2021-09-27T13:46:27Z
date_published: 2021-08-26T00:00:00Z
date_updated: 2026-04-08T07:01:44Z
day: '26'
department:
- _id: KrPi
- _id: DaAl
doi: 10.1109/sp40001.2021.00035
ec_funded: 1
external_id:
isi:
- '001316065000016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1489
month: '08'
oa: 1
oa_version: Preprint
page: 268-284
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '2021 IEEE Symposium on Security and Privacy '
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous
group key agreement'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2021'
...
---
_id: '10407'
abstract:
- lang: eng
text: Digital hardware Trojans are integrated circuits whose implementation differ
from the specification in an arbitrary and malicious way. For example, the circuit
can differ from its specified input/output behavior after some fixed number of
queries (known as “time bombs”) or on some particular input (known as “cheat codes”).
To detect such Trojans, countermeasures using multiparty computation (MPC) or
verifiable computation (VC) have been proposed. On a high level, to realize a
circuit with specification F one has more sophisticated circuits F⋄ manufactured
(where F⋄ specifies a MPC or VC of F ), and then embeds these F⋄ ’s into
a master circuit which must be trusted but is relatively simple compared to F
. Those solutions impose a significant overhead as F⋄ is much more complex
than F , also the master circuits are not exactly trivial. In this work, we
show that in restricted settings, where F has no evolving state and is queried
on independent inputs, we can achieve a relaxed security notion using very simple
constructions. In particular, we do not change the specification of the circuit
at all (i.e., F=F⋄ ). Moreover the master circuit basically just queries a subset
of its manufactured circuits and checks if they’re all the same. The security
we achieve guarantees that, if the manufactured circuits are initially tested
on up to T inputs, the master circuit will catch Trojans that try to deviate on
significantly more than a 1/T fraction of the inputs. This bound is optimal for
the type of construction considered, and we provably achieve it using a construction
where 12 instantiations of F need to be embedded into the master. We also discuss
an extremely simple construction with just 2 instantiations for which we conjecture
that it already achieves the optimal bound.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Małgorzata
full_name: Gałązka, Małgorzata
last_name: Gałązka
- first_name: Tomasz
full_name: Lizurej, Tomasz
last_name: Lizurej
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience
without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:10.1007/978-3-030-90453-1_14'
apa: 'Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z.,
& Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp.
397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC,
United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_14'
chicago: Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej,
Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,”
13043:397–428. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_14.
ieee: 'S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and
M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory
of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp.
397–428.'
ista: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX.
2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference,
LNCS, vol. 13043, 397–428.'
mla: Chakraborty, Suvradip, et al. Trojan-Resilience without Cryptography.
Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:10.1007/978-3-030-90453-1_14.
short: S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X.
Yeo, in:, Springer Nature, 2021, pp. 397–428.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-14T07:22:05Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_14
ec_funded: 1
external_id:
isi:
- '000728364000014'
intvolume: ' 13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1224
month: '11'
oa: 1
oa_version: Preprint
page: 397-428
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trojan-resilience without cryptography
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...
---
_id: '10408'
abstract:
- lang: eng
text: 'Key trees are often the best solution in terms of transmission cost and storage
requirements for managing keys in a setting where a group needs to share a secret
key, while being able to efficiently rotate the key material of users (in order
to recover from a potential compromise, or to add or remove users). Applications
include multicast encryption protocols like LKH (Logical Key Hierarchies) or group
messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced)
binary tree, where each node is identified with a key: leaf nodes hold users’
secret keys while the root is the shared group key. For a group of size N, each
user just holds log(N) keys (the keys on the path from its leaf to the root)
and its entire key material can be rotated by broadcasting 2log(N) ciphertexts
(encrypting each fresh key on the path under the keys of its parents). In this
work we consider the natural setting where we have many groups with partially
overlapping sets of users, and ask if we can find solutions where the cost of
rotating a key is better than in the trivial one where we have a separate key
tree for each group. We show that in an asymptotic setting (where the number m
of groups is fixed while the number N of users grows) there exist more general
key graphs whose cost converges to the cost of a single group, thus saving a factor
linear in the number of groups over the trivial solution. As our asymptotic “solution”
converges very slowly and performs poorly on concrete examples, we propose an
algorithm that uses a natural heuristic to compute a key graph for any given group
structure. Our algorithm combines two greedy algorithms, and is thus very efficient:
it first converts the group structure into a “lattice graph”, which is then turned
into a key graph by repeatedly applying the algorithm for constructing a Huffman
code. To better understand how far our proposal is from an optimal solution, we
prove lower bounds on the update cost of continuous group-key agreement and multicast
encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom
generators, and secret sharing as building blocks.'
acknowledgement: B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by
ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the
ERC under the European Union’s Horizon 2020 research and innovation programme (682815
- TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No. 665385; Michael Walter conducted part of this work at IST Austria, funded by
the ERC under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management
for overlapping groups. In: 19th International Conference. Vol 13044. Springer
Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8'
apa: 'Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual
Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for
overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253).
Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8'
chicago: 'Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval,
Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter.
“Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th
International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.'
ieee: 'J. F. Alwen et al., “Grafting key trees: Efficient key management
for overlapping groups,” in 19th International Conference, Raleigh, NC,
United States, 2021, vol. 13044, pp. 222–253.'
ista: 'Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak
KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping
groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol.
13044, 222–253.'
mla: 'Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping
Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021,
pp. 222–53, doi:10.1007/978-3-030-90456-2_8.'
short: J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual
Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer
Nature, 2021, pp. 222–253.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2026-04-07T13:01:26Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90456-2_8
ec_funded: 1
external_id:
isi:
- '000728363700008'
intvolume: ' 13044'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1158
month: '11'
oa: 1
oa_version: Preprint
page: 222-253
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: 19th International Conference
publication_identifier:
eisbn:
- 978-3-030-90456-2
eissn:
- 1611-3349
isbn:
- 9-783-0309-0455-5
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Grafting key trees: Efficient key management for overlapping groups'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13044
year: '2021'
...
---
_id: '10409'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a SO(w) loss
in security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the
circuit. The design of the strategy relies on separators, a graph-theoretic notion
with connections to circuit complexity. with only a SO(w) loss in security.
For instance, circuits with constant treewidth are as a result adaptively indistinguishable
with only a polynomial loss. This (partially) complements a negative result of
Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that
Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions,
we introduce a new pebble game that abstracts out our security reduction and then
present a pebbling strategy for this game where the number of pebbles used is
roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the
strategy relies on separators, a graph-theoretic notion with connections to circuit
complexity.
acknowledgement: We are grateful to Daniel Wichs for helpful discussions on the landscape
of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021
and TCC 2021 reviewers for their detailed review and suggestions, which helped improve
presentation considerably.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th International Conference. Vol 13043. Springer Nature;
2021:486-517. doi:10.1007/978-3-030-90453-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th International Conference (Vol. 13043,
pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th International Conference, 13043:486–517.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th International Conference, Raleigh, NC, United
States, 2021, vol. 13043, pp. 486–517.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS,
vol. 13043, 486–517.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517,
doi:10.1007/978-3-030-90453-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference,
Springer Nature, 2021, pp. 486–517.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-15T08:32:06Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_17
ec_funded: 1
external_id:
isi:
- '000728364000017'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '11'
oa: 1
oa_version: Preprint
page: 486-517
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10044'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On treewidth, separators and Yao’s garbling
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: '13043 '
year: '2021'
...
---
_id: '10410'
abstract:
- lang: eng
text: The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical framework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower bounds that
almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and broadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.
acknowledgement: C. Kamath—Supported by Azrieli International Postdoctoral Fellowship.
Most of the work was done while the author was at Northeastern University and Charles
University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9,
respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work
was done while the author was at IST Austria funded by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th International Conference. Vol 13043.
Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th International Conference
(Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th International
Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th International Conference, Raleigh,
NC, United States, 2021, vol. 13043, pp. 550–581.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th International Conference. TCC: Theory of Cryptography,
LNCS, vol. 13043, 550–581.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021,
pp. 550–81, doi:10.1007/978-3-030-90453-1_19.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International
Conference, Springer Nature, 2021, pp. 550–581.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-14T07:22:05Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_19
ec_funded: 1
external_id:
isi:
- '000728364000019'
intvolume: ' 13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '11'
oa: 1
oa_version: Preprint
page: 550-581
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10048'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...
---
_id: '10609'
abstract:
- lang: eng
text: "We study Multi-party computation (MPC) in the setting of subversion, where
the adversary tampers with the machines of honest parties. Our goal is to construct
actively secure MPC protocols where parties are corrupted adaptively by an adversary
(as in the standard adaptive security setting), and in addition, honest parties’
machines are compromised.\r\nThe idea of reverse firewalls (RF) was introduced
at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting
protocols against corruption of honest parties’ devices. Intuitively, an RF for
a party P is an external entity that sits between P and the outside world
and whose scope is to sanitize P ’s incoming and outgoing messages in the face
of subversion of their computer. Mironov and Stephens-Davidowitz constructed a
protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty,
Dziembowski and Nielsen constructed a protocol for secure computation with firewalls
that improved on this result, both by extending it to multi-party computation
protocol, and considering active security in the presence of static corruptions.
In this paper, we initiate the study of RF for MPC in the adaptive setting. We
put forward a definition for adaptively secure MPC in the reverse firewall setting,
explore relationships among the security notions, and then construct reverse firewalls
for MPC in this stronger setting of adaptive security. We also resolve the open
question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted
setup in constructing RF for MPC. Towards this end, we construct reverse firewalls
for adaptively secure augmented coin tossing and adaptively secure zero-knowledge
protocols and obtain a constant round adaptively secure MPC protocol in the reverse
firewall setting without setup. Along the way, we propose a new multi-party adaptively
secure coin tossing protocol in the plain model, that is of independent interest."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Chaya
full_name: Ganesh, Chaya
last_name: Ganesh
- first_name: Mahak
full_name: Pancholi, Mahak
last_name: Pancholi
- first_name: Pratik
full_name: Sarkar, Pratik
last_name: Sarkar
citation:
ama: 'Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively
secure MPC without setup. In: 27th International Conference on the Theory and
Application of Cryptology and Information Security. Vol 13091. Springer Nature;
2021:335-364. doi:10.1007/978-3-030-92075-3_12'
apa: 'Chakraborty, S., Ganesh, C., Pancholi, M., & Sarkar, P. (2021). Reverse
firewalls for adaptively secure MPC without setup. In 27th International Conference
on the Theory and Application of Cryptology and Information Security (Vol.
13091, pp. 335–364). Virtual, Singapore: Springer Nature. https://doi.org/10.1007/978-3-030-92075-3_12'
chicago: Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar.
“Reverse Firewalls for Adaptively Secure MPC without Setup.” In 27th International
Conference on the Theory and Application of Cryptology and Information Security,
13091:335–64. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-92075-3_12.
ieee: S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls
for adaptively secure MPC without setup,” in 27th International Conference
on the Theory and Application of Cryptology and Information Security, Virtual,
Singapore, 2021, vol. 13091, pp. 335–364.
ista: 'Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for
adaptively secure MPC without setup. 27th International Conference on the Theory
and Application of Cryptology and Information Security. ASIACRYPT: International
Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364.'
mla: Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC
without Setup.” 27th International Conference on the Theory and Application
of Cryptology and Information Security, vol. 13091, Springer Nature, 2021,
pp. 335–64, doi:10.1007/978-3-030-92075-3_12.
short: S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International
Conference on the Theory and Application of Cryptology and Information Security,
Springer Nature, 2021, pp. 335–364.
conference:
end_date: 2021-12-10
location: Virtual, Singapore
name: 'ASIACRYPT: International Conference on Cryptology in Asia'
start_date: 2021-12-06
date_created: 2022-01-09T23:01:27Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2025-04-14T07:22:06Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-030-92075-3_12
ec_funded: 1
external_id:
isi:
- '000927876200012'
intvolume: ' 13091'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1262
month: '12'
oa: 1
oa_version: Preprint
page: 335-364
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 27th International Conference on the Theory and Application of Cryptology
and Information Security
publication_identifier:
eisbn:
- 978-3-030-92075-3
eissn:
- 1611-3349
isbn:
- 978-3-030-92074-6
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reverse firewalls for adaptively secure MPC without setup
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13091
year: '2021'
...
---
_id: '9466'
abstract:
- lang: eng
text: In this work, we apply the dynamical systems analysis of Hanrot et al. (CRYPTO’11)
to a class of lattice block reduction algorithms that includes (natural variants
of) slide reduction and block-Rankin reduction. This implies sharper bounds on
the polynomial running times (in the query model) for these algorithms and opens
the door to faster practical variants of slide reduction. We give heuristic arguments
showing that such variants can indeed speed up slide reduction significantly in
practice. This is confirmed by experimental evidence, which also shows that our
variants are competitive with state-of-the-art reduction algorithms.
acknowledgement: 'This work was initiated in discussions with Léo Ducas, when the
author was visiting the Simons Institute for the Theory of Computation during the
program “Lattices: Algorithms, Complexity, and Cryptography”. We thank Thomas Espitau
for pointing out a bug in a proof in an earlier version of this manuscript.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. The convergence of slide-type reductions. In: Public-Key Cryptography
– PKC 2021. Vol 12710. Springer Nature; 2021:45-67. doi:10.1007/978-3-030-75245-3_3'
apa: 'Walter, M. (2021). The convergence of slide-type reductions. In Public-Key
Cryptography – PKC 2021 (Vol. 12710, pp. 45–67). Virtual: Springer Nature.
https://doi.org/10.1007/978-3-030-75245-3_3'
chicago: Walter, Michael. “The Convergence of Slide-Type Reductions.” In Public-Key
Cryptography – PKC 2021, 12710:45–67. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75245-3_3.
ieee: M. Walter, “The convergence of slide-type reductions,” in Public-Key Cryptography
– PKC 2021, Virtual, 2021, vol. 12710, pp. 45–67.
ista: 'Walter M. 2021. The convergence of slide-type reductions. Public-Key Cryptography
– PKC 2021. PKC: IACR International Conference on Practice and Theory of Public
Key Cryptography, LNCS, vol. 12710, 45–67.'
mla: Walter, Michael. “The Convergence of Slide-Type Reductions.” Public-Key
Cryptography – PKC 2021, vol. 12710, Springer Nature, 2021, pp. 45–67, doi:10.1007/978-3-030-75245-3_3.
short: M. Walter, in:, Public-Key Cryptography – PKC 2021, Springer Nature, 2021,
pp. 45–67.
conference:
end_date: 2021-05-13
location: Virtual
name: 'PKC: IACR International Conference on Practice and Theory of Public Key Cryptography'
start_date: 2021-05-10
corr_author: '1'
date_created: 2021-06-06T22:01:29Z
date_published: 2021-05-01T00:00:00Z
date_updated: 2026-04-16T09:25:35Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/978-3-030-75245-3_3
ec_funded: 1
external_id:
isi:
- '001294728500003'
file:
- access_level: open_access
checksum: 413e564d645ed93d7318672361d9d470
content_type: application/pdf
creator: dernst
date_created: 2022-05-27T09:48:31Z
date_updated: 2022-05-27T09:48:31Z
file_id: '11416'
file_name: 2021_PKC_Walter.pdf
file_size: 489017
relation: main_file
success: 1
file_date_updated: 2022-05-27T09:48:31Z
has_accepted_license: '1'
intvolume: ' 12710'
isi: 1
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: 45-67
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Public-Key Cryptography – PKC 2021
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030752446'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: The convergence of slide-type reductions
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12710
year: '2021'
...
---
_id: '9825'
abstract:
- lang: eng
text: "The dual attack has long been considered a relevant attack on lattice-based
cryptographic schemes relying on the hardness of learning with errors (LWE) and
its structured variants. As solving LWE corresponds to finding a nearest point
on a lattice, one may naturally wonder how efficient this dual approach is for
solving more general closest vector problems, such as the classical closest vector
problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP,
and preprocessing versions of these problems. While primal, sieving-based solutions
to these problems (with preprocessing) were recently studied in a series of works
on approximate Voronoi cells [Laa16b, DLdW19, Laa20, DLvW20], for the dual attack
no such overview exists, especially for problems with preprocessing. With one
of the take-away messages of the approximate Voronoi cell line of work being that
primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one
may further wonder if the dual attack suffers the same drawbacks, or if it is
perhaps a better solution when trying to solve BDD(P).\r\n\r\nIn this work we
provide an overview of cost estimates for dual algorithms for solving these “classical”
closest lattice vector problems. Heuristically we expect to solve the search version
of average-case CVPP in time and space 20.293\U0001D451+\U0001D45C(\U0001D451)
\ in the single-target model. The distinguishing version of average-case CVPP,
where we wish to distinguish between random targets and targets planted at distance
(say) 0.99⋅\U0001D454\U0001D451 from the lattice, has the same complexity in
the single-target model, but can be solved in time and space 20.195\U0001D451+\U0001D45C(\U0001D451)
\ in the multi-target setting, when given a large number of targets from either
target distribution. This suggests an inequivalence between distinguishing and
searching, as we do not expect a similar improvement in the multi-target setting
to hold for search-CVPP. We analyze three slightly different decoders, both for
distinguishing and searching, and experimentally obtain concrete cost estimates
for the dual attack in dimensions 50 to 80, which confirm our heuristic assumptions,
and show that the hidden order terms in the asymptotic estimates are quite small.\r\n\r\nOur
main take-away message is that the dual attack appears to mirror the approximate
Voronoi cell line of work – whereas using approximate Voronoi cells works well
for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales
well for BDD(P) instances but performs poorly on approximate CVP(P)."
acknowledgement: The authors thank Sauvik Bhattacharya, L´eo Ducas, Rachel Player,
and Christine van Vredendaal for early discussions on this topic and on preliminary
results. The authors further thank the reviewers of CT-RSA 2021 for their valuable
feedback.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thijs
full_name: Laarhoven, Thijs
last_name: Laarhoven
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Laarhoven T, Walter M. Dual lattice attacks for closest vector problems (with
preprocessing). In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer
Nature; 2021:478-502. doi:10.1007/978-3-030-75539-3_20'
apa: 'Laarhoven, T., & Walter, M. (2021). Dual lattice attacks for closest vector
problems (with preprocessing). In Topics in Cryptology – CT-RSA 2021 (Vol.
12704, pp. 478–502). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_20'
chicago: Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest
Vector Problems (with Preprocessing).” In Topics in Cryptology – CT-RSA 2021,
12704:478–502. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_20.
ieee: T. Laarhoven and M. Walter, “Dual lattice attacks for closest vector problems
(with preprocessing),” in Topics in Cryptology – CT-RSA 2021, Virtual Event,
2021, vol. 12704, pp. 478–502.
ista: 'Laarhoven T, Walter M. 2021. Dual lattice attacks for closest vector problems
(with preprocessing). Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’
Track at the RSA Conference, LNCS, vol. 12704, 478–502.'
mla: Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector
Problems (with Preprocessing).” Topics in Cryptology – CT-RSA 2021, vol.
12704, Springer Nature, 2021, pp. 478–502, doi:10.1007/978-3-030-75539-3_20.
short: T. Laarhoven, M. Walter, in:, Topics in Cryptology – CT-RSA 2021, Springer
Nature, 2021, pp. 478–502.
conference:
end_date: 2021-05-20
location: Virtual Event
name: 'CT-RSA: Cryptographers’ Track at the RSA Conference'
start_date: 2021-05-17
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2026-04-16T09:28:30Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-75539-3_20
intvolume: ' 12704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/557
month: '05'
oa: 1
oa_version: Preprint
page: 478-502
publication: Topics in Cryptology – CT-RSA 2021
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030755386'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dual lattice attacks for closest vector problems (with preprocessing)
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12704
year: '2021'
...
---
_id: '9826'
abstract:
- lang: eng
text: "Automated contract tracing aims at supporting manual contact tracing during
pandemics by alerting users of encounters with infected people. There are currently
many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized”
ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly
broadcast (using low energy Bluetooth) some values, and at the same time store
(a function of) incoming messages broadcasted by users in their proximity. In
the existing proposals one can trigger false positives on a massive scale by an
“inverse-Sybil” attack, where a large number of devices (malicious users or hacked
phones) pretend to be the same user, such that later, just a single person needs
to be diagnosed (and allowed to upload) to trigger an alert for all users who
were in proximity to any of this large group of devices.\r\n\r\nWe propose the
first protocols that do not succumb to such attacks assuming the devices involved
in the attack do not constantly communicate, which we observe is a necessary assumption.
The high level idea of the protocols is to derive the values to be broadcasted
by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil
attack will not be able to connect their respective chains and thus only one of
them will be able to upload. Our protocols also achieve security against replay,
belated replay, and one of them even against relay attacks."
acknowledgement: Guillermo Pascual-Perez and Michelle Yeo were funded by the European
Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie
Grant Agreement No. 665385; the remaining contributors to this project have received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (682815 - TOCNeT).
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: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- 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: 'Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated
contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer
Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17'
apa: 'Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K.
Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact
tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421).
Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17'
chicago: Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual
Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil
Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021,
12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17.
ieee: B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,”
in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704,
pp. 399–421.
ista: 'Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter
M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in
Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference,
LNCS, vol. 12704, 399–421.'
mla: Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.”
Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021,
pp. 399–421, doi:10.1007/978-3-030-75539-3_17.
short: B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M.
Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021,
pp. 399–421.
conference:
end_date: 2021-05-20
location: Virtual Event
name: 'CT-RSA: Cryptographers’ Track at the RSA Conference'
start_date: 2021-05-17
corr_author: '1'
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2026-04-16T09:28:46Z
day: '11'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-030-75539-3_17
ec_funded: 1
intvolume: ' 12704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/670
month: '05'
oa: 1
oa_version: Submitted Version
page: 399-421
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Topics in Cryptology – CT-RSA 2021
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030755386'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inverse-Sybil attacks in automated contact tracing
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 12704
year: '2021'
...
---
_id: '9969'
abstract:
- lang: eng
text: 'Payment channel networks are a promising approach to improve the scalability
of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion,
along multihop routes in the network, without requiring consensus on the blockchain.
However, during the discovery of cost-efficient routes for the transaction, critical
information may be revealed about the transacting entities. This paper initiates
the study of privacy-preserving route discovery mechanisms for payment channel
networks. In particular, we present LightPIR, an approach which allows a client
to learn the shortest (or cheapest in terms of fees) path between two nodes without
revealing any information about the endpoints of the transaction to the servers.
The two main observations which allow for an efficient solution in LightPIR are
that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess
“street network like” graphs so one can later efficiently compute shortest paths
– also perform well for the graphs underlying payment channel networks, and that
(2) hub labelling algorithms can be conveniently combined with private information
retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing
hub labeling algorithms which leverages the specific topological features of cryptocurrency
networks to further minimize storage and bandwidth overheads. In a case study
considering the Lightning network, we show that our approach is an order of magnitude
more efficient compared to a privacy-preserving baseline based on using private
information retrieval on a database that stores all pairs shortest paths.'
article_processing_charge: No
arxiv: 1
author:
- 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: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route
discovery for payment channel networks. In: IEEE; 2021. doi:10.23919/IFIPNetworking52078.2021.9472205'
apa: 'Pietrzak, K. Z., Salem, I., Schmid, S., & Yeo, M. X. (2021). LightPIR:
Privacy-preserving route discovery for payment channel networks. Presented at
the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland:
IEEE. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205'
chicago: 'Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo.
“LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE,
2021. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205.'
ieee: 'K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving
route discovery for payment channel networks,” presented at the 2021 IFIP Networking
Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.'
ista: 'Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving
route discovery for payment channel networks. 2021 IFIP Networking Conference
(IFIP Networking).'
mla: 'Pietrzak, Krzysztof Z., et al. LightPIR: Privacy-Preserving Route Discovery
for Payment Channel Networks. IEEE, 2021, doi:10.23919/IFIPNetworking52078.2021.9472205.'
short: K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.
conference:
end_date: 2021-06-24
location: Espoo and Helsinki, Finland
name: 2021 IFIP Networking Conference (IFIP Networking)
start_date: 2021-06-21
date_created: 2021-08-29T22:01:16Z
date_published: 2021-06-21T00:00:00Z
date_updated: 2026-04-07T13:29:44Z
day: '21'
department:
- _id: KrPi
doi: 10.23919/IFIPNetworking52078.2021.9472205
ec_funded: 1
external_id:
arxiv:
- '2104.04293'
isi:
- '000853016800008'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.04293
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eisbn:
- 978-3-9031-7639-3
eissn:
- 1861-2288
isbn:
- 978-1-6654-4501-6
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '14506'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'LightPIR: Privacy-preserving route discovery for payment channel networks'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...