---
_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: '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: '298'
abstract:
- lang: eng
text: "Memory-hard functions (MHF) are functions whose evaluation cost is dominated
by memory cost. MHFs are egalitarian, in the sense that evaluating them on dedicated
hardware (like FPGAs or ASICs) is not much cheaper than on off-the-shelf hardware
(like x86 CPUs). MHFs have interesting cryptographic applications, most notably
to password hashing and securing blockchains.\r\n\r\nAlwen and Serbinenko [STOC’15]
define the cumulative memory complexity (cmc) of a function as the sum (over all
time-steps) of the amount of memory required to compute the function. They advocate
that a good MHF must have high cmc. Unlike previous notions, cmc takes into account
that dedicated hardware might exploit amortization and parallelism. Still, cmc
has been critizised as insufficient, as it fails to capture possible time-memory
trade-offs; as memory cost doesn’t scale linearly, functions with the same cmc
could still have very different actual hardware cost.\r\n\r\nIn this work we address
this problem, and introduce the notion of sustained-memory complexity, which requires
that any algorithm evaluating the function must use a large amount of memory for
many steps. We construct functions (in the parallel random oracle model) whose
sustained-memory complexity is almost optimal: our function can be evaluated using
n steps and O(n/log(n)) memory, in each step making one query to the (fixed-input
length) random oracle, while any algorithm that can make arbitrary many parallel
queries to the random oracle, still needs Ω(n/log(n)) memory for Ω(n) steps.\r\n\r\nAs
has been done for various notions (including cmc) before, we reduce the task of
constructing an MHFs with high sustained-memory complexity to proving pebbling
lower bounds on DAGs. Our main technical contribution is the construction is a
family of DAGs on n nodes with constant indegree with high “sustained-space complexity”,
meaning that any parallel black-pebbling strategy requires Ω(n/log(n)) pebbles
for at least Ω(n) steps.\r\n\r\nAlong the way we construct a family of maximally
“depth-robust” DAGs with maximum indegree O(logn) , improving upon the construction
of Mahmoody et al. [ITCS’13] which had maximum indegree O(log2n⋅"
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Jeremiah
full_name: Blocki, Jeremiah
last_name: Blocki
- 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: 'Alwen JF, Blocki J, Pietrzak KZ. Sustained space complexity. In: Vol 10821.
Springer; 2018:99-130. doi:10.1007/978-3-319-78375-8_4'
apa: 'Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2018). Sustained space complexity
(Vol. 10821, pp. 99–130). Presented at the Eurocrypt 2018: Advances in Cryptology,
Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-319-78375-8_4'
chicago: Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Sustained Space
Complexity,” 10821:99–130. Springer, 2018. https://doi.org/10.1007/978-3-319-78375-8_4.
ieee: 'J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Sustained space complexity,”
presented at the Eurocrypt 2018: Advances in Cryptology, Tel Aviv, Israel, 2018,
vol. 10821, pp. 99–130.'
ista: 'Alwen JF, Blocki J, Pietrzak KZ. 2018. Sustained space complexity. Eurocrypt
2018: Advances in Cryptology, LNCS, vol. 10821, 99–130.'
mla: Alwen, Joel F., et al. Sustained Space Complexity. Vol. 10821, Springer,
2018, pp. 99–130, doi:10.1007/978-3-319-78375-8_4.
short: J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, Springer, 2018, pp. 99–130.
conference:
end_date: 2018-05-03
location: Tel Aviv, Israel
name: 'Eurocrypt 2018: Advances in Cryptology'
start_date: 2018-04-29
date_created: 2018-12-11T11:45:41Z
date_published: 2018-03-31T00:00:00Z
date_updated: 2023-09-19T09:59:30Z
day: '31'
department:
- _id: KrPi
doi: 10.1007/978-3-319-78375-8_4
ec_funded: 1
external_id:
arxiv:
- '1705.05313'
isi:
- '000517098700004'
intvolume: ' 10821'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1705.05313
month: '03'
oa: 1
oa_version: Preprint
page: 99 - 130
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_status: published
publisher: Springer
publist_id: '7583'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Sustained space complexity
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10821
year: '2018'
...
---
_id: '193'
abstract:
- lang: eng
text: 'We show attacks on five data-independent memory-hard functions (iMHF) that
were submitted to the password hashing competition (PHC). Informally, an MHF is
a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly
lower hardware and/or energy cost than evaluating a single instance on a standard
single-core architecture. Data-independent means the memory access pattern of
the function is independent of the input; this makes iMHFs harder to construct
than data-dependent ones, but the latter can be attacked by various side-channel
attacks. Following [Alwen-Blocki''16], we capture the evaluation of an iMHF as
a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of
this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC.
Ideally, one would like the complexity of a DAG underlying an iMHF to be as close
to quadratic in the number of nodes of the graph as possible. Instead, we show
that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2,
TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show
that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have
exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial
property of each underlying DAG (called its depth-robustness. By establishing
upper bounds on this property we are then able to apply the general technique
of [Alwen-Block''16] for analyzing the hardware costs of an iMHF.'
acknowledgement: Leonid Reyzin was supported in part by IST Austria and by US NSF
grants 1012910, 1012798, and 1422965; this research was performed while he was visiting
IST Austria.
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Peter
full_name: Gazi, Peter
last_name: Gazi
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Lenoid
full_name: Reyzin, Lenoid
last_name: Reyzin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: 'Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data
independent password hashing functions. In: Proceedings of the 2018 on Asia
Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534'
apa: 'Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak,
K. Z., … Rybar, M. (2018). On the memory hardness of data independent password
hashing functions. In Proceedings of the 2018 on Asia Conference on Computer
and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534'
chicago: Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F
Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar.
“On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings
of the 2018 on Asia Conference on Computer and Communication Security, 51–65.
ACM, 2018. https://doi.org/10.1145/3196494.3196534.
ieee: J. F. Alwen et al., “On the memory hardness of data independent password
hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.
ista: 'Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin
L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password
hashing functions. Proceedings of the 2018 on Asia Conference on Computer and
Communication Security. ASIACCS: Asia Conference on Computer and Communications
Security , 51–65.'
mla: Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password
Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534.
short: J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak,
L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference
on Computer and Communication Security, ACM, 2018, pp. 51–65.
conference:
end_date: 2018-06-08
location: Incheon, Republic of Korea
name: 'ASIACCS: Asia Conference on Computer and Communications Security '
start_date: 2018-06-04
date_created: 2018-12-11T11:45:07Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2023-09-13T09:13:12Z
day: '01'
department:
- _id: KrPi
- _id: HeEd
- _id: VlKo
doi: 10.1145/3196494.3196534
ec_funded: 1
external_id:
isi:
- '000516620100005'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/783
month: '06'
oa: 1
oa_version: Submitted Version
page: 51 - 65
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 2018 on Asia Conference on Computer and Communication
Security
publication_status: published
publisher: ACM
publist_id: '7723'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the memory hardness of data independent password hashing functions
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '6941'
abstract:
- lang: eng
text: "Bitcoin has become the most successful cryptocurrency ever deployed, and
its most distinctive feature is that it is decentralized. Its underlying protocol
(Nakamoto consensus) achieves this by using proof of work, which has the drawback
that it causes the consumption of vast amounts of energy to maintain the ledger.
Moreover, Bitcoin mining dynamics have become less distributed over time.\r\n\r\nTowards
addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs
of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather
than computation. We argue that SpaceMint’s design solves or alleviates several
of Bitcoin’s issues: most notably, its large energy consumption. SpaceMint also
rewards smaller miners fairly according to their contribution to the network,
thus incentivizing more distributed participation.\r\n\r\nThis paper adapts proof
of space to enable its use in cryptocurrency, studies the attacks that can arise
against a Bitcoin-like blockchain that uses proof of space, and proposes a new
blockchain format and transaction types to address these attacks. Our prototype
shows that initializing 1 TB for mining takes about a day (a one-off setup cost),
and miners spend on average just a fraction of a second per block mined. Finally,
we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the
canonical game-theoretic notion for games that take place over time) and show
that this stylized game satisfies a strong equilibrium notion, thereby arguing
for SpaceMint ’s stability and consensus."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sunoo
full_name: Park, Sunoo
last_name: Park
- first_name: Albert
full_name: Kwon, Albert
last_name: Kwon
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- 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: 'Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. SpaceMint: A
cryptocurrency based on proofs of space. In: 22nd International Conference
on Financial Cryptography and Data Security. Vol 10957. Springer Nature; 2018:480-499.
doi:10.1007/978-3-662-58387-6_26'
apa: 'Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J. F., & Pietrzak,
K. Z. (2018). SpaceMint: A cryptocurrency based on proofs of space. In 22nd
International Conference on Financial Cryptography and Data Security (Vol.
10957, pp. 480–499). Nieuwpoort, Curacao: Springer Nature. https://doi.org/10.1007/978-3-662-58387-6_26'
chicago: 'Park, Sunoo, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joel F Alwen,
and Krzysztof Z Pietrzak. “SpaceMint: A Cryptocurrency Based on Proofs of Space.”
In 22nd International Conference on Financial Cryptography and Data Security,
10957:480–99. Springer Nature, 2018. https://doi.org/10.1007/978-3-662-58387-6_26.'
ieee: 'S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J. F. Alwen, and K. Z. Pietrzak,
“SpaceMint: A cryptocurrency based on proofs of space,” in 22nd International
Conference on Financial Cryptography and Data Security, Nieuwpoort, Curacao,
2018, vol. 10957, pp. 480–499.'
ista: 'Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. 2018. SpaceMint:
A cryptocurrency based on proofs of space. 22nd International Conference on Financial
Cryptography and Data Security. FC: Financial Cryptography and Data Security,
LNCS, vol. 10957, 480–499.'
mla: 'Park, Sunoo, et al. “SpaceMint: A Cryptocurrency Based on Proofs of Space.”
22nd International Conference on Financial Cryptography and Data Security,
vol. 10957, Springer Nature, 2018, pp. 480–99, doi:10.1007/978-3-662-58387-6_26.'
short: S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J.F. Alwen, K.Z. Pietrzak, in:,
22nd International Conference on Financial Cryptography and Data Security, Springer
Nature, 2018, pp. 480–499.
conference:
end_date: 2018-03-02
location: Nieuwpoort, Curacao
name: 'FC: Financial Cryptography and Data Security'
start_date: 2018-02-26
date_created: 2019-10-14T06:35:38Z
date_published: 2018-12-07T00:00:00Z
date_updated: 2023-09-19T15:02:13Z
day: '07'
department:
- _id: KrPi
doi: 10.1007/978-3-662-58387-6_26
ec_funded: 1
external_id:
isi:
- '000540656400026'
intvolume: ' 10957'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2015/528
month: '12'
oa: 1
oa_version: Submitted Version
page: 480-499
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 22nd International Conference on Financial Cryptography and Data Security
publication_identifier:
eissn:
- 1611-3349
isbn:
- '9783662583869'
- '9783662583876'
issn:
- 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'SpaceMint: A cryptocurrency based on proofs of space'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10957
year: '2018'
...
---
_id: '1175'
abstract:
- lang: eng
text: We study space complexity and time-space trade-offs with a focus not on peak
memory usage but on overall memory consumption throughout the computation. Such
a cumulative space measure was introduced for the computational model of parallel
black pebbling by [Alwen and Serbinenko ’15] as a tool for obtaining results in
cryptography. We consider instead the non- deterministic black-white pebble game
and prove optimal cumulative space lower bounds and trade-offs, where in order
to minimize pebbling time the space has to remain large during a significant fraction
of the pebbling. We also initiate the study of cumulative space in proof complexity,
an area where other space complexity measures have been extensively studied during
the last 10–15 years. Using and extending the connection between proof complexity
and pebble games in [Ben-Sasson and Nordström ’08, ’11] we obtain several strong
cumulative space results for (even parallel versions of) the resolution proof
system, and outline some possible future directions of study of this, in our opinion,
natural and interesting space measure.
alternative_title:
- LIPIcs
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Susanna
full_name: De Rezende, Susanna
last_name: De Rezende
- first_name: Jakob
full_name: Nordstrom, Jakob
last_name: Nordstrom
- first_name: Marc
full_name: Vinyals, Marc
last_name: Vinyals
citation:
ama: 'Alwen JF, De Rezende S, Nordstrom J, Vinyals M. Cumulative space in black-white
pebbling and resolution. In: Papadimitriou C, ed. Vol 67. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2017:38:1-38-21. doi:10.4230/LIPIcs.ITCS.2017.38'
apa: 'Alwen, J. F., De Rezende, S., Nordstrom, J., & Vinyals, M. (2017). Cumulative
space in black-white pebbling and resolution. In C. Papadimitriou (Ed.) (Vol.
67, p. 38:1-38-21). Presented at the ITCS: Innovations in Theoretical Computer
Science, Berkeley, CA, United States: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ITCS.2017.38'
chicago: Alwen, Joel F, Susanna De Rezende, Jakob Nordstrom, and Marc Vinyals. “Cumulative
Space in Black-White Pebbling and Resolution.” edited by Christos Papadimitriou,
67:38:1-38-21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.ITCS.2017.38.
ieee: 'J. F. Alwen, S. De Rezende, J. Nordstrom, and M. Vinyals, “Cumulative space
in black-white pebbling and resolution,” presented at the ITCS: Innovations in
Theoretical Computer Science, Berkeley, CA, United States, 2017, vol. 67, p. 38:1-38-21.'
ista: 'Alwen JF, De Rezende S, Nordstrom J, Vinyals M. 2017. Cumulative space in
black-white pebbling and resolution. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 67, 38:1-38-21.'
mla: Alwen, Joel F., et al. Cumulative Space in Black-White Pebbling and Resolution.
Edited by Christos Papadimitriou, vol. 67, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2017, p. 38:1-38-21, doi:10.4230/LIPIcs.ITCS.2017.38.
short: J.F. Alwen, S. De Rezende, J. Nordstrom, M. Vinyals, in:, C. Papadimitriou
(Ed.), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, p. 38:1-38-21.
conference:
end_date: 2017-01-11
location: Berkeley, CA, United States
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2017-01-09
date_created: 2018-12-11T11:50:33Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T06:48:51Z
day: '01'
ddc:
- '005'
- '600'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.ITCS.2017.38
editor:
- first_name: Christos
full_name: Papadimitriou, Christos
last_name: Papadimitriou
file:
- access_level: open_access
checksum: dbc94810be07c2fb1945d5c2a6130e6c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:17:11Z
date_updated: 2020-07-14T12:44:37Z
file_id: '5263'
file_name: IST-2018-927-v1+1_LIPIcs-ITCS-2017-38.pdf
file_size: 557769
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 67'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 38:1-38-21
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6179'
pubrep_id: '927'
quality_controlled: '1'
scopus_import: 1
status: public
title: Cumulative space in black-white pebbling and resolution
tmp:
image: /images/cc_by.png
legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 67
year: '2017'
...
---
_id: '1176'
abstract:
- lang: eng
text: The algorithm Argon2i-B of Biryukov, Dinu and Khovratovich is currently being
considered by the IRTF (Internet Research Task Force) as a new de-facto standard
for password hashing. An older version (Argon2i-A) of the same algorithm was chosen
as the winner of the recent Password Hashing Competition. An important competitor
to Argon2i-B is the recently introduced Balloon Hashing (BH) algorithm of Corrigan-Gibs,
Boneh and Schechter. A key security desiderata for any such algorithm is that
evaluating it (even using a custom device) requires a large amount of memory amortized
across multiple instances. Alwen and Blocki (CRYPTO 2016) introduced a class of
theoretical attacks against Argon2i-A and BH. While these attacks yield large
asymptotic reductions in the amount of memory, it was not, a priori, clear if
(1) they can be extended to the newer Argon2i-B, (2) the attacks are effective
on any algorithm for practical parameter ranges (e.g., 1GB of memory) and (3)
if they can be effectively instantiated against any algorithm under realistic
hardware constrains. In this work we answer all three of these questions in the
affirmative for all three algorithms. This is also the first work to analyze the
security of Argon2i-B. In more detail, we extend the theoretical attacks of Alwen
and Blocki (CRYPTO 2016) to the recent Argon2i-B proposal demonstrating severe
asymptotic deficiencies in its security. Next we introduce several novel heuristics
for improving the attack's concrete memory efficiency even when on-chip memory
bandwidth is bounded. We then simulate our attacks on randomly sampled Argon2i-A,
Argon2i-B and BH instances and measure the resulting memory consumption for various
practical parameter ranges and for a variety of upperbounds on the amount of parallelism
available to the attacker. Finally we describe, implement, and test a new heuristic
for applying the Alwen-Blocki attack to functions employing a technique developed
by Corrigan-Gibs et al. for improving concrete security of memory-hard functions.
We analyze the collected data and show the effects various parameters have on
the memory consumption of the attack. In particular, we can draw several interesting
conclusions about the level of security provided by these functions. · For the
Alwen-Blocki attack to fail against practical memory parameters, Argon2i-B must
be instantiated with more than 10 passes on memory - beyond the "paranoid" parameter
setting in the current IRTF proposal. · The technique of Corrigan-Gibs for improving
security can also be overcome by the Alwen-Blocki attack under realistic hardware
constraints. · On a positive note, both the asymptotic and concrete security of
Argon2i-B seem to improve on that of Argon2i-A.
article_number: '7961977'
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: Jeremiah
full_name: Blocki, Jeremiah
last_name: Blocki
citation:
ama: 'Alwen JF, Blocki J. Towards practical attacks on Argon2i and balloon hashing.
In: IEEE; 2017. doi:10.1109/EuroSP.2017.47'
apa: 'Alwen, J. F., & Blocki, J. (2017). Towards practical attacks on Argon2i
and balloon hashing. Presented at the EuroS&P: European Symposium on Security
and Privacy, Paris, France: IEEE. https://doi.org/10.1109/EuroSP.2017.47'
chicago: Alwen, Joel F, and Jeremiah Blocki. “Towards Practical Attacks on Argon2i
and Balloon Hashing.” IEEE, 2017. https://doi.org/10.1109/EuroSP.2017.47.
ieee: 'J. F. Alwen and J. Blocki, “Towards practical attacks on Argon2i and balloon
hashing,” presented at the EuroS&P: European Symposium on Security and Privacy,
Paris, France, 2017.'
ista: 'Alwen JF, Blocki J. 2017. Towards practical attacks on Argon2i and balloon
hashing. EuroS&P: European Symposium on Security and Privacy, 7961977.'
mla: Alwen, Joel F., and Jeremiah Blocki. Towards Practical Attacks on Argon2i
and Balloon Hashing. 7961977, IEEE, 2017, doi:10.1109/EuroSP.2017.47.
short: J.F. Alwen, J. Blocki, in:, IEEE, 2017.
conference:
end_date: 2017-04-28
location: Paris, France
name: 'EuroS&P: European Symposium on Security and Privacy'
start_date: 2017-04-26
date_created: 2018-12-11T11:50:33Z
date_published: 2017-07-03T00:00:00Z
date_updated: 2023-09-20T11:22:25Z
day: '03'
department:
- _id: KrPi
doi: 10.1109/EuroSP.2017.47
external_id:
isi:
- '000424197300011'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/759
month: '07'
oa: 1
oa_version: Submitted Version
publication_identifier:
isbn:
- 978-150905761-0
publication_status: published
publisher: IEEE
publist_id: '6178'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Towards practical attacks on Argon2i and balloon hashing
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '559'
abstract:
- lang: eng
text: 'Proofs of space (PoS) were suggested as more ecological and economical alternative
to proofs of work, which are currently used in blockchain designs like Bitcoin.
The existing PoS are based on rather sophisticated graph pebbling lower bounds.
Much simpler and in several aspects more efficient schemes based on inverting
random functions have been suggested, but they don’t give meaningful security
guarantees due to existing time-memory trade-offs. In particular, Hellman showed
that any permutation over a domain of size N can be inverted in time T by an algorithm
that is given S bits of auxiliary information whenever (Formula presented). For
functions Hellman gives a weaker attack with S2· T≈ N2 (e.g., S= T≈ N2/3). To
prove lower bounds, one considers an adversary who has access to an oracle f:
[ N] → [N] and can make T oracle queries. The best known lower bound is S· T∈
Ω(N) and holds for random functions and permutations. We construct functions that
provably require more time and/or space to invert. Specifically, for any constant
k we construct a function [N] → [N] that cannot be inverted unless Sk· T∈ Ω(Nk)
(in particular, S= T≈ (Formula presented). Our construction does not contradict
Hellman’s time-memory trade-off, because it cannot be efficiently evaluated in
forward direction. However, its entire function table can be computed in time
quasilinear in N, which is sufficient for the PoS application. Our simplest construction
is built from a random function oracle g: [N] × [N] → [ N] and a random permutation
oracle f: [N] → N] and is defined as h(x) = g(x, x′) where f(x) = π(f(x′)) with
π being any involution without a fixed point, e.g. flipping all the bits. For
this function we prove that any adversary who gets S bits of auxiliary information,
makes at most T oracle queries, and inverts h on an ϵ fraction of outputs must
satisfy S2· T∈ Ω(ϵ2N2).'
alternative_title:
- LNCS
author:
- first_name: Hamza M
full_name: Abusalah, Hamza M
id: 40297222-F248-11E8-B48F-1D18A9856A87
last_name: Abusalah
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Bram
full_name: Cohen, Bram
last_name: Cohen
- first_name: Danylo
full_name: Khilko, Danylo
last_name: Khilko
- 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: Leonid
full_name: Reyzin, Leonid
last_name: Reyzin
citation:
ama: 'Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. Beyond Hellman’s
time-memory trade-offs with applications to proofs of space. In: Vol 10625. Springer;
2017:357-379. doi:10.1007/978-3-319-70697-9_13'
apa: 'Abusalah, H. M., Alwen, J. F., Cohen, B., Khilko, D., Pietrzak, K. Z., &
Reyzin, L. (2017). Beyond Hellman’s time-memory trade-offs with applications to
proofs of space (Vol. 10625, pp. 357–379). Presented at the ASIACRYPT: Theory
and Applications of Cryptology and Information Security, Hong Kong, China: Springer.
https://doi.org/10.1007/978-3-319-70697-9_13'
chicago: Abusalah, Hamza M, Joel F Alwen, Bram Cohen, Danylo Khilko, Krzysztof Z
Pietrzak, and Leonid Reyzin. “Beyond Hellman’s Time-Memory Trade-Offs with Applications
to Proofs of Space,” 10625:357–79. Springer, 2017. https://doi.org/10.1007/978-3-319-70697-9_13.
ieee: 'H. M. Abusalah, J. F. Alwen, B. Cohen, D. Khilko, K. Z. Pietrzak, and L.
Reyzin, “Beyond Hellman’s time-memory trade-offs with applications to proofs of
space,” presented at the ASIACRYPT: Theory and Applications of Cryptology and
Information Security, Hong Kong, China, 2017, vol. 10625, pp. 357–379.'
ista: 'Abusalah HM, Alwen JF, Cohen B, Khilko D, Pietrzak KZ, Reyzin L. 2017. Beyond
Hellman’s time-memory trade-offs with applications to proofs of space. ASIACRYPT:
Theory and Applications of Cryptology and Information Security, LNCS, vol. 10625,
357–379.'
mla: Abusalah, Hamza M., et al. Beyond Hellman’s Time-Memory Trade-Offs with
Applications to Proofs of Space. Vol. 10625, Springer, 2017, pp. 357–79, doi:10.1007/978-3-319-70697-9_13.
short: H.M. Abusalah, J.F. Alwen, B. Cohen, D. Khilko, K.Z. Pietrzak, L. Reyzin,
in:, Springer, 2017, pp. 357–379.
conference:
end_date: 2017-12-07
location: Hong Kong, China
name: 'ASIACRYPT: Theory and Applications of Cryptology and Information Security'
start_date: 2017-12-03
date_created: 2018-12-11T11:47:10Z
date_published: 2017-11-18T00:00:00Z
date_updated: 2023-09-07T12:30:22Z
day: '18'
department:
- _id: KrPi
doi: 10.1007/978-3-319-70697-9_13
ec_funded: 1
intvolume: ' 10625'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/893.pdf
month: '11'
oa: 1
oa_version: Submitted Version
page: 357 - 379
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331970696-2
publication_status: published
publisher: Springer
publist_id: '7257'
quality_controlled: '1'
related_material:
record:
- id: '83'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Beyond Hellman’s time-memory trade-offs with applications to proofs of space
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 10625
year: '2017'
...
---
_id: '609'
abstract:
- lang: eng
text: Several cryptographic schemes and applications are based on functions that
are both reasonably efficient to compute and moderately hard to invert, including
client puzzles for Denial-of-Service protection, password protection via salted
hashes, or recent proof-of-work blockchain systems. Despite their wide use, a
definition of this concept has not yet been distilled and formalized explicitly.
Instead, either the applications are proven directly based on the assumptions
underlying the function, or some property of the function is proven, but the security
of the application is argued only informally. The goal of this work is to provide
a (universal) definition that decouples the efforts of designing new moderately
hard functions and of building protocols based on them, serving as an interface
between the two. On a technical level, beyond the mentioned definitions, we instantiate
the model for four different notions of hardness. We extend the work of Alwen
and Serbinenko (STOC 2015) by providing a general tool for proving security for
the first notion of memory-hard functions that allows for provably secure applications.
The tool allows us to recover all of the graph-theoretic techniques developed
for proving security under the older, non-composable, notion of security used
by Alwen and Serbinenko. As an application of our definition of moderately hard
functions, we prove the security of two different schemes for proofs of effort
(PoE). We also formalize and instantiate the concept of a non-interactive proof
of effort (niPoE), in which the proof is not bound to a particular communication
context but rather any bit-string chosen by the prover.
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Björn
full_name: Tackmann, Björn
last_name: Tackmann
citation:
ama: 'Alwen JF, Tackmann B. Moderately hard functions: Definition, instantiations,
and applications. In: Kalai Y, Reyzin L, eds. Vol 10677. Springer; 2017:493-526.
doi:10.1007/978-3-319-70500-2_17'
apa: 'Alwen, J. F., & Tackmann, B. (2017). Moderately hard functions: Definition,
instantiations, and applications. In Y. Kalai & L. Reyzin (Eds.) (Vol. 10677,
pp. 493–526). Presented at the TCC: Theory of Cryptography, Baltimore, MD, United
States: Springer. https://doi.org/10.1007/978-3-319-70500-2_17'
chicago: 'Alwen, Joel F, and Björn Tackmann. “Moderately Hard Functions: Definition,
Instantiations, and Applications.” edited by Yael Kalai and Leonid Reyzin, 10677:493–526.
Springer, 2017. https://doi.org/10.1007/978-3-319-70500-2_17.'
ieee: 'J. F. Alwen and B. Tackmann, “Moderately hard functions: Definition, instantiations,
and applications,” presented at the TCC: Theory of Cryptography, Baltimore, MD,
United States, 2017, vol. 10677, pp. 493–526.'
ista: 'Alwen JF, Tackmann B. 2017. Moderately hard functions: Definition, instantiations,
and applications. TCC: Theory of Cryptography, LNCS, vol. 10677, 493–526.'
mla: 'Alwen, Joel F., and Björn Tackmann. Moderately Hard Functions: Definition,
Instantiations, and Applications. Edited by Yael Kalai and Leonid Reyzin,
vol. 10677, Springer, 2017, pp. 493–526, doi:10.1007/978-3-319-70500-2_17.'
short: J.F. Alwen, B. Tackmann, in:, Y. Kalai, L. Reyzin (Eds.), Springer, 2017,
pp. 493–526.
conference:
end_date: 2017-11-15
location: Baltimore, MD, United States
name: 'TCC: Theory of Cryptography'
start_date: 2017-11-12
date_created: 2018-12-11T11:47:28Z
date_published: 2017-11-05T00:00:00Z
date_updated: 2021-01-12T08:06:04Z
day: '05'
department:
- _id: KrPi
doi: 10.1007/978-3-319-70500-2_17
editor:
- first_name: Yael
full_name: Kalai, Yael
last_name: Kalai
- first_name: Leonid
full_name: Reyzin, Leonid
last_name: Reyzin
intvolume: ' 10677'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/945
month: '11'
oa: 1
oa_version: Submitted Version
page: 493 - 526
publication_identifier:
isbn:
- 978-331970499-9
publication_status: published
publisher: Springer
publist_id: '7196'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Moderately hard functions: Definition, instantiations, and applications'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10677
year: '2017'
...
---
_id: '635'
abstract:
- lang: eng
text: Memory-hard functions (MHFs) are hash algorithms whose evaluation cost is
dominated by memory cost. As memory, unlike computation, costs about the same
across different platforms, MHFs cannot be evaluated at significantly lower cost
on dedicated hardware like ASICs. MHFs have found widespread applications including
password hashing, key derivation, and proofs-of-work. This paper focuses on scrypt,
a simple candidate MHF designed by Percival, and described in RFC 7914. It has
been used within a number of cryptocurrencies (e.g., Litecoin and Dogecoin) and
has been an inspiration for Argon2d, one of the winners of the recent password-hashing
competition. Despite its popularity, no rigorous lower bounds on its memory complexity
are known. We prove that scrypt is optimally memory-hard, i.e., its cumulative
memory complexity (cmc) in the parallel random oracle model is Ω(n2w), where w
and n are the output length and number of invocations of the underlying hash function,
respectively. High cmc is a strong security target for MHFs introduced by Alwen
and Serbinenko (STOC’15) which implies high memory cost even for adversaries who
can amortize the cost over many evaluations and evaluate the underlying hash functions
many times in parallel. Our proof is the first showing optimal memory-hardness
for any MHF. Our result improves both quantitatively and qualitatively upon the
recent work by Alwen et al. (EUROCRYPT’16) who proved a weaker lower bound of
Ω(n2w/ log2 n) for a restricted class of adversaries.
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Binchi
full_name: Chen, Binchi
last_name: Chen
- 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: Leonid
full_name: Reyzin, Leonid
last_name: Reyzin
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. Scrypt is maximally memory
hard. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:33-62. doi:10.1007/978-3-319-56617-7_2'
apa: 'Alwen, J. F., Chen, B., Pietrzak, K. Z., Reyzin, L., & Tessaro, S. (2017).
Scrypt is maximally memory hard. In J.-S. Coron & J. Buus Nielsen (Eds.) (Vol.
10212, pp. 33–62). Presented at the EUROCRYPT: Theory and Applications of Cryptographic
Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_2'
chicago: Alwen, Joel F, Binchi Chen, Krzysztof Z Pietrzak, Leonid Reyzin, and Stefano
Tessaro. “Scrypt Is Maximally Memory Hard.” edited by Jean-Sébastien Coron and
Jesper Buus Nielsen, 10212:33–62. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_2.
ieee: 'J. F. Alwen, B. Chen, K. Z. Pietrzak, L. Reyzin, and S. Tessaro, “Scrypt
is maximally memory hard,” presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 33–62.'
ista: 'Alwen JF, Chen B, Pietrzak KZ, Reyzin L, Tessaro S. 2017. Scrypt is maximally
memory hard. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS,
vol. 10212, 33–62.'
mla: Alwen, Joel F., et al. Scrypt Is Maximally Memory Hard. Edited by Jean-Sébastien
Coron and Jesper Buus Nielsen, vol. 10212, Springer, 2017, pp. 33–62, doi:10.1007/978-3-319-56617-7_2.
short: J.F. Alwen, B. Chen, K.Z. Pietrzak, L. Reyzin, S. Tessaro, in:, J.-S. Coron,
J. Buus Nielsen (Eds.), Springer, 2017, pp. 33–62.
conference:
end_date: 2017-05-04
location: Paris, France
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2017-04-30
date_created: 2018-12-11T11:47:37Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:10Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-56617-7_2
ec_funded: 1
editor:
- first_name: Jean-Sébastien
full_name: Coron, Jean-Sébastien
last_name: Coron
- first_name: Jesper
full_name: Buus Nielsen, Jesper
last_name: Buus Nielsen
intvolume: ' 10212'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/989
month: '01'
oa: 1
oa_version: Submitted Version
page: 33 - 62
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331956616-0
publication_status: published
publisher: Springer
publist_id: '7154'
quality_controlled: '1'
scopus_import: 1
status: public
title: Scrypt is maximally memory hard
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 10212
year: '2017'
...
---
_id: '640'
abstract:
- lang: eng
text: 'Data-independent Memory Hard Functions (iMHFS) are finding a growing number
of applications in security; especially in the domain of password hashing. An
important property of a concrete iMHF is specified by fixing a directed acyclic
graph (DAG) Gn on n nodes. The quality of that iMHF is then captured by the following
two pebbling complexities of Gn: – The parallel cumulative pebbling complexity
Π∥cc(Gn) must be as high as possible (to ensure that the amortized cost of computing
the function on dedicated hardware is dominated by the cost of memory). – The
sequential space-time pebbling complexity Πst(Gn) should be as close as possible
to Π∥cc(Gn) (to ensure that using many cores in parallel and amortizing over many
instances does not give much of an advantage). In this paper we construct a family
of DAGs with best possible parameters in an asymptotic sense, i.e., where Π∥cc(Gn)
= Ω(n2/ log(n)) (which matches a known upper bound) and Πst(Gn) is within a constant
factor of Π∥cc(Gn). Our analysis relies on a new connection between the pebbling
complexity of a DAG and its depth-robustness (DR) – a well studied combinatorial
property. We show that high DR is sufficient for high Π∥cc. Alwen and Blocki (CRYPTO’16)
showed that high DR is necessary and so, together, these results fully characterize
DAGs with high Π∥cc in terms of DR. Complementing these results, we provide new
upper and lower bounds on the Π∥cc of several important candidate iMHFs from the
literature. We give the first lower bounds on the memory hardness of the Catena
and Balloon Hashing functions in a parallel model of computation and we give the
first lower bounds of any kind for (a version) of Argon2i. Finally we describe
a new class of pebbling attacks improving on those of Alwen and Blocki (CRYPTO’16).
By instantiating these attacks we upperbound the Π∥cc of the Password Hashing
Competition winner Argon2i and one of the Balloon Hashing functions by O (n1.71).
We also show an upper bound of O(n1.625) for the Catena functions and the two
remaining Balloon Hashing functions.'
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Jeremiah
full_name: Blocki, Jeremiah
last_name: Blocki
- 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: 'Alwen JF, Blocki J, Pietrzak KZ. Depth-robust graphs and their cumulative
memory complexity. In: Coron J-S, Buus Nielsen J, eds. Vol 10212. Springer; 2017:3-32.
doi:10.1007/978-3-319-56617-7_1'
apa: 'Alwen, J. F., Blocki, J., & Pietrzak, K. Z. (2017). Depth-robust graphs
and their cumulative memory complexity. In J.-S. Coron & J. Buus Nielsen (Eds.)
(Vol. 10212, pp. 3–32). Presented at the EUROCRYPT: Theory and Applications of
Cryptographic Techniques, Paris, France: Springer. https://doi.org/10.1007/978-3-319-56617-7_1'
chicago: Alwen, Joel F, Jeremiah Blocki, and Krzysztof Z Pietrzak. “Depth-Robust
Graphs and Their Cumulative Memory Complexity.” edited by Jean-Sébastien Coron
and Jesper Buus Nielsen, 10212:3–32. Springer, 2017. https://doi.org/10.1007/978-3-319-56617-7_1.
ieee: 'J. F. Alwen, J. Blocki, and K. Z. Pietrzak, “Depth-robust graphs and their
cumulative memory complexity,” presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, Paris, France, 2017, vol. 10212, pp. 3–32.'
ista: 'Alwen JF, Blocki J, Pietrzak KZ. 2017. Depth-robust graphs and their cumulative
memory complexity. EUROCRYPT: Theory and Applications of Cryptographic Techniques,
LNCS, vol. 10212, 3–32.'
mla: Alwen, Joel F., et al. Depth-Robust Graphs and Their Cumulative Memory Complexity.
Edited by Jean-Sébastien Coron and Jesper Buus Nielsen, vol. 10212, Springer,
2017, pp. 3–32, doi:10.1007/978-3-319-56617-7_1.
short: J.F. Alwen, J. Blocki, K.Z. Pietrzak, in:, J.-S. Coron, J. Buus Nielsen (Eds.),
Springer, 2017, pp. 3–32.
conference:
end_date: 2017-05-04
location: Paris, France
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2017-04-30
date_created: 2018-12-11T11:47:39Z
date_published: 2017-04-01T00:00:00Z
date_updated: 2021-01-12T08:07:22Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-56617-7_1
ec_funded: 1
editor:
- first_name: Jean-Sébastien
full_name: Coron, Jean-Sébastien
last_name: Coron
- first_name: Jesper
full_name: Buus Nielsen, Jesper
last_name: Buus Nielsen
intvolume: ' 10212'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/875
month: '04'
oa: 1
oa_version: Submitted Version
page: 3 - 32
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331956616-0
publication_status: published
publisher: Springer
publist_id: '7148'
quality_controlled: '1'
scopus_import: 1
status: public
title: Depth-robust graphs and their cumulative memory complexity
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10212
year: '2017'
...
---
_id: '6527'
abstract:
- lang: eng
text: "A memory-hard function (MHF) ƒn with parameter n can be computed in sequential
time and space n. Simultaneously, a high amortized parallel area-time complexity
(aAT) is incurred per evaluation. In practice, MHFs are used to limit the rate
at which an adversary (using a custom computational device) can evaluate a security
sensitive function that still occasionally needs to be evaluated by honest users
(using an off-the-shelf general purpose device). The most prevalent examples of
such sensitive functions are Key Derivation Functions (KDFs) and password hashing
algorithms where rate limits help mitigate off-line dictionary attacks. As the
honest users' inputs to these functions are often (low-entropy) passwords special
attention is given to a class of side-channel resistant MHFs called iMHFs.\r\n\r\nEssentially
all iMHFs can be viewed as some mode of operation (making n calls to some round
function) given by a directed acyclic graph (DAG) with very low indegree. Recently,
a combinatorial property of a DAG has been identified (called \"depth-robustness\")
which results in good provable security for an iMHF based on that DAG. Depth-robust
DAGs have also proven useful in other cryptographic applications. Unfortunately,
up till now, all known very depth-robust DAGs are impractically complicated and
little is known about their exact (i.e. non-asymptotic) depth-robustness both
in theory and in practice.\r\n\r\nIn this work we build and analyze (both formally
and empirically) several exceedingly simple and efficient to navigate practical
DAGs for use in iMHFs and other applications. For each DAG we:\r\n*Prove that
their depth-robustness is asymptotically maximal.\r\n*Prove bounds of at least
3 orders of magnitude better on their exact depth-robustness compared to known
bounds for other practical iMHF.\r\n*Implement and empirically evaluate their
depth-robustness and aAT against a variety of state-of-the art (and several new)
depth-reduction and low aAT attacks. \r\nWe find that, against all attacks, the
new DAGs perform significantly better in practice than Argon2i, the most widely
deployed iMHF in practice.\r\n\r\nAlong the way we also improve the best known
empirical attacks on the aAT of Argon2i by implementing and testing several heuristic
versions of a (hitherto purely theoretical) depth-reduction attack. Finally, we
demonstrate practicality of our constructions by modifying the Argon2i code base
to use one of the new high aAT DAGs. Experimental benchmarks on a standard off-the-shelf
CPU show that the new modifications do not adversely affect the impressive throughput
of Argon2i (despite seemingly enjoying significantly higher aAT).\r\n"
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Jeremiah
full_name: Blocki, Jeremiah
last_name: Blocki
- first_name: Ben
full_name: Harsha, Ben
last_name: Harsha
citation:
ama: 'Alwen JF, Blocki J, Harsha B. Practical graphs for optimal side-channel resistant
memory-hard functions. In: Proceedings of the 2017 ACM SIGSAC Conference on
Computer and Communications Security. ACM Press; 2017:1001-1017. doi:10.1145/3133956.3134031'
apa: 'Alwen, J. F., Blocki, J., & Harsha, B. (2017). Practical graphs for optimal
side-channel resistant memory-hard functions. In Proceedings of the 2017 ACM
SIGSAC Conference on Computer and Communications Security (pp. 1001–1017).
Dallas, TX, USA: ACM Press. https://doi.org/10.1145/3133956.3134031'
chicago: Alwen, Joel F, Jeremiah Blocki, and Ben Harsha. “Practical Graphs for Optimal
Side-Channel Resistant Memory-Hard Functions.” In Proceedings of the 2017 ACM
SIGSAC Conference on Computer and Communications Security, 1001–17. ACM Press,
2017. https://doi.org/10.1145/3133956.3134031.
ieee: J. F. Alwen, J. Blocki, and B. Harsha, “Practical graphs for optimal side-channel
resistant memory-hard functions,” in Proceedings of the 2017 ACM SIGSAC Conference
on Computer and Communications Security, Dallas, TX, USA, 2017, pp. 1001–1017.
ista: 'Alwen JF, Blocki J, Harsha B. 2017. Practical graphs for optimal side-channel
resistant memory-hard functions. Proceedings of the 2017 ACM SIGSAC Conference
on Computer and Communications Security. CCS: Conference on Computer and Communications
Security, 1001–1017.'
mla: Alwen, Joel F., et al. “Practical Graphs for Optimal Side-Channel Resistant
Memory-Hard Functions.” Proceedings of the 2017 ACM SIGSAC Conference on Computer
and Communications Security, ACM Press, 2017, pp. 1001–17, doi:10.1145/3133956.3134031.
short: J.F. Alwen, J. Blocki, B. Harsha, in:, Proceedings of the 2017 ACM SIGSAC
Conference on Computer and Communications Security, ACM Press, 2017, pp. 1001–1017.
conference:
end_date: 2017-11-03
location: Dallas, TX, USA
name: 'CCS: Conference on Computer and Communications Security'
start_date: 2017-10-30
date_created: 2019-06-06T13:21:29Z
date_published: 2017-10-30T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '30'
department:
- _id: KrPi
doi: 10.1145/3133956.3134031
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/443
month: '10'
oa: 1
oa_version: Submitted Version
page: 1001-1017
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications
Security
publication_identifier:
isbn:
- '9781450349468'
publication_status: published
publisher: ACM Press
quality_controlled: '1'
scopus_import: 1
status: public
title: Practical graphs for optimal side-channel resistant memory-hard functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '1365'
abstract:
- lang: eng
text: A memory-hard function (MHF) f is equipped with a space cost σ and time cost
τ parameter such that repeatedly computing fσ,τ on an application specific integrated
circuit (ASIC) is not economically advantageous relative to a general purpose
computer. Technically we would like that any (generalized) circuit for evaluating
an iMHF fσ,τ has area × time (AT) complexity at Θ(σ2 ∗ τ). A data-independent
MHF (iMHF) has the added property that it can be computed with almost optimal
memory and time complexity by an algorithm which accesses memory in a pattern
independent of the input value. Such functions can be specified by fixing a directed
acyclic graph (DAG) G on n = Θ(σ ∗ τ) nodes representing its computation graph.
In this work we develop new tools for analyzing iMHFs. First we define and motivate
a new complexity measure capturing the amount of energy (i.e. electricity) required
to compute a function. We argue that, in practice, this measure is at least as
important as the more traditional AT-complexity. Next we describe an algorithm
A for repeatedly evaluating an iMHF based on an arbitrary DAG G. We upperbound
both its energy and AT complexities per instance evaluated in terms of a certain
combinatorial property of G. Next we instantiate our attack for several general
classes of DAGs which include those underlying many of the most important iMHF
candidates in the literature. In particular, we obtain the following results which
hold for all choices of parameters σ and τ (and thread-count) such that n = σ
∗ τ. -The Catena-Dragonfly function of [FLW13] has AT and energy complexities
O(n1.67). -The Catena-Butterfly function of [FLW13] has complexities is O(n1.67).
-The Double-Buffer and the Linear functions of [CGBS16] both have complexities
in O(n1.67). -The Argon2i function of [BDK15] (winner of the Password Hashing
Competition [PHC]) has complexities O(n7/4 log(n)). -The Single-Buffer function
of [CGBS16] has complexities O(n7/4 log(n)). -Any iMHF can be computed by an algorithm
with complexities O(n2/ log1 −ε(n)) for all ε > 0. In particular when τ = 1
this shows that the goal of constructing an iMHF with AT-complexity Θ(σ2 ∗ τ )
is unachievable. Along the way we prove a lemma upper-bounding the depth-robustness
of any DAG which may prove to be of independent interest.
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Jeremiah
full_name: Blocki, Jeremiah
last_name: Blocki
citation:
ama: 'Alwen JF, Blocki J. Efficiently computing data-independent memory-hard functions.
In: Vol 9815. Springer; 2016:241-271. doi:10.1007/978-3-662-53008-5_9'
apa: 'Alwen, J. F., & Blocki, J. (2016). Efficiently computing data-independent
memory-hard functions (Vol. 9815, pp. 241–271). Presented at the CRYPTO: International
Cryptology Conference, Santa Barbara, CA, USA: Springer. https://doi.org/10.1007/978-3-662-53008-5_9'
chicago: Alwen, Joel F, and Jeremiah Blocki. “Efficiently Computing Data-Independent
Memory-Hard Functions,” 9815:241–71. Springer, 2016. https://doi.org/10.1007/978-3-662-53008-5_9.
ieee: 'J. F. Alwen and J. Blocki, “Efficiently computing data-independent memory-hard
functions,” presented at the CRYPTO: International Cryptology Conference, Santa
Barbara, CA, USA, 2016, vol. 9815, pp. 241–271.'
ista: 'Alwen JF, Blocki J. 2016. Efficiently computing data-independent memory-hard
functions. CRYPTO: International Cryptology Conference, LNCS, vol. 9815, 241–271.'
mla: Alwen, Joel F., and Jeremiah Blocki. Efficiently Computing Data-Independent
Memory-Hard Functions. Vol. 9815, Springer, 2016, pp. 241–71, doi:10.1007/978-3-662-53008-5_9.
short: J.F. Alwen, J. Blocki, in:, Springer, 2016, pp. 241–271.
conference:
end_date: 2016-08-18
location: Santa Barbara, CA, USA
name: 'CRYPTO: International Cryptology Conference'
start_date: 2016-08-14
date_created: 2018-12-11T11:51:36Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2021-01-12T06:50:11Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-662-53008-5_9
intvolume: ' 9815'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2016/115
month: '08'
oa: 1
oa_version: Preprint
page: 241 - 271
publication_status: published
publisher: Springer
publist_id: '5876'
quality_controlled: '1'
scopus_import: 1
status: public
title: Efficiently computing data-independent memory-hard functions
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9815
year: '2016'
...
---
_id: '1231'
abstract:
- lang: eng
text: 'We study the time-and memory-complexities of the problem of computing labels
of (multiple) randomly selected challenge-nodes in a directed acyclic graph. The
w-bit label of a node is the hash of the labels of its parents, and the hash function
is modeled as a random oracle. Specific instances of this problem underlie both
proofs of space [Dziembowski et al. CRYPTO’15] as well as popular memory-hard
functions like scrypt. As our main tool, we introduce the new notion of a probabilistic
parallel entangled pebbling game, a new type of combinatorial pebbling game on
a graph, which is closely related to the labeling game on the same graph. As a
first application of our framework, we prove that for scrypt, when the underlying
hash function is invoked n times, the cumulative memory complexity (CMC) (a notion
recently introduced by Alwen and Serbinenko (STOC’15) to capture amortized memory-hardness
for parallel adversaries) is at least Ω(w · (n/ log(n))2). This bound holds for
adversaries that can store many natural functions of the labels (e.g., linear
combinations), but still not arbitrary functions thereof. We then introduce and
study a combinatorial quantity, and show how a sufficiently small upper bound
on it (which we conjecture) extends our CMC bound for scrypt to hold against arbitrary
adversaries. We also show that such an upper bound solves the main open problem
for proofs-of-space protocols: namely, establishing that the time complexity of
computing the label of a random node in a graph on n nodes (given an initial kw-bit
state) reduces tightly to the time complexity for black pebbling on the same graph
(given an initial k-node pebbling).'
acknowledgement: "Joël Alwen, Chethan Kamath, and Krzysztof Pietrzak’s research is
partially supported by an ERC starting grant (259668-PSPC). Vladimir Kolmogorov
is partially supported by an ERC consolidator grant (616160-DOICV). Binyi Chen was
partially supported by NSF grants CNS-1423566 and CNS-1514526, and a gift from the
Gareatis Foundation. Stefano Tessaro was partially supported by NSF grants CNS-1423566,
CNS-1528178, a Hellman Fellowship, and the Glen and Susanne Culler Chair.\r\n\r\nThis
work was done in part while the authors were visiting the Simons Institute for the
Theory of Computing, supported by the Simons Foundation and by the DIMACS/Simons
Collaboration in Cryptography through NSF grant CNS-1523467."
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Binyi
full_name: Chen, Binyi
last_name: Chen
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Vladimir
full_name: Kolmogorov, Vladimir
id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
last_name: Kolmogorov
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S.
On the complexity of scrypt and proofs of space in the parallel random oracle
model. In: Vol 9666. Springer; 2016:358-387. doi:10.1007/978-3-662-49896-5_13'
apa: 'Alwen, J. F., Chen, B., Kamath Hosdurg, C., Kolmogorov, V., Pietrzak, K. Z.,
& Tessaro, S. (2016). On the complexity of scrypt and proofs of space in the
parallel random oracle model (Vol. 9666, pp. 358–387). Presented at the EUROCRYPT:
Theory and Applications of Cryptographic Techniques, Vienna, Austria: Springer.
https://doi.org/10.1007/978-3-662-49896-5_13'
chicago: Alwen, Joel F, Binyi Chen, Chethan Kamath Hosdurg, Vladimir Kolmogorov,
Krzysztof Z Pietrzak, and Stefano Tessaro. “On the Complexity of Scrypt and Proofs
of Space in the Parallel Random Oracle Model,” 9666:358–87. Springer, 2016. https://doi.org/10.1007/978-3-662-49896-5_13.
ieee: 'J. F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K. Z. Pietrzak, and
S. Tessaro, “On the complexity of scrypt and proofs of space in the parallel random
oracle model,” presented at the EUROCRYPT: Theory and Applications of Cryptographic
Techniques, Vienna, Austria, 2016, vol. 9666, pp. 358–387.'
ista: 'Alwen JF, Chen B, Kamath Hosdurg C, Kolmogorov V, Pietrzak KZ, Tessaro S.
2016. On the complexity of scrypt and proofs of space in the parallel random oracle
model. EUROCRYPT: Theory and Applications of Cryptographic Techniques, LNCS, vol.
9666, 358–387.'
mla: Alwen, Joel F., et al. On the Complexity of Scrypt and Proofs of Space in
the Parallel Random Oracle Model. Vol. 9666, Springer, 2016, pp. 358–87, doi:10.1007/978-3-662-49896-5_13.
short: J.F. Alwen, B. Chen, C. Kamath Hosdurg, V. Kolmogorov, K.Z. Pietrzak, S.
Tessaro, in:, Springer, 2016, pp. 358–387.
conference:
end_date: 2016-05-12
location: Vienna, Austria
name: 'EUROCRYPT: Theory and Applications of Cryptographic Techniques'
start_date: 2016-05-08
date_created: 2018-12-11T11:50:51Z
date_published: 2016-04-28T00:00:00Z
date_updated: 2021-01-12T06:49:15Z
day: '28'
department:
- _id: KrPi
- _id: VlKo
doi: 10.1007/978-3-662-49896-5_13
ec_funded: 1
intvolume: ' 9666'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/100
month: '04'
oa: 1
oa_version: Submitted Version
page: 358 - 387
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
publication_status: published
publisher: Springer
publist_id: '6103'
quality_controlled: '1'
scopus_import: 1
status: public
title: On the complexity of scrypt and proofs of space in the parallel random oracle
model
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9666
year: '2016'
...
---
_id: '1652'
abstract:
- lang: eng
text: We develop new theoretical tools for proving lower-bounds on the (amortized)
complexity of certain functions in models of parallel computation. We apply the
tools to construct a class of functions with high amortized memory complexity
in the parallel Random Oracle Model (pROM); a variant of the standard ROM allowing
for batches of simultaneous queries. In particular we obtain a new, more robust,
type of Memory-Hard Functions (MHF); a security primitive which has recently been
gaining acceptance in practice as an effective means of countering brute-force
attacks on security relevant functions. Along the way we also demonstrate an important
shortcoming of previous definitions of MHFs and give a new definition addressing
the problem. The tools we develop represent an adaptation of the powerful pebbling
paradigm (initially introduced by Hewitt and Paterson [HP70] and Cook [Coo73])
to a simple and intuitive parallel setting. We define a simple pebbling game Gp
over graphs which aims to abstract parallel computation in an intuitive way. As
a conceptual contribution we define a measure of pebbling complexity for graphs
called cumulative complexity (CC) and show how it overcomes a crucial shortcoming
(in the parallel setting) exhibited by more traditional complexity measures used
in the past. As a main technical contribution we give an explicit construction
of a constant in-degree family of graphs whose CC in Gp approaches maximality
to within a polylogarithmic factor for any graph of equal size (analogous to the
graphs of Tarjan et. al. [PTC76, LT82] for sequential pebbling games). Finally,
for a given graph G and related function fG, we derive a lower-bound on the amortized
memory complexity of fG in the pROM in terms of the CC of G in the game Gp.
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Vladimir
full_name: Serbinenko, Vladimir
last_name: Serbinenko
citation:
ama: 'Alwen JF, Serbinenko V. High parallel complexity graphs and memory-hard functions.
In: Proceedings of the 47th Annual ACM Symposium on Theory of Computing.
ACM; 2015:595-603. doi:10.1145/2746539.2746622'
apa: 'Alwen, J. F., & Serbinenko, V. (2015). High parallel complexity graphs
and memory-hard functions. In Proceedings of the 47th annual ACM symposium
on Theory of computing (pp. 595–603). Portland, OR, United States: ACM. https://doi.org/10.1145/2746539.2746622'
chicago: Alwen, Joel F, and Vladimir Serbinenko. “High Parallel Complexity Graphs
and Memory-Hard Functions.” In Proceedings of the 47th Annual ACM Symposium
on Theory of Computing, 595–603. ACM, 2015. https://doi.org/10.1145/2746539.2746622.
ieee: J. F. Alwen and V. Serbinenko, “High parallel complexity graphs and memory-hard
functions,” in Proceedings of the 47th annual ACM symposium on Theory of computing,
Portland, OR, United States, 2015, pp. 595–603.
ista: 'Alwen JF, Serbinenko V. 2015. High parallel complexity graphs and memory-hard
functions. Proceedings of the 47th annual ACM symposium on Theory of computing.
STOC: Symposium on the Theory of Computing, 595–603.'
mla: Alwen, Joel F., and Vladimir Serbinenko. “High Parallel Complexity Graphs and
Memory-Hard Functions.” Proceedings of the 47th Annual ACM Symposium on Theory
of Computing, ACM, 2015, pp. 595–603, doi:10.1145/2746539.2746622.
short: J.F. Alwen, V. Serbinenko, in:, Proceedings of the 47th Annual ACM Symposium
on Theory of Computing, ACM, 2015, pp. 595–603.
conference:
end_date: 2015-06-17
location: Portland, OR, United States
name: 'STOC: Symposium on the Theory of Computing'
start_date: 2015-06-14
date_created: 2018-12-11T11:53:16Z
date_published: 2015-06-01T00:00:00Z
date_updated: 2021-01-12T06:52:16Z
day: '01'
department:
- _id: KrPi
doi: 10.1145/2746539.2746622
ec_funded: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2014/238
month: '06'
oa: 1
oa_version: Submitted Version
page: 595 - 603
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Proceedings of the 47th annual ACM symposium on Theory of computing
publication_status: published
publisher: ACM
publist_id: '5498'
quality_controlled: '1'
scopus_import: 1
status: public
title: High parallel complexity graphs and memory-hard functions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1672'
abstract:
- lang: eng
text: Composable notions of incoercibility aim to forbid a coercer from using anything
beyond the coerced parties’ inputs and outputs to catch them when they try to
deceive him. Existing definitions are restricted to weak coercion types, and/or
are not universally composable. Furthermore, they often make too strong assumptions
on the knowledge of coerced parties—e.g., they assume they known the identities
and/or the strategies of other coerced parties, or those of corrupted parties—
which makes them unsuitable for applications of incoercibility such as e-voting,
where colluding adversarial parties may attempt to coerce honest voters, e.g.,
by offering them money for a promised vote, and use their own view to check that
the voter keeps his end of the bargain. In this work we put forward the first
universally composable notion of incoercible multi-party computation, which satisfies
the above intuition and does not assume collusions among coerced parties or knowledge
of the corrupted set. We define natural notions of UC incoercibility corresponding
to standard coercion-types, i.e., receipt-freeness and resistance to full-active
coercion. Importantly, our suggested notion has the unique property that it builds
on top of the well studied UC framework by Canetti instead of modifying it. This
guarantees backwards compatibility, and allows us to inherit results from the
rich UC literature. We then present MPC protocols which realize our notions of
UC incoercibility given access to an arguably minimal setup—namely honestly generate
tamper-proof hardware performing a very simple cryptographic operation—e.g., a
smart card. This is, to our knowledge, the first proposed construction of an MPC
protocol (for more than two parties) that is incoercibly secure and universally
composable, and therefore the first construction of a universally composable receipt-free
e-voting protocol.
acknowledgement: Joël Alwen was supported by the ERC starting grant (259668-PSPC).
Rafail Ostrovsky was supported in part by NSF grants 09165174, 1065276, 1118126
and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty
Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award,
Teradata Research Award, Lockheed-Martin Corporation Research Award, and the Defense
Advanced Research Projects Agency through the U.S. Office of Naval Research under
Contract N00014 -11 -1-0392. The views expressed are those of the author and do
not reflect the official policy or position of the Department of Defense or the
U.S. Government. Vassilis Zikas was supported in part by the Swiss National Science
Foundation (SNF) via the Ambizione grant PZ00P-2142549.
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: Rafail
full_name: Ostrovsky, Rafail
last_name: Ostrovsky
- first_name: Hongsheng
full_name: Zhou, Hongsheng
last_name: Zhou
- first_name: Vassilis
full_name: Zikas, Vassilis
last_name: Zikas
citation:
ama: 'Alwen JF, Ostrovsky R, Zhou H, Zikas V. Incoercible multi-party computation
and universally composable receipt-free voting. In: Advances in Cryptology
- CRYPTO 2015. Vol 9216. Lecture Notes in Computer Science. Springer; 2015:763-780.
doi:10.1007/978-3-662-48000-7_37'
apa: 'Alwen, J. F., Ostrovsky, R., Zhou, H., & Zikas, V. (2015). Incoercible
multi-party computation and universally composable receipt-free voting. In Advances
in Cryptology - CRYPTO 2015 (Vol. 9216, pp. 763–780). Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-662-48000-7_37'
chicago: Alwen, Joel F, Rafail Ostrovsky, Hongsheng Zhou, and Vassilis Zikas. “Incoercible
Multi-Party Computation and Universally Composable Receipt-Free Voting.” In Advances
in Cryptology - CRYPTO 2015, 9216:763–80. Lecture Notes in Computer Science.
Springer, 2015. https://doi.org/10.1007/978-3-662-48000-7_37.
ieee: J. F. Alwen, R. Ostrovsky, H. Zhou, and V. Zikas, “Incoercible multi-party
computation and universally composable receipt-free voting,” in Advances in
Cryptology - CRYPTO 2015, Santa Barbara, CA, United States, 2015, vol. 9216,
pp. 763–780.
ista: 'Alwen JF, Ostrovsky R, Zhou H, Zikas V. 2015. Incoercible multi-party computation
and universally composable receipt-free voting. Advances in Cryptology - CRYPTO
2015. CRYPTO: International Cryptology ConferenceLecture Notes in Computer Science,
LNCS, vol. 9216, 763–780.'
mla: Alwen, Joel F., et al. “Incoercible Multi-Party Computation and Universally
Composable Receipt-Free Voting.” Advances in Cryptology - CRYPTO 2015,
vol. 9216, Springer, 2015, pp. 763–80, doi:10.1007/978-3-662-48000-7_37.
short: J.F. Alwen, R. Ostrovsky, H. Zhou, V. Zikas, in:, Advances in Cryptology
- CRYPTO 2015, Springer, 2015, pp. 763–780.
conference:
end_date: 2015-08-20
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2015-08-16
date_created: 2018-12-11T11:53:23Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2022-06-07T09:51:55Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48000-7_37
ec_funded: 1
file:
- access_level: open_access
checksum: 5b6649e80d1f781a8910f7cce6427f78
content_type: application/pdf
creator: dernst
date_created: 2020-05-15T08:55:29Z
date_updated: 2020-07-14T12:45:11Z
file_id: '7853'
file_name: 2015_CRYPTO_Alwen.pdf
file_size: 397363
relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: ' 9216'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 763 - 780
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Advances in Cryptology - CRYPTO 2015
publication_identifier:
eisbn:
- 978-3-662-48000-7
isbn:
- 978-3-662-47999-5
publication_status: published
publisher: Springer
publist_id: '5476'
quality_controlled: '1'
scopus_import: '1'
series_title: Lecture Notes in Computer Science
status: public
title: Incoercible multi-party computation and universally composable receipt-free
voting
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9216
year: '2015'
...
---
_id: '2259'
abstract:
- lang: eng
text: "The learning with rounding (LWR) problem, introduced by Banerjee, Peikert
and Rosen at EUROCRYPT ’12, is a variant of learning with errors (LWE), where
one replaces random errors with deterministic rounding. The LWR problem was shown
to be as hard as LWE for a setting of parameters where the modulus and modulus-to-error
ratio are super-polynomial. In this work we resolve the main open problem and
give a new reduction that works for a larger range of parameters, allowing for
a polynomial modulus and modulus-to-error ratio. In particular, a smaller modulus
gives us greater efficiency, and a smaller modulus-to-error ratio gives us greater
security, which now follows from the worst-case hardness of GapSVP with polynomial
(rather than super-polynomial) approximation factors.\r\n\r\nAs a tool in the
reduction, we show that there is a “lossy mode” for the LWR problem, in which
LWR samples only reveal partial information about the secret. This property gives
us several interesting new applications, including a proof that LWR remains secure
with weakly random secrets of sufficient min-entropy, and very simple constructions
of deterministic encryption, lossy trapdoor functions and reusable extractors.\r\n\r\nOur
approach is inspired by a technique of Goldwasser et al. from ICS ’10, which implicitly
showed the existence of a “lossy mode” for LWE. By refining this technique, we
also improve on the parameters of that work to only requiring a polynomial (instead
of super-polynomial) modulus and modulus-to-error ratio.\r\n"
alternative_title:
- LNCS
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Stephan
full_name: Krenn, Stephan
id: 329FCCF0-F248-11E8-B48F-1D18A9856A87
last_name: Krenn
orcid: 0000-0003-2835-9093
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. Learning with rounding, revisited:
New reduction properties and applications. 2013;8042(1):57-74. doi:10.1007/978-3-642-40041-4_4'
apa: 'Alwen, J. F., Krenn, S., Pietrzak, K. Z., & Wichs, D. (2013). Learning
with rounding, revisited: New reduction properties and applications. Presented
at the CRYPTO: International Cryptology Conference, Santa Barbara, CA, United
States: Springer. https://doi.org/10.1007/978-3-642-40041-4_4'
chicago: 'Alwen, Joel F, Stephan Krenn, Krzysztof Z Pietrzak, and Daniel Wichs.
“Learning with Rounding, Revisited: New Reduction Properties and Applications.”
Lecture Notes in Computer Science. Springer, 2013. https://doi.org/10.1007/978-3-642-40041-4_4.'
ieee: 'J. F. Alwen, S. Krenn, K. Z. Pietrzak, and D. Wichs, “Learning with rounding,
revisited: New reduction properties and applications,” vol. 8042, no. 1. Springer,
pp. 57–74, 2013.'
ista: 'Alwen JF, Krenn S, Pietrzak KZ, Wichs D. 2013. Learning with rounding, revisited:
New reduction properties and applications. 8042(1), 57–74.'
mla: 'Alwen, Joel F., et al. Learning with Rounding, Revisited: New Reduction
Properties and Applications. Vol. 8042, no. 1, Springer, 2013, pp. 57–74,
doi:10.1007/978-3-642-40041-4_4.'
short: J.F. Alwen, S. Krenn, K.Z. Pietrzak, D. Wichs, 8042 (2013) 57–74.
conference:
end_date: 2013-08-22
location: Santa Barbara, CA, United States
name: 'CRYPTO: International Cryptology Conference'
start_date: 2013-08-18
date_created: 2018-12-11T11:56:37Z
date_published: 2013-01-01T00:00:00Z
date_updated: 2021-01-12T06:56:21Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-642-40041-4_4
ec_funded: 1
file:
- access_level: open_access
checksum: 16d428408a806b8e49eecc607deab115
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:11:55Z
date_updated: 2020-07-14T12:45:35Z
file_id: '4912'
file_name: IST-2016-684-v1+1_098.pdf
file_size: 587898
relation: main_file
file_date_updated: 2020-07-14T12:45:35Z
has_accepted_license: '1'
intvolume: ' 8042'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 57 - 74
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication_status: published
publisher: Springer
publist_id: '4687'
pubrep_id: '684'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'Learning with rounding, revisited: New reduction properties and applications'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8042
year: '2013'
...