---
_id: '193'
abstract:
- lang: eng
text: 'We show attacks on five data-independent memory-hard functions (iMHF) that
were submitted to the password hashing competition (PHC). Informally, an MHF is
a function which cannot be evaluated on dedicated hardware, like ASICs, at significantly
lower hardware and/or energy cost than evaluating a single instance on a standard
single-core architecture. Data-independent means the memory access pattern of
the function is independent of the input; this makes iMHFs harder to construct
than data-dependent ones, but the latter can be attacked by various side-channel
attacks. Following [Alwen-Blocki''16], we capture the evaluation of an iMHF as
a directed acyclic graph (DAG). The cumulative parallel pebbling complexity of
this DAG is a measure for the hardware cost of evaluating the iMHF on an ASIC.
Ideally, one would like the complexity of a DAG underlying an iMHF to be as close
to quadratic in the number of nodes of the graph as possible. Instead, we show
that (the DAGs underlying) the following iMHFs are far from this bound: Rig.v2,
TwoCats and Gambit each having an exponent no more than 1.75. Moreover, we show
that the complexity of the iMHF modes of the PHC finalists Pomelo and Lyra2 have
exponents at most 1.83 and 1.67 respectively. To show this we investigate a combinatorial
property of each underlying DAG (called its depth-robustness. By establishing
upper bounds on this property we are then able to apply the general technique
of [Alwen-Block''16] for analyzing the hardware costs of an iMHF.'
acknowledgement: Leonid Reyzin was supported in part by IST Austria and by US NSF
grants 1012910, 1012798, and 1422965; this research was performed while he was visiting
IST Austria.
article_processing_charge: No
author:
- first_name: Joel F
full_name: Alwen, Joel F
id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
last_name: Alwen
- first_name: Peter
full_name: Gazi, Peter
last_name: Gazi
- first_name: Chethan
full_name: Kamath Hosdurg, Chethan
id: 4BD3F30E-F248-11E8-B48F-1D18A9856A87
last_name: Kamath Hosdurg
- first_name: Karen
full_name: Klein, Karen
id: 3E83A2F8-F248-11E8-B48F-1D18A9856A87
last_name: Klein
- first_name: Georg F
full_name: Osang, Georg F
id: 464B40D6-F248-11E8-B48F-1D18A9856A87
last_name: Osang
orcid: 0000-0002-8882-5116
- first_name: Krzysztof Z
full_name: Pietrzak, Krzysztof Z
id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
last_name: Pietrzak
orcid: 0000-0002-9139-1654
- first_name: Lenoid
full_name: Reyzin, Lenoid
last_name: Reyzin
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
citation:
ama: 'Alwen JF, Gazi P, Kamath Hosdurg C, et al. On the memory hardness of data
independent password hashing functions. In: Proceedings of the 2018 on Asia
Conference on Computer and Communication Security. ACM; 2018:51-65. doi:10.1145/3196494.3196534'
apa: 'Alwen, J. F., Gazi, P., Kamath Hosdurg, C., Klein, K., Osang, G. F., Pietrzak,
K. Z., … Rybar, M. (2018). On the memory hardness of data independent password
hashing functions. In Proceedings of the 2018 on Asia Conference on Computer
and Communication Security (pp. 51–65). Incheon, Republic of Korea: ACM. https://doi.org/10.1145/3196494.3196534'
chicago: Alwen, Joel F, Peter Gazi, Chethan Kamath Hosdurg, Karen Klein, Georg F
Osang, Krzysztof Z Pietrzak, Lenoid Reyzin, Michal Rolinek, and Michal Rybar.
“On the Memory Hardness of Data Independent Password Hashing Functions.” In Proceedings
of the 2018 on Asia Conference on Computer and Communication Security, 51–65.
ACM, 2018. https://doi.org/10.1145/3196494.3196534.
ieee: J. F. Alwen et al., “On the memory hardness of data independent password
hashing functions,” in Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, Incheon, Republic of Korea, 2018, pp. 51–65.
ista: 'Alwen JF, Gazi P, Kamath Hosdurg C, Klein K, Osang GF, Pietrzak KZ, Reyzin
L, Rolinek M, Rybar M. 2018. On the memory hardness of data independent password
hashing functions. Proceedings of the 2018 on Asia Conference on Computer and
Communication Security. ASIACCS: Asia Conference on Computer and Communications
Security , 51–65.'
mla: Alwen, Joel F., et al. “On the Memory Hardness of Data Independent Password
Hashing Functions.” Proceedings of the 2018 on Asia Conference on Computer
and Communication Security, ACM, 2018, pp. 51–65, doi:10.1145/3196494.3196534.
short: J.F. Alwen, P. Gazi, C. Kamath Hosdurg, K. Klein, G.F. Osang, K.Z. Pietrzak,
L. Reyzin, M. Rolinek, M. Rybar, in:, Proceedings of the 2018 on Asia Conference
on Computer and Communication Security, ACM, 2018, pp. 51–65.
conference:
end_date: 2018-06-08
location: Incheon, Republic of Korea
name: 'ASIACCS: Asia Conference on Computer and Communications Security '
start_date: 2018-06-04
date_created: 2018-12-11T11:45:07Z
date_published: 2018-06-01T00:00:00Z
date_updated: 2023-09-13T09:13:12Z
day: '01'
department:
- _id: KrPi
- _id: HeEd
- _id: VlKo
doi: 10.1145/3196494.3196534
ec_funded: 1
external_id:
isi:
- '000516620100005'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2016/783
month: '06'
oa: 1
oa_version: Submitted Version
page: 51 - 65
project:
- _id: 25FBA906-B435-11E9-9278-68D0E5697425
call_identifier: FP7
grant_number: '616160'
name: 'Discrete Optimization in Computer Vision: Theory and Practice'
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
call_identifier: H2020
grant_number: '682815'
name: Teaching Old Crypto New Tricks
publication: Proceedings of the 2018 on Asia Conference on Computer and Communication
Security
publication_status: published
publisher: ACM
publist_id: '7723'
quality_controlled: '1'
scopus_import: '1'
status: public
title: On the memory hardness of data independent password hashing functions
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
year: '2018'
...
---
_id: '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: '2047'
abstract:
- lang: eng
text: Following the publication of an attack on genome-wide association studies
(GWAS) data proposed by Homer et al., considerable attention has been given to
developing methods for releasing GWAS data in a privacy-preserving way. Here,
we develop an end-to-end differentially private method for solving regression
problems with convex penalty functions and selecting the penalty parameters by
cross-validation. In particular, we focus on penalized logistic regression with
elastic-net regularization, a method widely used to in GWAS analyses to identify
disease-causing genes. We show how a differentially private procedure for penalized
logistic regression with elastic-net regularization can be applied to the analysis
of GWAS data and evaluate our method’s performance.
acknowledgement: This research was partially supported by BCS- 0941518 to the Department
of Statistics at Carnegie Mellon University.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Fei
full_name: Yu, Fei
last_name: Yu
- first_name: Michal
full_name: Rybar, Michal
id: 2B3E3DE8-F248-11E8-B48F-1D18A9856A87
last_name: Rybar
- first_name: Caroline
full_name: Uhler, Caroline
id: 49ADD78E-F248-11E8-B48F-1D18A9856A87
last_name: Uhler
orcid: 0000-0002-7008-0216
- first_name: Stephen
full_name: Fienberg, Stephen
last_name: Fienberg
citation:
ama: 'Yu F, Rybar M, Uhler C, Fienberg S. Differentially-private logistic regression
for detecting multiple-SNP association in GWAS databases. In: Domingo Ferrer J,
ed. Lecture Notes in Computer Science (Including Subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics). Vol 8744. Springer;
2014:170-184. doi:10.1007/978-3-319-11257-2_14'
apa: 'Yu, F., Rybar, M., Uhler, C., & Fienberg, S. (2014). Differentially-private
logistic regression for detecting multiple-SNP association in GWAS databases.
In J. Domingo Ferrer (Ed.), Lecture Notes in Computer Science (including subseries
Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
(Vol. 8744, pp. 170–184). Ibiza, Spain: Springer. https://doi.org/10.1007/978-3-319-11257-2_14'
chicago: Yu, Fei, Michal Rybar, Caroline Uhler, and Stephen Fienberg. “Differentially-Private
Logistic Regression for Detecting Multiple-SNP Association in GWAS Databases.”
In Lecture Notes in Computer Science (Including Subseries Lecture Notes in
Artificial Intelligence and Lecture Notes in Bioinformatics), edited by Josep
Domingo Ferrer, 8744:170–84. Springer, 2014. https://doi.org/10.1007/978-3-319-11257-2_14.
ieee: F. Yu, M. Rybar, C. Uhler, and S. Fienberg, “Differentially-private logistic
regression for detecting multiple-SNP association in GWAS databases,” in Lecture
Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Ibiza, Spain, 2014, vol. 8744, pp. 170–184.
ista: 'Yu F, Rybar M, Uhler C, Fienberg S. 2014. Differentially-private logistic
regression for detecting multiple-SNP association in GWAS databases. Lecture Notes
in Computer Science (including subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics). PSD: Privacy in Statistical Databases, LNCS,
vol. 8744, 170–184.'
mla: Yu, Fei, et al. “Differentially-Private Logistic Regression for Detecting Multiple-SNP
Association in GWAS Databases.” Lecture Notes in Computer Science (Including
Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics),
edited by Josep Domingo Ferrer, vol. 8744, Springer, 2014, pp. 170–84, doi:10.1007/978-3-319-11257-2_14.
short: F. Yu, M. Rybar, C. Uhler, S. Fienberg, in:, J. Domingo Ferrer (Ed.), Lecture
Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence
and Lecture Notes in Bioinformatics), Springer, 2014, pp. 170–184.
conference:
end_date: 2014-09-19
location: Ibiza, Spain
name: 'PSD: Privacy in Statistical Databases'
start_date: 2014-09-17
date_created: 2018-12-11T11:55:24Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:54:57Z
day: '01'
department:
- _id: KrPi
- _id: CaUh
doi: 10.1007/978-3-319-11257-2_14
editor:
- first_name: Josep
full_name: Domingo Ferrer, Josep
last_name: Domingo Ferrer
external_id:
arxiv:
- '1407.8067'
intvolume: ' 8744'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1407.8067
month: '01'
oa: 1
oa_version: Submitted Version
page: 170 - 184
project:
- _id: 25636330-B435-11E9-9278-68D0E5697425
grant_number: 11-NSF-1070
name: ROOTS Genome-wide Analysis of Root Traits
publication: Lecture Notes in Computer Science (including subseries Lecture Notes
in Artificial Intelligence and Lecture Notes in Bioinformatics)
publication_status: published
publisher: Springer
publist_id: '5004'
quality_controlled: '1'
scopus_import: 1
status: public
title: Differentially-private logistic regression for detecting multiple-SNP association
in GWAS databases
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8744
year: '2014'
...
---
_id: '2082'
abstract:
- lang: eng
text: '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). Security proofs and attacks for NMAC can typically be lifted to HMAC. 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, assuming that (1)
f is a PRF and (2) the function we get when cascading f is weakly collision-resistant.
Unfortunately, HMAC is typically instantiated with cryptographic hash functions
like MD5 or SHA-1 for which (2) has been found to be wrong. To restore the provable
guarantees for NMAC, Bellare [Crypto''06] showed its security based solely on
the assumption that f is a PRF, albeit via a non-uniform reduction. - Our first
contribution is a simpler and uniform proof for this fact: 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 then show that this ε+ℓqδ bound is basically tight. For the most interesting
case where ℓqδ ≥ ε we prove this by constructing an f for which an attack with
advantage ℓqδ exists. This also violates the bound O(ℓε) on the PRF-security of
NMAC recently claimed by Koblitz and Menezes. - Finally, we analyze the PRF-security
of a modification of NMAC called NI [An and Bellare, Crypto''99] that differs
mainly by using a compression function with an additional keying input. This avoids
the constant rekeying on multi-block messages in NMAC and allows for a security
proof starting by the standard switch from a PRF to a random function, followed
by an information-theoretic analysis. We carry out such an analysis, obtaining
a tight ℓq2/2 c bound for this step, improving over the trivial bound of ℓ2q2/2c.
The proof borrows combinatorial techniques originally developed for proving the
security of CBC-MAC [Bellare et al., Crypto''05].'
alternative_title:
- LNCS
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 PRF-security of NMAC and HMAC. In:
Garay J, Gennaro R, eds. Vol 8616. Springer; 2014:113-130. doi:10.1007/978-3-662-44371-2_7'
apa: 'Gazi, P., Pietrzak, K. Z., & Rybar, M. (2014). The exact PRF-security
of NMAC and HMAC. In J. Garay & R. Gennaro (Eds.) (Vol. 8616, pp. 113–130).
Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, USA:
Springer. https://doi.org/10.1007/978-3-662-44371-2_7'
chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact PRF-Security
of NMAC and HMAC.” edited by Juan Garay and Rosario Gennaro, 8616:113–30. Springer,
2014. https://doi.org/10.1007/978-3-662-44371-2_7.
ieee: 'P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact PRF-security of NMAC and
HMAC,” presented at the CRYPTO: International Cryptology Conference, Santa Barbara,
USA, 2014, vol. 8616, no. 1, pp. 113–130.'
ista: 'Gazi P, Pietrzak KZ, Rybar M. 2014. The exact PRF-security of NMAC and HMAC.
CRYPTO: International Cryptology Conference, LNCS, vol. 8616, 113–130.'
mla: Gazi, Peter, et al. The Exact PRF-Security of NMAC and HMAC. Edited
by Juan Garay and Rosario Gennaro, vol. 8616, no. 1, Springer, 2014, pp. 113–30,
doi:10.1007/978-3-662-44371-2_7.
short: P. Gazi, K.Z. Pietrzak, M. Rybar, in:, J. Garay, R. Gennaro (Eds.), Springer,
2014, pp. 113–130.
conference:
end_date: 2014-08-21
location: Santa Barbara, USA
name: 'CRYPTO: International Cryptology Conference'
start_date: 2014-08-17
date_created: 2018-12-11T11:55:36Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2023-09-07T12:02:27Z
day: '01'
ddc:
- '000'
- '004'
department:
- _id: KrPi
doi: 10.1007/978-3-662-44371-2_7
ec_funded: 1
editor:
- first_name: Juan
full_name: Garay, Juan
last_name: Garay
- first_name: Rosario
full_name: Gennaro, Rosario
last_name: Gennaro
file:
- access_level: open_access
checksum: dab6ab36a5f6af94f2b597e6404ed11d
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:13:17Z
date_updated: 2020-07-14T12:45:28Z
file_id: '4999'
file_name: IST-2016-682-v1+1_578.pdf
file_size: 492310
relation: main_file
file_date_updated: 2020-07-14T12:45:28Z
has_accepted_license: '1'
intvolume: ' 8616'
issue: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Submitted Version
page: 113 - 130
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: '4955'
pubrep_id: '682'
quality_controlled: '1'
related_material:
record:
- id: '838'
relation: dissertation_contains
status: public
status: public
title: The exact PRF-security of NMAC and HMAC
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 8616
year: '2014'
...