---
_id: '14428'
abstract:
- lang: eng
text: "Suppose we have two hash functions h1 and h2, but we trust the security of
only one of them. To mitigate this worry, we wish to build a hash combiner Ch1,h2
which is secure so long as one of the underlying hash functions is. This question
has been well-studied in the regime of collision resistance. In this case, concatenating
the two hash function outputs clearly works. Unfortunately, a long series of works
(Boneh and Boyen, CRYPTO’06; Pietrzak, Eurocrypt’07; Pietrzak, CRYPTO’08) showed
no (noticeably) shorter combiner for collision resistance is possible.\r\nIn this
work, we revisit this pessimistic state of affairs, motivated by the observation
that collision-resistance is insufficient for many interesting applications of
cryptographic hash functions anyway. We argue the right formulation of the “hash
combiner” is to build what we call random oracle (RO) combiners, utilizing stronger
assumptions for stronger constructions.\r\nIndeed, we circumvent the previous
lower bounds for collision resistance by constructing a simple length-preserving
RO combiner C˜h1,h2Z1,Z2(M)=h1(M,Z1)⊕h2(M,Z2),where Z1,Z2\r\n are random salts
of appropriate length. We show that this extra randomness is necessary for RO
combiners, and indeed our construction is somewhat tight with this lower bound.\r\nOn
the negative side, we show that one cannot generically apply the composition theorem
to further replace “monolithic” hash functions h1 and h2 by some simpler indifferentiable
construction (such as the Merkle-Damgård transformation) from smaller components,
such as fixed-length compression functions. Finally, despite this issue, we directly
prove collision resistance of the Merkle-Damgård variant of our combiner, where
h1 and h2 are replaced by iterative Merkle-Damgård hashes applied to a fixed-length
compression function. Thus, we can still subvert the concatenation barrier for
collision-resistance combiners while utilizing practically small fixed-length
components underneath."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Yevgeniy
full_name: Dodis, Yevgeniy
last_name: Dodis
- first_name: Niels
full_name: Ferguson, Niels
last_name: Ferguson
- first_name: Eli
full_name: Goldin, Eli
last_name: Goldin
- first_name: Peter
full_name: Hall, Peter
last_name: Hall
- 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: 'Dodis Y, Ferguson N, Goldin E, Hall P, Pietrzak KZ. Random oracle combiners:
Breaking the concatenation barrier for collision-resistance. In: 43rd Annual
International Cryptology Conference. Vol 14082. Springer Nature; 2023:514-546.
doi:10.1007/978-3-031-38545-2_17'
apa: 'Dodis, Y., Ferguson, N., Goldin, E., Hall, P., & Pietrzak, K. Z. (2023).
Random oracle combiners: Breaking the concatenation barrier for collision-resistance.
In 43rd Annual International Cryptology Conference (Vol. 14082, pp. 514–546).
Santa Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-031-38545-2_17'
chicago: 'Dodis, Yevgeniy, Niels Ferguson, Eli Goldin, Peter Hall, and Krzysztof
Z Pietrzak. “Random Oracle Combiners: Breaking the Concatenation Barrier for Collision-Resistance.”
In 43rd Annual International Cryptology Conference, 14082:514–46. Springer
Nature, 2023. https://doi.org/10.1007/978-3-031-38545-2_17.'
ieee: 'Y. Dodis, N. Ferguson, E. Goldin, P. Hall, and K. Z. Pietrzak, “Random oracle
combiners: Breaking the concatenation barrier for collision-resistance,” in 43rd
Annual International Cryptology Conference, Santa Barbara, CA, United States,
2023, vol. 14082, pp. 514–546.'
ista: 'Dodis Y, Ferguson N, Goldin E, Hall P, Pietrzak KZ. 2023. Random oracle combiners:
Breaking the concatenation barrier for collision-resistance. 43rd Annual International
Cryptology Conference. CRYPTO: Advances in Cryptology, LNCS, vol. 14082, 514–546.'
mla: 'Dodis, Yevgeniy, et al. “Random Oracle Combiners: Breaking the Concatenation
Barrier for Collision-Resistance.” 43rd Annual International Cryptology Conference,
vol. 14082, Springer Nature, 2023, pp. 514–46, doi:10.1007/978-3-031-38545-2_17.'
short: Y. Dodis, N. Ferguson, E. Goldin, P. Hall, K.Z. Pietrzak, in:, 43rd Annual
International Cryptology Conference, Springer Nature, 2023, pp. 514–546.
conference:
end_date: 2023-08-24
location: Santa Barbara, CA, United States
name: 'CRYPTO: Advances in Cryptology'
start_date: 2023-08-20
date_created: 2023-10-15T22:01:11Z
date_published: 2023-08-09T00:00:00Z
date_updated: 2023-10-16T08:02:11Z
day: '09'
department:
- _id: KrPi
doi: 10.1007/978-3-031-38545-2_17
intvolume: ' 14082'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1041
month: '08'
oa: 1
oa_version: Preprint
page: 514-546
publication: 43rd Annual International Cryptology Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031385445'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Random oracle combiners: Breaking the concatenation barrier for collision-resistance'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14082
year: '2023'
...
---
_id: '14691'
abstract:
- lang: eng
text: "Continuous Group-Key Agreement (CGKA) allows a group of users to maintain
a shared key. It is the fundamental cryptographic primitive underlying group messaging
schemes and related protocols, most notably TreeKEM, the underlying key agreement
protocol of the Messaging Layer Security (MLS) protocol, a standard for group
messaging by the IETF. CKGA works in an asynchronous setting where parties only
occasionally must come online, and their messages are relayed by an untrusted
server. The most expensive operation provided by CKGA is that which allows for
a user to refresh their key material in order to achieve forward secrecy (old
messages are secure when a user is compromised) and post-compromise security (users
can heal from compromise). One caveat of early CGKA protocols is that these update
operations had to be performed sequentially, with any user wanting to update their
key material having had to receive and process all previous updates. Late versions
of TreeKEM do allow for concurrent updates at the cost of a communication overhead
per update message that is linear in the number of updating parties. This was
shown to be indeed necessary when achieving PCS in just two rounds of communication
by [Bienstock et al. TCC’20].\r\nThe recently proposed protocol CoCoA [Alwen et
al. Eurocrypt’22], however, shows that this overhead can be reduced if PCS requirements
are relaxed, and only a logarithmic number of rounds is required. The natural
question, thus, is whether CoCoA is optimal in this setting.\r\nIn this work we
answer this question, providing a lower bound on the cost (concretely, the amount
of data to be uploaded to the server) for CGKA protocols that heal in an arbitrary
k number of rounds, that shows that CoCoA is very close to optimal. Additionally,
we extend CoCoA to heal in an arbitrary number of rounds, and propose a modification
of it, with a reduced communication cost for certain k.\r\nWe prove our bound
in a combinatorial setting where the state of the protocol progresses in rounds,
and the state of the protocol in each round is captured by a set system, each
set specifying a set of users who share a secret key. We show this combinatorial
model is equivalent to a symbolic model capturing building blocks including PRFs
and public-key encryption, related to the one used by Bienstock et al.\r\nOur
lower bound is of order k•n1+1/(k-1)/log(k), where 2≤k≤log(n) is the number of
updates per user the protocol requires to heal. This generalizes the n2 bound
for k=2 from Bienstock et al.. This bound almost matches the k⋅n1+2/(k-1) or k2⋅n1+1/(k-1)
efficiency we get for the variants of the CoCoA protocol also introduced in this
paper."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. On the cost of post-compromise
security in concurrent Continuous Group-Key Agreement. In: 21st International
Conference on Theory of Cryptography. Vol 14371. Springer Nature; 2023:271-300.
doi:10.1007/978-3-031-48621-0_10'
apa: 'Auerbach, B., Cueto Noval, M., Pascual Perez, G., & Pietrzak, K. Z. (2023).
On the cost of post-compromise security in concurrent Continuous Group-Key Agreement.
In 21st International Conference on Theory of Cryptography (Vol. 14371,
pp. 271–300). Taipei, Taiwan: Springer Nature. https://doi.org/10.1007/978-3-031-48621-0_10'
chicago: Auerbach, Benedikt, Miguel Cueto Noval, Guillermo Pascual Perez, and Krzysztof
Z Pietrzak. “On the Cost of Post-Compromise Security in Concurrent Continuous
Group-Key Agreement.” In 21st International Conference on Theory of Cryptography,
14371:271–300. Springer Nature, 2023. https://doi.org/10.1007/978-3-031-48621-0_10.
ieee: B. Auerbach, M. Cueto Noval, G. Pascual Perez, and K. Z. Pietrzak, “On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement,” in
21st International Conference on Theory of Cryptography, Taipei, Taiwan,
2023, vol. 14371, pp. 271–300.
ista: 'Auerbach B, Cueto Noval M, Pascual Perez G, Pietrzak KZ. 2023. On the cost
of post-compromise security in concurrent Continuous Group-Key Agreement. 21st
International Conference on Theory of Cryptography. TCC: Theory of Cryptography,
LNCS, vol. 14371, 271–300.'
mla: Auerbach, Benedikt, et al. “On the Cost of Post-Compromise Security in Concurrent
Continuous Group-Key Agreement.” 21st International Conference on Theory of
Cryptography, vol. 14371, Springer Nature, 2023, pp. 271–300, doi:10.1007/978-3-031-48621-0_10.
short: B. Auerbach, M. Cueto Noval, G. Pascual Perez, K.Z. Pietrzak, in:, 21st International
Conference on Theory of Cryptography, Springer Nature, 2023, pp. 271–300.
conference:
end_date: 2023-12-02
location: Taipei, Taiwan
name: 'TCC: Theory of Cryptography'
start_date: 2023-11-29
date_created: 2023-12-17T23:00:53Z
date_published: 2023-11-27T00:00:00Z
date_updated: 2023-12-18T08:36:51Z
day: '27'
department:
- _id: KrPi
doi: 10.1007/978-3-031-48621-0_10
intvolume: ' 14371'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/1123
month: '11'
oa: 1
oa_version: Preprint
page: 271-300
publication: 21st International Conference on Theory of Cryptography
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031486203'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the cost of post-compromise security in concurrent Continuous Group-Key
Agreement
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 14371
year: '2023'
...
---
_id: '13143'
abstract:
- lang: eng
text: "GIMPS and PrimeGrid are large-scale distributed projects dedicated to searching
giant prime numbers, usually of special forms like Mersenne and Proth primes.
The numbers in the current search-space are millions of digits large and the participating
volunteers need to run resource-consuming primality tests. Once a candidate prime
N has been found, the only way for another party to independently verify the primality
of N used to be by repeating the expensive primality test. To avoid the need for
second recomputation of each primality test, these projects have recently adopted
certifying mechanisms that enable efficient verification of performed tests. However,
the mechanisms presently in place only detect benign errors and there is no guarantee
against adversarial behavior: a malicious volunteer can mislead the project to
reject a giant prime as being non-prime.\r\nIn this paper, we propose a practical,
cryptographically-sound mechanism for certifying the non-primality of Proth numbers.
That is, a volunteer can – parallel to running the primality test for N – generate
an efficiently verifiable proof at a little extra cost certifying that N is not
prime. The interactive protocol has statistical soundness and can be made non-interactive
using the Fiat-Shamir heuristic.\r\nOur approach is based on a cryptographic primitive
called Proof of Exponentiation (PoE) which, for a group G, certifies that a tuple
(x,y,T)∈G2×N satisfies x2T=y (Pietrzak, ITCS 2019 and Wesolowski, J. Cryptol.
2020). In particular, we show how to adapt Pietrzak’s PoE at a moderate additional
cost to make it a cryptographically-sound certificate of non-primality."
acknowledgement: 'We are grateful to Pavel Atnashev for clarifying via e-mail several
aspects of the primality tests implementated in the PrimeGrid project. Pavel Hubáček
is supported by the Czech Academy of Sciences (RVO 67985840), the Grant Agency of
the Czech Republic under the grant agreement no. 19-27871X, and by the Charles University
project UNCE/SCI/004. Chethan Kamath is supported by Azrieli International Postdoctoral
Fellowship, ISF grants 484/18 and 1789/19, and ERC StG project SPP: Secrecy Preserving
Proofs.'
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- 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, Pietrzak KZ. Certifying giant nonprimes.
In: Public-Key Cryptography - PKC 2023. Vol 13940. Springer Nature; 2023:530-553.
doi:10.1007/978-3-031-31368-4_19'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., & Pietrzak, K. Z. (2023). Certifying
giant nonprimes. In Public-Key Cryptography - PKC 2023 (Vol. 13940, pp.
530–553). Atlanta, GA, United States: Springer Nature. https://doi.org/10.1007/978-3-031-31368-4_19'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, and Krzysztof Z Pietrzak.
“Certifying Giant Nonprimes.” In Public-Key Cryptography - PKC 2023, 13940:530–53.
Springer Nature, 2023. https://doi.org/10.1007/978-3-031-31368-4_19.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, and K. Z. Pietrzak, “Certifying giant
nonprimes,” in Public-Key Cryptography - PKC 2023, Atlanta, GA, United
States, 2023, vol. 13940, pp. 530–553.
ista: 'Hoffmann C, Hubáček P, Kamath C, Pietrzak KZ. 2023. Certifying giant nonprimes.
Public-Key Cryptography - PKC 2023. PKC: Public-Key Cryptography, LNCS, vol. 13940,
530–553.'
mla: Hoffmann, Charlotte, et al. “Certifying Giant Nonprimes.” Public-Key Cryptography
- PKC 2023, vol. 13940, Springer Nature, 2023, pp. 530–53, doi:10.1007/978-3-031-31368-4_19.
short: C. Hoffmann, P. Hubáček, C. Kamath, K.Z. Pietrzak, in:, Public-Key Cryptography
- PKC 2023, Springer Nature, 2023, pp. 530–553.
conference:
end_date: 2023-05-10
location: Atlanta, GA, United States
name: 'PKC: Public-Key Cryptography'
start_date: 2023-05-07
date_created: 2023-06-18T22:00:47Z
date_published: 2023-05-02T00:00:00Z
date_updated: 2023-06-19T08:03:37Z
day: '02'
department:
- _id: KrPi
doi: 10.1007/978-3-031-31368-4_19
intvolume: ' 13940'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2023/238
month: '05'
oa: 1
oa_version: Submitted Version
page: 530-553
publication: Public-Key Cryptography - PKC 2023
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783031313677'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Certifying giant nonprimes
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13940
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
- 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
- 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: Annual International Conference on the
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: Annual International Conference on the Theory and Applications
of Cryptology and Information Security'
start_date: 2022-05-30
date_created: 2022-06-30T16:48:00Z
date_published: 2022-05-25T00:00:00Z
date_updated: 2023-08-03T07:25:02Z
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'
scopus_import: '1'
status: public
title: 'CoCoA: Concurrent continuous group key agreement'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
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
citation:
ama: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. Hide &
Seek: Privacy-preserving rebalancing on payment channel networks. In: Financial
Cryptography and Data Security. Vol 13411. Springer Nature; 2022:358-373.
doi:10.1007/978-3-031-18283-9_17'
apa: 'Avarikioti, G., Pietrzak, K. Z., Salem, I., Schmid, S., Tiwari, S., &
Yeo, M. X. (2022). Hide & Seek: Privacy-preserving rebalancing on payment
channel networks. In Financial Cryptography and Data Security (Vol. 13411,
pp. 358–373). Grenada: Springer Nature. https://doi.org/10.1007/978-3-031-18283-9_17'
chicago: 'Avarikioti, Georgia, Krzysztof Z Pietrzak, Iosif Salem, Stefan Schmid,
Samarth Tiwari, and Michelle X Yeo. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” In Financial Cryptography and Data Security,
13411:358–73. Springer Nature, 2022. https://doi.org/10.1007/978-3-031-18283-9_17.'
ieee: 'G. Avarikioti, K. Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, and M. X.
Yeo, “Hide & Seek: Privacy-preserving rebalancing on payment channel networks,”
in Financial Cryptography and Data Security, Grenada, 2022, vol. 13411,
pp. 358–373.'
ista: 'Avarikioti G, Pietrzak KZ, Salem I, Schmid S, Tiwari S, Yeo MX. 2022. Hide
& Seek: Privacy-preserving rebalancing on payment channel networks. Financial
Cryptography and Data Security. FC: Financial Cryptography and Data Security,
LNCS, vol. 13411, 358–373.'
mla: 'Avarikioti, Georgia, et al. “Hide & Seek: Privacy-Preserving Rebalancing
on Payment Channel Networks.” Financial Cryptography and Data Security,
vol. 13411, Springer Nature, 2022, pp. 358–73, doi:10.1007/978-3-031-18283-9_17.'
short: G. Avarikioti, K.Z. Pietrzak, I. Salem, S. Schmid, S. Tiwari, M.X. Yeo, in:,
Financial Cryptography and Data Security, Springer Nature, 2022, pp. 358–373.
conference:
end_date: 2022-05-06
location: Grenada
name: 'FC: Financial Cryptography and Data Security'
start_date: 2022-05-02
date_created: 2023-01-12T12:10:38Z
date_published: 2022-10-22T00:00:00Z
date_updated: 2023-09-05T15:10:57Z
day: '22'
department:
- _id: KrPi
doi: 10.1007/978-3-031-18283-9_17
external_id:
arxiv:
- '2110.08848'
intvolume: ' 13411'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2110.08848
month: '10'
oa: 1
oa_version: Preprint
page: 358-373
publication: Financial Cryptography and Data Security
publication_identifier:
eisbn:
- '9783031182839'
eissn:
- 1611-3349
isbn:
- '9783031182822'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Hide & Seek: Privacy-preserving rebalancing on payment channel networks'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13411
year: '2022'
...
---
_id: '12176'
abstract:
- lang: eng
text: "A proof of exponentiation (PoE) in a group G of unknown order allows a prover
to convince a verifier that a tuple (x,q,T,y)∈G×N×N×G satisfies xqT=y. This primitive
has recently found exciting applications in the constructions of verifiable delay
functions and succinct arguments of knowledge. The most practical PoEs only achieve
soundness either under computational assumptions, i.e., they are arguments (Wesolowski,
Journal of Cryptology 2020), or in groups that come with the promise of not having
any small subgroups (Pietrzak, ITCS 2019). The only statistically-sound PoE in
general groups of unknown order is due to Block et al. (CRYPTO 2021), and can
be seen as an elaborate parallel repetition of Pietrzak’s PoE: to achieve λ bits
of security, say λ=80, the number of repetitions required (and thus the blow-up
in communication) is as large as λ.\r\n\r\nIn this work, we propose a statistically-sound
PoE for the case where the exponent q is the product of all primes up to some
bound B. We show that, in this case, it suffices to run only λ/log(B) parallel
instances of Pietrzak’s PoE, which reduces the concrete proof-size compared to
Block et al. by an order of magnitude. Furthermore, we show that in the known
applications where PoEs are used as a building block such structured exponents
are viable. Finally, we also discuss batching of our PoE, showing that many proofs
(for the same G and q but different x and T) can be batched by adding only a single
element to the proof per additional statement."
acknowledgement: "We would like to thank the authors of [BHR+21] for clarifying several
questions we had\r\nregarding their results. Pavel Hubá£ek was supported by the
Grant Agency of the Czech\r\nRepublic under the grant agreement no. 19-27871X and
by the Charles University project\r\nUNCE/SCI/004. Chethan Kamath is supported by
Azrieli International Postdoctoral Fellowship\r\nand ISF grants 484/18 and 1789/19.
Karen Klein was supported in part by ERC CoG grant\r\n724307 and conducted part
of this work at Institute of Science and Technology Austria."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Charlotte
full_name: Hoffmann, Charlotte
id: 0f78d746-dc7d-11ea-9b2f-83f92091afe7
last_name: Hoffmann
orcid: 0000-0003-2027-5549
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath, Chethan
last_name: Kamath
- first_name: Karen
full_name: Klein, Karen
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. Practical statistically-sound
proofs of exponentiation in any group. In: Advances in Cryptology – CRYPTO
2022. Vol 13508. Springer Nature; 2022:370-399. doi:10.1007/978-3-031-15979-4_13'
apa: 'Hoffmann, C., Hubáček, P., Kamath, C., Klein, K., & Pietrzak, K. Z. (2022).
Practical statistically-sound proofs of exponentiation in any group. In Advances
in Cryptology – CRYPTO 2022 (Vol. 13508, pp. 370–399). Santa Barbara, CA,
United States: Springer Nature. https://doi.org/10.1007/978-3-031-15979-4_13'
chicago: Hoffmann, Charlotte, Pavel Hubáček, Chethan Kamath, Karen Klein, and Krzysztof
Z Pietrzak. “Practical Statistically-Sound Proofs of Exponentiation in Any Group.”
In Advances in Cryptology – CRYPTO 2022, 13508:370–99. Springer Nature,
2022. https://doi.org/10.1007/978-3-031-15979-4_13.
ieee: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, and K. Z. Pietrzak, “Practical
statistically-sound proofs of exponentiation in any group,” in Advances in
Cryptology – CRYPTO 2022, Santa Barbara, CA, United States, 2022, vol. 13508,
pp. 370–399.
ista: 'Hoffmann C, Hubáček P, Kamath C, Klein K, Pietrzak KZ. 2022. Practical statistically-sound
proofs of exponentiation in any group. Advances in Cryptology – CRYPTO 2022. CRYYPTO:
International Cryptology Conference, LNCS, vol. 13508, 370–399.'
mla: Hoffmann, Charlotte, et al. “Practical Statistically-Sound Proofs of Exponentiation
in Any Group.” Advances in Cryptology – CRYPTO 2022, vol. 13508, Springer
Nature, 2022, pp. 370–99, doi:10.1007/978-3-031-15979-4_13.
short: C. Hoffmann, P. Hubáček, C. Kamath, K. Klein, K.Z. Pietrzak, in:, Advances
in Cryptology – CRYPTO 2022, Springer Nature, 2022, pp. 370–399.
conference:
end_date: 2022-08-18
location: Santa Barbara, CA, United States
name: 'CRYYPTO: International Cryptology Conference'
start_date: 2022-08-15
date_created: 2023-01-12T12:12:07Z
date_published: 2022-10-13T00:00:00Z
date_updated: 2023-09-05T15:12:27Z
day: '13'
department:
- _id: KrPi
doi: 10.1007/978-3-031-15979-4_13
external_id:
isi:
- '000886792700013'
intvolume: ' 13508'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2022/1021
month: '10'
oa: 1
oa_version: Preprint
page: 370-399
publication: Advances in Cryptology – CRYPTO 2022
publication_identifier:
eisbn:
- '9783031159794'
eissn:
- 1611-3349
isbn:
- '9783031159787'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Practical statistically-sound proofs of exponentiation in any group
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 13508
year: '2022'
...
---
_id: '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
- 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: 2023-09-07T13:32:11Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-84245-1_17
ec_funded: 1
intvolume: ' 12826'
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
status: public
title: Limits on the Adaptive Security of Yao’s Garbling
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
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
- 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: 2023-09-07T13:32:11Z
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
- 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: 2023-10-17T09:24:08Z
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
- 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
- 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
- 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
date_created: 2021-09-27T13:46:27Z
date_published: 2021-08-26T00:00:00Z
date_updated: 2023-09-07T13:32:11Z
day: '26'
department:
- _id: KrPi
- _id: DaAl
doi: 10.1109/sp40001.2021.00035
ec_funded: 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: '10035'
relation: dissertation_contains
status: public
status: public
title: 'Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous
group key agreement'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
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
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: 2023-08-14T13:07:46Z
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
- 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: 2023-08-14T13:19:39Z
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'
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: 2023-08-17T06:21:38Z
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: 2023-10-17T09:24:07Z
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: '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
- 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
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
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2023-02-23T14:09:56Z
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:
- '16113349'
isbn:
- '9783030755386'
issn:
- '03029743'
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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
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: 2023-11-30T10:54:50Z
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'
...
---
_id: '8987'
abstract:
- lang: eng
text: "Currently several projects aim at designing and implementing protocols for
privacy preserving automated contact tracing to help fight the current pandemic.
Those proposal are quite similar, and in their most basic form basically propose
an app for mobile phones which broadcasts frequently changing pseudorandom identifiers
via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast
by phones in its proximity. Only if a user is tested positive, they upload either
the beacons they did broadcast (which is the case in decentralized proposals as
DP-3T, east and west coast PACT or Covid watch) or received (as in Popp-PT or
ROBERT) during the last two weeks or so.\r\n\r\nVaudenay [eprint 2020/399] observes
that this basic scheme (he considers the DP-3T proposal) succumbs to relay and
even replay attacks, and proposes more complex interactive schemes which prevent
those attacks without giving up too many privacy aspects. Unfortunately interaction
is problematic for this application for efficiency and security reasons. The countermeasures
that have been suggested so far are either not practical or give up on key privacy
aspects. We propose a simple non-interactive variant of the basic protocol that\r\n(security)
Provably prevents replay and (if location data is available) relay attacks.\r\n(privacy)
The data of all parties (even jointly) reveals no information on the location
or time where encounters happened.\r\n(efficiency) The broadcasted message can
fit into 128 bits and uses only basic crypto (commitments and secret key authentication).\r\n\r\nTowards
this end we introduce the concept of “delayed authentication”, which basically
is a message authentication code where verification can be done in two steps,
where the first doesn’t require the key, and the second doesn’t require the message."
article_processing_charge: No
author:
- 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: 'Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in
private contact tracing. In: Progress in Cryptology. Vol 12578. LNCS. Springer
Nature; 2020:3-15. doi:10.1007/978-3-030-65277-7_1'
apa: 'Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay
attacks in private contact tracing. In Progress in Cryptology (Vol. 12578,
pp. 3–15). Bangalore, India: Springer Nature. https://doi.org/10.1007/978-3-030-65277-7_1'
chicago: 'Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and
Relay Attacks in Private Contact Tracing.” In Progress in Cryptology, 12578:3–15.
LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-65277-7_1.'
ieee: 'K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks
in private contact tracing,” in Progress in Cryptology, Bangalore, India,
2020, vol. 12578, pp. 3–15.'
ista: 'Pietrzak KZ. 2020. Delayed authentication: Preventing replay and relay attacks
in private contact tracing. Progress in Cryptology. INDOCRYPT: International Conference
on Cryptology in IndiaLNCS vol. 12578, 3–15.'
mla: 'Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay
Attacks in Private Contact Tracing.” Progress in Cryptology, vol. 12578,
Springer Nature, 2020, pp. 3–15, doi:10.1007/978-3-030-65277-7_1.'
short: K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.
conference:
end_date: 2020-12-16
location: Bangalore, India
name: 'INDOCRYPT: International Conference on Cryptology in India'
start_date: 2020-12-13
date_created: 2021-01-03T23:01:23Z
date_published: 2020-12-08T00:00:00Z
date_updated: 2023-08-24T11:08:58Z
day: '08'
department:
- _id: KrPi
doi: 10.1007/978-3-030-65277-7_1
ec_funded: 1
external_id:
isi:
- '000927592800001'
intvolume: ' 12578'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/418
month: '12'
oa: 1
oa_version: Preprint
page: 3-15
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030652760'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: 'Delayed authentication: Preventing replay and relay attacks in private contact
tracing'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 12578
year: '2020'
...
---
_id: '6677'
abstract:
- lang: eng
text: "The Fiat-Shamir heuristic transforms a public-coin interactive proof into
a non-interactive argument, by replacing the verifier with a cryptographic hash
function that is applied to the protocol’s transcript. Constructing hash functions
for which this transformation is sound is a central and long-standing open question
in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is
no easier than breaking the soundness of the Fiat-Shamir transformation when applied
to the sumcheck protocol. In particular, if the transformed protocol is sound,
then any hard problem in #P gives rise to a hard distribution in the class CLS,
which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized
games for which it is hard to find a Nash equilibrium, by reducing the inversion
of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution
is a stateful incrementally verifiable procedure that, given a SAT instance over
n variables, counts the number of satisfying assignments. This is accomplished
via an exponential sequence of small steps, each computable in time poly(n). Incremental
verifiability means that each intermediate state includes a sumcheck-based proof
of its correctness, and the proof can be updated and verified in time poly(n)."
article_processing_charge: No
author:
- first_name: Arka Rai
full_name: Choudhuri, Arka Rai
last_name: Choudhuri
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- 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: Alon
full_name: Rosen, Alon
last_name: Rosen
- first_name: Guy N.
full_name: Rothblum, Guy N.
last_name: Rothblum
citation:
ama: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019.
ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400'
apa: 'Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen,
A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than
breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States:
ACM Press. https://doi.org/10.1145/3313276.3316400'
chicago: Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z
Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier
than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400.
ieee: A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen,
and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,”
in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
- STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.
ista: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. STOC:
Symposium on Theory of Computing, 1103–1114.'
mla: Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking
Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.
short: A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N.
Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
Computing - STOC 2019, ACM Press, 2019, pp. 1103–1114.
conference:
end_date: 2019-06-26
location: Phoenix, AZ, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2019-06-23
date_created: 2019-07-24T09:20:53Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:15:55Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/3313276.3316400
ec_funded: 1
external_id:
isi:
- '000523199100100'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/549
month: '06'
oa: 1
oa_version: Preprint
page: 1103-1114
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing -
STOC 2019
publication_identifier:
isbn:
- '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
related_material:
record:
- id: '7896'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '7411'
abstract:
- lang: eng
text: "Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving
a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently
and publicly verifiable. The proof can be computed in T sequential steps, but
not much less, even by a malicious party having large parallelism. A PoSW thus
serves as a proof that T units of time have passed since χ\r\n\r\nwas received.\r\n\r\nPoSW
were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical
construction was only recently proposed by Cohen and Pietrzak [CP18].\r\n\r\nIn
this work we construct a new simple PoSW in the random permutation model which
is almost as simple and efficient as [CP18] but conceptually very different. Whereas
the structure underlying [CP18] is a hash tree, our construction is based on skip
lists and has the interesting property that computing the PoSW is a reversible
computation.\r\nThe fact that the construction is reversible can potentially be
used for new applications like constructing proofs of replication. We also show
how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW
to get a PoSW where one additionally can verify correctness of the output much
more efficiently than recomputing it (though recent constructions of “verifiable
delay functions” subsume most of the applications this construction was aiming
at)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Hamza M
full_name: Abusalah, Hamza M
id: 40297222-F248-11E8-B48F-1D18A9856A87
last_name: Abusalah
- 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: 'Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible
proofs of sequential work. In: Advances in Cryptology – EUROCRYPT 2019.
Vol 11477. Springer International Publishing; 2019:277-291. doi:10.1007/978-3-030-17656-3_10'
apa: 'Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter,
M. (2019). Reversible proofs of sequential work. In Advances in Cryptology
– EUROCRYPT 2019 (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International
Publishing. https://doi.org/10.1007/978-3-030-17656-3_10'
chicago: Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak,
and Michael Walter. “Reversible Proofs of Sequential Work.” In Advances in
Cryptology – EUROCRYPT 2019, 11477:277–91. Springer International Publishing,
2019. https://doi.org/10.1007/978-3-030-17656-3_10.
ieee: H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter,
“Reversible proofs of sequential work,” in Advances in Cryptology – EUROCRYPT
2019, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.
ista: Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible
proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. International
Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
11477, 277–291.
mla: Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” Advances
in Cryptology – EUROCRYPT 2019, vol. 11477, Springer International Publishing,
2019, pp. 277–91, doi:10.1007/978-3-030-17656-3_10.
short: H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:,
Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019,
pp. 277–291.
conference:
end_date: 2019-05-23
location: Darmstadt, Germany
name: International Conference on the Theory and Applications of Cryptographic Techniques
start_date: 2019-05-19
date_created: 2020-01-30T09:26:14Z
date_published: 2019-04-24T00:00:00Z
date_updated: 2023-09-06T15:26:06Z
day: '24'
department:
- _id: KrPi
doi: 10.1007/978-3-030-17656-3_10
ec_funded: 1
external_id:
isi:
- '000483516200010'
intvolume: ' 11477'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/252
month: '04'
oa: 1
oa_version: Submitted Version
page: 277-291
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – EUROCRYPT 2019
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030176556'
- '9783030176563'
issn:
- 0302-9743
publication_status: published
publisher: Springer International Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reversible proofs of sequential work
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11477
year: '2019'
...
---
_id: '6430'
abstract:
- lang: eng
text: "A proxy re-encryption (PRE) scheme is a public-key encryption scheme that
allows the holder of a key pk to derive a re-encryption key for any other key
\U0001D45D\U0001D458′. This re-encryption key lets anyone transform ciphertexts
under pk into ciphertexts under \U0001D45D\U0001D458′ without having to know the
underlying message, while transformations from \U0001D45D\U0001D458′ to pk should
not be possible (unidirectional). Security is defined in a multi-user setting
against an adversary that gets the users’ public keys and can ask for re-encryption
keys and can corrupt users by requesting their secret keys. Any ciphertext that
the adversary cannot trivially decrypt given the obtained secret and re-encryption
keys should be secure.\r\n\r\nAll existing security proofs for PRE only show selective
security, where the adversary must first declare the users it wants to corrupt.
This can be lifted to more meaningful adaptive security by guessing the set of
corrupted users among the n users, which loses a factor exponential in Open image
in new window , rendering the result meaningless already for moderate Open image
in new window .\r\n\r\nJafargholi et al. (CRYPTO’17) proposed a framework that
in some cases allows to give adaptive security proofs for schemes which were previously
only known to be selectively secure, while avoiding the exponential loss that
results from guessing the adaptive choices made by an adversary. We apply their
framework to PREs that satisfy some natural additional properties. Concretely,
we give a more fine-grained reduction for several unidirectional PREs, proving
adaptive security at a much smaller loss. The loss depends on the graph of users
whose edges represent the re-encryption keys queried by the adversary. For trees
and chains the loss is quasi-polynomial in the size and for general graphs it
is exponential in their depth and indegree (instead of their size as for previous
reductions). Fortunately, trees and low-depth graphs cover many, if not most,
interesting applications.\r\n\r\nOur results apply e.g. to the bilinear-map based
PRE schemes by Ateniese et al. (NDSS’05 and CT-RSA’09), Gentry’s FHE-based scheme
(STOC’09) and the LWE-based scheme by Chandran et al. (PKC’14)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- 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: 'Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. Adaptively secure proxy
re-encryption. In: Vol 11443. Springer Nature; 2019:317-346. doi:10.1007/978-3-030-17259-6_11'
apa: 'Fuchsbauer, G., Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2019).
Adaptively secure proxy re-encryption (Vol. 11443, pp. 317–346). Presented at
the PKC: Public-Key Cryptograhy, Beijing, China: Springer Nature. https://doi.org/10.1007/978-3-030-17259-6_11'
chicago: Fuchsbauer, Georg, Chethan Kamath Hosdurg, Karen Klein, and Krzysztof Z
Pietrzak. “Adaptively Secure Proxy Re-Encryption,” 11443:317–46. Springer Nature,
2019. https://doi.org/10.1007/978-3-030-17259-6_11.
ieee: 'G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “Adaptively
secure proxy re-encryption,” presented at the PKC: Public-Key Cryptograhy, Beijing,
China, 2019, vol. 11443, pp. 317–346.'
ista: 'Fuchsbauer G, Kamath Hosdurg C, Klein K, Pietrzak KZ. 2019. Adaptively secure
proxy re-encryption. PKC: Public-Key Cryptograhy, LNCS, vol. 11443, 317–346.'
mla: Fuchsbauer, Georg, et al. Adaptively Secure Proxy Re-Encryption. Vol.
11443, Springer Nature, 2019, pp. 317–46, doi:10.1007/978-3-030-17259-6_11.
short: G. Fuchsbauer, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, Springer
Nature, 2019, pp. 317–346.
conference:
end_date: 2019-04-17
location: Beijing, China
name: 'PKC: Public-Key Cryptograhy'
start_date: 2019-04-14
date_created: 2019-05-13T08:13:46Z
date_published: 2019-04-06T00:00:00Z
date_updated: 2023-09-08T11:33:20Z
day: '06'
department:
- _id: KrPi
doi: 10.1007/978-3-030-17259-6_11
ec_funded: 1
intvolume: ' 11443'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2018/426
month: '04'
oa: 1
oa_version: Preprint
page: 317-346
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030172589'
issn:
- '03029743'
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: Adaptively secure proxy re-encryption
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11443
year: '2019'
...