---
_id: '10048'
abstract:
- lang: eng
text: "The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical\r\nframework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower\r\nbounds
that almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and\r\nbroadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.\r\n"
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th Theory of Cryptography Conference 2021.
International Association for Cryptologic Research; 2021.'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th Theory of Cryptography
Conference 2021. Raleigh, NC, United States: International Association for
Cryptologic Research.'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th Theory
of Cryptography Conference 2021. International Association for Cryptologic
Research, 2021.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th Theory of Cryptography Conference 2021,
Raleigh, NC, United States, 2021.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th Theory of Cryptography Conference 2021. TCC:
Theory of Cryptography Conference.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th Theory of Cryptography Conference 2021, International Association
for Cryptologic Research, 2021.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th Theory of
Cryptography Conference 2021, International Association for Cryptologic Research,
2021.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-09-27T12:52:05Z
date_published: 2021-07-08T00:00:00Z
date_updated: 2023-10-17T09:24:08Z
day: '08'
department:
- _id: KrPi
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '07'
oa: 1
oa_version: Preprint
publication: 19th Theory of Cryptography Conference 2021
publication_status: published
publisher: International Association for Cryptologic Research
quality_controlled: '1'
related_material:
record:
- id: '10410'
relation: later_version
status: public
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2021'
...
---
_id: '10049'
abstract:
- lang: eng
text: While messaging systems with strong security guarantees are widely used in
practice, designing a protocol that scales efficiently to large groups and enjoys
similar security guarantees remains largely open. The two existing proposals to
date are ART (Cohn-Gordon et al., CCS18) and TreeKEM (IETF, The Messaging Layer
Security Protocol, draft). TreeKEM is the currently considered candidate by the
IETF MLS working group, but dynamic group operations (i.e. adding and removing
users) can cause efficiency issues. In this paper we formalize and analyze a variant
of TreeKEM which we term Tainted TreeKEM (TTKEM for short). The basic idea underlying
TTKEM was suggested by Millican (MLS mailing list, February 2018). This version
is more efficient than TreeKEM for some natural distributions of group operations,
we quantify this through simulations.Our second contribution is two security proofs
for TTKEM which establish post compromise and forward secrecy even against adaptive
attackers. The security loss (to the underlying PKE) in the Random Oracle Model
is a polynomial factor, and a quasipolynomial one in the Standard Model. Our proofs
can be adapted to TreeKEM as well. Before our work no security proof for any TreeKEM-like
protocol establishing tight security against an adversary who can adaptively choose
the sequence of operations was known. We also are the first to prove (or even
formalize) active security where the server can arbitrarily deviate from the protocol
specification. Proving fully active security – where also the users can arbitrarily
deviate – remains open.
acknowledgement: The first three authors contributed equally to this work. Funded
by the European Research Council (ERC) under the European Union’s Horizon2020 research
and innovation programme (682815-TOCNeT). Funded by the European Union’s Horizon
2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No.665385.
article_processing_charge: No
author:
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Margarita
full_name: Capretto, Margarita
last_name: Capretto
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
- first_name: Ilia
full_name: Markov, Ilia
id: D0CF4148-C985-11E9-8066-0BDEE5697425
last_name: Markov
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Klein K, Pascual Perez G, Walter M, et al. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. In: 2021 IEEE
Symposium on Security and Privacy . IEEE; 2021:268-284. doi:10.1109/sp40001.2021.00035'
apa: 'Klein, K., Pascual Perez, G., Walter, M., Kamath Hosdurg, C., Capretto, M.,
Cueto Noval, M., … Pietrzak, K. Z. (2021). Keep the dirt: tainted TreeKEM, adaptively
and actively secure continuous group key agreement. In 2021 IEEE Symposium
on Security and Privacy (pp. 268–284). San Francisco, CA, United States:
IEEE. https://doi.org/10.1109/sp40001.2021.00035'
chicago: 'Klein, Karen, Guillermo Pascual Perez, Michael Walter, Chethan Kamath
Hosdurg, Margarita Capretto, Miguel Cueto Noval, Ilia Markov, Michelle X Yeo,
Joel F Alwen, and Krzysztof Z Pietrzak. “Keep the Dirt: Tainted TreeKEM, Adaptively
and Actively Secure Continuous Group Key Agreement.” In 2021 IEEE Symposium
on Security and Privacy , 268–84. IEEE, 2021. https://doi.org/10.1109/sp40001.2021.00035.'
ieee: 'K. Klein et al., “Keep the dirt: tainted TreeKEM, adaptively and actively
secure continuous group key agreement,” in 2021 IEEE Symposium on Security
and Privacy , San Francisco, CA, United States, 2021, pp. 268–284.'
ista: 'Klein K, Pascual Perez G, Walter M, Kamath Hosdurg C, Capretto M, Cueto Noval
M, Markov I, Yeo MX, Alwen JF, Pietrzak KZ. 2021. Keep the dirt: tainted TreeKEM,
adaptively and actively secure continuous group key agreement. 2021 IEEE Symposium
on Security and Privacy . SP: Symposium on Security and Privacy, 268–284.'
mla: 'Klein, Karen, et al. “Keep the Dirt: Tainted TreeKEM, Adaptively and Actively
Secure Continuous Group Key Agreement.” 2021 IEEE Symposium on Security and
Privacy , IEEE, 2021, pp. 268–84, doi:10.1109/sp40001.2021.00035.'
short: K. Klein, G. Pascual Perez, M. Walter, C. Kamath Hosdurg, M. Capretto, M.
Cueto Noval, I. Markov, M.X. Yeo, J.F. Alwen, K.Z. Pietrzak, in:, 2021 IEEE Symposium
on Security and Privacy , IEEE, 2021, pp. 268–284.
conference:
end_date: 2021-05-27
location: San Francisco, CA, United States
name: 'SP: Symposium on Security and Privacy'
start_date: 2021-05-24
date_created: 2021-09-27T13:46:27Z
date_published: 2021-08-26T00:00:00Z
date_updated: 2023-09-07T13:32:11Z
day: '26'
department:
- _id: KrPi
- _id: DaAl
doi: 10.1109/sp40001.2021.00035
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1489
month: '08'
oa: 1
oa_version: Preprint
page: 268-284
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: '2021 IEEE Symposium on Security and Privacy '
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
status: public
title: 'Keep the dirt: tainted TreeKEM, adaptively and actively secure continuous
group key agreement'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2021'
...
---
_id: '10407'
abstract:
- lang: eng
text: Digital hardware Trojans are integrated circuits whose implementation differ
from the specification in an arbitrary and malicious way. For example, the circuit
can differ from its specified input/output behavior after some fixed number of
queries (known as “time bombs”) or on some particular input (known as “cheat codes”).
To detect such Trojans, countermeasures using multiparty computation (MPC) or
verifiable computation (VC) have been proposed. On a high level, to realize a
circuit with specification F one has more sophisticated circuits F⋄ manufactured
(where F⋄ specifies a MPC or VC of F ), and then embeds these F⋄ ’s into
a master circuit which must be trusted but is relatively simple compared to F
. Those solutions impose a significant overhead as F⋄ is much more complex
than F , also the master circuits are not exactly trivial. In this work, we
show that in restricted settings, where F has no evolving state and is queried
on independent inputs, we can achieve a relaxed security notion using very simple
constructions. In particular, we do not change the specification of the circuit
at all (i.e., F=F⋄ ). Moreover the master circuit basically just queries a subset
of its manufactured circuits and checks if they’re all the same. The security
we achieve guarantees that, if the manufactured circuits are initially tested
on up to T inputs, the master circuit will catch Trojans that try to deviate on
significantly more than a 1/T fraction of the inputs. This bound is optimal for
the type of construction considered, and we provably achieve it using a construction
where 12 instantiations of F need to be embedded into the master. We also discuss
an extremely simple construction with just 2 instantiations for which we conjecture
that it already achieves the optimal bound.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Stefan
full_name: Dziembowski, Stefan
last_name: Dziembowski
- first_name: Małgorzata
full_name: Gałązka, Małgorzata
last_name: Gałązka
- first_name: Tomasz
full_name: Lizurej, Tomasz
last_name: Lizurej
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
citation:
ama: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX. Trojan-resilience
without cryptography. In: Vol 13043. Springer Nature; 2021:397-428. doi:10.1007/978-3-030-90453-1_14'
apa: 'Chakraborty, S., Dziembowski, S., Gałązka, M., Lizurej, T., Pietrzak, K. Z.,
& Yeo, M. X. (2021). Trojan-resilience without cryptography (Vol. 13043, pp.
397–428). Presented at the TCC: Theory of Cryptography Conference, Raleigh, NC,
United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_14'
chicago: Chakraborty, Suvradip, Stefan Dziembowski, Małgorzata Gałązka, Tomasz Lizurej,
Krzysztof Z Pietrzak, and Michelle X Yeo. “Trojan-Resilience without Cryptography,”
13043:397–428. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_14.
ieee: 'S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K. Z. Pietrzak, and
M. X. Yeo, “Trojan-resilience without cryptography,” presented at the TCC: Theory
of Cryptography Conference, Raleigh, NC, United States, 2021, vol. 13043, pp.
397–428.'
ista: 'Chakraborty S, Dziembowski S, Gałązka M, Lizurej T, Pietrzak KZ, Yeo MX.
2021. Trojan-resilience without cryptography. TCC: Theory of Cryptography Conference,
LNCS, vol. 13043, 397–428.'
mla: Chakraborty, Suvradip, et al. Trojan-Resilience without Cryptography.
Vol. 13043, Springer Nature, 2021, pp. 397–428, doi:10.1007/978-3-030-90453-1_14.
short: S. Chakraborty, S. Dziembowski, M. Gałązka, T. Lizurej, K.Z. Pietrzak, M.X.
Yeo, in:, Springer Nature, 2021, pp. 397–428.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography Conference'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2023-08-14T13:07:46Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_14
ec_funded: 1
external_id:
isi:
- '000728364000014'
intvolume: ' 13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1224
month: '11'
oa: 1
oa_version: Preprint
page: 397-428
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Trojan-resilience without cryptography
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...
---
_id: '10408'
abstract:
- lang: eng
text: 'Key trees are often the best solution in terms of transmission cost and storage
requirements for managing keys in a setting where a group needs to share a secret
key, while being able to efficiently rotate the key material of users (in order
to recover from a potential compromise, or to add or remove users). Applications
include multicast encryption protocols like LKH (Logical Key Hierarchies) or group
messaging like the current IETF proposal TreeKEM. A key tree is a (typically balanced)
binary tree, where each node is identified with a key: leaf nodes hold users’
secret keys while the root is the shared group key. For a group of size N, each
user just holds log(N) keys (the keys on the path from its leaf to the root)
and its entire key material can be rotated by broadcasting 2log(N) ciphertexts
(encrypting each fresh key on the path under the keys of its parents). In this
work we consider the natural setting where we have many groups with partially
overlapping sets of users, and ask if we can find solutions where the cost of
rotating a key is better than in the trivial one where we have a separate key
tree for each group. We show that in an asymptotic setting (where the number m
of groups is fixed while the number N of users grows) there exist more general
key graphs whose cost converges to the cost of a single group, thus saving a factor
linear in the number of groups over the trivial solution. As our asymptotic “solution”
converges very slowly and performs poorly on concrete examples, we propose an
algorithm that uses a natural heuristic to compute a key graph for any given group
structure. Our algorithm combines two greedy algorithms, and is thus very efficient:
it first converts the group structure into a “lattice graph”, which is then turned
into a key graph by repeatedly applying the algorithm for constructing a Huffman
code. To better understand how far our proposal is from an optimal solution, we
prove lower bounds on the update cost of continuous group-key agreement and multicast
encryption in a symbolic model admitting (asymmetric) encryption, pseudorandom
generators, and secret sharing as building blocks.'
acknowledgement: B. Auerbach, M.A. Baig and K. Pietrzak—received funding from the
European Research Council (ERC) under the European Union’s Horizon 2020 research
and innovation programme (682815 - TOCNeT); Karen Klein was supported in part by
ERC CoG grant 724307 and conducted part of this work at IST Austria, funded by the
ERC under the European Union’s Horizon 2020 research and innovation programme (682815
- TOCNeT); Guillermo Pascual-Perez was funded by the European Union’s Horizon 2020
research and innovation programme under the Marie Skłodowska-Curie Grant Agreement
No. 665385; Michael Walter conducted part of this work at IST Austria, funded by
the ERC under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Mirza Ahad
full_name: Baig, Mirza Ahad
id: 3EDE6DE4-AA5A-11E9-986D-341CE6697425
last_name: Baig
- first_name: Miguel
full_name: Cueto Noval, Miguel
id: ffc563a3-f6e0-11ea-865d-e3cce03d17cc
last_name: Cueto Noval
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
orcid: 0000-0001-8630-415X
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Alwen JF, Auerbach B, Baig MA, et al. Grafting key trees: Efficient key management
for overlapping groups. In: 19th International Conference. Vol 13044. Springer
Nature; 2021:222-253. doi:10.1007/978-3-030-90456-2_8'
apa: 'Alwen, J. F., Auerbach, B., Baig, M. A., Cueto Noval, M., Klein, K., Pascual
Perez, G., … Walter, M. (2021). Grafting key trees: Efficient key management for
overlapping groups. In 19th International Conference (Vol. 13044, pp. 222–253).
Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90456-2_8'
chicago: 'Alwen, Joel F, Benedikt Auerbach, Mirza Ahad Baig, Miguel Cueto Noval,
Karen Klein, Guillermo Pascual Perez, Krzysztof Z Pietrzak, and Michael Walter.
“Grafting Key Trees: Efficient Key Management for Overlapping Groups.” In 19th
International Conference, 13044:222–53. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90456-2_8.'
ieee: 'J. F. Alwen et al., “Grafting key trees: Efficient key management
for overlapping groups,” in 19th International Conference, Raleigh, NC,
United States, 2021, vol. 13044, pp. 222–253.'
ista: 'Alwen JF, Auerbach B, Baig MA, Cueto Noval M, Klein K, Pascual Perez G, Pietrzak
KZ, Walter M. 2021. Grafting key trees: Efficient key management for overlapping
groups. 19th International Conference. TCC: Theory of Cryptography, LNCS, vol.
13044, 222–253.'
mla: 'Alwen, Joel F., et al. “Grafting Key Trees: Efficient Key Management for Overlapping
Groups.” 19th International Conference, vol. 13044, Springer Nature, 2021,
pp. 222–53, doi:10.1007/978-3-030-90456-2_8.'
short: J.F. Alwen, B. Auerbach, M.A. Baig, M. Cueto Noval, K. Klein, G. Pascual
Perez, K.Z. Pietrzak, M. Walter, in:, 19th International Conference, Springer
Nature, 2021, pp. 222–253.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:42Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2023-08-14T13:19:39Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90456-2_8
ec_funded: 1
external_id:
isi:
- '000728363700008'
intvolume: ' 13044'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/1158
month: '11'
oa: 1
oa_version: Preprint
page: 222-253
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
publication: 19th International Conference
publication_identifier:
eisbn:
- 978-3-030-90456-2
eissn:
- 1611-3349
isbn:
- 9-783-0309-0455-5
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Grafting key trees: Efficient key management for overlapping groups'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13044
year: '2021'
...
---
_id: '10409'
abstract:
- lang: eng
text: We show that Yao’s garbling scheme is adaptively indistinguishable for the
class of Boolean circuits of size S and treewidth w with only a SO(w) loss
in security. For instance, circuits with constant treewidth are as a result adaptively
indistinguishable with only a polynomial loss. This (partially) complements a
negative result of Applebaum et al. (Crypto 2013), which showed (assuming one-way
functions) that Yao’s garbling scheme cannot be adaptively simulatable. As main
technical contributions, we introduce a new pebble game that abstracts out our
security reduction and then present a pebbling strategy for this game where the
number of pebbles used is roughly O(δwlog(S)) , δ being the fan-out of the
circuit. The design of the strategy relies on separators, a graph-theoretic notion
with connections to circuit complexity. with only a SO(w) loss in security.
For instance, circuits with constant treewidth are as a result adaptively indistinguishable
with only a polynomial loss. This (partially) complements a negative result of
Applebaum et al. (Crypto 2013), which showed (assuming one-way functions) that
Yao’s garbling scheme cannot be adaptively simulatable. As main technical contributions,
we introduce a new pebble game that abstracts out our security reduction and then
present a pebbling strategy for this game where the number of pebbles used is
roughly O(δwlog(S)) , δ being the fan-out of the circuit. The design of the
strategy relies on separators, a graph-theoretic notion with connections to circuit
complexity.
acknowledgement: We are grateful to Daniel Wichs for helpful discussions on the landscape
of adaptive security of Yao’s garbling. We would also like to thank Crypto 2021
and TCC 2021 reviewers for their detailed review and suggestions, which helped improve
presentation considerably.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. On treewidth, separators and Yao’s
garbling. In: 19th International Conference. Vol 13043. Springer Nature;
2021:486-517. doi:10.1007/978-3-030-90453-1_17'
apa: 'Kamath Hosdurg, C., Klein, K., & Pietrzak, K. Z. (2021). On treewidth,
separators and Yao’s garbling. In 19th International Conference (Vol. 13043,
pp. 486–517). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_17'
chicago: Kamath Hosdurg, Chethan, Karen Klein, and Krzysztof Z Pietrzak. “On Treewidth,
Separators and Yao’s Garbling.” In 19th International Conference, 13043:486–517.
Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_17.
ieee: C. Kamath Hosdurg, K. Klein, and K. Z. Pietrzak, “On treewidth, separators
and Yao’s garbling,” in 19th International Conference, Raleigh, NC, United
States, 2021, vol. 13043, pp. 486–517.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ. 2021. On treewidth, separators and
Yao’s garbling. 19th International Conference. TCC: Theory of Cryptography, LNCS,
vol. 13043, 486–517.'
mla: Kamath Hosdurg, Chethan, et al. “On Treewidth, Separators and Yao’s Garbling.”
19th International Conference, vol. 13043, Springer Nature, 2021, pp. 486–517,
doi:10.1007/978-3-030-90453-1_17.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, in:, 19th International Conference,
Springer Nature, 2021, pp. 486–517.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2023-08-17T06:21:38Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_17
ec_funded: 1
external_id:
isi:
- '000728364000017'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/926
month: '11'
oa: 1
oa_version: Preprint
page: 486-517
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10044'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: On treewidth, separators and Yao’s garbling
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: '13043 '
year: '2021'
...
---
_id: '10410'
abstract:
- lang: eng
text: The security of cryptographic primitives and protocols against adversaries
that are allowed to make adaptive choices (e.g., which parties to corrupt or which
queries to make) is notoriously difficult to establish. A broad theoretical framework
was introduced by Jafargholi et al. [Crypto’17] for this purpose. In this paper
we initiate the study of lower bounds on loss in adaptive security for certain
cryptographic protocols considered in the framework. We prove lower bounds that
almost match the upper bounds (proven using the framework) for proxy re-encryption,
prefix-constrained PRFs and generalized selective decryption, a security game
that captures the security of certain group messaging and broadcast encryption
schemes. Those primitives have in common that their security game involves an
underlying graph that can be adaptively built by the adversary. Some of our lower
bounds only apply to a restricted class of black-box reductions which we term
“oblivious” (the existing upper bounds are of this restricted type), some apply
to the broader but still restricted class of non-rewinding reductions, while our
lower bound for proxy re-encryption applies to all black-box reductions. The fact
that some of our lower bounds seem to crucially rely on obliviousness or at least
a non-rewinding reduction hints to the exciting possibility that the existing
upper bounds can be improved by using more sophisticated reductions. Our main
conceptual contribution is a two-player multi-stage game called the Builder-Pebbler
Game. We can translate bounds on the winning probabilities for various instantiations
of this game into cryptographic lower bounds for the above-mentioned primitives
using oracle separation techniques.
acknowledgement: C. Kamath—Supported by Azrieli International Postdoctoral Fellowship.
Most of the work was done while the author was at Northeastern University and Charles
University, funded by the IARPA grant IARPA/2019-19-020700009 and project PRIMUS/17/SCI/9,
respectively. K. Klein—Supported in part by ERC CoG grant 724307. Most of the work
was done while the author was at IST Austria funded by the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT). K. Pietrzak—Funded by the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation programme (682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. The cost of adaptivity in
security games on graphs. In: 19th International Conference. Vol 13043.
Springer Nature; 2021:550-581. doi:10.1007/978-3-030-90453-1_19'
apa: 'Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter, M. (2021). The
cost of adaptivity in security games on graphs. In 19th International Conference
(Vol. 13043, pp. 550–581). Raleigh, NC, United States: Springer Nature. https://doi.org/10.1007/978-3-030-90453-1_19'
chicago: Kamath Hosdurg, Chethan, Karen Klein, Krzysztof Z Pietrzak, and Michael
Walter. “The Cost of Adaptivity in Security Games on Graphs.” In 19th International
Conference, 13043:550–81. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-90453-1_19.
ieee: C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter, “The cost of adaptivity
in security games on graphs,” in 19th International Conference, Raleigh,
NC, United States, 2021, vol. 13043, pp. 550–581.
ista: 'Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2021. The cost of adaptivity
in security games on graphs. 19th International Conference. TCC: Theory of Cryptography,
LNCS, vol. 13043, 550–581.'
mla: Kamath Hosdurg, Chethan, et al. “The Cost of Adaptivity in Security Games on
Graphs.” 19th International Conference, vol. 13043, Springer Nature, 2021,
pp. 550–81, doi:10.1007/978-3-030-90453-1_19.
short: C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:, 19th International
Conference, Springer Nature, 2021, pp. 550–581.
conference:
end_date: 2021-11-11
location: Raleigh, NC, United States
name: 'TCC: Theory of Cryptography'
start_date: 2021-11-08
date_created: 2021-12-05T23:01:43Z
date_published: 2021-11-04T00:00:00Z
date_updated: 2023-10-17T09:24:07Z
day: '04'
department:
- _id: KrPi
doi: 10.1007/978-3-030-90453-1_19
ec_funded: 1
external_id:
isi:
- '000728364000019'
intvolume: ' 13043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://ia.cr/2021/059
month: '11'
oa: 1
oa_version: Preprint
page: 550-581
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 19th International Conference
publication_identifier:
eissn:
- 1611-3349
isbn:
- 9-783-0309-0452-4
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
record:
- id: '10048'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: The cost of adaptivity in security games on graphs
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 13043
year: '2021'
...
---
_id: '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: '9825'
abstract:
- lang: eng
text: "The dual attack has long been considered a relevant attack on lattice-based
cryptographic schemes relying on the hardness of learning with errors (LWE) and
its structured variants. As solving LWE corresponds to finding a nearest point
on a lattice, one may naturally wonder how efficient this dual approach is for
solving more general closest vector problems, such as the classical closest vector
problem (CVP), the variants bounded distance decoding (BDD) and approximate CVP,
and preprocessing versions of these problems. While primal, sieving-based solutions
to these problems (with preprocessing) were recently studied in a series of works
on approximate Voronoi cells [Laa16b, DLdW19, Laa20, DLvW20], for the dual attack
no such overview exists, especially for problems with preprocessing. With one
of the take-away messages of the approximate Voronoi cell line of work being that
primal attacks work well for approximate CVP(P) but scale poorly for BDD(P), one
may further wonder if the dual attack suffers the same drawbacks, or if it is
perhaps a better solution when trying to solve BDD(P).\r\n\r\nIn this work we
provide an overview of cost estimates for dual algorithms for solving these “classical”
closest lattice vector problems. Heuristically we expect to solve the search version
of average-case CVPP in time and space 20.293\U0001D451+\U0001D45C(\U0001D451)
\ in the single-target model. The distinguishing version of average-case CVPP,
where we wish to distinguish between random targets and targets planted at distance
(say) 0.99⋅\U0001D454\U0001D451 from the lattice, has the same complexity in
the single-target model, but can be solved in time and space 20.195\U0001D451+\U0001D45C(\U0001D451)
\ in the multi-target setting, when given a large number of targets from either
target distribution. This suggests an inequivalence between distinguishing and
searching, as we do not expect a similar improvement in the multi-target setting
to hold for search-CVPP. We analyze three slightly different decoders, both for
distinguishing and searching, and experimentally obtain concrete cost estimates
for the dual attack in dimensions 50 to 80, which confirm our heuristic assumptions,
and show that the hidden order terms in the asymptotic estimates are quite small.\r\n\r\nOur
main take-away message is that the dual attack appears to mirror the approximate
Voronoi cell line of work – whereas using approximate Voronoi cells works well
for approximate CVP(P) but scales poorly for BDD(P), the dual approach scales
well for BDD(P) instances but performs poorly on approximate CVP(P)."
acknowledgement: The authors thank Sauvik Bhattacharya, L´eo Ducas, Rachel Player,
and Christine van Vredendaal for early discussions on this topic and on preliminary
results. The authors further thank the reviewers of CT-RSA 2021 for their valuable
feedback.
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Thijs
full_name: Laarhoven, Thijs
last_name: Laarhoven
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Laarhoven T, Walter M. Dual lattice attacks for closest vector problems (with
preprocessing). In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer
Nature; 2021:478-502. doi:10.1007/978-3-030-75539-3_20'
apa: 'Laarhoven, T., & Walter, M. (2021). Dual lattice attacks for closest vector
problems (with preprocessing). In Topics in Cryptology – CT-RSA 2021 (Vol.
12704, pp. 478–502). Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_20'
chicago: Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest
Vector Problems (with Preprocessing).” In Topics in Cryptology – CT-RSA 2021,
12704:478–502. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_20.
ieee: T. Laarhoven and M. Walter, “Dual lattice attacks for closest vector problems
(with preprocessing),” in Topics in Cryptology – CT-RSA 2021, Virtual Event,
2021, vol. 12704, pp. 478–502.
ista: 'Laarhoven T, Walter M. 2021. Dual lattice attacks for closest vector problems
(with preprocessing). Topics in Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’
Track at the RSA Conference, LNCS, vol. 12704, 478–502.'
mla: Laarhoven, Thijs, and Michael Walter. “Dual Lattice Attacks for Closest Vector
Problems (with Preprocessing).” Topics in Cryptology – CT-RSA 2021, vol.
12704, Springer Nature, 2021, pp. 478–502, doi:10.1007/978-3-030-75539-3_20.
short: T. Laarhoven, M. Walter, in:, Topics in Cryptology – CT-RSA 2021, Springer
Nature, 2021, pp. 478–502.
conference:
end_date: 2021-05-20
location: Virtual Event
name: 'CT-RSA: Cryptographers’ Track at the RSA Conference'
start_date: 2021-05-17
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2023-02-23T14:09:54Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-030-75539-3_20
intvolume: ' 12704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2021/557
month: '05'
oa: 1
oa_version: Preprint
page: 478-502
publication: Topics in Cryptology – CT-RSA 2021
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030755386'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Dual lattice attacks for closest vector problems (with preprocessing)
type: conference
user_id: 6785fbc1-c503-11eb-8a32-93094b40e1cf
volume: 12704
year: '2021'
...
---
_id: '9826'
abstract:
- lang: eng
text: "Automated contract tracing aims at supporting manual contact tracing during
pandemics by alerting users of encounters with infected people. There are currently
many proposals for protocols (like the “decentralized” DP-3T and PACT or the “centralized”
ROBERT and DESIRE) to be run on mobile phones, where the basic idea is to regularly
broadcast (using low energy Bluetooth) some values, and at the same time store
(a function of) incoming messages broadcasted by users in their proximity. In
the existing proposals one can trigger false positives on a massive scale by an
“inverse-Sybil” attack, where a large number of devices (malicious users or hacked
phones) pretend to be the same user, such that later, just a single person needs
to be diagnosed (and allowed to upload) to trigger an alert for all users who
were in proximity to any of this large group of devices.\r\n\r\nWe propose the
first protocols that do not succumb to such attacks assuming the devices involved
in the attack do not constantly communicate, which we observe is a necessary assumption.
The high level idea of the protocols is to derive the values to be broadcasted
by a hash chain, so that two (or more) devices who want to launch an inverse-Sybil
attack will not be able to connect their respective chains and thus only one of
them will be able to upload. Our protocols also achieve security against replay,
belated replay, and one of them even against relay attacks."
acknowledgement: Guillermo Pascual-Perez and Michelle Yeo were funded by the European
Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska–Curie
Grant Agreement No. 665385; the remaining contributors to this project have received
funding from the European Research Council (ERC) under the European Union’s Horizon
2020 research and innovation programme (682815 - TOCNeT).
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Suvradip
full_name: Chakraborty, Suvradip
id: B9CD0494-D033-11E9-B219-A439E6697425
last_name: Chakraborty
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Guillermo
full_name: Pascual Perez, Guillermo
id: 2D7ABD02-F248-11E8-B48F-1D18A9856A87
last_name: Pascual Perez
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
citation:
ama: 'Auerbach B, Chakraborty S, Klein K, et al. Inverse-Sybil attacks in automated
contact tracing. In: Topics in Cryptology – CT-RSA 2021. Vol 12704. Springer
Nature; 2021:399-421. doi:10.1007/978-3-030-75539-3_17'
apa: 'Auerbach, B., Chakraborty, S., Klein, K., Pascual Perez, G., Pietrzak, K.
Z., Walter, M., & Yeo, M. X. (2021). Inverse-Sybil attacks in automated contact
tracing. In Topics in Cryptology – CT-RSA 2021 (Vol. 12704, pp. 399–421).
Virtual Event: Springer Nature. https://doi.org/10.1007/978-3-030-75539-3_17'
chicago: Auerbach, Benedikt, Suvradip Chakraborty, Karen Klein, Guillermo Pascual
Perez, Krzysztof Z Pietrzak, Michael Walter, and Michelle X Yeo. “Inverse-Sybil
Attacks in Automated Contact Tracing.” In Topics in Cryptology – CT-RSA 2021,
12704:399–421. Springer Nature, 2021. https://doi.org/10.1007/978-3-030-75539-3_17.
ieee: B. Auerbach et al., “Inverse-Sybil attacks in automated contact tracing,”
in Topics in Cryptology – CT-RSA 2021, Virtual Event, 2021, vol. 12704,
pp. 399–421.
ista: 'Auerbach B, Chakraborty S, Klein K, Pascual Perez G, Pietrzak KZ, Walter
M, Yeo MX. 2021. Inverse-Sybil attacks in automated contact tracing. Topics in
Cryptology – CT-RSA 2021. CT-RSA: Cryptographers’ Track at the RSA Conference,
LNCS, vol. 12704, 399–421.'
mla: Auerbach, Benedikt, et al. “Inverse-Sybil Attacks in Automated Contact Tracing.”
Topics in Cryptology – CT-RSA 2021, vol. 12704, Springer Nature, 2021,
pp. 399–421, doi:10.1007/978-3-030-75539-3_17.
short: B. Auerbach, S. Chakraborty, K. Klein, G. Pascual Perez, K.Z. Pietrzak, M.
Walter, M.X. Yeo, in:, Topics in Cryptology – CT-RSA 2021, Springer Nature, 2021,
pp. 399–421.
conference:
end_date: 2021-05-20
location: Virtual Event
name: 'CT-RSA: Cryptographers’ Track at the RSA Conference'
start_date: 2021-05-17
date_created: 2021-08-08T22:01:30Z
date_published: 2021-05-11T00:00:00Z
date_updated: 2023-02-23T14:09:56Z
day: '11'
department:
- _id: KrPi
- _id: GradSch
doi: 10.1007/978-3-030-75539-3_17
ec_funded: 1
intvolume: ' 12704'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/670
month: '05'
oa: 1
oa_version: Submitted Version
page: 399-421
project:
- _id: 2564DBCA-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '665385'
name: International IST Doctoral Program
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Topics in Cryptology – CT-RSA 2021
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030755386'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Inverse-Sybil attacks in automated contact tracing
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12704
year: '2021'
...
---
_id: '9969'
abstract:
- lang: eng
text: 'Payment channel networks are a promising approach to improve the scalability
of cryptocurrencies: they allow to perform transactions in a peer-to-peer fashion,
along multihop routes in the network, without requiring consensus on the blockchain.
However, during the discovery of cost-efficient routes for the transaction, critical
information may be revealed about the transacting entities. This paper initiates
the study of privacy-preserving route discovery mechanisms for payment channel
networks. In particular, we present LightPIR, an approach which allows a client
to learn the shortest (or cheapest in terms of fees) path between two nodes without
revealing any information about the endpoints of the transaction to the servers.
The two main observations which allow for an efficient solution in LightPIR are
that: (1) surprisingly, hub labelling algorithms – which were developed to preprocess
“street network like” graphs so one can later efficiently compute shortest paths
– also perform well for the graphs underlying payment channel networks, and that
(2) hub labelling algorithms can be conveniently combined with private information
retrieval. LightPIR relies on a simple hub labeling heuristic on top of existing
hub labeling algorithms which leverages the specific topological features of cryptocurrency
networks to further minimize storage and bandwidth overheads. In a case study
considering the Lightning network, we show that our approach is an order of magnitude
more efficient compared to a privacy-preserving baseline based on using private
information retrieval on a database that stores all pairs shortest paths.'
article_processing_charge: No
arxiv: 1
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Iosif
full_name: Salem, Iosif
last_name: Salem
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
citation:
ama: 'Pietrzak KZ, Salem I, Schmid S, Yeo MX. LightPIR: Privacy-preserving route
discovery for payment channel networks. In: IEEE; 2021. doi:10.23919/IFIPNetworking52078.2021.9472205'
apa: 'Pietrzak, K. Z., Salem, I., Schmid, S., & Yeo, M. X. (2021). LightPIR:
Privacy-preserving route discovery for payment channel networks. Presented at
the 2021 IFIP Networking Conference (IFIP Networking), Espoo and Helsinki, Finland:
IEEE. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205'
chicago: 'Pietrzak, Krzysztof Z, Iosif Salem, Stefan Schmid, and Michelle X Yeo.
“LightPIR: Privacy-Preserving Route Discovery for Payment Channel Networks.” IEEE,
2021. https://doi.org/10.23919/IFIPNetworking52078.2021.9472205.'
ieee: 'K. Z. Pietrzak, I. Salem, S. Schmid, and M. X. Yeo, “LightPIR: Privacy-preserving
route discovery for payment channel networks,” presented at the 2021 IFIP Networking
Conference (IFIP Networking), Espoo and Helsinki, Finland, 2021.'
ista: 'Pietrzak KZ, Salem I, Schmid S, Yeo MX. 2021. LightPIR: Privacy-preserving
route discovery for payment channel networks. 2021 IFIP Networking Conference
(IFIP Networking).'
mla: 'Pietrzak, Krzysztof Z., et al. LightPIR: Privacy-Preserving Route Discovery
for Payment Channel Networks. IEEE, 2021, doi:10.23919/IFIPNetworking52078.2021.9472205.'
short: K.Z. Pietrzak, I. Salem, S. Schmid, M.X. Yeo, in:, IEEE, 2021.
conference:
end_date: 2021-06-24
location: Espoo and Helsinki, Finland
name: 2021 IFIP Networking Conference (IFIP Networking)
start_date: 2021-06-21
date_created: 2021-08-29T22:01:16Z
date_published: 2021-06-21T00:00:00Z
date_updated: 2023-11-30T10:54:50Z
day: '21'
department:
- _id: KrPi
doi: 10.23919/IFIPNetworking52078.2021.9472205
ec_funded: 1
external_id:
arxiv:
- '2104.04293'
isi:
- '000853016800008'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/2104.04293
month: '06'
oa: 1
oa_version: Submitted Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
eisbn:
- 978-3-9031-7639-3
eissn:
- 1861-2288
isbn:
- 978-1-6654-4501-6
publication_status: published
publisher: IEEE
quality_controlled: '1'
related_material:
record:
- id: '14506'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'LightPIR: Privacy-preserving route discovery for payment channel networks'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2021'
...
---
_id: '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
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.
date_created: 2020-05-26T14:08:55Z
date_published: 2020-05-25T00:00:00Z
date_updated: 2023-09-07T13:15:55Z
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: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2020'
...
---
_id: '7966'
abstract:
- lang: eng
text: "For 1≤m≤n, we consider a natural m-out-of-n multi-instance scenario for a
public-key encryption (PKE) scheme. An adversary, given n independent instances
of PKE, wins if he breaks at least m out of the n instances. In this work, we
are interested in the scaling factor of PKE schemes, SF, which measures how well
the difficulty of breaking m out of the n instances scales in m. That is, a scaling
factor SF=ℓ indicates that breaking m out of n instances is at least ℓ times more
difficult than breaking one single instance. A PKE scheme with small scaling factor
hence provides an ideal target for mass surveillance. In fact, the Logjam attack
(CCS 2015) implicitly exploited, among other things, an almost constant scaling
factor of ElGamal over finite fields (with shared group parameters).\r\n\r\nFor
Hashed ElGamal over elliptic curves, we use the generic group model to argue that
the scaling factor depends on the scheme's granularity. In low granularity, meaning
each public key contains its independent group parameter, the scheme has optimal
scaling factor SF=m; In medium and high granularity, meaning all public keys share
the same group parameter, the scheme still has a reasonable scaling factor SF=√m.
Our findings underline that instantiating ElGamal over elliptic curves should
be preferred to finite fields in a multi-instance scenario.\r\n\r\nAs our main
technical contribution, we derive new generic-group lower bounds of Ω(√(mp)) on
the difficulty of solving both the m-out-of-n Gap Discrete Logarithm and the m-out-of-n
Gap Computational Diffie-Hellman problem over groups of prime order p, extending
a recent result by Yun (EUROCRYPT 2015). We establish the lower bound by studying
the hardness of a related computational problem which we call the search-by-hypersurface
problem."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Benedikt
full_name: Auerbach, Benedikt
id: D33D2B18-E445-11E9-ABB7-15F4E5697425
last_name: Auerbach
orcid: 0000-0002-7553-6606
- first_name: Federico
full_name: Giacon, Federico
last_name: Giacon
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
citation:
ama: 'Auerbach B, Giacon F, Kiltz E. Everybody’s a target: Scalability in public-key
encryption. In: Advances in Cryptology – EUROCRYPT 2020. Vol 12107. Springer
Nature; 2020:475-506. doi:10.1007/978-3-030-45727-3_16'
apa: 'Auerbach, B., Giacon, F., & Kiltz, E. (2020). Everybody’s a target: Scalability
in public-key encryption. In Advances in Cryptology – EUROCRYPT 2020 (Vol.
12107, pp. 475–506). Springer Nature. https://doi.org/10.1007/978-3-030-45727-3_16'
chicago: 'Auerbach, Benedikt, Federico Giacon, and Eike Kiltz. “Everybody’s a Target:
Scalability in Public-Key Encryption.” In Advances in Cryptology – EUROCRYPT
2020, 12107:475–506. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45727-3_16.'
ieee: 'B. Auerbach, F. Giacon, and E. Kiltz, “Everybody’s a target: Scalability
in public-key encryption,” in Advances in Cryptology – EUROCRYPT 2020,
2020, vol. 12107, pp. 475–506.'
ista: 'Auerbach B, Giacon F, Kiltz E. 2020. Everybody’s a target: Scalability in
public-key encryption. Advances in Cryptology – EUROCRYPT 2020. EUROCRYPT: Theory
and Applications of Cryptographic Techniques, LNCS, vol. 12107, 475–506.'
mla: 'Auerbach, Benedikt, et al. “Everybody’s a Target: Scalability in Public-Key
Encryption.” Advances in Cryptology – EUROCRYPT 2020, vol. 12107, Springer
Nature, 2020, pp. 475–506, doi:10.1007/978-3-030-45727-3_16.'
short: B. Auerbach, F. Giacon, E. Kiltz, in:, Advances in Cryptology – EUROCRYPT
2020, Springer Nature, 2020, pp. 475–506.
conference:
end_date: 2020-05-15
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2020-05-11
date_created: 2020-06-15T07:13:37Z
date_published: 2020-05-01T00:00:00Z
date_updated: 2023-09-05T15:06:40Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-030-45727-3_16
ec_funded: 1
external_id:
isi:
- '000828688000016'
intvolume: ' 12107'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/364
month: '05'
oa: 1
oa_version: Submitted Version
page: 475-506
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – EUROCRYPT 2020
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030457266'
- '9783030457273'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
status: public
title: 'Everybody’s a target: Scalability in public-key encryption'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 12107
year: '2020'
...
---
_id: '8322'
abstract:
- lang: eng
text: "Reverse firewalls were introduced at Eurocrypt 2015 by Miro-nov and Stephens-Davidowitz,
as a method for protecting cryptographic protocols against attacks on the devices
of the honest parties. In a nutshell: a reverse firewall is placed outside of
a device and its goal is to “sanitize” the messages sent by it, in such a way
that a malicious device cannot leak its secrets to the outside world. It is typically
assumed that the cryptographic devices are attacked in a “functionality-preserving
way” (i.e. informally speaking, the functionality of the protocol remains unchanged
under this attacks). In their paper, Mironov and Stephens-Davidowitz construct
a protocol for passively-secure two-party computations with firewalls, leaving
extension of this result to stronger models as an open question.\r\nIn this paper,
we address this problem by constructing a protocol for secure computation with
firewalls that has two main advantages over the original protocol from Eurocrypt
2015. Firstly, it is a multiparty computation protocol (i.e. it works for an arbitrary
number n of the parties, and not just for 2). Secondly, it is secure in much stronger
corruption settings, namely in the active corruption model. More precisely: we
consider an adversary that can fully corrupt up to \U0001D45B−1 parties, while
the remaining parties are corrupt in a functionality-preserving way.\r\nOur core
techniques are: malleable commitments and malleable non-interactive zero-knowledge,
which in particular allow us to create a novel protocol for multiparty augmented
coin-tossing into the well with reverse firewalls (that is based on a protocol
of Lindell from Crypto 2001)."
acknowledgement: We would like to thank the anonymous reviewers for their helpful
comments and suggestions. The work was initiated while the first author was in IIT
Madras, India. Part of this work was done while the author was visiting the University
of Warsaw. This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(682815 - TOCNeT) and from the Foundation for Polish Science under grant TEAM/2016-1/4
founded within the UE 2014–2020 Smart Growth Operational Program. The last author
was supported by the Independent Research Fund Denmark project BETHE and the Concordium
Blockchain Research Center, Aarhus University, Denmark.
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: Jesper Buus
full_name: Nielsen, Jesper Buus
last_name: Nielsen
citation:
ama: 'Chakraborty S, Dziembowski S, Nielsen JB. Reverse firewalls for actively secure MPCs.
In: Advances in Cryptology – CRYPTO 2020. Vol 12171. Springer Nature; 2020:732-762.
doi:10.1007/978-3-030-56880-1_26'
apa: 'Chakraborty, S., Dziembowski, S., & Nielsen, J. B. (2020). Reverse firewalls for actively secure MPCs.
In Advances in Cryptology – CRYPTO 2020 (Vol. 12171, pp. 732–762). Santa
Barbara, CA, United States: Springer Nature. https://doi.org/10.1007/978-3-030-56880-1_26'
chicago: Chakraborty, Suvradip, Stefan Dziembowski, and Jesper Buus Nielsen. “Reverse Firewalls for Actively Secure MPCs.”
In Advances in Cryptology – CRYPTO 2020, 12171:732–62. Springer Nature,
2020. https://doi.org/10.1007/978-3-030-56880-1_26.
ieee: S. Chakraborty, S. Dziembowski, and J. B. Nielsen, “Reverse firewalls for actively secure MPCs,”
in Advances in Cryptology – CRYPTO 2020, Santa Barbara, CA, United States,
2020, vol. 12171, pp. 732–762.
ista: 'Chakraborty S, Dziembowski S, Nielsen JB. 2020. Reverse firewalls for actively secure MPCs.
Advances in Cryptology – CRYPTO 2020. CRYPTO: Annual International Cryptology
Conference, LNCS, vol. 12171, 732–762.'
mla: Chakraborty, Suvradip, et al. “Reverse Firewalls for Actively Secure MPCs.”
Advances in Cryptology – CRYPTO 2020, vol. 12171, Springer Nature, 2020,
pp. 732–62, doi:10.1007/978-3-030-56880-1_26.
short: S. Chakraborty, S. Dziembowski, J.B. Nielsen, in:, Advances in Cryptology
– CRYPTO 2020, Springer Nature, 2020, pp. 732–762.
conference:
end_date: 2020-08-21
location: Santa Barbara, CA, United States
name: 'CRYPTO: Annual International Cryptology Conference'
start_date: 2020-08-17
date_created: 2020-08-30T22:01:12Z
date_published: 2020-08-10T00:00:00Z
date_updated: 2021-01-12T08:18:08Z
day: '10'
department:
- _id: KrPi
doi: 10.1007/978-3-030-56880-1_26
ec_funded: 1
intvolume: ' 12171'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/1317
month: '08'
oa: 1
oa_version: Preprint
page: 732-762
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – CRYPTO 2020
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030568795'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reverse firewalls for actively secure MPCs
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12171
year: '2020'
...
---
_id: '8339'
abstract:
- lang: eng
text: "Discrete Gaussian distributions over lattices are central to lattice-based
cryptography, and to the computational and mathematical aspects of lattices more
broadly. The literature contains a wealth of useful theorems about the behavior
of discrete Gaussians under convolutions and related operations. Yet despite their
structural similarities, most of these theorems are formally incomparable, and
their proofs tend to be monolithic and written nearly “from scratch,” making them
unnecessarily hard to verify, understand, and extend.\r\nIn this work we present
a modular framework for analyzing linear operations on discrete Gaussian distributions.
The framework abstracts away the particulars of Gaussians, and usually reduces
proofs to the choice of appropriate linear transformations and elementary linear
algebra. To showcase the approach, we establish several general properties of
discrete Gaussians, and show how to obtain all prior convolution theorems (along
with some new ones) as straightforward corollaries. As another application, we
describe a self-reduction for Learning With Errors (LWE) that uses a fixed number
of samples to generate an unlimited number of additional ones (having somewhat
larger error). The distinguishing features of our reduction are its simple analysis
in our framework, and its exclusive use of discrete Gaussians without any loss
in parameters relative to a prior mixed discrete-and-continuous approach.\r\nAs
a contribution of independent interest, for subgaussian random matrices we prove
a singular value concentration bound with explicitly stated constants, and we
give tighter heuristics for specific distributions that are commonly used for
generating lattice trapdoors. These bounds yield improvements in the concrete
bit-security estimates for trapdoor lattice cryptosystems."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Nicholas
full_name: Genise, Nicholas
last_name: Genise
- first_name: Daniele
full_name: Micciancio, Daniele
last_name: Micciancio
- first_name: Chris
full_name: Peikert, Chris
last_name: Peikert
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Genise N, Micciancio D, Peikert C, Walter M. Improved discrete Gaussian and
subgaussian analysis for lattice cryptography. In: 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography. Vol 12110.
Springer Nature; 2020:623-651. doi:10.1007/978-3-030-45374-9_21'
apa: 'Genise, N., Micciancio, D., Peikert, C., & Walter, M. (2020). Improved
discrete Gaussian and subgaussian analysis for lattice cryptography. In 23rd
IACR International Conference on the Practice and Theory of Public-Key Cryptography
(Vol. 12110, pp. 623–651). Edinburgh, United Kingdom: Springer Nature. https://doi.org/10.1007/978-3-030-45374-9_21'
chicago: Genise, Nicholas, Daniele Micciancio, Chris Peikert, and Michael Walter.
“Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography.”
In 23rd IACR International Conference on the Practice and Theory of Public-Key
Cryptography, 12110:623–51. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-45374-9_21.
ieee: N. Genise, D. Micciancio, C. Peikert, and M. Walter, “Improved discrete Gaussian
and subgaussian analysis for lattice cryptography,” in 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography, Edinburgh,
United Kingdom, 2020, vol. 12110, pp. 623–651.
ista: 'Genise N, Micciancio D, Peikert C, Walter M. 2020. Improved discrete Gaussian
and subgaussian analysis for lattice cryptography. 23rd IACR International Conference
on the Practice and Theory of Public-Key Cryptography. PKC: Public-Key Cryptography,
LNCS, vol. 12110, 623–651.'
mla: Genise, Nicholas, et al. “Improved Discrete Gaussian and Subgaussian Analysis
for Lattice Cryptography.” 23rd IACR International Conference on the Practice
and Theory of Public-Key Cryptography, vol. 12110, Springer Nature, 2020,
pp. 623–51, doi:10.1007/978-3-030-45374-9_21.
short: N. Genise, D. Micciancio, C. Peikert, M. Walter, in:, 23rd IACR International
Conference on the Practice and Theory of Public-Key Cryptography, Springer Nature,
2020, pp. 623–651.
conference:
end_date: 2020-05-07
location: Edinburgh, United Kingdom
name: 'PKC: Public-Key Cryptography'
start_date: 2020-05-04
date_created: 2020-09-06T22:01:13Z
date_published: 2020-05-15T00:00:00Z
date_updated: 2023-02-23T13:31:06Z
day: '15'
department:
- _id: KrPi
doi: 10.1007/978-3-030-45374-9_21
ec_funded: 1
intvolume: ' 12110'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/337
month: '05'
oa: 1
oa_version: Preprint
page: 623-651
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 23rd IACR International Conference on the Practice and Theory of Public-Key
Cryptography
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030453732'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Improved discrete Gaussian and subgaussian analysis for lattice cryptography
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 12110
year: '2020'
...
---
_id: '8987'
abstract:
- lang: eng
text: "Currently several projects aim at designing and implementing protocols for
privacy preserving automated contact tracing to help fight the current pandemic.
Those proposal are quite similar, and in their most basic form basically propose
an app for mobile phones which broadcasts frequently changing pseudorandom identifiers
via (low energy) Bluetooth, and at the same time, the app stores IDs broadcast
by phones in its proximity. Only if a user is tested positive, they upload either
the beacons they did broadcast (which is the case in decentralized proposals as
DP-3T, east and west coast PACT or Covid watch) or received (as in Popp-PT or
ROBERT) during the last two weeks or so.\r\n\r\nVaudenay [eprint 2020/399] observes
that this basic scheme (he considers the DP-3T proposal) succumbs to relay and
even replay attacks, and proposes more complex interactive schemes which prevent
those attacks without giving up too many privacy aspects. Unfortunately interaction
is problematic for this application for efficiency and security reasons. The countermeasures
that have been suggested so far are either not practical or give up on key privacy
aspects. We propose a simple non-interactive variant of the basic protocol that\r\n(security)
Provably prevents replay and (if location data is available) relay attacks.\r\n(privacy)
The data of all parties (even jointly) reveals no information on the location
or time where encounters happened.\r\n(efficiency) The broadcasted message can
fit into 128 bits and uses only basic crypto (commitments and secret key authentication).\r\n\r\nTowards
this end we introduce the concept of “delayed authentication”, which basically
is a message authentication code where verification can be done in two steps,
where the first doesn’t require the key, and the second doesn’t require the message."
article_processing_charge: No
author:
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Pietrzak KZ. Delayed authentication: Preventing replay and relay attacks in
private contact tracing. In: Progress in Cryptology. Vol 12578. LNCS. Springer
Nature; 2020:3-15. doi:10.1007/978-3-030-65277-7_1'
apa: 'Pietrzak, K. Z. (2020). Delayed authentication: Preventing replay and relay
attacks in private contact tracing. In Progress in Cryptology (Vol. 12578,
pp. 3–15). Bangalore, India: Springer Nature. https://doi.org/10.1007/978-3-030-65277-7_1'
chicago: 'Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and
Relay Attacks in Private Contact Tracing.” In Progress in Cryptology, 12578:3–15.
LNCS. Springer Nature, 2020. https://doi.org/10.1007/978-3-030-65277-7_1.'
ieee: 'K. Z. Pietrzak, “Delayed authentication: Preventing replay and relay attacks
in private contact tracing,” in Progress in Cryptology, Bangalore, India,
2020, vol. 12578, pp. 3–15.'
ista: 'Pietrzak KZ. 2020. Delayed authentication: Preventing replay and relay attacks
in private contact tracing. Progress in Cryptology. INDOCRYPT: International Conference
on Cryptology in IndiaLNCS vol. 12578, 3–15.'
mla: 'Pietrzak, Krzysztof Z. “Delayed Authentication: Preventing Replay and Relay
Attacks in Private Contact Tracing.” Progress in Cryptology, vol. 12578,
Springer Nature, 2020, pp. 3–15, doi:10.1007/978-3-030-65277-7_1.'
short: K.Z. Pietrzak, in:, Progress in Cryptology, Springer Nature, 2020, pp. 3–15.
conference:
end_date: 2020-12-16
location: Bangalore, India
name: 'INDOCRYPT: International Conference on Cryptology in India'
start_date: 2020-12-13
date_created: 2021-01-03T23:01:23Z
date_published: 2020-12-08T00:00:00Z
date_updated: 2023-08-24T11:08:58Z
day: '08'
department:
- _id: KrPi
doi: 10.1007/978-3-030-65277-7_1
ec_funded: 1
external_id:
isi:
- '000927592800001'
intvolume: ' 12578'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2020/418
month: '12'
oa: 1
oa_version: Preprint
page: 3-15
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology
publication_identifier:
eissn:
- '16113349'
isbn:
- '9783030652760'
issn:
- '03029743'
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: 'Delayed authentication: Preventing replay and relay attacks in private contact
tracing'
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
volume: 12578
year: '2020'
...
---
_id: '6677'
abstract:
- lang: eng
text: "The Fiat-Shamir heuristic transforms a public-coin interactive proof into
a non-interactive argument, by replacing the verifier with a cryptographic hash
function that is applied to the protocol’s transcript. Constructing hash functions
for which this transformation is sound is a central and long-standing open question
in cryptography.\r\n\r\nWe show that solving the END−OF−METERED−LINE problem is
no easier than breaking the soundness of the Fiat-Shamir transformation when applied
to the sumcheck protocol. In particular, if the transformed protocol is sound,
then any hard problem in #P gives rise to a hard distribution in the class CLS,
which is contained in PPAD. Our result opens up the possibility of sampling moderately-sized
games for which it is hard to find a Nash equilibrium, by reducing the inversion
of appropriately chosen one-way functions to #SAT.\r\n\r\nOur main technical contribution
is a stateful incrementally verifiable procedure that, given a SAT instance over
n variables, counts the number of satisfying assignments. This is accomplished
via an exponential sequence of small steps, each computable in time poly(n). Incremental
verifiability means that each intermediate state includes a sumcheck-based proof
of its correctness, and the proof can be updated and verified in time poly(n)."
article_processing_charge: No
author:
- first_name: Arka Rai
full_name: Choudhuri, Arka Rai
last_name: Choudhuri
- first_name: Pavel
full_name: Hubáček, Pavel
last_name: Hubáček
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Alon
full_name: Rosen, Alon
last_name: Rosen
- first_name: Guy N.
full_name: Rothblum, Guy N.
last_name: Rothblum
citation:
ama: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
GN. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. In: Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019.
ACM Press; 2019:1103-1114. doi:10.1145/3313276.3316400'
apa: 'Choudhuri, A. R., Hubáček, P., Kamath Hosdurg, C., Pietrzak, K. Z., Rosen,
A., & Rothblum, G. N. (2019). Finding a Nash equilibrium is no easier than
breaking Fiat-Shamir. In Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2019 (pp. 1103–1114). Phoenix, AZ, United States:
ACM Press. https://doi.org/10.1145/3313276.3316400'
chicago: Choudhuri, Arka Rai, Pavel Hubáček, Chethan Kamath Hosdurg, Krzysztof Z
Pietrzak, Alon Rosen, and Guy N. Rothblum. “Finding a Nash Equilibrium Is No Easier
than Breaking Fiat-Shamir.” In Proceedings of the 51st Annual ACM SIGACT Symposium
on Theory of Computing - STOC 2019, 1103–14. ACM Press, 2019. https://doi.org/10.1145/3313276.3316400.
ieee: A. R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K. Z. Pietrzak, A. Rosen,
and G. N. Rothblum, “Finding a Nash equilibrium is no easier than breaking Fiat-Shamir,”
in Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing
- STOC 2019, Phoenix, AZ, United States, 2019, pp. 1103–1114.
ista: 'Choudhuri AR, Hubáček P, Kamath Hosdurg C, Pietrzak KZ, Rosen A, Rothblum
GN. 2019. Finding a Nash equilibrium is no easier than breaking Fiat-Shamir. Proceedings
of the 51st Annual ACM SIGACT Symposium on Theory of Computing - STOC 2019. STOC:
Symposium on Theory of Computing, 1103–1114.'
mla: Choudhuri, Arka Rai, et al. “Finding a Nash Equilibrium Is No Easier than Breaking
Fiat-Shamir.” Proceedings of the 51st Annual ACM SIGACT Symposium on Theory
of Computing - STOC 2019, ACM Press, 2019, pp. 1103–14, doi:10.1145/3313276.3316400.
short: A.R. Choudhuri, P. Hubáček, C. Kamath Hosdurg, K.Z. Pietrzak, A. Rosen, G.N.
Rothblum, in:, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of
Computing - STOC 2019, ACM Press, 2019, pp. 1103–1114.
conference:
end_date: 2019-06-26
location: Phoenix, AZ, United States
name: 'STOC: Symposium on Theory of Computing'
start_date: 2019-06-23
date_created: 2019-07-24T09:20:53Z
date_published: 2019-06-01T00:00:00Z
date_updated: 2023-09-07T13:15:55Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/3313276.3316400
ec_funded: 1
external_id:
isi:
- '000523199100100'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/549
month: '06'
oa: 1
oa_version: Preprint
page: 1103-1114
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing -
STOC 2019
publication_identifier:
isbn:
- '9781450367059'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
related_material:
record:
- id: '7896'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
type: conference
user_id: 4359f0d1-fa6c-11eb-b949-802e58b17ae8
year: '2019'
...
---
_id: '6726'
abstract:
- lang: eng
text: Randomness is an essential part of any secure cryptosystem, but many constructions
rely on distributions that are not uniform. This is particularly true for lattice
based cryptosystems, which more often than not make use of discrete Gaussian distributions
over the integers. For practical purposes it is crucial to evaluate the impact
that approximation errors have on the security of a scheme to provide the best
possible trade-off between security and performance. Recent years have seen surprising
results allowing to use relatively low precision while maintaining high levels
of security. A key insight in these results is that sampling a distribution with
low relative error can provide very strong security guarantees. Since floating
point numbers provide guarantees on the relative approximation error, they seem
a suitable tool in this setting, but it is not obvious which sampling algorithms
can actually profit from them. While previous works have shown that inversion
sampling can be adapted to provide a low relative error (Pöppelmann et al., CHES
2014; Prest, ASIACRYPT 2017), other works have called into question if this is
possible for other sampling techniques (Zheng et al., Eprint report 2018/309).
In this work, we consider all sampling algorithms that are popular in the cryptographic
setting and analyze the relationship of floating point precision and the resulting
relative error. We show that all of the algorithms either natively achieve a low
relative error or can be adapted to do so.
article_processing_charge: No
author:
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Walter M. Sampling the integers with low relative error. In: Buchmann J, Nitaj
A, Rachidi T, eds. Progress in Cryptology – AFRICACRYPT 2019. Vol 11627.
LNCS. Cham: Springer Nature; 2019:157-180. doi:10.1007/978-3-030-23696-0_9'
apa: 'Walter, M. (2019). Sampling the integers with low relative error. In J. Buchmann,
A. Nitaj, & T. Rachidi (Eds.), Progress in Cryptology – AFRICACRYPT 2019
(Vol. 11627, pp. 157–180). Cham: Springer Nature. https://doi.org/10.1007/978-3-030-23696-0_9'
chicago: 'Walter, Michael. “Sampling the Integers with Low Relative Error.” In Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann, A Nitaj, and T Rachidi,
11627:157–80. LNCS. Cham: Springer Nature, 2019. https://doi.org/10.1007/978-3-030-23696-0_9.'
ieee: 'M. Walter, “Sampling the integers with low relative error,” in Progress
in Cryptology – AFRICACRYPT 2019, vol. 11627, J. Buchmann, A. Nitaj, and T.
Rachidi, Eds. Cham: Springer Nature, 2019, pp. 157–180.'
ista: 'Walter M. 2019.Sampling the integers with low relative error. In: Progress
in Cryptology – AFRICACRYPT 2019. vol. 11627, 157–180.'
mla: Walter, Michael. “Sampling the Integers with Low Relative Error.” Progress
in Cryptology – AFRICACRYPT 2019, edited by J Buchmann et al., vol. 11627,
Springer Nature, 2019, pp. 157–80, doi:10.1007/978-3-030-23696-0_9.
short: M. Walter, in:, J. Buchmann, A. Nitaj, T. Rachidi (Eds.), Progress in Cryptology
– AFRICACRYPT 2019, Springer Nature, Cham, 2019, pp. 157–180.
conference:
end_date: 2019-07-11
location: Rabat, Morocco
name: 'AFRICACRYPT: International Conference on Cryptology in Africa'
start_date: 2019-07-09
date_created: 2019-07-29T12:25:31Z
date_published: 2019-06-29T00:00:00Z
date_updated: 2023-02-23T12:50:15Z
day: '29'
department:
- _id: KrPi
doi: 10.1007/978-3-030-23696-0_9
ec_funded: 1
editor:
- first_name: J
full_name: Buchmann, J
last_name: Buchmann
- first_name: A
full_name: Nitaj, A
last_name: Nitaj
- first_name: T
full_name: Rachidi, T
last_name: Rachidi
intvolume: ' 11627'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/068
month: '06'
oa: 1
oa_version: Preprint
page: 157-180
place: Cham
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Progress in Cryptology – AFRICACRYPT 2019
publication_identifier:
eisbn:
- 978-3-0302-3696-0
isbn:
- 978-3-0302-3695-3
issn:
- 0302-9743
- 1611-3349
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
series_title: LNCS
status: public
title: Sampling the integers with low relative error
type: book_chapter
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 11627
year: '2019'
...
---
_id: '7136'
abstract:
- lang: eng
text: "It is well established that the notion of min-entropy fails to satisfy the
\\emph{chain rule} of the form H(X,Y)=H(X|Y)+H(Y), known for Shannon Entropy.
Such a property would help to analyze how min-entropy is split among smaller blocks.
Problems of this kind arise for example when constructing extractors and dispersers.\r\nWe
show that any sequence of variables exhibits a very strong strong block-source
structure (conditional distributions of blocks are nearly flat) when we \\emph{spoil
few correlated bits}. This implies, conditioned on the spoiled bits, that \\emph{splitting-recombination
properties} hold. In particular, we have many nice properties that min-entropy
doesn't obey in general, for example strong chain rules, \"information can't hurt\"
inequalities, equivalences of average and worst-case conditional entropy definitions
and others. Quantitatively, for any sequence X1,…,Xt of random variables over
an alphabet X we prove that, when conditioned on m=t⋅O(loglog|X|+loglog(1/ϵ)+logt)
bits of auxiliary information, all conditional distributions of the form Xi|X2019 IEEE International Symposium on Information Theory. IEEE; 2019. doi:10.1109/isit.2019.8849240'
apa: 'Skórski, M. (2019). Strong chain rules for min-entropy under few bits spoiled.
In 2019 IEEE International Symposium on Information Theory. Paris, France:
IEEE. https://doi.org/10.1109/isit.2019.8849240'
chicago: Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.”
In 2019 IEEE International Symposium on Information Theory. IEEE, 2019.
https://doi.org/10.1109/isit.2019.8849240.
ieee: M. Skórski, “Strong chain rules for min-entropy under few bits spoiled,” in
2019 IEEE International Symposium on Information Theory, Paris, France,
2019.
ista: 'Skórski M. 2019. Strong chain rules for min-entropy under few bits spoiled.
2019 IEEE International Symposium on Information Theory. ISIT: International Symposium
on Information Theory, 8849240.'
mla: Skórski, Maciej. “Strong Chain Rules for Min-Entropy under Few Bits Spoiled.”
2019 IEEE International Symposium on Information Theory, 8849240, IEEE,
2019, doi:10.1109/isit.2019.8849240.
short: M. Skórski, in:, 2019 IEEE International Symposium on Information Theory,
IEEE, 2019.
conference:
end_date: 2019-07-12
location: Paris, France
name: 'ISIT: International Symposium on Information Theory'
start_date: 2019-07-07
date_created: 2019-11-28T10:19:21Z
date_published: 2019-07-01T00:00:00Z
date_updated: 2023-09-06T11:15:41Z
day: '01'
department:
- _id: KrPi
doi: 10.1109/isit.2019.8849240
external_id:
arxiv:
- '1702.08476'
isi:
- '000489100301043'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1702.08476
month: '07'
oa: 1
oa_version: Preprint
publication: 2019 IEEE International Symposium on Information Theory
publication_identifier:
isbn:
- '9781538692912'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: '1'
status: public
title: Strong chain rules for min-entropy under few bits spoiled
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2019'
...
---
_id: '7411'
abstract:
- lang: eng
text: "Proofs of sequential work (PoSW) are proof systems where a prover, upon receiving
a statement χ and a time parameter T computes a proof ϕ(χ,T) which is efficiently
and publicly verifiable. The proof can be computed in T sequential steps, but
not much less, even by a malicious party having large parallelism. A PoSW thus
serves as a proof that T units of time have passed since χ\r\n\r\nwas received.\r\n\r\nPoSW
were introduced by Mahmoody, Moran and Vadhan [MMV11], a simple and practical
construction was only recently proposed by Cohen and Pietrzak [CP18].\r\n\r\nIn
this work we construct a new simple PoSW in the random permutation model which
is almost as simple and efficient as [CP18] but conceptually very different. Whereas
the structure underlying [CP18] is a hash tree, our construction is based on skip
lists and has the interesting property that computing the PoSW is a reversible
computation.\r\nThe fact that the construction is reversible can potentially be
used for new applications like constructing proofs of replication. We also show
how to “embed” the sloth function of Lenstra and Weselowski [LW17] into our PoSW
to get a PoSW where one additionally can verify correctness of the output much
more efficiently than recomputing it (though recent constructions of “verifiable
delay functions” subsume most of the applications this construction was aiming
at)."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Hamza M
full_name: Abusalah, Hamza M
id: 40297222-F248-11E8-B48F-1D18A9856A87
last_name: Abusalah
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Michael
full_name: Walter, Michael
id: 488F98B0-F248-11E8-B48F-1D18A9856A87
last_name: Walter
orcid: 0000-0003-3186-2482
citation:
ama: 'Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. Reversible
proofs of sequential work. In: Advances in Cryptology – EUROCRYPT 2019.
Vol 11477. Springer International Publishing; 2019:277-291. doi:10.1007/978-3-030-17656-3_10'
apa: 'Abusalah, H. M., Kamath Hosdurg, C., Klein, K., Pietrzak, K. Z., & Walter,
M. (2019). Reversible proofs of sequential work. In Advances in Cryptology
– EUROCRYPT 2019 (Vol. 11477, pp. 277–291). Darmstadt, Germany: Springer International
Publishing. https://doi.org/10.1007/978-3-030-17656-3_10'
chicago: Abusalah, Hamza M, Chethan Kamath Hosdurg, Karen Klein, Krzysztof Z Pietrzak,
and Michael Walter. “Reversible Proofs of Sequential Work.” In Advances in
Cryptology – EUROCRYPT 2019, 11477:277–91. Springer International Publishing,
2019. https://doi.org/10.1007/978-3-030-17656-3_10.
ieee: H. M. Abusalah, C. Kamath Hosdurg, K. Klein, K. Z. Pietrzak, and M. Walter,
“Reversible proofs of sequential work,” in Advances in Cryptology – EUROCRYPT
2019, Darmstadt, Germany, 2019, vol. 11477, pp. 277–291.
ista: Abusalah HM, Kamath Hosdurg C, Klein K, Pietrzak KZ, Walter M. 2019. Reversible
proofs of sequential work. Advances in Cryptology – EUROCRYPT 2019. International
Conference on the Theory and Applications of Cryptographic Techniques, LNCS, vol.
11477, 277–291.
mla: Abusalah, Hamza M., et al. “Reversible Proofs of Sequential Work.” Advances
in Cryptology – EUROCRYPT 2019, vol. 11477, Springer International Publishing,
2019, pp. 277–91, doi:10.1007/978-3-030-17656-3_10.
short: H.M. Abusalah, C. Kamath Hosdurg, K. Klein, K.Z. Pietrzak, M. Walter, in:,
Advances in Cryptology – EUROCRYPT 2019, Springer International Publishing, 2019,
pp. 277–291.
conference:
end_date: 2019-05-23
location: Darmstadt, Germany
name: International Conference on the Theory and Applications of Cryptographic Techniques
start_date: 2019-05-19
date_created: 2020-01-30T09:26:14Z
date_published: 2019-04-24T00:00:00Z
date_updated: 2023-09-06T15:26:06Z
day: '24'
department:
- _id: KrPi
doi: 10.1007/978-3-030-17656-3_10
ec_funded: 1
external_id:
isi:
- '000483516200010'
intvolume: ' 11477'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2019/252
month: '04'
oa: 1
oa_version: Submitted Version
page: 277-291
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Advances in Cryptology – EUROCRYPT 2019
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783030176556'
- '9783030176563'
issn:
- 0302-9743
publication_status: published
publisher: Springer International Publishing
quality_controlled: '1'
scopus_import: '1'
status: public
title: Reversible proofs of sequential work
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 11477
year: '2019'
...
---
_id: '5887'
abstract:
- lang: eng
text: 'Cryptographic security is usually defined as a guarantee that holds except
when a bad event with negligible probability occurs, and nothing is guaranteed
in that bad case. However, in settings where such failure can happen with substantial
probability, one needs to provide guarantees even for the bad case. A typical
example is where a (possibly weak) password is used instead of a secure cryptographic
key to protect a session, the bad event being that the adversary correctly guesses
the password. In a situation with multiple such sessions, a per-session guarantee
is desired: any session for which the password has not been guessed remains secure,
independently of whether other sessions have been compromised. A new formalism
for stating such gracefully degrading security guarantees is introduced and applied
to analyze the examples of password-based message authentication and password-based
encryption. While a natural per-message guarantee is achieved for authentication,
the situation of password-based encryption is more delicate: a per-session confidentiality
guarantee only holds against attackers for which the distribution of password-guessing
effort over the sessions is known in advance. In contrast, for more general attackers
without such a restriction, a strong, composable notion of security cannot be
achieved.'
article_processing_charge: No
article_type: original
author:
- first_name: Gregory
full_name: Demay, Gregory
last_name: Demay
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Ueli
full_name: Maurer, Ueli
last_name: Maurer
- first_name: Bjorn
full_name: Tackmann, Bjorn
last_name: Tackmann
citation:
ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based
cryptography revisited. Journal of Computer Security. 2019;27(1):75-111.
doi:10.3233/JCS-181131'
apa: 'Demay, G., Gazi, P., Maurer, U., & Tackmann, B. (2019). Per-session security:
Password-based cryptography revisited. Journal of Computer Security. IOS
Press. https://doi.org/10.3233/JCS-181131'
chicago: 'Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session
Security: Password-Based Cryptography Revisited.” Journal of Computer Security.
IOS Press, 2019. https://doi.org/10.3233/JCS-181131.'
ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based
cryptography revisited,” Journal of Computer Security, vol. 27, no. 1.
IOS Press, pp. 75–111, 2019.'
ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2019. Per-session security: Password-based
cryptography revisited. Journal of Computer Security. 27(1), 75–111.'
mla: 'Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography
Revisited.” Journal of Computer Security, vol. 27, no. 1, IOS Press, 2019,
pp. 75–111, doi:10.3233/JCS-181131.'
short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27
(2019) 75–111.
date_created: 2019-01-27T22:59:10Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:05:08Z
day: '1'
department:
- _id: KrPi
doi: 10.3233/JCS-181131
ec_funded: 1
intvolume: ' 27'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/166
month: '01'
oa: 1
oa_version: Preprint
page: 75-111
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Journal of Computer Security
publication_identifier:
issn:
- 0926227X
publication_status: published
publisher: IOS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Per-session security: Password-based cryptography revisited'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2019'
...