---
_id: '650'
abstract:
- lang: eng
text: 'In this work we present a short and unified proof for the Strong and Weak
Regularity Lemma, based on the cryptographic tech-nique called low-complexity
approximations. In short, both problems reduce to a task of finding constructively
an approximation for a certain target function under a class of distinguishers
(test functions), where dis-tinguishers are combinations of simple rectangle-indicators.
In our case these approximations can be learned by a simple iterative procedure,
which yields a unified and simple proof, achieving for any graph with density
d and any approximation parameter the partition size. The novelty in our proof
is: (a) a simple approach which yields both strong and weaker variant, and (b)
improvements when d = o(1). At an abstract level, our proof can be seen a refinement
and simplification of the “analytic” proof given by Lovasz and Szegedy.'
alternative_title:
- LNCS
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. A cryptographic view of regularity lemmas: Simpler unified proofs
and refined bounds. In: Jäger G, Steila S, eds. Vol 10185. Springer; 2017:586-599.
doi:10.1007/978-3-319-55911-7_42'
apa: 'Skórski, M. (2017). A cryptographic view of regularity lemmas: Simpler unified
proofs and refined bounds. In G. Jäger & S. Steila (Eds.) (Vol. 10185, pp.
586–599). Presented at the TAMC: Theory and Applications of Models of Computation,
Bern, Switzerland: Springer. https://doi.org/10.1007/978-3-319-55911-7_42'
chicago: 'Skórski, Maciej. “A Cryptographic View of Regularity Lemmas: Simpler Unified
Proofs and Refined Bounds.” edited by Gerhard Jäger and Silvia Steila, 10185:586–99.
Springer, 2017. https://doi.org/10.1007/978-3-319-55911-7_42.'
ieee: 'M. Skórski, “A cryptographic view of regularity lemmas: Simpler unified proofs
and refined bounds,” presented at the TAMC: Theory and Applications of Models
of Computation, Bern, Switzerland, 2017, vol. 10185, pp. 586–599.'
ista: 'Skórski M. 2017. A cryptographic view of regularity lemmas: Simpler unified
proofs and refined bounds. TAMC: Theory and Applications of Models of Computation,
LNCS, vol. 10185, 586–599.'
mla: 'Skórski, Maciej. A Cryptographic View of Regularity Lemmas: Simpler Unified
Proofs and Refined Bounds. Edited by Gerhard Jäger and Silvia Steila, vol.
10185, Springer, 2017, pp. 586–99, doi:10.1007/978-3-319-55911-7_42.'
short: M. Skórski, in:, G. Jäger, S. Steila (Eds.), Springer, 2017, pp. 586–599.
conference:
end_date: 2017-04-22
location: Bern, Switzerland
name: 'TAMC: Theory and Applications of Models of Computation'
start_date: 2017-04-20
date_created: 2018-12-11T11:47:42Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2021-01-12T08:07:46Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-55911-7_42
editor:
- first_name: Gerhard
full_name: Jäger, Gerhard
last_name: Jäger
- first_name: Silvia
full_name: Steila, Silvia
last_name: Steila
intvolume: ' 10185'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/965.pdf
month: '01'
oa: 1
oa_version: Submitted Version
page: 586 - 599
publication_identifier:
issn:
- '03029743'
publication_status: published
publisher: Springer
publist_id: '7119'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'A cryptographic view of regularity lemmas: Simpler unified proofs and refined
bounds'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10185
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: '6526'
abstract:
- lang: eng
text: 'This paper studies the complexity of estimating Rényi divergences of discrete
distributions: p observed from samples and the baseline distribution q known a
priori. Extending the results of Acharya et al. (SODA''15) on estimating Rényi
entropy, we present improved estimation techniques together with upper and lower
bounds on the sample complexity. We show that, contrarily to estimating Rényi
entropy where a sublinear (in the alphabet size) number of samples suffices, the
sample complexity is heavily dependent on events occurring unlikely in q, and
is unbounded in general (no matter what an estimation technique is used). For
any divergence of integer order bigger than 1, we provide upper and lower bounds
on the number of samples dependent on probabilities of p and q (the lower bounds
hold for non-integer orders as well). We conclude that the worst-case sample complexity
is polynomial in the alphabet size if and only if the probabilities of q are non-negligible.
This gives theoretical insights into heuristics used in the applied literature
to handle numerical instability, which occurs for small probabilities of q. Our
result shows that they should be handled with care not only because of numerical
issues, but also because of a blow up in the sample complexity.'
article_number: '8006529'
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. On the complexity of estimating Rènyi divergences. In: 2017
IEEE International Symposium on Information Theory (ISIT). IEEE; 2017. doi:10.1109/isit.2017.8006529'
apa: 'Skórski, M. (2017). On the complexity of estimating Rènyi divergences. In
2017 IEEE International Symposium on Information Theory (ISIT). Aachen,
Germany: IEEE. https://doi.org/10.1109/isit.2017.8006529'
chicago: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” In
2017 IEEE International Symposium on Information Theory (ISIT). IEEE, 2017.
https://doi.org/10.1109/isit.2017.8006529.
ieee: M. Skórski, “On the complexity of estimating Rènyi divergences,” in 2017
IEEE International Symposium on Information Theory (ISIT), Aachen, Germany,
2017.
ista: 'Skórski M. 2017. On the complexity of estimating Rènyi divergences. 2017
IEEE International Symposium on Information Theory (ISIT). ISIT: International
Symposium on Information Theory, 8006529.'
mla: Skórski, Maciej. “On the Complexity of Estimating Rènyi Divergences.” 2017
IEEE International Symposium on Information Theory (ISIT), 8006529, IEEE,
2017, doi:10.1109/isit.2017.8006529.
short: M. Skórski, in:, 2017 IEEE International Symposium on Information Theory
(ISIT), IEEE, 2017.
conference:
end_date: 2017-06-30
location: Aachen, Germany
name: 'ISIT: International Symposium on Information Theory'
start_date: 2017-06-25
date_created: 2019-06-06T12:53:09Z
date_published: 2017-08-09T00:00:00Z
date_updated: 2021-01-12T08:07:53Z
day: '09'
department:
- _id: KrPi
doi: 10.1109/isit.2017.8006529
ec_funded: 1
external_id:
arxiv:
- '1702.01666'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://arxiv.org/abs/1702.01666
month: '08'
oa: 1
oa_version: Preprint
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: 2017 IEEE International Symposium on Information Theory (ISIT)
publication_identifier:
isbn:
- '9781509040964'
publication_status: published
publisher: IEEE
quality_controlled: '1'
scopus_import: 1
status: public
title: On the complexity of estimating Rènyi divergences
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
year: '2017'
...
---
_id: '697'
abstract:
- lang: eng
text: 'De, Trevisan and Tulsiani [CRYPTO 2010] show that every distribution over
n-bit strings which has constant statistical distance to uniform (e.g., the output
of a pseudorandom generator mapping n-1 to n bit strings), can be distinguished
from the uniform distribution with advantage epsilon by a circuit of size O( 2^n
epsilon^2). We generalize this result, showing that a distribution which has less
than k bits of min-entropy, can be distinguished from any distribution with k
bits of delta-smooth min-entropy with advantage epsilon by a circuit of size O(2^k
epsilon^2/delta^2). As a special case, this implies that any distribution with
support at most 2^k (e.g., the output of a pseudoentropy generator mapping k to
n bit strings) can be distinguished from any given distribution with min-entropy
k+1 with advantage epsilon by a circuit of size O(2^k epsilon^2). Our result thus
shows that pseudoentropy distributions face basically the same non-uniform attacks
as pseudorandom distributions. '
alternative_title:
- LIPIcs
article_number: '39'
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: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Pietrzak KZ, Skórski M. Non uniform attacks against pseudoentropy. In: Vol
80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.ICALP.2017.39'
apa: 'Pietrzak, K. Z., & Skórski, M. (2017). Non uniform attacks against pseudoentropy
(Vol. 80). Presented at the ICALP: International Colloquium on Automata, Languages,
and Programming, Warsaw, Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.ICALP.2017.39'
chicago: Pietrzak, Krzysztof Z, and Maciej Skórski. “Non Uniform Attacks against
Pseudoentropy,” Vol. 80. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
https://doi.org/10.4230/LIPIcs.ICALP.2017.39.
ieee: 'K. Z. Pietrzak and M. Skórski, “Non uniform attacks against pseudoentropy,”
presented at the ICALP: International Colloquium on Automata, Languages, and Programming,
Warsaw, Poland, 2017, vol. 80.'
ista: 'Pietrzak KZ, Skórski M. 2017. Non uniform attacks against pseudoentropy.
ICALP: International Colloquium on Automata, Languages, and Programming, LIPIcs,
vol. 80, 39.'
mla: Pietrzak, Krzysztof Z., and Maciej Skórski. Non Uniform Attacks against
Pseudoentropy. Vol. 80, 39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017, doi:10.4230/LIPIcs.ICALP.2017.39.
short: K.Z. Pietrzak, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017.
conference:
end_date: 2017-07-14
location: Warsaw, Poland
name: 'ICALP: International Colloquium on Automata, Languages, and Programming'
start_date: 2017-07-10
date_created: 2018-12-11T11:47:59Z
date_published: 2017-07-01T00:00:00Z
date_updated: 2021-01-12T08:11:15Z
day: '01'
ddc:
- '005'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.ICALP.2017.39
ec_funded: 1
file:
- access_level: open_access
checksum: e95618a001692f1af2d68f5fde43bc1f
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:08:40Z
date_updated: 2020-07-14T12:47:46Z
file_id: '4701'
file_name: IST-2017-893-v1+1_LIPIcs-ICALP-2017-39.pdf
file_size: 601004
relation: main_file
file_date_updated: 2020-07-14T12:47:46Z
has_accepted_license: '1'
intvolume: ' 80'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '7003'
pubrep_id: '893'
quality_controlled: '1'
scopus_import: 1
status: public
title: Non uniform attacks against pseudoentropy
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 80
year: '2017'
...
---
_id: '710'
abstract:
- lang: eng
text: 'We revisit the problem of estimating entropy of discrete distributions from
independent samples, studied recently by Acharya, Orlitsky, Suresh and Tyagi (SODA
2015), improving their upper and lower bounds on the necessary sample size n.
For estimating Renyi entropy of order alpha, up to constant accuracy and error
probability, we show the following * Upper bounds n = O(1) 2^{(1-1/alpha)H_alpha}
for integer alpha>1, as the worst case over distributions with Renyi entropy
equal to H_alpha. * Lower bounds n = Omega(1) K^{1-1/alpha} for any real alpha>1,
with the constant being an inverse polynomial of the accuracy, as the worst case
over all distributions on K elements. Our upper bounds essentially replace the
alphabet size by a factor exponential in the entropy, which offers improvements
especially in low or medium entropy regimes (interesting for example in anomaly
detection). As for the lower bounds, our proof explicitly shows how the complexity
depends on both alphabet and accuracy, partially solving the open problem posted
in previous works. The argument for upper bounds derives a clean identity for
the variance of falling-power sum of a multinomial distribution. Our approach
for lower bounds utilizes convex optimization to find a distribution with possibly
worse estimation performance, and may be of independent interest as a tool to
work with Le Cam’s two point method. '
alternative_title:
- LIPIcs
article_number: '20'
author:
- first_name: Maciej
full_name: Obremski, Maciej
last_name: Obremski
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Obremski M, Skórski M. Renyi entropy estimation revisited. In: Vol 81. Schloss
Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20'
apa: 'Obremski, M., & Skórski, M. (2017). Renyi entropy estimation revisited
(Vol. 81). Presented at the 20th International Workshop on Approximation Algorithms
for Combinatorial Optimization Problems, APPROX, Berkeley, USA: Schloss Dagstuhl
- Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20'
chicago: Obremski, Maciej, and Maciej Skórski. “Renyi Entropy Estimation Revisited,”
Vol. 81. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2017.20.
ieee: M. Obremski and M. Skórski, “Renyi entropy estimation revisited,” presented
at the 20th International Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, APPROX, Berkeley, USA, 2017, vol. 81.
ista: Obremski M, Skórski M. 2017. Renyi entropy estimation revisited. 20th International
Workshop on Approximation Algorithms for Combinatorial Optimization Problems,
APPROX, LIPIcs, vol. 81, 20.
mla: Obremski, Maciej, and Maciej Skórski. Renyi Entropy Estimation Revisited.
Vol. 81, 20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.APPROX-RANDOM.2017.20.
short: M. Obremski, M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2017.
conference:
end_date: 2017-08-18
location: Berkeley, USA
name: 20th International Workshop on Approximation Algorithms for Combinatorial
Optimization Problems, APPROX
start_date: 2017-08-18
date_created: 2018-12-11T11:48:04Z
date_published: 2017-08-01T00:00:00Z
date_updated: 2021-01-12T08:11:50Z
day: '01'
ddc:
- '005'
- '600'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.APPROX-RANDOM.2017.20
ec_funded: 1
file:
- access_level: open_access
checksum: 89225c7dcec2c93838458c9102858985
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:10Z
date_updated: 2020-07-14T12:47:49Z
file_id: '4991'
file_name: IST-2017-888-v1+1_LIPIcs-APPROX-RANDOM-2017-20.pdf
file_size: 604813
relation: main_file
file_date_updated: 2020-07-14T12:47:49Z
has_accepted_license: '1'
intvolume: ' 81'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6979'
pubrep_id: '888'
quality_controlled: '1'
scopus_import: 1
status: public
title: Renyi entropy estimation revisited
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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 81
year: '2017'
...
---
_id: '838'
abstract:
- lang: eng
text: 'In this thesis we discuss the exact security of message authentications codes
HMAC , NMAC , and PMAC . NMAC is a mode of operation which turns a fixed input-length
keyed hash function f into a variable input-length function. A practical single-key
variant of NMAC called HMAC is a very popular and widely deployed message authentication
code (MAC). PMAC is a block-cipher based mode of operation, which also happens
to be the most famous fully parallel MAC. NMAC was introduced by Bellare, Canetti
and Krawczyk Crypto’96, who proved it to be a secure pseudorandom function (PRF),
and thus also a MAC, under two assumptions. Unfortunately, for many instantiations
of HMAC one of them has been found to be wrong. To restore the provable guarantees
for NMAC , Bellare [Crypto’06] showed its security without this assumption. PMAC
was introduced by Black and Rogaway at Eurocrypt 2002. If instantiated with a
pseudorandom permutation over n -bit strings, PMAC constitutes a provably secure
variable input-length PRF. For adversaries making q queries, each of length at
most ` (in n -bit blocks), and of total length σ ≤ q` , the original paper proves
an upper bound on the distinguishing advantage of O ( σ 2 / 2 n ), while the currently
best bound is O ( qσ/ 2 n ). In this work we show that this bound is tight by
giving an attack with advantage Ω( q 2 `/ 2 n ). In the PMAC construction one
initially XORs a mask to every message block, where the mask for the i th block
is computed as τ i := γ i · L , where L is a (secret) random value, and γ i is
the i -th codeword of the Gray code. Our attack applies more generally to any
sequence of γ i ’s which contains a large coset of a subgroup of GF (2 n ). As
for NMAC , our first contribution is a simpler and uniform proof: If f is an ε
-secure PRF (against q queries) and a δ - non-adaptively secure PRF (against q
queries), then NMAC f is an ( ε + `qδ )-secure PRF against q queries of length
at most ` blocks each. We also show that this ε + `qδ bound is basically tight
by constructing an f for which an attack with advantage `qδ exists. Moreover,
we analyze the PRF-security of a modification of NMAC called NI by An and Bellare
that avoids the constant rekeying on multi-block messages in NMAC and allows for
an information-theoretic analysis. We carry out such an analysis, obtaining a
tight `q 2 / 2 c bound for this step, improving over the trivial bound of ` 2
q 2 / 2 c . Finally, we investigate, if the security of PMAC can be further improved
by using τ i ’s that are k -wise independent, for k > 1 (the original has k
= 1). We observe that the security of PMAC will not increase in general if k =
2, and then prove that the security increases to O ( q 2 / 2 n ), if the k = 4.
Due to simple extension attacks, this is the best bound one can hope for, using
any distribution on the masks. Whether k = 3 is already sufficient to get this
level of security is left as an open problem. Keywords: Message authentication
codes, Pseudorandom functions, HMAC, PMAC. '
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: Rybar M. (The exact security of) Message authentication codes. 2017. doi:10.15479/AT:ISTA:th_828
apa: Rybar, M. (2017). (The exact security of) Message authentication codes.
Institute of Science and Technology Austria. https://doi.org/10.15479/AT:ISTA:th_828
chicago: Rybar, Michal. “(The Exact Security of) Message Authentication Codes.”
Institute of Science and Technology Austria, 2017. https://doi.org/10.15479/AT:ISTA:th_828.
ieee: M. Rybar, “(The exact security of) Message authentication codes,” Institute
of Science and Technology Austria, 2017.
ista: Rybar M. 2017. (The exact security of) Message authentication codes. Institute
of Science and Technology Austria.
mla: Rybar, Michal. (The Exact Security of) Message Authentication Codes.
Institute of Science and Technology Austria, 2017, doi:10.15479/AT:ISTA:th_828.
short: M. Rybar, (The Exact Security of) Message Authentication Codes, Institute
of Science and Technology Austria, 2017.
date_created: 2018-12-11T11:48:46Z
date_published: 2017-06-26T00:00:00Z
date_updated: 2023-09-07T12:02:28Z
day: '26'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: KrPi
doi: 10.15479/AT:ISTA:th_828
file:
- access_level: open_access
checksum: ff8639ec4bded6186f44c7bd3ee26804
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:10:13Z
date_updated: 2020-07-14T12:48:12Z
file_id: '4799'
file_name: IST-2017-828-v1+3_2017_Rybar_thesis.pdf
file_size: 847400
relation: main_file
- access_level: closed
checksum: 3462101745ce8ad199c2d0f75dae4a7e
content_type: application/zip
creator: dernst
date_created: 2019-04-05T08:24:11Z
date_updated: 2020-07-14T12:48:12Z
file_id: '6202'
file_name: 2017_Thesis_Rybar_source.zip
file_size: 26054879
relation: source_file
file_date_updated: 2020-07-14T12:48:12Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '86'
publication_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publist_id: '6810'
pubrep_id: '828'
related_material:
record:
- id: '2082'
relation: part_of_dissertation
status: public
- id: '6196'
relation: part_of_dissertation
status: public
status: public
title: (The exact security of) Message authentication codes
type: dissertation
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2017'
...
---
_id: '6196'
abstract:
- lang: eng
text: PMAC is a simple and parallel block-cipher mode of operation, which was introduced
by Black and Rogaway at Eurocrypt 2002. If instantiated with a (pseudo)random
permutation over n-bit strings, PMAC constitutes a provably secure variable input-length
(pseudo)random function. For adversaries making q queries, each of length at most
l (in n-bit blocks), and of total length σ ≤ ql, the original paper proves an
upper bound on the distinguishing advantage of Ο(σ2/2n), while the currently
best bound is Ο (qσ/2n).In this work we show that this bound is tight by giving
an attack with advantage Ω (q2l/2n). In the PMAC construction one initially XORs
a mask to every message block, where the mask for the ith block is computed as
τi := γi·L, where L is a (secret) random value, and γi is the i-th codeword of
the Gray code. Our attack applies more generally to any sequence of γi’s which
contains a large coset of a subgroup of GF(2n). We then investigate if the security
of PMAC can be further improved by using τi’s that are k-wise independent, for
k > 1 (the original distribution is only 1-wise independent). We observe that
the security of PMAC will not increase in general, even if the masks are chosen
from a 2-wise independent distribution, and then prove that the security increases
to O(q<2/2n), if the τi are 4-wise independent. Due to simple extension attacks,
this is the best bound one can hope for, using any distribution on the masks.
Whether 3-wise independence is already sufficient to get this level of security
is left as an open problem.
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- 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: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: Gazi P, Pietrzak KZ, Rybar M. The exact security of PMAC. IACR Transactions
on Symmetric Cryptology. 2017;2016(2):145-161. doi:10.13154/TOSC.V2016.I2.145-161
apa: Gazi, P., Pietrzak, K. Z., & Rybar, M. (2017). The exact security of PMAC.
IACR Transactions on Symmetric Cryptology. Ruhr University Bochum. https://doi.org/10.13154/TOSC.V2016.I2.145-161
chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security
of PMAC.” IACR Transactions on Symmetric Cryptology. Ruhr University Bochum,
2017. https://doi.org/10.13154/TOSC.V2016.I2.145-161.
ieee: P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” IACR
Transactions on Symmetric Cryptology, vol. 2016, no. 2. Ruhr University Bochum,
pp. 145–161, 2017.
ista: Gazi P, Pietrzak KZ, Rybar M. 2017. The exact security of PMAC. IACR Transactions
on Symmetric Cryptology. 2016(2), 145–161.
mla: Gazi, Peter, et al. “The Exact Security of PMAC.” IACR Transactions on Symmetric
Cryptology, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:10.13154/TOSC.V2016.I2.145-161.
short: P. Gazi, K.Z. Pietrzak, M. Rybar, IACR Transactions on Symmetric Cryptology
2016 (2017) 145–161.
date_created: 2019-04-04T13:48:23Z
date_published: 2017-02-03T00:00:00Z
date_updated: 2023-09-07T12:02:27Z
day: '03'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.13154/TOSC.V2016.I2.145-161
ec_funded: 1
file:
- access_level: open_access
checksum: f23161d685dd957ae8d7274132999684
content_type: application/pdf
creator: dernst
date_created: 2019-04-04T13:53:58Z
date_updated: 2020-07-14T12:47:24Z
file_id: '6197'
file_name: 2017_IACR_Gazi.pdf
file_size: 597335
relation: main_file
file_date_updated: 2020-07-14T12:47:24Z
has_accepted_license: '1'
intvolume: ' 2016'
issue: '2'
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
page: 145-161
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: IACR Transactions on Symmetric Cryptology
publication_identifier:
eissn:
- 2519-173X
publication_status: published
publisher: Ruhr University Bochum
quality_controlled: '1'
related_material:
record:
- id: '838'
relation: dissertation_contains
status: public
status: public
title: The exact security of PMAC
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: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 2016
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: '637'
abstract:
- lang: eng
text: For many cryptographic primitives, it is relatively easy to achieve selective
security (where the adversary commits a-priori to some of the choices to be made
later in the attack) but appears difficult to achieve the more natural notion
of adaptive security (where the adversary can make all choices on the go as the
attack progresses). A series of several recent works shows how to cleverly achieve
adaptive security in several such scenarios including generalized selective decryption
(Panjwani, TCC ’07 and Fuchsbauer et al., CRYPTO ’15), constrained PRFs (Fuchsbauer
et al., ASIACRYPT ’14), and Yao garbled circuits (Jafargholi and Wichs, TCC ’16b).
Although the above works expressed vague intuition that they share a common technique,
the connection was never made precise. In this work we present a new framework
that connects all of these works and allows us to present them in a unified and
simplified fashion. Moreover, we use the framework to derive a new result for
adaptively secure secret sharing over access structures defined via monotone circuits.
We envision that further applications will follow in the future. Underlying our
framework is the following simple idea. It is well known that selective security,
where the adversary commits to n-bits of information about his future choices,
automatically implies adaptive security at the cost of amplifying the adversary’s
advantage by a factor of up to 2n. However, in some cases the proof of selective
security proceeds via a sequence of hybrids, where each pair of adjacent hybrids
locally only requires some smaller partial information consisting of m ≪ n bits.
The partial information needed might be completely different between different
pairs of hybrids, and if we look across all the hybrids we might rely on the entire
n-bit commitment. Nevertheless, the above is sufficient to prove adaptive security,
at the cost of amplifying the adversary’s advantage by a factor of only 2m ≪ 2n.
In all of our examples using the above framework, the different hybrids are captured
by some sort of a graph pebbling game and the amount of information that the adversary
needs to commit to in each pair of hybrids is bounded by the maximum number of
pebbles in play at any point in time. Therefore, coming up with better strategies
for proving adaptive security translates to various pebbling strategies for different
types of graphs.
alternative_title:
- LNCS
author:
- first_name: Zahra
full_name: Jafargholi, Zahra
last_name: Jafargholi
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Ilan
full_name: Komargodski, Ilan
last_name: Komargodski
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Daniel
full_name: Wichs, Daniel
last_name: Wichs
citation:
ama: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs
D. Be adaptive avoid overcommitting. In: Katz J, Shacham H, eds. Vol 10401. Springer;
2017:133-163. doi:10.1007/978-3-319-63688-7_5'
apa: 'Jafargholi, Z., Kamath Hosdurg, C., Klein, K., Komargodski, I., Pietrzak,
K. Z., & Wichs, D. (2017). Be adaptive avoid overcommitting. In J. Katz &
H. Shacham (Eds.) (Vol. 10401, pp. 133–163). Presented at the CRYPTO: Cryptology,
Santa Barbara, CA, United States: Springer. https://doi.org/10.1007/978-3-319-63688-7_5'
chicago: Jafargholi, Zahra, Chethan Kamath Hosdurg, Karen Klein, Ilan Komargodski,
Krzysztof Z Pietrzak, and Daniel Wichs. “Be Adaptive Avoid Overcommitting.” edited
by Jonathan Katz and Hovav Shacham, 10401:133–63. Springer, 2017. https://doi.org/10.1007/978-3-319-63688-7_5.
ieee: 'Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K. Z. Pietrzak,
and D. Wichs, “Be adaptive avoid overcommitting,” presented at the CRYPTO: Cryptology,
Santa Barbara, CA, United States, 2017, vol. 10401, pp. 133–163.'
ista: 'Jafargholi Z, Kamath Hosdurg C, Klein K, Komargodski I, Pietrzak KZ, Wichs
D. 2017. Be adaptive avoid overcommitting. CRYPTO: Cryptology, LNCS, vol. 10401,
133–163.'
mla: Jafargholi, Zahra, et al. Be Adaptive Avoid Overcommitting. Edited by
Jonathan Katz and Hovav Shacham, vol. 10401, Springer, 2017, pp. 133–63, doi:10.1007/978-3-319-63688-7_5.
short: Z. Jafargholi, C. Kamath Hosdurg, K. Klein, I. Komargodski, K.Z. Pietrzak,
D. Wichs, in:, J. Katz, H. Shacham (Eds.), Springer, 2017, pp. 133–163.
conference:
end_date: 2017-07-24
location: Santa Barbara, CA, United States
name: 'CRYPTO: Cryptology'
start_date: 2017-07-20
date_created: 2018-12-11T11:47:38Z
date_published: 2017-01-01T00:00:00Z
date_updated: 2023-09-07T13:32:11Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-63688-7_5
ec_funded: 1
editor:
- first_name: Jonathan
full_name: Katz, Jonathan
last_name: Katz
- first_name: Hovav
full_name: Shacham, Hovav
last_name: Shacham
intvolume: ' 10401'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2017/515
month: '01'
oa: 1
oa_version: Submitted Version
page: 133 - 163
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_identifier:
isbn:
- 978-331963687-0
publication_status: published
publisher: Springer
publist_id: '7151'
quality_controlled: '1'
related_material:
record:
- id: '10035'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Be adaptive avoid overcommitting
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 10401
year: '2017'
...
---
_id: '1174'
abstract:
- lang: eng
text: Security of cryptographic applications is typically defined by security games.
The adversary, within certain resources, cannot win with probability much better
than 0 (for unpredictability applications, like one-way functions) or much better
than 1/2 (indistinguishability applications for instance encryption schemes).
In so called squared-friendly applications the winning probability of the adversary,
for different values of the application secret randomness, is not only close to
0 or 1/2 on average, but also concentrated in the sense that its second central
moment is small. The class of squared-friendly applications, which contains all
unpredictability applications and many indistinguishability applications, is particularly
important for key derivation. Barak et al. observed that for square-friendly applications
one can beat the "RT-bound", extracting secure keys with significantly
smaller entropy loss. In turn Dodis and Yu showed that in squared-friendly applications
one can directly use a "weak" key, which has only high entropy, as a
secure key. In this paper we give sharp lower bounds on square security assuming
security for "weak" keys. We show that any application which is either
(a) secure with weak keys or (b) allows for entropy savings for keys derived by
universal hashing, must be square-friendly. Quantitatively, our lower bounds match
the positive results of Dodis and Yu and Barak et al. (TCC\'13, CRYPTO\'11) Hence,
they can be understood as a general characterization of squared-friendly applications.
While the positive results on squared-friendly applications where derived by one
clever application of the Cauchy-Schwarz Inequality, for tight lower bounds we
need more machinery. In our approach we use convex optimization techniques and
some theory of circular matrices.
alternative_title:
- LIPIcs
article_number: '57'
article_processing_charge: No
author:
- first_name: Maciej
full_name: Skórski, Maciej
id: EC09FA6A-02D0-11E9-8223-86B7C91467DD
last_name: Skórski
citation:
ama: 'Skórski M. Lower bounds on key derivation for square-friendly applications.
In: Vol 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.STACS.2017.57'
apa: 'Skórski, M. (2017). Lower bounds on key derivation for square-friendly applications
(Vol. 66). Presented at the STACS: Symposium on Theoretical Aspects of Computer
Science, Hannover, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
https://doi.org/10.4230/LIPIcs.STACS.2017.57'
chicago: Skórski, Maciej. “Lower Bounds on Key Derivation for Square-Friendly Applications,”
Vol. 66. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.STACS.2017.57.
ieee: 'M. Skórski, “Lower bounds on key derivation for square-friendly applications,”
presented at the STACS: Symposium on Theoretical Aspects of Computer Science,
Hannover, Germany, 2017, vol. 66.'
ista: 'Skórski M. 2017. Lower bounds on key derivation for square-friendly applications.
STACS: Symposium on Theoretical Aspects of Computer Science, LIPIcs, vol. 66,
57.'
mla: Skórski, Maciej. Lower Bounds on Key Derivation for Square-Friendly Applications.
Vol. 66, 57, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.STACS.2017.57.
short: M. Skórski, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
conference:
end_date: 2017-03-11
location: Hannover, Germany
name: 'STACS: Symposium on Theoretical Aspects of Computer Science'
start_date: 2017-03-08
date_created: 2018-12-11T11:50:32Z
date_published: 2017-03-01T00:00:00Z
date_updated: 2023-09-20T11:23:15Z
day: '01'
department:
- _id: KrPi
doi: 10.4230/LIPIcs.STACS.2017.57
ec_funded: 1
external_id:
isi:
- '000521077300057'
intvolume: ' 66'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://drops.dagstuhl.de/opus/volltexte/2017/6976
month: '03'
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:
issn:
- '18688969'
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6180'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Lower bounds on key derivation for square-friendly applications
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 66
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: '1187'
abstract:
- lang: eng
text: We construct efficient authentication protocols and message authentication
codes (MACs) whose security can be reduced to the learning parity with noise (LPN)
problem. Despite a large body of work—starting with the (Formula presented.) protocol
of Hopper and Blum in 2001—until now it was not even known how to construct an
efficient authentication protocol from LPN which is secure against man-in-the-middle
attacks. A MAC implies such a (two-round) protocol.
article_processing_charge: No
article_type: original
author:
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- 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: Daniele
full_name: Venturi, Daniele
last_name: Venturi
- first_name: David
full_name: Cash, David
last_name: Cash
- first_name: Abhishek
full_name: Jain, Abhishek
last_name: Jain
citation:
ama: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. Efficient authentication from
hard learning problems. Journal of Cryptology. 2017;30(4):1238-1275. doi:10.1007/s00145-016-9247-3
apa: Kiltz, E., Pietrzak, K. Z., Venturi, D., Cash, D., & Jain, A. (2017). Efficient
authentication from hard learning problems. Journal of Cryptology. Springer.
https://doi.org/10.1007/s00145-016-9247-3
chicago: Kiltz, Eike, Krzysztof Z Pietrzak, Daniele Venturi, David Cash, and Abhishek
Jain. “Efficient Authentication from Hard Learning Problems.” Journal of Cryptology.
Springer, 2017. https://doi.org/10.1007/s00145-016-9247-3.
ieee: E. Kiltz, K. Z. Pietrzak, D. Venturi, D. Cash, and A. Jain, “Efficient authentication
from hard learning problems,” Journal of Cryptology, vol. 30, no. 4. Springer,
pp. 1238–1275, 2017.
ista: Kiltz E, Pietrzak KZ, Venturi D, Cash D, Jain A. 2017. Efficient authentication
from hard learning problems. Journal of Cryptology. 30(4), 1238–1275.
mla: Kiltz, Eike, et al. “Efficient Authentication from Hard Learning Problems.”
Journal of Cryptology, vol. 30, no. 4, Springer, 2017, pp. 1238–75, doi:10.1007/s00145-016-9247-3.
short: E. Kiltz, K.Z. Pietrzak, D. Venturi, D. Cash, A. Jain, Journal of Cryptology
30 (2017) 1238–1275.
date_created: 2018-12-11T11:50:37Z
date_published: 2017-10-01T00:00:00Z
date_updated: 2023-09-20T11:20:58Z
day: '01'
ddc:
- '000'
department:
- _id: KrPi
doi: 10.1007/s00145-016-9247-3
ec_funded: 1
external_id:
isi:
- '000410788600007'
file:
- access_level: open_access
checksum: c647520d115b772a1682fc06fa273eb1
content_type: application/pdf
creator: dernst
date_created: 2020-05-14T16:30:17Z
date_updated: 2020-07-14T12:44:37Z
file_id: '7843'
file_name: 2017_JournalCrypto_Kiltz.pdf
file_size: 516959
relation: main_file
file_date_updated: 2020-07-14T12:44:37Z
has_accepted_license: '1'
intvolume: ' 30'
isi: 1
issue: '4'
language:
- iso: eng
month: '10'
oa: 1
oa_version: Submitted Version
page: 1238 - 1275
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '6166'
quality_controlled: '1'
related_material:
record:
- id: '3238'
relation: earlier_version
status: public
scopus_import: '1'
status: public
title: Efficient authentication from hard learning problems
type: journal_article
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 30
year: '2017'
...
---
_id: '1177'
abstract:
- lang: eng
text: Boldyreva, Palacio and Warinschi introduced a multiple forking game as an
extension of general forking. The notion of (multiple) forking is a useful abstraction
from the actual simulation of cryptographic scheme to the adversary in a security
reduction, and is achieved through the intermediary of a so-called wrapper algorithm.
Multiple forking has turned out to be a useful tool in the security argument of
several cryptographic protocols. However, a reduction employing multiple forking
incurs a significant degradation of (Formula presented.) , where (Formula presented.)
denotes the upper bound on the underlying random oracle calls and (Formula presented.)
, the number of forkings. In this work we take a closer look at the reasons for
the degradation with a tighter security bound in mind. We nail down the exact
set of conditions for success in the multiple forking game. A careful analysis
of the cryptographic schemes and corresponding security reduction employing multiple
forking leads to the formulation of ‘dependence’ and ‘independence’ conditions
pertaining to the output of the wrapper in different rounds. Based on the (in)dependence
conditions we propose a general framework of multiple forking and a General Multiple
Forking Lemma. Leveraging (in)dependence to the full allows us to improve the
degradation factor in the multiple forking game by a factor of (Formula presented.).
By implication, the cost of a single forking involving two random oracles (augmented
forking) matches that involving a single random oracle (elementary forking). Finally,
we study the effect of these observations on the concrete security of existing
schemes employing multiple forking. We conclude that by careful design of the
protocol (and the wrapper in the security reduction) it is possible to harness
our observations to the full extent.
acknowledgement: "We are grateful to the anonymous reviewers for their insightful
comments. The\r\ndetailed reports helped us a lot to address the technical mistakes
as well as to improve the overall presentation of the paper."
author:
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Sanjit
full_name: Chatterjee, Sanjit
last_name: Chatterjee
citation:
ama: 'Kamath Hosdurg C, Chatterjee S. A closer look at multiple-forking: Leveraging
(in)dependence for a tighter bound. Algorithmica. 2016;74(4):1321-1362.
doi:10.1007/s00453-015-9997-6'
apa: 'Kamath Hosdurg, C., & Chatterjee, S. (2016). A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound. Algorithmica. Springer.
https://doi.org/10.1007/s00453-015-9997-6'
chicago: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking:
Leveraging (in)Dependence for a Tighter Bound.” Algorithmica. Springer,
2016. https://doi.org/10.1007/s00453-015-9997-6.'
ieee: 'C. Kamath Hosdurg and S. Chatterjee, “A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound,” Algorithmica, vol. 74,
no. 4. Springer, pp. 1321–1362, 2016.'
ista: 'Kamath Hosdurg C, Chatterjee S. 2016. A closer look at multiple-forking:
Leveraging (in)dependence for a tighter bound. Algorithmica. 74(4), 1321–1362.'
mla: 'Kamath Hosdurg, Chethan, and Sanjit Chatterjee. “A Closer Look at Multiple-Forking:
Leveraging (in)Dependence for a Tighter Bound.” Algorithmica, vol. 74,
no. 4, Springer, 2016, pp. 1321–62, doi:10.1007/s00453-015-9997-6.'
short: C. Kamath Hosdurg, S. Chatterjee, Algorithmica 74 (2016) 1321–1362.
date_created: 2018-12-11T11:50:33Z
date_published: 2016-04-01T00:00:00Z
date_updated: 2021-01-12T06:48:52Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00453-015-9997-6
intvolume: ' 74'
issue: '4'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://eprint.iacr.org/2013/651
month: '04'
oa: 1
oa_version: Submitted Version
page: 1321 - 1362
publication: Algorithmica
publication_status: published
publisher: Springer
publist_id: '6177'
quality_controlled: '1'
status: public
title: 'A closer look at multiple-forking: Leveraging (in)dependence for a tighter
bound'
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 74
year: '2016'
...
---
_id: '1179'
abstract:
- lang: eng
text: "Computational notions of entropy have recently found many applications, including
leakage-resilient cryptography, deterministic encryption or memory delegation.
The two main types of results which make computational notions so useful are (1)
Chain rules, which quantify by how much the computational entropy of a variable
decreases if conditioned on some other variable (2) Transformations, which quantify
to which extend one type of entropy implies another.\r\n\r\nSuch chain rules and
transformations typically lose a significant amount in quality of the entropy,
and are the reason why applying these results one gets rather weak quantitative
security bounds. In this paper we for the first time prove lower bounds in this
context, showing that existing results for transformations are, unfortunately,
basically optimal for non-adaptive black-box reductions (and it’s hard to imagine
how non black-box reductions or adaptivity could be useful here.)\r\n\r\nA variable
X has k bits of HILL entropy of quality (ϵ,s)\r\nif there exists a variable Y
with k bits min-entropy which cannot be distinguished from X with advantage ϵ\r\n\r\nby
distinguishing circuits of size s. A weaker notion is Metric entropy, where we
switch quantifiers, and only require that for every distinguisher of size s, such
a Y exists.\r\n\r\nWe first describe our result concerning transformations. By
definition, HILL implies Metric without any loss in quality. Metric entropy often
comes up in applications, but must be transformed to HILL for meaningful security
guarantees. The best known result states that if a variable X has k bits of Metric
entropy of quality (ϵ,s)\r\n, then it has k bits of HILL with quality (2ϵ,s⋅ϵ2).
We show that this loss of a factor Ω(ϵ−2)\r\n\r\nin circuit size is necessary.
In fact, we show the stronger result that this loss is already necessary when
transforming so called deterministic real valued Metric entropy to randomised
boolean Metric (both these variants of Metric entropy are implied by HILL without
loss in quality).\r\n\r\nThe chain rule for HILL entropy states that if X has
k bits of HILL entropy of quality (ϵ,s)\r\n, then for any variable Z of length
m, X conditioned on Z has k−m bits of HILL entropy with quality (ϵ,s⋅ϵ2/2m). We
show that a loss of Ω(2m/ϵ) in circuit size necessary here. Note that this still
leaves a gap of ϵ between the known bound and our lower bound."
acknowledgement: "K. Pietrzak—Supported by the European Research Council consolidator
grant (682815-TOCNeT).\r\nM. Skórski—Supported by the National Science Center, Poland
(2015/17/N/ST6/03564)."
alternative_title:
- LNCS
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: Skorski
full_name: Maciej, Skorski
last_name: Maciej
citation:
ama: 'Pietrzak KZ, Maciej S. Pseudoentropy: Lower-bounds for chain rules and transformations.
In: Vol 9985. Springer; 2016:183-203. doi:10.1007/978-3-662-53641-4_8'
apa: 'Pietrzak, K. Z., & Maciej, S. (2016). Pseudoentropy: Lower-bounds for
chain rules and transformations (Vol. 9985, pp. 183–203). Presented at the TCC:
Theory of Cryptography Conference, Beijing, China: Springer. https://doi.org/10.1007/978-3-662-53641-4_8'
chicago: 'Pietrzak, Krzysztof Z, and Skorski Maciej. “Pseudoentropy: Lower-Bounds
for Chain Rules and Transformations,” 9985:183–203. Springer, 2016. https://doi.org/10.1007/978-3-662-53641-4_8.'
ieee: 'K. Z. Pietrzak and S. Maciej, “Pseudoentropy: Lower-bounds for chain rules
and transformations,” presented at the TCC: Theory of Cryptography Conference,
Beijing, China, 2016, vol. 9985, pp. 183–203.'
ista: 'Pietrzak KZ, Maciej S. 2016. Pseudoentropy: Lower-bounds for chain rules
and transformations. TCC: Theory of Cryptography Conference, LNCS, vol. 9985,
183–203.'
mla: 'Pietrzak, Krzysztof Z., and Skorski Maciej. Pseudoentropy: Lower-Bounds
for Chain Rules and Transformations. Vol. 9985, Springer, 2016, pp. 183–203,
doi:10.1007/978-3-662-53641-4_8.'
short: K.Z. Pietrzak, S. Maciej, in:, Springer, 2016, pp. 183–203.
conference:
end_date: 2016-11-03
location: Beijing, China
name: 'TCC: Theory of Cryptography Conference'
start_date: 2016-10-31
date_created: 2018-12-11T11:50:34Z
date_published: 2016-10-22T00:00:00Z
date_updated: 2021-01-12T06:48:53Z
day: '22'
department:
- _id: KrPi
doi: 10.1007/978-3-662-53641-4_8
ec_funded: 1
intvolume: ' 9985'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/159
month: '10'
oa: 1
oa_version: Preprint
page: 183 - 203
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: '6175'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Pseudoentropy: Lower-bounds for chain rules and transformations'
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9985
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: '1233'
abstract:
- lang: eng
text: About three decades ago it was realized that implementing private channels
between parties which can be adaptively corrupted requires an encryption scheme
that is secure against selective opening attacks. Whether standard (IND-CPA) security
implies security against selective opening attacks has been a major open question
since. The only known reduction from selective opening to IND-CPA security loses
an exponential factor. A polynomial reduction is only known for the very special
case where the distribution considered in the selective opening security experiment
is a product distribution, i.e., the messages are sampled independently from each
other. In this paper we give a reduction whose loss is quantified via the dependence
graph (where message dependencies correspond to edges) of the underlying message
distribution. In particular, for some concrete distributions including Markov
distributions, our reduction is polynomial.
acknowledgement: G. Fuchsbauer and K. Pietrzak are supported by the European Research
Council, ERC Starting Grant (259668-PSPC). F. Heuer is funded by a Sofja Kovalevskaja
Award of the Alexander von Humboldt Foundation and DFG SPP 1736, Algorithms for
BIG DATA. E. Kiltz is supported by a Sofja Kovalevskaja Award of the Alexander von
Humboldt Foundation, the German Israel Foundation, and ERC Project ERCC (FP7/615074).
alternative_title:
- LNCS
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Felix
full_name: Heuer, Felix
last_name: Heuer
- first_name: Eike
full_name: Kiltz, Eike
last_name: Kiltz
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
citation:
ama: 'Fuchsbauer G, Heuer F, Kiltz E, Pietrzak KZ. Standard security does imply
security against selective opening for markov distributions. In: Vol 9562. Springer;
2016:282-305. doi:10.1007/978-3-662-49096-9_12'
apa: 'Fuchsbauer, G., Heuer, F., Kiltz, E., & Pietrzak, K. Z. (2016). Standard
security does imply security against selective opening for markov distributions
(Vol. 9562, pp. 282–305). Presented at the TCC: Theory of Cryptography Conference,
Tel Aviv, Israel: Springer. https://doi.org/10.1007/978-3-662-49096-9_12'
chicago: Fuchsbauer, Georg, Felix Heuer, Eike Kiltz, and Krzysztof Z Pietrzak. “Standard
Security Does Imply Security against Selective Opening for Markov Distributions,”
9562:282–305. Springer, 2016. https://doi.org/10.1007/978-3-662-49096-9_12.
ieee: 'G. Fuchsbauer, F. Heuer, E. Kiltz, and K. Z. Pietrzak, “Standard security
does imply security against selective opening for markov distributions,” presented
at the TCC: Theory of Cryptography Conference, Tel Aviv, Israel, 2016, vol. 9562,
pp. 282–305.'
ista: 'Fuchsbauer G, Heuer F, Kiltz E, Pietrzak KZ. 2016. Standard security does
imply security against selective opening for markov distributions. TCC: Theory
of Cryptography Conference, LNCS, vol. 9562, 282–305.'
mla: Fuchsbauer, Georg, et al. Standard Security Does Imply Security against
Selective Opening for Markov Distributions. Vol. 9562, Springer, 2016, pp.
282–305, doi:10.1007/978-3-662-49096-9_12.
short: G. Fuchsbauer, F. Heuer, E. Kiltz, K.Z. Pietrzak, in:, Springer, 2016, pp.
282–305.
conference:
end_date: 2016-01-13
location: Tel Aviv, Israel
name: 'TCC: Theory of Cryptography Conference'
start_date: 2016-01-10
date_created: 2018-12-11T11:50:51Z
date_published: 2016-01-01T00:00:00Z
date_updated: 2021-01-12T06:49:16Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-662-49096-9_12
ec_funded: 1
intvolume: ' 9562'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2015/853
month: '01'
oa: 1
oa_version: Submitted Version
page: 282 - 305
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: '6100'
quality_controlled: '1'
scopus_import: 1
status: public
title: Standard security does imply security against selective opening for markov
distributions
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9562
year: '2016'
...
---
_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: '1366'
abstract:
- lang: eng
text: 'We study the problem of devising provably secure PRNGs with input based on
the sponge paradigm. Such constructions are very appealing, as efficient software/hardware
implementations of SHA-3 can easily be translated into a PRNG in a nearly black-box
way. The only existing sponge-based construction, proposed by Bertoni et al. (CHES
2010), fails to achieve the security notion of robustness recently considered
by Dodis et al. (CCS 2013), for two reasons: (1) The construction is deterministic,
and thus there are high-entropy input distributions on which the construction
fails to extract random bits, and (2) The construction is not forward secure,
and presented solutions aiming at restoring forward security have not been rigorously
analyzed. We propose a seeded variant of Bertoni et al.’s PRNG with input which
we prove secure in the sense of robustness, delivering in particular concrete
security bounds. On the way, we make what we believe to be an important conceptual
contribution, developing a variant of the security framework of Dodis et al. tailored
at the ideal permutation model that captures PRNG security in settings where the
weakly random inputs are provided from a large class of possible adversarial samplers
which are also allowed to query the random permutation. As a further application
of our techniques, we also present an efficient sponge-based key-derivation function
(which can be instantiated from SHA-3 in a black-box fashion), which we also prove
secure when fed with samples from permutation-dependent distributions.'
alternative_title:
- LNCS
author:
- first_name: Peter
full_name: Gazi, Peter
id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
last_name: Gazi
- first_name: Stefano
full_name: Tessaro, Stefano
last_name: Tessaro
citation:
ama: 'Gazi P, Tessaro S. Provably robust sponge-based PRNGs and KDFs. In: Vol 9665.
Springer; 2016:87-116. doi:10.1007/978-3-662-49890-3_4'
apa: 'Gazi, P., & Tessaro, S. (2016). Provably robust sponge-based PRNGs and
KDFs (Vol. 9665, pp. 87–116). Presented at the EUROCRYPT: Theory and Applications
of Cryptographic Techniques, Vienna, Austria: Springer. https://doi.org/10.1007/978-3-662-49890-3_4'
chicago: Gazi, Peter, and Stefano Tessaro. “Provably Robust Sponge-Based PRNGs and
KDFs,” 9665:87–116. Springer, 2016. https://doi.org/10.1007/978-3-662-49890-3_4.
ieee: 'P. Gazi and S. Tessaro, “Provably robust sponge-based PRNGs and KDFs,” presented
at the EUROCRYPT: Theory and Applications of Cryptographic Techniques, Vienna,
Austria, 2016, vol. 9665, pp. 87–116.'
ista: 'Gazi P, Tessaro S. 2016. Provably robust sponge-based PRNGs and KDFs. EUROCRYPT:
Theory and Applications of Cryptographic Techniques, LNCS, vol. 9665, 87–116.'
mla: Gazi, Peter, and Stefano Tessaro. Provably Robust Sponge-Based PRNGs and
KDFs. Vol. 9665, Springer, 2016, pp. 87–116, doi:10.1007/978-3-662-49890-3_4.
short: P. Gazi, S. Tessaro, in:, Springer, 2016, pp. 87–116.
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:51:36Z
date_published: 2016-05-01T00:00:00Z
date_updated: 2021-01-12T06:50:11Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-662-49890-3_4
ec_funded: 1
intvolume: ' 9665'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/169/20160219:201940
month: '05'
oa: 1
oa_version: Preprint
page: 87 - 116
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: '5872'
quality_controlled: '1'
scopus_import: 1
status: public
title: Provably robust sponge-based PRNGs and KDFs
type: conference
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 9665
year: '2016'
...
---
_id: '1592'
abstract:
- lang: eng
text: A modular approach to constructing cryptographic protocols leads to simple
designs but often inefficient instantiations. On the other hand, ad hoc constructions
may yield efficient protocols at the cost of losing conceptual simplicity. We
suggest a new design paradigm, structure-preserving cryptography, that provides
a way to construct modular protocols with reasonable efficiency while retaining
conceptual simplicity. A cryptographic scheme over a bilinear group is called
structure-preserving if its public inputs and outputs consist of elements from
the bilinear groups and their consistency can be verified by evaluating pairing-product
equations. As structure-preserving schemes smoothly interoperate with each other,
they are useful as building blocks in modular design of cryptographic applications.
This paper introduces structure-preserving commitment and signature schemes over
bilinear groups with several desirable properties. The commitment schemes include
homomorphic, trapdoor and length-reducing commitments to group elements, and the
structure-preserving signature schemes are the first ones that yield constant-size
signatures on multiple group elements. A structure-preserving signature scheme
is called automorphic if the public keys lie in the message space, which cannot
be achieved by compressing inputs via a cryptographic hash function, as this would
destroy the mathematical structure we are trying to preserve. Automorphic signatures
can be used for building certification chains underlying privacy-preserving protocols.
Among a vast number of applications of structure-preserving protocols, we present
an efficient round-optimal blind-signature scheme and a group signature scheme
with an efficient and concurrently secure protocol for enrolling new members.
acknowledgement: The authors would like to thank the anonymous reviewers of this paper.
We also would like to express our appreciation to the program committee and the
anonymous reviewers for CRYPTO 2010. The first author thanks Sherman S. M. Chow
for his comment on group signatures in Sect. 7.1.
author:
- first_name: Masayuki
full_name: Abe, Masayuki
last_name: Abe
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Jens
full_name: Groth, Jens
last_name: Groth
- first_name: Kristiyan
full_name: Haralambiev, Kristiyan
last_name: Haralambiev
- first_name: Miyako
full_name: Ohkubo, Miyako
last_name: Ohkubo
citation:
ama: Abe M, Fuchsbauer G, Groth J, Haralambiev K, Ohkubo M. Structure preserving
signatures and commitments to group elements. Journal of Cryptology. 2016;29(2):363-421.
doi:10.1007/s00145-014-9196-7
apa: Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., & Ohkubo, M. (2016).
Structure preserving signatures and commitments to group elements. Journal
of Cryptology. Springer. https://doi.org/10.1007/s00145-014-9196-7
chicago: Abe, Masayuki, Georg Fuchsbauer, Jens Groth, Kristiyan Haralambiev, and
Miyako Ohkubo. “Structure Preserving Signatures and Commitments to Group Elements.”
Journal of Cryptology. Springer, 2016. https://doi.org/10.1007/s00145-014-9196-7.
ieee: M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, and M. Ohkubo, “Structure
preserving signatures and commitments to group elements,” Journal of Cryptology,
vol. 29, no. 2. Springer, pp. 363–421, 2016.
ista: Abe M, Fuchsbauer G, Groth J, Haralambiev K, Ohkubo M. 2016. Structure preserving
signatures and commitments to group elements. Journal of Cryptology. 29(2), 363–421.
mla: Abe, Masayuki, et al. “Structure Preserving Signatures and Commitments to Group
Elements.” Journal of Cryptology, vol. 29, no. 2, Springer, 2016, pp. 363–421,
doi:10.1007/s00145-014-9196-7.
short: M. Abe, G. Fuchsbauer, J. Groth, K. Haralambiev, M. Ohkubo, Journal of Cryptology
29 (2016) 363–421.
date_created: 2018-12-11T11:52:54Z
date_published: 2016-04-01T00:00:00Z
date_updated: 2021-01-12T06:51:49Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/s00145-014-9196-7
intvolume: ' 29'
issue: '2'
language:
- iso: eng
month: '04'
oa_version: None
page: 363 - 421
publication: Journal of Cryptology
publication_status: published
publisher: Springer
publist_id: '5579'
quality_controlled: '1'
scopus_import: 1
status: public
title: Structure preserving signatures and commitments to group elements
type: journal_article
user_id: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87
volume: 29
year: '2016'
...
---
_id: '1225'
abstract:
- lang: eng
text: At Crypto 2015 Fuchsbauer, Hanser and Slamanig (FHS) presented the first standard-model
construction of efficient roundoptimal blind signatures that does not require
complexity leveraging. It is conceptually simple and builds on the primitive of
structure-preserving signatures on equivalence classes (SPS-EQ). FHS prove the
unforgeability of their scheme assuming EUF-CMA security of the SPS-EQ scheme
and hardness of a version of the DH inversion problem. Blindness under adversarially
chosen keys is proven under an interactive variant of the DDH assumption. We propose
a variant of their scheme whose blindness can be proven under a non-interactive
assumption, namely a variant of the bilinear DDH assumption. We moreover prove
its unforgeability assuming only unforgeability of the underlying SPS-EQ but no
additional assumptions as needed for the FHS scheme.
alternative_title:
- LNCS
author:
- first_name: Georg
full_name: Fuchsbauer, Georg
id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
last_name: Fuchsbauer
- first_name: Christian
full_name: Hanser, Christian
last_name: Hanser
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Daniel
full_name: Slamanig, Daniel
last_name: Slamanig
citation:
ama: 'Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. Practical round-optimal
blind signatures in the standard model from weaker assumptions. In: Vol 9841.
Springer; 2016:391-408. doi:10.1007/978-3-319-44618-9_21'
apa: 'Fuchsbauer, G., Hanser, C., Kamath Hosdurg, C., & Slamanig, D. (2016).
Practical round-optimal blind signatures in the standard model from weaker assumptions
(Vol. 9841, pp. 391–408). Presented at the SCN: Security and Cryptography for
Networks, Amalfi, Italy: Springer. https://doi.org/10.1007/978-3-319-44618-9_21'
chicago: Fuchsbauer, Georg, Christian Hanser, Chethan Kamath Hosdurg, and Daniel
Slamanig. “Practical Round-Optimal Blind Signatures in the Standard Model from
Weaker Assumptions,” 9841:391–408. Springer, 2016. https://doi.org/10.1007/978-3-319-44618-9_21.
ieee: 'G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, and D. Slamanig, “Practical
round-optimal blind signatures in the standard model from weaker assumptions,”
presented at the SCN: Security and Cryptography for Networks, Amalfi, Italy, 2016,
vol. 9841, pp. 391–408.'
ista: 'Fuchsbauer G, Hanser C, Kamath Hosdurg C, Slamanig D. 2016. Practical round-optimal
blind signatures in the standard model from weaker assumptions. SCN: Security
and Cryptography for Networks, LNCS, vol. 9841, 391–408.'
mla: Fuchsbauer, Georg, et al. Practical Round-Optimal Blind Signatures in the
Standard Model from Weaker Assumptions. Vol. 9841, Springer, 2016, pp. 391–408,
doi:10.1007/978-3-319-44618-9_21.
short: G. Fuchsbauer, C. Hanser, C. Kamath Hosdurg, D. Slamanig, in:, Springer,
2016, pp. 391–408.
conference:
end_date: 2016-09-02
location: Amalfi, Italy
name: 'SCN: Security and Cryptography for Networks'
start_date: 2016-08-31
date_created: 2018-12-11T11:50:49Z
date_published: 2016-08-11T00:00:00Z
date_updated: 2023-02-23T10:08:16Z
day: '11'
department:
- _id: KrPi
doi: 10.1007/978-3-319-44618-9_21
ec_funded: 1
intvolume: ' 9841'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/662
month: '08'
oa: 1
oa_version: Submitted Version
page: 391 - 408
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '259668'
name: Provable Security for Physical Cryptography
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication_status: published
publisher: Springer
publist_id: '6109'
quality_controlled: '1'
related_material:
record:
- id: '1647'
relation: earlier_version
status: public
scopus_import: 1
status: public
title: Practical round-optimal blind signatures in the standard model from weaker
assumptions
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9841
year: '2016'
...