---
_id: '10409'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a SO(w) loss
in security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the
circuit. The design of the strategy relies on separators, a graph-theoretic notion
with connections to circuit complexity. with only a SO(w) loss in security.
For instance, circuits with constant treewidth are as a result adaptively indistinguishable
with only a polynomial loss. This (partially) complements a negative result of
Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that
Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions,
we introduce a new pebble game that abstracts out our security reduction and then
present a pebbling strategy for this game where the number of pebbles used is
roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the
strategy relies on separators, a graph-theoretic notion with connections to circuit
complexity.
acknowledgement: We are grateful to Daniel Wichs for helpful discussions on the landscape
of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021
and TCC 2021 reviewers for their detailed review and suggestions, which helped improve
presentation considerably.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th International Conference. Vol 13043. Springer Nature;
2021:486-517. doi:10.1007/978-3-030-90453-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th International Conference (Vol. 13043,
pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th International Conference, 13043:486–517.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th International Conference, Raleigh, NC, United
States, 2021, vol. 13043, pp. 486–517.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS,
vol. 13043, 486–517.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517,
doi:10.1007/978-3-030-90453-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference,
Springer Nature, 2021, pp. 486–517.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-15T08:32:06Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_17
ec_funded: 1
external_id:
isi:
- '000728364000017'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '11'
oa: 1
oa_version: Preprint
page: 486-517
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10044'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On treewidth, separators and Yao’s garbling
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: '13043 '
year: '2021'
...
---
_id: '10410'
abstract:
- lang: eng
text: The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical framework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower bounds that
almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and broadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.
acknowledgement: C. Kamath—Supported by Azrieli International Postdoctoral Fellowship.
Most of the work was done while the author was at Northeastern University and Charles
University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9,
respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work
was done while the author was at IST Austria funded by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th International Conference. Vol 13043.
Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th International Conference
(Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th International
Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th International Conference, Raleigh,
NC, United States, 2021, vol. 13043, pp. 550–581.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th International Conference. TCC: Theory of Cryptography,
LNCS, vol. 13043, 550–581.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021,
pp. 550–81, doi:10.1007/978-3-030-90453-1_19.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International
Conference, Springer Nature, 2021, pp. 550–581.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2025-04-14T07:22:05Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_19
ec_funded: 1
external_id:
isi:
- '000728364000019'
intvolume: ' 13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '11'
oa: 1
oa_version: Preprint
page: 550-581
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10048'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...
---
_id: '10041'
abstract:
- lang: eng
text: Yao’s garbling scheme is one of the most fundamental cryptographic constructions.
Lindell and Pinkas (Journal of Cryptograhy 2009) gave a formal proof of security
in the selective setting where the adversary chooses the challenge inputs before
seeing the garbled circuit assuming secure symmetric-key encryption (and hence
one-way functions). This was followed by results, both positive and negative,
concerning its security in the, stronger, adaptive setting. Applebaum et al. (Crypto
2013) showed that it cannot satisfy adaptive security as is, due to a simple incompressibility
argument. Jafargholi and Wichs (TCC 2017) considered a natural adaptation of Yao’s
scheme (where the output mapping is sent in the online phase, together with the
garbled input) that circumvents this negative result, and proved that it is adaptively
secure, at least for shallow circuits. In particular, they showed that for the
class of circuits of depth δ , the loss in security is at most exponential in δ
. The above results all concern the simulation-based notion of security. In this
work, we show that the upper bound of Jafargholi and Wichs is basically optimal
in a strong sense. As our main result, we show that there exists a family of Boolean
circuits, one for each depth δ∈N , such that any black-box reduction proving
the adaptive indistinguishability of the natural adaptation of Yao’s scheme from
any symmetric-key encryption has to lose a factor that is exponential in δ√
. Since indistinguishability is a weaker notion than simulation, our bound also
applies to adaptive simulation. To establish our results, we build on the recent
approach of Kamath et al. (Eprint 2021), which uses pebbling lower bounds in conjunction
with oracle separations to prove fine-grained lower bounds on loss in cryptographic
security.
acknowledgement: We would like to thank the anonymous reviewers of Crypto’21 whose
detailed comments helped us considerably improve the presentation of the paper.
alternative_title:
- LCNS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. Limits on the Adaptive Security
of Yao’s Garbling. In: 41st Annual International Cryptology Conference, Part
II . Vol 12826. Cham: Springer Nature; 2021:486-515. doi:10.1007/978-3-030-84245-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Wichs, D. (2021). Limits
on the Adaptive Security of Yao’s Garbling. In 41st Annual International Cryptology
Conference, Part II (Vol. 12826, pp. 486–515). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-84245-1_17'
chicago: 'Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Daniel
Wichs. “Limits on the Adaptive Security of Yao’s Garbling.” In 41st Annual
International Cryptology Conference, Part II , 12826:486–515. Cham: Springer
Nature, 2021. https://doi.org/10.1007/978-3-030-84245-1_17.'
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and D. Wichs, “Limits on the
Adaptive Security of Yao’s Garbling,” in 41st Annual International Cryptology
Conference, Part II , Virtual, 2021, vol. 12826, pp. 486–515.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Wichs D. 2021. Limits on the Adaptive
Security of Yao’s Garbling. 41st Annual International Cryptology Conference, Part
II . CRYPTO: Annual International Cryptology Conference, LCNS, vol. 12826, 486–515.'
mla: Kamath Hosdurg, Chethan, et al. “Limits on the Adaptive Security of Yao’s Garbling.”
41st Annual International Cryptology Conference, Part II , vol. 12826,
Springer Nature, 2021, pp. 486–515, doi:10.1007/978-3-030-84245-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, D. Wichs, in:, 41st Annual International
Cryptology Conference, Part II , Springer Nature, Cham, 2021, pp. 486–515.
conference:
end_date: 2021-08-20
location: Virtual
name: 'CRYPTO: Annual International Cryptology Conference'
start_date: 2021-08-16
date_created: 2021-09-23T14:06:15Z
date_published: 2021-08-11T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-84245-1_17
ec_funded: 1
external_id:
isi:
- '000696697800017'
intvolume: ' 12826'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/945
month: '08'
oa: 1
oa_version: Preprint
page: 486-515
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '41st Annual International Cryptology Conference, Part II '
publication_identifier:
eisbn:
- 978-3-030-84245-1
eissn:
- 1611-3349
isbn:
- 978-3-030-84244-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Limits on the Adaptive Security of Yao’s Garbling
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 12826
year: '2021'
...
---
_id: '10049'
abstract:
- lang: eng
text: While messaging systems with strong security guarantees are widely used in
practice, designing a protocol that scales efficiently to large groups and enjoys
similar security guarantees remains largely open. The two existing proposals to
date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer
Security Protocol, draft). TreeKEM is the currently considered candidate by the
IETF MLS working group, but dynamic group operations (i.e. adding and removing
users) can cause efficiency issues. In this paper we formalize and analyze a variant
of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying
TTKEM was suggested by Millican (MLS mailing list, February 2018). This version
is more efficient than TreeKEM for some natural distributions of group operations,
we quantify this through simulations.Our second contribution is two security proofs
for TTKEM which establish post compromise and forward secrecy even against adaptive
attackers. The security loss (to the underlying PKE) in the Random Oracle Model
is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs
can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like
protocol establishing tight security against an adversary who can adaptively choose
the sequence of operations was known. We also are the first to prove (or even
formalize) active security where the server can arbitrarily deviate from the protocol
specification. Proving fully active security – where also the users can arbitrarily
deviate – remains open.
acknowledgement: The first three authors contributed equally to this work. Funded
by the European Research Council (ERC) under the European Union’s Horizon2020 research
and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No.665385.
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Margarita
full_name: Capretto, Margarita
last_name: Capretto
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
orcid: 0000-0002-2505-4246
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. In: 2021 IEEE
Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035'
apa: 'Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M.,
Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively
and actively secure continuous group key agreement. In 2021 IEEE Symposium
on Security and Privacy (pp. 268–284). San Francisco, CA, United States:
IEEE. https://doi.org/10.1109/sp40001.2021.00035'
chicago: 'Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath
Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo,
Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively
and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium
on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.'
ieee: 'K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively
secure continuous group key agreement,” in 2021 IEEE Symposium on Security
and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.'
ista: 'Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval
M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium
on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.'
mla: 'Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively
Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and
Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.'
short: K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M.
Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium
on Security and Privacy , IEEE, 2021, pp. 268–284.
conference:
end_date: 2021-05-27
location: San Francisco, CA, United States
name: 'SP: Symposium on Security and Privacy'
start_date: 2021-05-24
corr_author: '1'
date_created: 2021-09-27T13:46:27Z
date_published: 2021-08-26T00:00:00Z
date_updated: 2026-04-08T07:01:44Z
day: '26'
department:
- _id: KrPi
- _id: DaAl
doi: 10.1109/sp40001.2021.00035
ec_funded: 1
external_id:
isi:
- '001316065000016'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1489
month: '08'
oa: 1
oa_version: Preprint
page: 268-284
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '2021 IEEE Symposium on Security and Privacy '
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '18088'
relation: dissertation_contains
status: public
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous
group key agreement'
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
year: '2021'
...
---
_id: '10048'
abstract:
- lang: eng
text: "The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower\r\nbounds
that almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and\r\nbroadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.\r\n"
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th Theory of Cryptography
Conference 2021. Raleigh, NC, United States: International Association for
Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory
of Cryptography Conference 2021. International Association for Cryptologic
Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th Theory of Cryptography Conference 2021,
Raleigh, NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC:
Theory of Cryptography Conference.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th Theory of Cryptography Conference 2021, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of
Cryptography Conference 2021, International Association for Cryptologic Research,
2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-09-27T12:52:05Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '08'
department:
- _id: KrPi
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '07'
oa: 1
oa_version: Preprint
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10410'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10044'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a S^O(w) loss in
security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(d w log(S)), d being the fan-out of the circuit.
The design of the strategy relies on separators, a graph-theoretic notion with
connections to circuit complexity.
acknowledgement: 'We would like to thank Daniel Wichs for helpful discussions on the
landscape of adaptive security of Yao’s garbling. '
article_number: 2021/926
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th Theory of Cryptography Conference 2021. International
Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th Theory of Cryptography Conference 2021.
Raleigh, NC, United States: International Association for Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th Theory of Cryptography Conference 2021, Raleigh,
NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th Theory of Cryptography Conference 2021. TCC: Theory of Cryptography
Conference, 2021/926.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th Theory of Cryptography Conference 2021, 2021/926, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th Theory of Cryptography
Conference 2021, International Association for Cryptologic Research, 2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-09-24T12:01:34Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2026-04-08T07:01:43Z
day: '08'
department:
- _id: KrPi
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '07'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10409'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: On treewidth, separators and Yao's garbling
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
OA_place: publisher
_id: '7896'
abstract:
- lang: eng
text: "A search problem lies in the complexity class FNP if a solution to the given
instance of the problem can be verified efficiently. The complexity class TFNP
consists of all search problems in FNP that are total in the sense that a solution
is guaranteed to exist. TFNP contains a host of interesting problems from fields
such as algorithmic game theory, computational topology, number theory and combinatorics.
Since TFNP is a semantic class, it is unlikely to have a complete problem. Instead,
one studies its syntactic subclasses which are defined based on the combinatorial
principle used to argue totality. Of particular interest is the subclass PPAD,
which contains important problems\r\nlike computing Nash equilibrium for bimatrix
games and computational counterparts of several fixed-point theorems as complete.
In the thesis, we undertake the study of averagecase hardness of TFNP, and in
particular its subclass PPAD.\r\nAlmost nothing was known about average-case hardness
of PPAD before a series of recent results showed how to achieve it using a cryptographic
primitive called program obfuscation.\r\nHowever, it is currently not known how
to construct program obfuscation from standard cryptographic assumptions. Therefore,
it is desirable to relax the assumption under which average-case hardness of PPAD
can be shown. In the thesis we take a step in this direction. First, we show that
assuming the (average-case) hardness of a numbertheoretic\r\nproblem related to
factoring of integers, which we call Iterated-Squaring, PPAD is hard-on-average
in the random-oracle model. Then we strengthen this result to show that the average-case
hardness of PPAD reduces to the (adaptive) soundness of the Fiat-Shamir Transform,
a well-known technique used to compile a public-coin interactive protocol into
a non-interactive one. As a corollary, we obtain average-case hardness for PPAD
in the random-oracle model assuming the worst-case hardness of #SAT. Moreover,
the above results can all be strengthened to obtain average-case hardness for
the class CLS ⊆ PPAD.\r\nOur main technical contribution is constructing incrementally-verifiable
procedures for computing Iterated-Squaring and #SAT. By incrementally-verifiable,
we mean that every intermediate state of the computation includes a proof of its
correctness, and the proof can be updated and verified in polynomial time. Previous
constructions of such procedures relied on strong, non-standard assumptions. Instead,
we introduce a technique called recursive proof-merging to obtain the same from
weaker assumptions. "
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
citation:
ama: Kamath Hosdurg C. On the average-case hardness of total search problems. 2020.
doi:10.15479/AT:ISTA:7896
apa: Kamath Hosdurg, C. (2020). On the average-case hardness of total search
problems. Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:7896
chicago: Kamath Hosdurg, Chethan. “On the Average-Case Hardness of Total Search
Problems.” Institute of Science and Technology Austria, 2020. https://doi.org/10.15479/AT:ISTA:7896.
ieee: C. Kamath Hosdurg, “On the average-case hardness of total search problems,”
Institute of Science and Technology Austria, 2020.
ista: Kamath Hosdurg C. 2020. On the average-case hardness of total search problems.
Institute of Science and Technology Austria.
mla: Kamath Hosdurg, Chethan. On the Average-Case Hardness of Total Search Problems.
Institute of Science and Technology Austria, 2020, doi:10.15479/AT:ISTA:7896.
short: C. Kamath Hosdurg, On the Average-Case Hardness of Total Search Problems,
Institute of Science and Technology Austria, 2020.
corr_author: '1'
date_created: 2020-05-26T14:08:55Z
date_published: 2020-05-25T00:00:00Z
date_updated: 2026-04-08T07:24:42Z
day: '25'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrPi
doi: 10.15479/AT:ISTA:7896
ec_funded: 1
file:
- access_level: open_access
checksum: b39e2e1c376f5819b823fb7077491c64
content_type: application/pdf
creator: dernst
date_created: 2020-05-26T14:08:13Z
date_updated: 2020-07-14T12:48:04Z
file_id: '7897'
file_name: 2020_Thesis_Kamath.pdf
file_size: 1622742
relation: main_file
- access_level: closed
checksum: 8b26ba729c1a85ac6bea775f5d73cdc7
content_type: application/x-zip-compressed
creator: dernst
date_created: 2020-05-26T14:08:23Z
date_updated: 2020-07-14T12:48:04Z
file_id: '7898'
file_name: Thesis_Kamath.zip
file_size: 15301529
relation: source_file
file_date_updated: 2020-07-14T12:48:04Z
has_accepted_license: '1'
language:
- iso: eng
month: '05'
oa: 1
oa_version: Published Version
page: '126'
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '6677'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On the average-case hardness of total search problems
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: dissertation
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
year: '2020'
...
---
_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
orcid: 0009-0006-6812-7317
- 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; 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. 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, 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, 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, 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: 2026-04-08T07:24:42Z
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
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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
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
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: '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: 2026-04-16T09:52:04Z
day: '06'
department:
- _id: KrPi
doi: 10.1007/978-3-030-17259-6_11
ec_funded: 1
external_id:
isi:
- '001299215500011'
intvolume: ' 11443'
isi: 1
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:
- 1611-3349
isbn:
- '9783030172589'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Adaptively secure proxy re-encryption
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 11443
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
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: '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. EUROCRYPT:
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: 'EUROCRYPT: 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: 2026-04-16T10:27:47Z
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:
eisbn:
- '9783030176563'
eissn:
- 1611-3349
isbn:
- '9783030176556'
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: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 11477
year: '2019'
...
---
_id: '193'
abstract:
- lang: eng
text: 'We show attacks on five data-independent memory-hard functions (iMHF) that
were submitted to the password hashing competition (PHC). Informally, an MHF is
a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly
lower hardware and/or energy cost than evaluating a single instance on a standard
single-core architecture. Data-independent means the memory access pattern of
the function is independent of the input; this makes iMHFs harder to construct
than data-dependent ones, but the latter can be attacked by various side-channel
attacks. Following [Alwen-Blocki''16], we capture the evaluation of an iMHF as
a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of
this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC.
Ideally, one would like the complexity of a DAG underlying an iMHF to be as close
to quadratic in the number of nodes of the graph as possible. Instead, we show
that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2,
TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show
that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have
exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial
property of each underlying DAG (called its depth-robustness. By establishing
upper bounds on this property we are then able to apply the general technique
of [Alwen-Block''16] for analyzing the hardware costs of an iMHF.'
acknowledgement: Leonid Reyzin was supported in part by IST Austria and by US NSF
grants 1012910, 1012798, and 1422965; this research was performed while he was visiting
IST Austria.
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: Peter
full_name: Gazi, Peter
last_name: Gazi
- 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: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
- 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: Lenoid
full_name: Reyzin, Lenoid
last_name: Reyzin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: 'Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data
independent password hashing functions. In: Proceedings of the 2018 on Asia
Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534'
apa: 'Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak,
K. Z., … Rybar, M. (2018). On the memory hardness of data independent password
hashing functions. In Proceedings of the 2018 on Asia Conference on Computer
and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534'
chicago: Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F
Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar.
“On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings
of the 2018 on Asia Conference on Computer and Communication Security, 51–65.
ACM, 2018. https://doi.org/10.1145/3196494.3196534.
ieee: J. F. Alwen et al., “On the memory hardness of data independent password
hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.
ista: 'Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin
L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password
hashing functions. Proceedings of the 2018 on Asia Conference on Computer and
Communication Security. ASIACCS: Asia Conference on Computer and Communications
Security , 51–65.'
mla: Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password
Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534.
short: J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak,
L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference
on Computer and Communication Security, ACM, 2018, pp. 51–65.
conference:
end_date: 2018-06-08
location: Incheon, Republic of Korea
name: 'ASIACCS: Asia Conference on Computer and Communications Security '
start_date: 2018-06-04
date_created: 2018-12-11T11:45:07Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2024-11-04T13:52:29Z
day: '01'
department:
- _id: KrPi
- _id: HeEd
- _id: VlKo
doi: 10.1145/3196494.3196534
ec_funded: 1
external_id:
isi:
- '000516620100005'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/783
month: '06'
oa: 1
oa_version: Submitted Version
page: 51 - 65
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 2018 on Asia Conference on Computer and Communication
Security
publication_status: published
publisher: ACM
publist_id: '7723'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the memory hardness of data independent password hashing functions
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '5980'
abstract:
- lang: eng
text: The problem of private set-intersection (PSI) has been traditionally treated
as an instance of the more general problem of multi-party computation (MPC). Consequently,
in order to argue security, or compose these protocols one has to rely on the
general theory that was developed for the purpose of MPC. The pursuit of efficient
protocols, however, has resulted in designs that exploit properties pertaining
to PSI. In almost all practical applications where a PSI protocol is deployed,
it is expected to be executed multiple times, possibly on related inputs. In this
work we initiate a dedicated study of PSI in the multi-interaction (MI) setting.
In this model a server sets up the common system parameters and executes set-intersection
multiple times with potentially different clients. We discuss a few attacks that
arise when protocols are naïvely composed in this manner and, accordingly, craft
security definitions for the MI setting and study their inter-relation. Finally,
we suggest a set of protocols that are MI-secure, at the same time almost as efficient
as their parent, stand-alone, protocols.
article_processing_charge: No
author:
- first_name: Sanjit
full_name: Chatterjee, Sanjit
last_name: Chatterjee
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Vikas
full_name: Kumar, Vikas
last_name: Kumar
citation:
ama: Chatterjee S, Kamath Hosdurg C, Kumar V. Private set-intersection with common
set-up. American Institute of Mathematical Sciences. 2018;12(1):17-47.
doi:10.3934/amc.2018002
apa: Chatterjee, S., Kamath Hosdurg, C., & Kumar, V. (2018). Private set-intersection
with common set-up. American Institute of Mathematical Sciences. AIMS.
https://doi.org/10.3934/amc.2018002
chicago: Chatterjee, Sanjit, Chethan Kamath Hosdurg, and Vikas Kumar. “Private Set-Intersection
with Common Set-Up.” American Institute of Mathematical Sciences. AIMS,
2018. https://doi.org/10.3934/amc.2018002.
ieee: S. Chatterjee, C. Kamath Hosdurg, and V. Kumar, “Private set-intersection
with common set-up,” American Institute of Mathematical Sciences, vol.
12, no. 1. AIMS, pp. 17–47, 2018.
ista: Chatterjee S, Kamath Hosdurg C, Kumar V. 2018. Private set-intersection with
common set-up. American Institute of Mathematical Sciences. 12(1), 17–47.
mla: Chatterjee, Sanjit, et al. “Private Set-Intersection with Common Set-Up.” American
Institute of Mathematical Sciences, vol. 12, no. 1, AIMS, 2018, pp. 17–47,
doi:10.3934/amc.2018002.
short: S. Chatterjee, C. Kamath Hosdurg, V. Kumar, American Institute of Mathematical
Sciences 12 (2018) 17–47.
date_created: 2019-02-13T13:49:41Z
date_published: 2018-02-01T00:00:00Z
date_updated: 2023-09-19T14:27:59Z
day: '01'
department:
- _id: KrPi
doi: 10.3934/amc.2018002
external_id:
isi:
- '000430950400002'
intvolume: ' 12'
isi: 1
issue: '1'
language:
- iso: eng
month: '02'
oa_version: None
page: 17-47
publication: American Institute of Mathematical Sciences
publication_status: published
publisher: AIMS
quality_controlled: '1'
scopus_import: '1'
status: public
title: Private set-intersection with common set-up
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12
year: '2018'
...
---
_id: '637'
abstract:
- lang: eng
text: For many cryptographic primitives, it is relatively easy to achieve selective
security (where the adversary commits a-priori to some of the choices to be made
later in the attack) but appears difficult to achieve the more natural notion
of adaptive security (where the adversary can make all choices on the go as the
attack progresses). A series of several recent works shows how to cleverly achieve
adaptive security in several such scenarios including generalized selective decryption
(Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer
et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b).
Although the above works expressed vague intuition that they share a common technique,
the connection was never made precise. In this work we present a new framework
that connects all of these works and allows us to present them in a unified and
simplified fashion. Moreover, we use the framework to derive a new result for
adaptively secure secret sharing over access structures defined via monotone circuits.
We envision that further applications will follow in the future. Underlying our
framework is the following simple idea. It is well known that selective security,
where the adversary commits to n-bits of information about his future choices,
automatically implies adaptive security at the cost of amplifying the adversary’s
advantage by a factor of up to 2n. However, in some cases the proof of selective
security proceeds via a sequence of hybrids, where each pair of adjacent hybrids
locally only requires some smaller partial information consisting of m ≪ n bits.
The partial information needed might be completely different between different
pairs of hybrids, and if we look across all the hybrids we might rely on the entire
n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security,
at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n.
In all of our examples using the above framework, the different hybrids are captured
by some sort of a graph pebbling game and the amount of information that the adversary
needs to commit to in each pair of hybrids is bounded by the maximum number of
pebbles in play at any point in time. Therefore, coming up with better strategies
for proving adaptive security translates to various pebbling strategies for different
types of graphs.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Zahra
full_name: Jafargholi, Zahra
last_name: Jafargholi
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
orcid: 0009-0006-6812-7317
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Ilan
full_name: Komargodski, Ilan
last_name: Komargodski
- 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: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs
D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer;
2017:133-163. doi:10.1007/978-3-319-63688-7_5'
apa: 'Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak,
K. Z., & Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz &
H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology,
Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-319-63688-7_5'
chicago: Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski,
Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited
by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_5.
ieee: 'Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak,
and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology,
Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.'
ista: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs
D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401,
133–163.'
mla: Jafargholi, Zahra, et al. Be Adaptive Avoid Overcommitting. Edited by
Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:10.1007/978-3-319-63688-7_5.
short: Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak,
D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163.
conference:
end_date: 2017-07-24
location: Santa Barbara, CA, United States
name: 'CRYPTO: Cryptology'
start_date: 2017-07-20
date_created: 2018-12-11T11:47:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2026-04-08T07:01:44Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-63688-7_5
ec_funded: 1
editor:
- first_name: Jonathan
full_name: Katz, Jonathan
last_name: Katz
- first_name: Hovav
full_name: Shacham, Hovav
last_name: Shacham
external_id:
isi:
- '000438672600005'
intvolume: ' 10401'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/515
month: '01'
oa: 1
oa_version: Submitted Version
page: 133 - 163
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331963687-0
publication_status: published
publisher: Springer
publist_id: '7151'
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Be adaptive avoid overcommitting
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 10401
year: '2017'
...
---
_id: '1177'
abstract:
- lang: eng
text: Boldyreva, Palacio and Warinschi introduced a multiple forking game as an
extension of general forking. The notion of (multiple) forking is a useful abstraction
from the actual simulation of cryptographic scheme to the adversary in a security
reduction, and is achieved through the intermediary of a so-called wrapper algorithm.
Multiple forking has turned out to be a useful tool in the security argument of
several cryptographic protocols. However, a reduction employing multiple forking
incurs a significant degradation of (Formula presented.) , where (Formula presented.)
denotes the upper bound on the underlying random oracle calls and (Formula presented.)
, the number of forkings. In this work we take a closer look at the reasons for
the degradation with a tighter security bound in mind. We nail down the exact
set of conditions for success in the multiple forking game. A careful analysis
of the cryptographic schemes and corresponding security reduction employing multiple
forking leads to the formulation of ‘dependence’ and ‘independence’ conditions
pertaining to the output of the wrapper in different rounds. Based on the (in)dependence
conditions we propose a general framework of multiple forking and a General Multiple
Forking Lemma. Leveraging (in)dependence to the full allows us to improve the
degradation factor in the multiple forking game by a factor of (Formula presented.).
By implication, the cost of a single forking involving two random oracles (augmented
forking) matches that involving a single random oracle (elementary forking). Finally,
we study the effect of these observations on the concrete security of existing
schemes employing multiple forking. We conclude that by careful design of the
protocol (and the wrapper in the security reduction) it is possible to harness
our observations to the full extent.
acknowledgement: "We are grateful to the anonymous reviewers for their insightful
comments. The\r\ndetailed reports helped us a lot to address the technical mistakes
as well as to improve the overall presentation of the paper."
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: Sanjit
full_name: Chatterjee, Sanjit
last_name: Chatterjee
citation:
ama: 'Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging
(in)dependence for a tighter bound. Algorithmica. 2016;74(4):1321-1362.
doi:10.1007/s00453-015-9997-6'
apa: 'Kamath Hosdurg, C., & Chatterjee, S. (2016). A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound. Algorithmica. Springer.
https://doi.org/10.1007/s00453-015-9997-6'
chicago: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking:
Leveraging (in)Dependence for a Tighter Bound.” Algorithmica. Springer,
2016. https://doi.org/10.1007/s00453-015-9997-6.'
ieee: 'C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound,” Algorithmica, vol. 74,
no. 4. Springer, pp. 1321–1362, 2016.'
ista: 'Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.'
mla: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking:
Leveraging (in)Dependence for a Tighter Bound.” Algorithmica, vol. 74,
no. 4, Springer, 2016, pp. 1321–62, doi:10.1007/s00453-015-9997-6.'
short: C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362.
date_created: 2018-12-11T11:50:33Z
date_published: 2016-04-01T00:00:00Z
date_updated: 2025-09-22T09:49:20Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00453-015-9997-6
external_id:
isi:
- '000373640000005'
intvolume: ' 74'
isi: 1
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2013/651
month: '04'
oa: 1
oa_version: Submitted Version
page: 1321 - 1362
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '6177'
quality_controlled: '1'
status: public
title: 'A closer look at multiple-forking: Leveraging (in)dependence for a tighter
bound'
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 74
year: '2016'
...
---
_id: '1225'
abstract:
- lang: eng
text: At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model
construction of efficient roundoptimal blind signatures that does not require
complexity leveraging. It is conceptually simple and builds on the primitive of
structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the
unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme
and hardness of a version of the DH inversion problem. Blindness under adversarially
chosen keys is proven under an interactive variant of the DDH assumption. We propose
a variant of their scheme whose blindness can be proven under a non-interactive
assumption, namely a variant of the bilinear DDH assumption. We moreover prove
its unforgeability assuming only unforgeability of the underlying SPS-EQ but no
additional assumptions as needed for the FHS scheme.
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: Christian
full_name: Hanser, Christian
last_name: Hanser
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Daniel
full_name: Slamanig, Daniel
last_name: Slamanig
citation:
ama: 'Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. Practical round-optimal
blind signatures in the standard model from weaker assumptions. In: Vol 9841.
Springer; 2016:391-408. doi:10.1007/978-3-319-44618-9_21'
apa: 'Fuchsbauer, G., Hanser, C., Kamath Hosdurg, C., & Slamanig, D. (2016).
Practical round-optimal blind signatures in the standard model from weaker assumptions
(Vol. 9841, pp. 391–408). Presented at the SCN: Security and Cryptography for
Networks, Amalfi, Italy: Springer. https://doi.org/10.1007/978-3-319-44618-9_21'
chicago: Fuchsbauer, Georg, Christian Hanser, Chethan Kamath Hosdurg, and Daniel
Slamanig. “Practical Round-Optimal Blind Signatures in the Standard Model from
Weaker Assumptions,” 9841:391–408. Springer, 2016. https://doi.org/10.1007/978-3-319-44618-9_21.
ieee: 'G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, and D. Slamanig, “Practical
round-optimal blind signatures in the standard model from weaker assumptions,”
presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy, 2016,
vol. 9841, pp. 391–408.'
ista: 'Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. 2016. Practical round-optimal
blind signatures in the standard model from weaker assumptions. SCN: Security
and Cryptography for Networks, LNCS, vol. 9841, 391–408.'
mla: Fuchsbauer, Georg, et al. Practical Round-Optimal Blind Signatures in the
Standard Model from Weaker Assumptions. Vol. 9841, Springer, 2016, pp. 391–408,
doi:10.1007/978-3-319-44618-9_21.
short: G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer,
2016, pp. 391–408.
conference:
end_date: 2016-09-02
location: Amalfi, Italy
name: 'SCN: Security and Cryptography for Networks'
start_date: 2016-08-31
date_created: 2018-12-11T11:50:49Z
date_published: 2016-08-11T00:00:00Z
date_updated: 2025-09-23T09:53:45Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-319-44618-9_21
ec_funded: 1
external_id:
isi:
- '000389516500021'
intvolume: ' 9841'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/662
month: '08'
oa: 1
oa_version: Submitted Version
page: 391 - 408
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_status: published
publisher: Springer
publist_id: '6109'
quality_controlled: '1'
related_material:
record:
- id: '1647'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Practical round-optimal blind signatures in the standard model from weaker
assumptions
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9841
year: '2016'
...
---
_id: '1231'
abstract:
- lang: eng
text: 'We study the time-and memory-complexities of the problem of computing labels
of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The
w-bit label of a node is the hash of the labels of its parents, and the hash function
is modeled as a random oracle. Specific instances of this problem underlie both
proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard
functions like scrypt. As our main tool, we introduce the new notion of a probabilistic
parallel entangled pebbling game, a new type of combinatorial pebbling game on
a graph, which is closely related to the labeling game on the same graph. As a
first application of our framework, we prove that for scrypt, when the underlying
hash function is invoked n times, the cumulative memory complexity (CMC) (a notion
recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness
for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for
adversaries that can store many natural functions of the labels (e.g., linear
combinations), but still not arbitrary functions thereof. We then introduce and
study a combinatorial quantity, and show how a sufficiently small upper bound
on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary
adversaries. We also show that such an upper bound solves the main open problem
for proofs-of-space protocols: namely, establishing that the time complexity of
computing the label of a random node in a graph on n nodes (given an initial kw-bit
state) reduces tightly to the time complexity for black pebbling on the same graph
(given an initial k-node pebbling).'
acknowledgement: "Joël Alwen, Chethan Kamath, and Krzysztof Pietrzak’s research is
partially supported by an ERC starting grant (259668-PSPC). Vladimir Kolmogorov
is partially supported by an ERC consolidator grant (616160-DOICV). Binyi Chen was
partially supported by NSF grants CNS-1423566 and CNS-1514526, and a gift from the
Gareatis Foundation. Stefano Tessaro was partially supported by NSF grants CNS-1423566,
CNS-1528178, a Hellman Fellowship, and the Glen and Susanne Culler Chair.\r\n\r\nThis
work was done in part while the authors were visiting the Simons Institute for the
Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons
Collaboration in Cryptography through NSF grant CNS-1523467."
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: Binyi
full_name: Chen, Binyi
last_name: Chen
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- 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: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S.
On the complexity of scrypt and proofs of space in the parallel random oracle
model. In: Vol 9666. Springer; 2016:358-387. doi:10.1007/978-3-662-49896-5_13'
apa: 'Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z.,
& Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the
parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT:
Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer.
https://doi.org/10.1007/978-3-662-49896-5_13'
chicago: Alwen, Joel F, Binyi Chen, Chethan Kamath Hosdurg, Vladimir Kolmogorov,
Krzysztof Z Pietrzak, and Stefano Tessaro. “On the Complexity of Scrypt and Proofs
of Space in the Parallel Random Oracle Model,” 9666:358–87. Springer, 2016. https://doi.org/10.1007/978-3-662-49896-5_13.
ieee: 'J. F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K. Z. Pietrzak, and
S. Tessaro, “On the complexity of scrypt and proofs of space in the parallel random
oracle model,” presented at the EUROCRYPT: Theory and Applications of Cryptographic
Techniques, Vienna, Austria, 2016, vol. 9666, pp. 358–387.'
ista: 'Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S.
2016. On the complexity of scrypt and proofs of space in the parallel random oracle
model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol.
9666, 358–387.'
mla: Alwen, Joel F., et al. On the Complexity of Scrypt and Proofs of Space in
the Parallel Random Oracle Model. Vol. 9666, Springer, 2016, pp. 358–87, doi:10.1007/978-3-662-49896-5_13.
short: J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S.
Tessaro, in:, Springer, 2016, pp. 358–387.
conference:
end_date: 2016-05-12
location: Vienna, Austria
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2016-05-08
date_created: 2018-12-11T11:50:51Z
date_published: 2016-04-28T00:00:00Z
date_updated: 2025-09-22T09:22:54Z
day: '28'
department:
- _id: KrPi
- _id: VlKo
doi: 10.1007/978-3-662-49896-5_13
ec_funded: 1
external_id:
isi:
- '000389727200013'
intvolume: ' 9666'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/100
month: '04'
oa: 1
oa_version: Submitted Version
page: 358 - 387
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_status: published
publisher: Springer
publist_id: '6103'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the complexity of scrypt and proofs of space in the parallel random oracle
model
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 9666
year: '2016'
...