---
_id: '5887'
abstract:
- lang: eng
  text: 'Cryptographic security is usually defined as a guarantee that holds except
    when a bad event with negligible probability occurs, and nothing is guaranteed
    in that bad case. However, in settings where such failure can happen with substantial
    probability, one needs to provide guarantees even for the bad case. A typical
    example is where a (possibly weak) password is used instead of a secure cryptographic
    key to protect a session, the bad event being that the adversary correctly guesses
    the password. In a situation with multiple such sessions, a per-session guarantee
    is desired: any session for which the password has not been guessed remains secure,
    independently of whether other sessions have been compromised. A new formalism
    for stating such gracefully degrading security guarantees is introduced and applied
    to analyze the examples of password-based message authentication and password-based
    encryption. While a natural per-message guarantee is achieved for authentication,
    the situation of password-based encryption is more delicate: a per-session confidentiality
    guarantee only holds against attackers for which the distribution of password-guessing
    effort over the sessions is known in advance. In contrast, for more general attackers
    without such a restriction, a strong, composable notion of security cannot be
    achieved.'
article_processing_charge: No
article_type: original
author:
- first_name: Gregory
  full_name: Demay, Gregory
  last_name: Demay
- first_name: Peter
  full_name: Gazi, Peter
  id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
  last_name: Gazi
- first_name: Ueli
  full_name: Maurer, Ueli
  last_name: Maurer
- first_name: Bjorn
  full_name: Tackmann, Bjorn
  last_name: Tackmann
citation:
  ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Per-session security: Password-based
    cryptography revisited. <i>Journal of Computer Security</i>. 2019;27(1):75-111.
    doi:<a href="https://doi.org/10.3233/JCS-181131">10.3233/JCS-181131</a>'
  apa: 'Demay, G., Gazi, P., Maurer, U., &#38; Tackmann, B. (2019). Per-session security:
    Password-based cryptography revisited. <i>Journal of Computer Security</i>. IOS
    Press. <a href="https://doi.org/10.3233/JCS-181131">https://doi.org/10.3233/JCS-181131</a>'
  chicago: 'Demay, Gregory, Peter Gazi, Ueli Maurer, and Bjorn Tackmann. “Per-Session
    Security: Password-Based Cryptography Revisited.” <i>Journal of Computer Security</i>.
    IOS Press, 2019. <a href="https://doi.org/10.3233/JCS-181131">https://doi.org/10.3233/JCS-181131</a>.'
  ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Per-session security: Password-based
    cryptography revisited,” <i>Journal of Computer Security</i>, vol. 27, no. 1.
    IOS Press, pp. 75–111, 2019.'
  ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2019. Per-session security: Password-based
    cryptography revisited. Journal of Computer Security. 27(1), 75–111.'
  mla: 'Demay, Gregory, et al. “Per-Session Security: Password-Based Cryptography
    Revisited.” <i>Journal of Computer Security</i>, vol. 27, no. 1, IOS Press, 2019,
    pp. 75–111, doi:<a href="https://doi.org/10.3233/JCS-181131">10.3233/JCS-181131</a>.'
  short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, Journal of Computer Security 27
    (2019) 75–111.
date_created: 2019-01-27T22:59:10Z
date_published: 2019-01-01T00:00:00Z
date_updated: 2021-01-12T08:05:08Z
day: '1'
department:
- _id: KrPi
doi: 10.3233/JCS-181131
ec_funded: 1
intvolume: '        27'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2016/166
month: '01'
oa: 1
oa_version: Preprint
page: 75-111
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: Journal of Computer Security
publication_identifier:
  issn:
  - 0926227X
publication_status: published
publisher: IOS Press
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'Per-session security: Password-based cryptography revisited'
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 27
year: '2019'
...
---
_id: '6941'
abstract:
- lang: eng
  text: "Bitcoin has become the most successful cryptocurrency ever deployed, and
    its most distinctive feature is that it is decentralized. Its underlying protocol
    (Nakamoto consensus) achieves this by using proof of work, which has the drawback
    that it causes the consumption of vast amounts of energy to maintain the ledger.
    Moreover, Bitcoin mining dynamics have become less distributed over time.\r\n\r\nTowards
    addressing these issues, we propose SpaceMint, a cryptocurrency based on proofs
    of space instead of proofs of work. Miners in SpaceMint dedicate disk space rather
    than computation. We argue that SpaceMint’s design solves or alleviates several
    of Bitcoin’s issues: most notably, its large energy consumption. SpaceMint also
    rewards smaller miners fairly according to their contribution to the network,
    thus incentivizing more distributed participation.\r\n\r\nThis paper adapts proof
    of space to enable its use in cryptocurrency, studies the attacks that can arise
    against a Bitcoin-like blockchain that uses proof of space, and proposes a new
    blockchain format and transaction types to address these attacks. Our prototype
    shows that initializing 1 TB for mining takes about a day (a one-off setup cost),
    and miners spend on average just a fraction of a second per block mined. Finally,
    we provide a game-theoretic analysis modeling SpaceMint as an extensive game (the
    canonical game-theoretic notion for games that take place over time) and show
    that this stylized game satisfies a strong equilibrium notion, thereby arguing
    for SpaceMint ’s stability and consensus."
alternative_title:
- LNCS
article_processing_charge: No
author:
- first_name: Sunoo
  full_name: Park, Sunoo
  last_name: Park
- first_name: Albert
  full_name: Kwon, Albert
  last_name: Kwon
- first_name: Georg
  full_name: Fuchsbauer, Georg
  id: 46B4C3EE-F248-11E8-B48F-1D18A9856A87
  last_name: Fuchsbauer
- first_name: Peter
  full_name: Gazi, Peter
  id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
  last_name: Gazi
- first_name: Joel F
  full_name: Alwen, Joel F
  id: 2A8DFA8C-F248-11E8-B48F-1D18A9856A87
  last_name: Alwen
- first_name: Krzysztof Z
  full_name: Pietrzak, Krzysztof Z
  id: 3E04A7AA-F248-11E8-B48F-1D18A9856A87
  last_name: Pietrzak
  orcid: 0000-0002-9139-1654
citation:
  ama: 'Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. SpaceMint: A
    cryptocurrency based on proofs of space. In: <i>22nd International Conference
    on Financial Cryptography and Data Security</i>. Vol 10957. Springer Nature; 2018:480-499.
    doi:<a href="https://doi.org/10.1007/978-3-662-58387-6_26">10.1007/978-3-662-58387-6_26</a>'
  apa: 'Park, S., Kwon, A., Fuchsbauer, G., Gazi, P., Alwen, J. F., &#38; Pietrzak,
    K. Z. (2018). SpaceMint: A cryptocurrency based on proofs of space. In <i>22nd
    International Conference on Financial Cryptography and Data Security</i> (Vol.
    10957, pp. 480–499). Nieuwpoort, Curacao: Springer Nature. <a href="https://doi.org/10.1007/978-3-662-58387-6_26">https://doi.org/10.1007/978-3-662-58387-6_26</a>'
  chicago: 'Park, Sunoo, Albert Kwon, Georg Fuchsbauer, Peter Gazi, Joel F Alwen,
    and Krzysztof Z Pietrzak. “SpaceMint: A Cryptocurrency Based on Proofs of Space.”
    In <i>22nd International Conference on Financial Cryptography and Data Security</i>,
    10957:480–99. Springer Nature, 2018. <a href="https://doi.org/10.1007/978-3-662-58387-6_26">https://doi.org/10.1007/978-3-662-58387-6_26</a>.'
  ieee: 'S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J. F. Alwen, and K. Z. Pietrzak,
    “SpaceMint: A cryptocurrency based on proofs of space,” in <i>22nd International
    Conference on Financial Cryptography and Data Security</i>, Nieuwpoort, Curacao,
    2018, vol. 10957, pp. 480–499.'
  ista: 'Park S, Kwon A, Fuchsbauer G, Gazi P, Alwen JF, Pietrzak KZ. 2018. SpaceMint:
    A cryptocurrency based on proofs of space. 22nd International Conference on Financial
    Cryptography and Data Security. FC: Financial Cryptography and Data Security,
    LNCS, vol. 10957, 480–499.'
  mla: 'Park, Sunoo, et al. “SpaceMint: A Cryptocurrency Based on Proofs of Space.”
    <i>22nd International Conference on Financial Cryptography and Data Security</i>,
    vol. 10957, Springer Nature, 2018, pp. 480–99, doi:<a href="https://doi.org/10.1007/978-3-662-58387-6_26">10.1007/978-3-662-58387-6_26</a>.'
  short: S. Park, A. Kwon, G. Fuchsbauer, P. Gazi, J.F. Alwen, K.Z. Pietrzak, in:,
    22nd International Conference on Financial Cryptography and Data Security, Springer
    Nature, 2018, pp. 480–499.
conference:
  end_date: 2018-03-02
  location: Nieuwpoort, Curacao
  name: 'FC: Financial Cryptography and Data Security'
  start_date: 2018-02-26
date_created: 2019-10-14T06:35:38Z
date_published: 2018-12-07T00:00:00Z
date_updated: 2023-09-19T15:02:13Z
day: '07'
department:
- _id: KrPi
doi: 10.1007/978-3-662-58387-6_26
ec_funded: 1
external_id:
  isi:
  - '000540656400026'
intvolume: '     10957'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2015/528
month: '12'
oa: 1
oa_version: Submitted Version
page: 480-499
project:
- _id: 258AA5B2-B435-11E9-9278-68D0E5697425
  call_identifier: H2020
  grant_number: '682815'
  name: Teaching Old Crypto New Tricks
publication: 22nd International Conference on Financial Cryptography and Data Security
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783662583869'
  - '9783662583876'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: 'SpaceMint: A cryptocurrency based on proofs of space'
type: conference
user_id: c635000d-4b10-11ee-a964-aac5a93f6ac1
volume: 10957
year: '2018'
...
---
_id: '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. <i>IACR Transactions
    on Symmetric Cryptology</i>. 2017;2016(2):145-161. doi:<a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">10.13154/TOSC.V2016.I2.145-161</a>
  apa: Gazi, P., Pietrzak, K. Z., &#38; Rybar, M. (2017). The exact security of PMAC.
    <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum. <a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>
  chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Michal Rybar. “The Exact Security
    of PMAC.” <i>IACR Transactions on Symmetric Cryptology</i>. Ruhr University Bochum,
    2017. <a href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">https://doi.org/10.13154/TOSC.V2016.I2.145-161</a>.
  ieee: P. Gazi, K. Z. Pietrzak, and M. Rybar, “The exact security of PMAC,” <i>IACR
    Transactions on Symmetric Cryptology</i>, 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.” <i>IACR Transactions on Symmetric
    Cryptology</i>, vol. 2016, no. 2, Ruhr University Bochum, 2017, pp. 145–61, doi:<a
    href="https://doi.org/10.13154/TOSC.V2016.I2.145-161">10.13154/TOSC.V2016.I2.145-161</a>.
  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: '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:<a href="https://doi.org/10.1007/978-3-662-49890-3_4">10.1007/978-3-662-49890-3_4</a>'
  apa: 'Gazi, P., &#38; 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. <a href="https://doi.org/10.1007/978-3-662-49890-3_4">https://doi.org/10.1007/978-3-662-49890-3_4</a>'
  chicago: Gazi, Peter, and Stefano Tessaro. “Provably Robust Sponge-Based PRNGs and
    KDFs,” 9665:87–116. Springer, 2016. <a href="https://doi.org/10.1007/978-3-662-49890-3_4">https://doi.org/10.1007/978-3-662-49890-3_4</a>.
  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. <i>Provably Robust Sponge-Based PRNGs and
    KDFs</i>. Vol. 9665, Springer, 2016, pp. 87–116, doi:<a href="https://doi.org/10.1007/978-3-662-49890-3_4">10.1007/978-3-662-49890-3_4</a>.
  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: '1644'
abstract:
- lang: eng
  text: Increasing the computational complexity of evaluating a hash function, both
    for the honest users as well as for an adversary, is a useful technique employed
    for example in password-based cryptographic schemes to impede brute-force attacks,
    and also in so-called proofs of work (used in protocols like Bitcoin) to show
    that a certain amount of computation was performed by a legitimate user. A natural
    approach to adjust the complexity of a hash function is to iterate it c times,
    for some parameter c, in the hope that any query to the scheme requires c evaluations
    of the underlying hash function. However, results by Dodis et al. (Crypto 2012)
    imply that plain iteration falls short of achieving this goal, and designing schemes
    which provably have such a desirable property remained an open problem. This paper
    formalizes explicitly what it means for a given scheme to amplify the query complexity
    of a hash function. In the random oracle model, the goal of a secure query-complexity
    amplifier (QCA) scheme is captured as transforming, in the sense of indifferentiability,
    a random oracle allowing R queries (for the adversary) into one provably allowing
    only r &lt; R queries. Turned around, this means that making r queries to the
    scheme requires at least R queries to the actual random oracle. Second, a new
    scheme, called collision-free iteration, is proposed and proven to achieve c-fold
    QCA for both the honest parties and the adversary, for any fixed parameter c.
alternative_title:
- LNCS
author:
- first_name: Grégory
  full_name: Demay, Grégory
  last_name: Demay
- first_name: Peter
  full_name: Gazi, Peter
  id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
  last_name: Gazi
- first_name: Ueli
  full_name: Maurer, Ueli
  last_name: Maurer
- first_name: Björn
  full_name: Tackmann, Björn
  last_name: Tackmann
citation:
  ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Query-complexity amplification for
    random oracles. In: Vol 9063. Springer; 2015:159-180. doi:<a href="https://doi.org/10.1007/978-3-319-17470-9_10">10.1007/978-3-319-17470-9_10</a>'
  apa: 'Demay, G., Gazi, P., Maurer, U., &#38; Tackmann, B. (2015). Query-complexity
    amplification for random oracles (Vol. 9063, pp. 159–180). Presented at the ICITS:
    International Conference on Information Theoretic Security, Lugano, Switzerland:
    Springer. <a href="https://doi.org/10.1007/978-3-319-17470-9_10">https://doi.org/10.1007/978-3-319-17470-9_10</a>'
  chicago: Demay, Grégory, Peter Gazi, Ueli Maurer, and Björn Tackmann. “Query-Complexity
    Amplification for Random Oracles,” 9063:159–80. Springer, 2015. <a href="https://doi.org/10.1007/978-3-319-17470-9_10">https://doi.org/10.1007/978-3-319-17470-9_10</a>.
  ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Query-complexity amplification
    for random oracles,” presented at the ICITS: International Conference on Information
    Theoretic Security, Lugano, Switzerland, 2015, vol. 9063, pp. 159–180.'
  ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2015. Query-complexity amplification
    for random oracles. ICITS: International Conference on Information Theoretic Security,
    LNCS, vol. 9063, 159–180.'
  mla: Demay, Grégory, et al. <i>Query-Complexity Amplification for Random Oracles</i>.
    Vol. 9063, Springer, 2015, pp. 159–80, doi:<a href="https://doi.org/10.1007/978-3-319-17470-9_10">10.1007/978-3-319-17470-9_10</a>.
  short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, Springer, 2015, pp. 159–180.
conference:
  end_date: 2015-05-05
  location: Lugano, Switzerland
  name: 'ICITS: International Conference on Information Theoretic Security'
  start_date: 2015-05-02
date_created: 2018-12-11T11:53:13Z
date_published: 2015-01-01T00:00:00Z
date_updated: 2021-01-12T06:52:13Z
day: '01'
department:
- _id: KrPi
doi: 10.1007/978-3-319-17470-9_10
ec_funded: 1
intvolume: '      9063'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://eprint.iacr.org/2015/315
month: '01'
oa: 1
oa_version: Submitted Version
page: 159 - 180
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: '5507'
quality_controlled: '1'
scopus_import: 1
status: public
title: Query-complexity amplification for random oracles
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9063
year: '2015'
...
---
_id: '1645'
abstract:
- lang: eng
  text: Secret-key constructions are often proved secure in a model where one or more
    underlying components are replaced by an idealized oracle accessible to the attacker.
    This model gives rise to information-theoretic security analyses, and several
    advances have been made in this area over the last few years. This paper provides
    a systematic overview of what is achievable in this model, and how existing works
    fit into this view.
article_number: '7133163'
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. Secret-key cryptography from ideal primitives: A systematic
    verview. In: <i>2015 IEEE Information Theory Workshop</i>. IEEE; 2015. doi:<a
    href="https://doi.org/10.1109/ITW.2015.7133163">10.1109/ITW.2015.7133163</a>'
  apa: 'Gazi, P., &#38; Tessaro, S. (2015). Secret-key cryptography from ideal primitives:
    A systematic verview. In <i>2015 IEEE Information Theory Workshop</i>. Jerusalem,
    Israel: IEEE. <a href="https://doi.org/10.1109/ITW.2015.7133163">https://doi.org/10.1109/ITW.2015.7133163</a>'
  chicago: 'Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal
    Primitives: A Systematic Verview.” In <i>2015 IEEE Information Theory Workshop</i>.
    IEEE, 2015. <a href="https://doi.org/10.1109/ITW.2015.7133163">https://doi.org/10.1109/ITW.2015.7133163</a>.'
  ieee: 'P. Gazi and S. Tessaro, “Secret-key cryptography from ideal primitives: A
    systematic verview,” in <i>2015 IEEE Information Theory Workshop</i>, Jerusalem,
    Israel, 2015.'
  ista: 'Gazi P, Tessaro S. 2015. Secret-key cryptography from ideal primitives: A
    systematic verview. 2015 IEEE Information Theory Workshop. ITW 2015: IEEE Information
    Theory Workshop, 7133163.'
  mla: 'Gazi, Peter, and Stefano Tessaro. “Secret-Key Cryptography from Ideal Primitives:
    A Systematic Verview.” <i>2015 IEEE Information Theory Workshop</i>, 7133163,
    IEEE, 2015, doi:<a href="https://doi.org/10.1109/ITW.2015.7133163">10.1109/ITW.2015.7133163</a>.'
  short: P. Gazi, S. Tessaro, in:, 2015 IEEE Information Theory Workshop, IEEE, 2015.
conference:
  end_date: 2015-05-01
  location: Jerusalem, Israel
  name: 'ITW 2015: IEEE Information Theory Workshop'
  start_date: 2015-04-26
date_created: 2018-12-11T11:53:13Z
date_published: 2015-06-24T00:00:00Z
date_updated: 2021-01-12T06:52:13Z
day: '24'
department:
- _id: KrPi
doi: 10.1109/ITW.2015.7133163
ec_funded: 1
language:
- iso: eng
month: '06'
oa_version: None
project:
- _id: 258C570E-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '259668'
  name: Provable Security for Physical Cryptography
publication: 2015 IEEE Information Theory Workshop
publication_status: published
publisher: IEEE
publist_id: '5506'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Secret-key cryptography from ideal primitives: A systematic verview'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2015'
...
---
_id: '1654'
abstract:
- lang: eng
  text: "HMAC and its variant NMAC are the most popular approaches to deriving a MAC
    (and more generally, a PRF) from a cryptographic hash function. Despite nearly
    two decades of research, their exact security still remains far from understood
    in many different contexts. Indeed, recent works have re-surfaced interest for
    {\\em generic} attacks, i.e., attacks that treat the compression function of the
    underlying hash function as a black box.\r\n\r\nGeneric security can be proved
    in a model where the underlying compression function is modeled as a random function
    -- yet, to date, the question of proving tight, non-trivial bounds on the generic
    security of HMAC/NMAC even as a PRF remains a challenging open question.\r\n\r\nIn
    this paper, we ask the question of whether a small modification to HMAC and NMAC
    can allow us to exactly characterize the security of the resulting constructions,
    while only incurring little penalty with respect to efficiency. To this end, we
    present simple variants of NMAC and HMAC, for which we prove tight bounds on the
    generic PRF security, expressed in terms of numbers of construction and compression
    function queries necessary to break the construction. All of our constructions
    are obtained via a (near) {\\em black-box} modification of NMAC and HMAC, which
    can be interpreted as an initial step of key-dependent message pre-processing.\r\n\r\nWhile
    our focus is on PRF security, a further attractive feature of our new constructions
    is that they clearly defeat all recent generic attacks against properties such
    as state recovery and universal forgery. These exploit properties of the so-called
    ``functional graph'' which are not directly accessible in our new constructions. "
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: Stefano
  full_name: Tessaro, Stefano
  last_name: Tessaro
citation:
  ama: Gazi P, Pietrzak KZ, Tessaro S. Generic security of NMAC and HMAC with input
    whitening. 2015;9453:85-109. doi:<a href="https://doi.org/10.1007/978-3-662-48800-3_4">10.1007/978-3-662-48800-3_4</a>
  apa: 'Gazi, P., Pietrzak, K. Z., &#38; Tessaro, S. (2015). Generic security of NMAC
    and HMAC with input whitening. Presented at the ASIACRYPT: Theory and Application
    of Cryptology and Information Security, Auckland, New Zealand: Springer. <a href="https://doi.org/10.1007/978-3-662-48800-3_4">https://doi.org/10.1007/978-3-662-48800-3_4</a>'
  chicago: Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “Generic Security
    of NMAC and HMAC with Input Whitening.” Lecture Notes in Computer Science. Springer,
    2015. <a href="https://doi.org/10.1007/978-3-662-48800-3_4">https://doi.org/10.1007/978-3-662-48800-3_4</a>.
  ieee: P. Gazi, K. Z. Pietrzak, and S. Tessaro, “Generic security of NMAC and HMAC
    with input whitening,” vol. 9453. Springer, pp. 85–109, 2015.
  ista: Gazi P, Pietrzak KZ, Tessaro S. 2015. Generic security of NMAC and HMAC with
    input whitening. 9453, 85–109.
  mla: Gazi, Peter, et al. <i>Generic Security of NMAC and HMAC with Input Whitening</i>.
    Vol. 9453, Springer, 2015, pp. 85–109, doi:<a href="https://doi.org/10.1007/978-3-662-48800-3_4">10.1007/978-3-662-48800-3_4</a>.
  short: P. Gazi, K.Z. Pietrzak, S. Tessaro, 9453 (2015) 85–109.
conference:
  end_date: 2015-12-03
  location: Auckland, New Zealand
  name: 'ASIACRYPT: Theory and Application of Cryptology and Information Security'
  start_date: 2015-11-29
date_created: 2018-12-11T11:53:17Z
date_published: 2015-12-30T00:00:00Z
date_updated: 2021-01-12T06:52:16Z
day: '30'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48800-3_4
ec_funded: 1
file:
- access_level: open_access
  checksum: d1e53203db2d8573a560995ccdffac62
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:09:09Z
  date_updated: 2020-07-14T12:45:08Z
  file_id: '4732'
  file_name: IST-2016-676-v1+1_881.pdf
  file_size: 512071
  relation: main_file
file_date_updated: 2020-07-14T12:45:08Z
has_accepted_license: '1'
intvolume: '      9453'
language:
- iso: eng
month: '12'
oa: 1
oa_version: Submitted Version
page: 85 - 109
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: '5496'
pubrep_id: '676'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Generic security of NMAC and HMAC with input whitening
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9453
year: '2015'
...
---
_id: '1668'
abstract:
- lang: eng
  text: "We revisit the security (as a pseudorandom permutation) of cascading-based
    constructions for block-cipher key-length extension. Previous works typically
    considered the extreme case where the adversary is given the entire codebook of
    the construction, the only complexity measure being the number qe of queries to
    the underlying ideal block cipher, representing adversary’s secret-key-independent
    computation. Here, we initiate a systematic study of the more natural case of
    an adversary restricted to adaptively learning a number qc of plaintext/ciphertext
    pairs that is less than the entire codebook. For any such qc, we aim to determine
    the highest number of block-cipher queries qe the adversary can issue without
    being able to successfully distinguish the construction (under a secret key) from
    a random permutation.\r\nMore concretely, we show the following results for key-length
    extension schemes using a block cipher with n-bit blocks and κ-bit keys:\r\nPlain
    cascades of length ℓ=2r+1 are secure whenever qcqre≪2r(κ+n), qc≪2κ and qe≪22κ.
    The bound for r=1 also applies to two-key triple encryption (as used within Triple
    DES).\r\nThe r-round XOR-cascade is secure as long as qcqre≪2r(κ+n), matching
    an attack by Gaži (CRYPTO 2013).\r\nWe fully characterize the security of Gaži
    and Tessaro’s two-call "
alternative_title:
- LNCS
author:
- first_name: Peter
  full_name: Gazi, Peter
  id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
  last_name: Gazi
- first_name: Jooyoung
  full_name: Lee, Jooyoung
  last_name: Lee
- first_name: Yannick
  full_name: Seurin, Yannick
  last_name: Seurin
- first_name: John
  full_name: Steinberger, John
  last_name: Steinberger
- first_name: Stefano
  full_name: Tessaro, Stefano
  last_name: Tessaro
citation:
  ama: 'Gazi P, Lee J, Seurin Y, Steinberger J, Tessaro S. Relaxing full-codebook
    security: A refined analysis of key-length extension schemes. 2015;9054:319-341.
    doi:<a href="https://doi.org/10.1007/978-3-662-48116-5_16">10.1007/978-3-662-48116-5_16</a>'
  apa: 'Gazi, P., Lee, J., Seurin, Y., Steinberger, J., &#38; Tessaro, S. (2015).
    Relaxing full-codebook security: A refined analysis of key-length extension schemes.
    Presented at the FSE: Fast Software Encryption, Istanbul, Turkey: Springer. <a
    href="https://doi.org/10.1007/978-3-662-48116-5_16">https://doi.org/10.1007/978-3-662-48116-5_16</a>'
  chicago: 'Gazi, Peter, Jooyoung Lee, Yannick Seurin, John Steinberger, and Stefano
    Tessaro. “Relaxing Full-Codebook Security: A Refined Analysis of Key-Length Extension
    Schemes.” Lecture Notes in Computer Science. Springer, 2015. <a href="https://doi.org/10.1007/978-3-662-48116-5_16">https://doi.org/10.1007/978-3-662-48116-5_16</a>.'
  ieee: 'P. Gazi, J. Lee, Y. Seurin, J. Steinberger, and S. Tessaro, “Relaxing full-codebook
    security: A refined analysis of key-length extension schemes,” vol. 9054. Springer,
    pp. 319–341, 2015.'
  ista: 'Gazi P, Lee J, Seurin Y, Steinberger J, Tessaro S. 2015. Relaxing full-codebook
    security: A refined analysis of key-length extension schemes. 9054, 319–341.'
  mla: 'Gazi, Peter, et al. <i>Relaxing Full-Codebook Security: A Refined Analysis
    of Key-Length Extension Schemes</i>. Vol. 9054, Springer, 2015, pp. 319–41, doi:<a
    href="https://doi.org/10.1007/978-3-662-48116-5_16">10.1007/978-3-662-48116-5_16</a>.'
  short: P. Gazi, J. Lee, Y. Seurin, J. Steinberger, S. Tessaro, 9054 (2015) 319–341.
conference:
  end_date: 2015-03-11
  location: Istanbul, Turkey
  name: 'FSE: Fast Software Encryption'
  start_date: 2015-03-08
date_created: 2018-12-11T11:53:22Z
date_published: 2015-08-12T00:00:00Z
date_updated: 2020-08-11T10:09:26Z
day: '12'
department:
- _id: KrPi
doi: 10.1007/978-3-662-48116-5_16
ec_funded: 1
intvolume: '      9054'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://eprint.iacr.org/2015/397
month: '08'
oa: 1
oa_version: Submitted Version
page: 319 - 341
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: '5481'
quality_controlled: '1'
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: 'Relaxing full-codebook security: A refined analysis of key-length extension
  schemes'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9054
year: '2015'
...
---
_id: '1671'
abstract:
- lang: eng
  text: This paper studies the concrete security of PRFs and MACs obtained by keying
    hash functions based on the sponge paradigm. One such hash function is KECCAK,
    selected as NIST’s new SHA-3 standard. In contrast to other approaches like HMAC,
    the exact security of keyed sponges is not well understood. Indeed, recent security
    analyses delivered concrete security bounds which are far from existing attacks.
    This paper aims to close this gap. We prove (nearly) exact bounds on the concrete
    PRF security of keyed sponges using a random permutation. These bounds are tight
    for the most relevant ranges of parameters, i.e., for messages of length (roughly)
    l ≤ min{2n/4, 2r} blocks, where n is the state size and r is the desired output
    length; and for l ≤ q queries (to the construction or the underlying permutation).
    Moreover, we also improve standard-model bounds. As an intermediate step of independent
    interest, we prove tight bounds on the PRF security of the truncated CBC-MAC construction,
    which operates as plain CBC-MAC, but only returns a prefix of the output.
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: Stefano
  full_name: Tessaro, Stefano
  last_name: Tessaro
citation:
  ama: 'Gazi P, Pietrzak KZ, Tessaro S. The exact PRF security of truncation: Tight
    bounds for keyed sponges and truncated CBC. In: Vol 9215. Springer; 2015:368-387.
    doi:<a href="https://doi.org/10.1007/978-3-662-47989-6_18">10.1007/978-3-662-47989-6_18</a>'
  apa: 'Gazi, P., Pietrzak, K. Z., &#38; Tessaro, S. (2015). The exact PRF security
    of truncation: Tight bounds for keyed sponges and truncated CBC (Vol. 9215, pp.
    368–387). Presented at the CRYPTO: International Cryptology Conference, Santa
    Barbara, CA, United States: Springer. <a href="https://doi.org/10.1007/978-3-662-47989-6_18">https://doi.org/10.1007/978-3-662-47989-6_18</a>'
  chicago: 'Gazi, Peter, Krzysztof Z Pietrzak, and Stefano Tessaro. “The Exact PRF
    Security of Truncation: Tight Bounds for Keyed Sponges and Truncated CBC,” 9215:368–87.
    Springer, 2015. <a href="https://doi.org/10.1007/978-3-662-47989-6_18">https://doi.org/10.1007/978-3-662-47989-6_18</a>.'
  ieee: 'P. Gazi, K. Z. Pietrzak, and S. Tessaro, “The exact PRF security of truncation:
    Tight bounds for keyed sponges and truncated CBC,” presented at the CRYPTO: International
    Cryptology Conference, Santa Barbara, CA, United States, 2015, vol. 9215, pp.
    368–387.'
  ista: 'Gazi P, Pietrzak KZ, Tessaro S. 2015. The exact PRF security of truncation:
    Tight bounds for keyed sponges and truncated CBC. CRYPTO: International Cryptology
    Conference, LNCS, vol. 9215, 368–387.'
  mla: 'Gazi, Peter, et al. <i>The Exact PRF Security of Truncation: Tight Bounds
    for Keyed Sponges and Truncated CBC</i>. Vol. 9215, Springer, 2015, pp. 368–87,
    doi:<a href="https://doi.org/10.1007/978-3-662-47989-6_18">10.1007/978-3-662-47989-6_18</a>.'
  short: P. Gazi, K.Z. Pietrzak, S. Tessaro, in:, Springer, 2015, pp. 368–387.
conference:
  end_date: 2015-08-20
  location: Santa Barbara, CA, United States
  name: 'CRYPTO: International Cryptology Conference'
  start_date: 2015-08-16
date_created: 2018-12-11T11:53:23Z
date_published: 2015-08-01T00:00:00Z
date_updated: 2021-01-12T06:52:25Z
day: '01'
ddc:
- '004'
- '005'
department:
- _id: KrPi
doi: 10.1007/978-3-662-47989-6_18
ec_funded: 1
file:
- access_level: open_access
  checksum: 17d854227b3b753fd34f5d29e5b5a32e
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:10:38Z
  date_updated: 2020-07-14T12:45:11Z
  file_id: '4827'
  file_name: IST-2016-673-v1+1_053.pdf
  file_size: 592296
  relation: main_file
file_date_updated: 2020-07-14T12:45:11Z
has_accepted_license: '1'
intvolume: '      9215'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Submitted Version
page: 368 - 387
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: '5478'
pubrep_id: '673'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'The exact PRF security of truncation: Tight bounds for keyed sponges and truncated
  CBC'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 9215
year: '2015'
...
---
_id: '1907'
abstract:
- lang: eng
  text: 'Most cryptographic security proofs require showing that two systems are indistinguishable.
    A central tool in such proofs is that of a game, where winning the game means
    provoking a certain condition, and it is shown that the two systems considered
    cannot be distinguished unless this condition is provoked. Upper bounding the
    probability of winning such a game, i.e., provoking this condition, for an arbitrary
    strategy is usually hard, except in the special case where the best strategy for
    winning such a game is known to be non-adaptive. A sufficient criterion for ensuring
    the optimality of non-adaptive strategies is that of conditional equivalence to
    a system, a notion introduced in [1]. In this paper, we show that this criterion
    is not necessary to ensure the optimality of non-adaptive strategies by giving
    two results of independent interest: 1) the optimality of non-adaptive strategies
    is not preserved under parallel composition; 2) in contrast, conditional equivalence
    is preserved under parallel composition.'
article_number: '6875125'
author:
- first_name: Grégory
  full_name: Demay, Grégory
  last_name: Demay
- first_name: Peter
  full_name: Gazi, Peter
  id: 3E0BFE38-F248-11E8-B48F-1D18A9856A87
  last_name: Gazi
- first_name: Ueli
  full_name: Maurer, Ueli
  last_name: Maurer
- first_name: Björn
  full_name: Tackmann, Björn
  last_name: Tackmann
citation:
  ama: 'Demay G, Gazi P, Maurer U, Tackmann B. Optimality of non-adaptive strategies:
    The case of parallel games. In: <i>IEEE International Symposium on Information
    Theory</i>. IEEE; 2014. doi:<a href="https://doi.org/10.1109/ISIT.2014.6875125">10.1109/ISIT.2014.6875125</a>'
  apa: 'Demay, G., Gazi, P., Maurer, U., &#38; Tackmann, B. (2014). Optimality of
    non-adaptive strategies: The case of parallel games. In <i>IEEE International
    Symposium on Information Theory</i>. Honolulu, USA: IEEE. <a href="https://doi.org/10.1109/ISIT.2014.6875125">https://doi.org/10.1109/ISIT.2014.6875125</a>'
  chicago: 'Demay, Grégory, Peter Gazi, Ueli Maurer, and Björn Tackmann. “Optimality
    of Non-Adaptive Strategies: The Case of Parallel Games.” In <i>IEEE International
    Symposium on Information Theory</i>. IEEE, 2014. <a href="https://doi.org/10.1109/ISIT.2014.6875125">https://doi.org/10.1109/ISIT.2014.6875125</a>.'
  ieee: 'G. Demay, P. Gazi, U. Maurer, and B. Tackmann, “Optimality of non-adaptive
    strategies: The case of parallel games,” in <i>IEEE International Symposium on
    Information Theory</i>, Honolulu, USA, 2014.'
  ista: 'Demay G, Gazi P, Maurer U, Tackmann B. 2014. Optimality of non-adaptive strategies:
    The case of parallel games. IEEE International Symposium on Information Theory.
    IEEE International Symposium on Information Theory Proceedings, 6875125.'
  mla: 'Demay, Grégory, et al. “Optimality of Non-Adaptive Strategies: The Case of
    Parallel Games.” <i>IEEE International Symposium on Information Theory</i>, 6875125,
    IEEE, 2014, doi:<a href="https://doi.org/10.1109/ISIT.2014.6875125">10.1109/ISIT.2014.6875125</a>.'
  short: G. Demay, P. Gazi, U. Maurer, B. Tackmann, in:, IEEE International Symposium
    on Information Theory, IEEE, 2014.
conference:
  end_date: 2014-07-04
  location: Honolulu, USA
  name: IEEE International Symposium on Information Theory Proceedings
  start_date: 2014-06-29
date_created: 2018-12-11T11:54:39Z
date_published: 2014-01-01T00:00:00Z
date_updated: 2021-01-12T06:53:59Z
day: '01'
department:
- _id: KrPi
doi: 10.1109/ISIT.2014.6875125
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://eprint.iacr.org/2014/299
month: '01'
oa: 1
oa_version: Submitted Version
publication: IEEE International Symposium on Information Theory
publication_status: published
publisher: IEEE
publist_id: '5188'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Optimality of non-adaptive strategies: The case of parallel games'
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
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:<a href="https://doi.org/10.1007/978-3-662-44371-2_7">10.1007/978-3-662-44371-2_7</a>'
  apa: 'Gazi, P., Pietrzak, K. Z., &#38; Rybar, M. (2014). The exact PRF-security
    of NMAC and HMAC. In J. Garay &#38; R. Gennaro (Eds.) (Vol. 8616, pp. 113–130).
    Presented at the CRYPTO: International Cryptology Conference, Santa Barbara, USA:
    Springer. <a href="https://doi.org/10.1007/978-3-662-44371-2_7">https://doi.org/10.1007/978-3-662-44371-2_7</a>'
  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. <a href="https://doi.org/10.1007/978-3-662-44371-2_7">https://doi.org/10.1007/978-3-662-44371-2_7</a>.
  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. <i>The Exact PRF-Security of NMAC and HMAC</i>. Edited
    by Juan Garay and Rosario Gennaro, vol. 8616, no. 1, Springer, 2014, pp. 113–30,
    doi:<a href="https://doi.org/10.1007/978-3-662-44371-2_7">10.1007/978-3-662-44371-2_7</a>.
  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'
...
