---
_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: '10609'
abstract:
- lang: eng
text: "We study Multi-party computation (MPC) in the setting of subversion, where
the adversary tampers with the machines of honest parties. Our goal is to construct
actively secure MPC protocols where parties are corrupted adaptively by an adversary
(as in the standard adaptive security setting), and in addition, honest parties’
machines are compromised.\r\nThe idea of reverse firewalls (RF) was introduced
at EUROCRYPT’15 by Mironov and Stephens-Davidowitz as an approach to protecting
protocols against corruption of honest parties’ devices. Intuitively, an RF for
a party P is an external entity that sits between P and the outside world
and whose scope is to sanitize P ’s incoming and outgoing messages in the face
of subversion of their computer. Mironov and Stephens-Davidowitz constructed a
protocol for passively-secure two-party computation. At CRYPTO’20, Chakraborty,
Dziembowski and Nielsen constructed a protocol for secure computation with firewalls
that improved on this result, both by extending it to multi-party computation
protocol, and considering active security in the presence of static corruptions.
In this paper, we initiate the study of RF for MPC in the adaptive setting. We
put forward a definition for adaptively secure MPC in the reverse firewall setting,
explore relationships among the security notions, and then construct reverse firewalls
for MPC in this stronger setting of adaptive security. We also resolve the open
question of Chakraborty, Dziembowski and Nielsen by removing the need for a trusted
setup in constructing RF for MPC. Towards this end, we construct reverse firewalls
for adaptively secure augmented coin tossing and adaptively secure zero-knowledge
protocols and obtain a constant round adaptively secure MPC protocol in the reverse
firewall setting without setup. Along the way, we propose a new multi-party adaptively
secure coin tossing protocol in the plain model, that is of independent interest."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Chaya
full_name: Ganesh, Chaya
last_name: Ganesh
- first_name: Mahak
full_name: Pancholi, Mahak
last_name: Pancholi
- first_name: Pratik
full_name: Sarkar, Pratik
last_name: Sarkar
citation:
ama: 'Chakraborty S, Ganesh C, Pancholi M, Sarkar P. Reverse firewalls for adaptively
secure MPC without setup. In: 27th International Conference on the Theory and
Application of Cryptology and Information Security. Vol 13091. Springer Nature;
2021:335-364. doi:10.1007/978-3-030-92075-3_12'
apa: 'Chakraborty, S., Ganesh, C., Pancholi, M., & Sarkar, P. (2021). Reverse
firewalls for adaptively secure MPC without setup. In 27th International Conference
on the Theory and Application of Cryptology and Information Security (Vol.
13091, pp. 335–364). Virtual, Singapore: Springer Nature. https://doi.org/10.1007/978-3-030-92075-3_12'
chicago: Chakraborty, Suvradip, Chaya Ganesh, Mahak Pancholi, and Pratik Sarkar.
“Reverse Firewalls for Adaptively Secure MPC without Setup.” In 27th International
Conference on the Theory and Application of Cryptology and Information Security,
13091:335–64. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-92075-3_12.
ieee: S. Chakraborty, C. Ganesh, M. Pancholi, and P. Sarkar, “Reverse firewalls
for adaptively secure MPC without setup,” in 27th International Conference
on the Theory and Application of Cryptology and Information Security, Virtual,
Singapore, 2021, vol. 13091, pp. 335–364.
ista: 'Chakraborty S, Ganesh C, Pancholi M, Sarkar P. 2021. Reverse firewalls for
adaptively secure MPC without setup. 27th International Conference on the Theory
and Application of Cryptology and Information Security. ASIACRYPT: International
Conference on Cryptology in Asia, LNCS, vol. 13091, 335–364.'
mla: Chakraborty, Suvradip, et al. “Reverse Firewalls for Adaptively Secure MPC
without Setup.” 27th International Conference on the Theory and Application
of Cryptology and Information Security, vol. 13091, Springer Nature, 2021,
pp. 335–64, doi:10.1007/978-3-030-92075-3_12.
short: S. Chakraborty, C. Ganesh, M. Pancholi, P. Sarkar, in:, 27th International
Conference on the Theory and Application of Cryptology and Information Security,
Springer Nature, 2021, pp. 335–364.
conference:
end_date: 2021-12-10
location: Virtual, Singapore
name: 'ASIACRYPT: International Conference on Cryptology in Asia'
start_date: 2021-12-06
date_created: 2022-01-09T23:01:27Z
date_published: 2021-12-01T00:00:00Z
date_updated: 2023-08-17T06:34:41Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-030-92075-3_12
ec_funded: 1
external_id:
isi:
- '000927876200012'
intvolume: ' 13091'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1262
month: '12'
oa: 1
oa_version: Preprint
page: 335-364
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 27th International Conference on the Theory and Application of Cryptology
and Information Security
publication_identifier:
eisbn:
- 978-3-030-92075-3
eissn:
- 1611-3349
isbn:
- 978-3-030-92074-6
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reverse firewalls for adaptively secure MPC without setup
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13091
year: '2021'
...
---
_id: '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: '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: '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: '10035'
abstract:
- lang: eng
text: 'Many security definitions come in two flavors: a stronger “adaptive” flavor,
where the adversary can arbitrarily make various choices during the course of
the attack, and a weaker “selective” flavor where the adversary must commit to
some or all of their choices a-priori. For example, in the context of identity-based
encryption, selective security requires the adversary to decide on the identity
of the attacked party at the very beginning of the game whereas adaptive security
allows the attacker to first see the master public key and some secret keys before
making this choice. Often, it appears to be much easier to achieve selective security
than it is to achieve adaptive security. A series of several recent works shows
how to cleverly achieve adaptive security in several such scenarios including
generalized selective decryption [Pan07][FJP15], constrained PRFs [FKPR14], and
Yao’s garbled circuits [JW16]. Although the above works expressed vague intuition
that they share a common technique, the connection was never made precise. In
this work we present a new framework (published at Crypto ’17 [JKK+17a]) that
connects all of these works and allows us to present them in a unified and simplified
fashion. Having the framework in place, we show how to achieve adaptive security
for proxy re-encryption schemes (published at PKC ’19 [FKKP19]) and provide the
first adaptive security proofs for continuous group key agreement protocols (published
at S&P ’21 [KPW+21]). Questioning optimality of our framework, we then show that
currently used proof techniques cannot lead to significantly better security guarantees
for "graph-building" games (published at TCC ’21 [KKPW21a]). These games cover
generalized selective decryption, as well as the security of prominent constructions
for constrained PRFs, continuous group key agreement, and proxy re-encryption.
Finally, we revisit the adaptive security of Yao’s garbled circuits and extend
the analysis of Jafargholi and Wichs in two directions: While they prove adaptive
security only for a modified construction with increased online complexity, we
provide the first positive results for the original construction by Yao (published
at TCC ’21 [KKP21a]). On the negative side, we prove that the results of Jafargholi
and Wichs are essentially optimal by showing that no black-box reduction can provide
a significantly better security bound (published at Crypto ’21 [KKPW21c]).'
acknowledgement: "I want to acknowledge the funding by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
citation:
ama: Klein K. On the adaptive security of graph-based games. 2021. doi:10.15479/at:ista:10035
apa: Klein, K. (2021). On the adaptive security of graph-based games. Institute
of Science and Technology Austria. https://doi.org/10.15479/at:ista:10035
chicago: Klein, Karen. “On the Adaptive Security of Graph-Based Games.” Institute
of Science and Technology Austria, 2021. https://doi.org/10.15479/at:ista:10035.
ieee: K. Klein, “On the adaptive security of graph-based games,” Institute of Science
and Technology Austria, 2021.
ista: Klein K. 2021. On the adaptive security of graph-based games. Institute of
Science and Technology Austria.
mla: Klein, Karen. On the Adaptive Security of Graph-Based Games. Institute
of Science and Technology Austria, 2021, doi:10.15479/at:ista:10035.
short: K. Klein, On the Adaptive Security of Graph-Based Games, Institute of Science
and Technology Austria, 2021.
date_created: 2021-09-23T07:31:44Z
date_published: 2021-09-23T00:00:00Z
date_updated: 2023-10-17T09:24:07Z
day: '23'
ddc:
- '519'
degree_awarded: PhD
department:
- _id: GradSch
- _id: KrPi
doi: 10.15479/at:ista:10035
ec_funded: 1
file:
- access_level: open_access
checksum: 73a44345c683e81f3e765efbf86fdcc5
content_type: application/pdf
creator: cchlebak
date_created: 2021-10-04T12:22:33Z
date_updated: 2021-10-04T12:22:33Z
file_id: '10082'
file_name: thesis_pdfa.pdf
file_size: 2104726
relation: main_file
success: 1
- access_level: closed
checksum: 7b80df30a0e686c3ef6a56d4e1c59e29
content_type: application/x-zip-compressed
creator: cchlebak
date_created: 2021-10-05T07:04:37Z
date_updated: 2022-03-10T12:15:18Z
file_id: '10085'
file_name: thesis_final (1).zip
file_size: 9538359
relation: source_file
file_date_updated: 2022-03-10T12:15:18Z
has_accepted_license: '1'
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '09'
oa: 1
oa_version: Published Version
page: '276'
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
related_material:
record:
- id: '10044'
relation: part_of_dissertation
status: public
- id: '10049'
relation: part_of_dissertation
status: public
- id: '637'
relation: part_of_dissertation
status: public
- id: '10041'
relation: part_of_dissertation
status: public
- id: '6430'
relation: part_of_dissertation
status: public
- id: '10048'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
title: On the adaptive security of graph-based games
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
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: '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'
...