International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Mihir Bellare

ORCID: 0000-0002-8765-5573

Publications

Year
Venue
Title
2023
PKC
Hardening Signature Schemes via Derive-then-Derandomize: Stronger Security Proofs for EdDSA
Mihir Bellare Hannah Davis Zijing Di
We consider a transform, called Derive-then-Derandomize, that hardens a given signature scheme against randomness failure and implementation error. We prove that it works. We then give a general lemma showing indifferentiability of a class of constructions that apply a shrinking output transform to an MD-style hash function. Armed with these tools, we give new proofs for the widely standardized and used $\EdDSA$ signature scheme, improving prior work in two ways: (1) we give proofs for the case that the hash function is an MD-style one, reflecting the use of SHA512 in the NIST standard, and (2) we improve the tightness of the reduction so that one has guarantees for group sizes in actual use.
2023
CRYPTO
When Messages are Keys: Is HMAC a dual-PRF?
In Internet security protocols including TLS 1.3, KEMTLS, MLS and Noise, HMAC is being assumed to be a dual-PRF, meaning a PRF not only when keyed conventionally (through its first input), but also when "swapped" and keyed (unconventionally) through its second (message) input. We give the first in-depth analysis of the dual-PRF assumption on HMAC. For the swap case, we note that security does not hold in general, but completely characterize when it does; we show that HMAC is swap-PRF secure if and only if keys are restricted to sets satisfying a condition called feasibility, that we give, and that holds in applications. The sufficiency is shown by proof and the necessity by attacks. For the conventional PRF case, we fill a gap in the literature by proving PRF security of HMAC for keys of arbitrary length. Our proofs are in the standard model, make assumptions only on the compression function underlying the hash function, and give good bounds in the multi-user setting. The positive results are strengthened through achieving a new notion of variable key-length PRF security that guarantees security even if different users use keys of different lengths, as happens in practice.
2022
EUROCRYPT
Efficient Schemes for Committing Authenticated Encryption 📺
Mihir Bellare Viet Tung Hoang
This paper provides efficient authenticated-encryption (AE) schemes in which a ciphertext is a commitment to the key. These are extended, at minimal additional cost, to schemes where the ciphertext is a commitment to all encryption inputs, meaning key, nonce, associated data and message. Our primary schemes are modifications of GCM (for basic, unique-nonce AE security) and AES-GCM-SIV (for misuse-resistant AE security) and add both forms of commitment without any increase in ciphertext size. We also give more generic, but somewhat more costly, solutions.
2022
CRYPTO
Better than Advertised Security for Non-Interactive Threshold Signatures 📺
We give a unified syntax, and a hierarchy of definitions of security of increasing strength, for non-interactive threshold signature schemes. These are schemes having a single-round signing protocol, possibly with one prior round of message-independent pre-processing. We fit FROST1 and BLS, which are leading practical schemes, into our hierarchy, in particular showing they meet stronger security definitions than they have been shown to meet so far. We also fit in our hierarchy a more efficient version FROST2 of FROST1 that we give. These definitions and results, for simplicity, all assume trusted key generation. Finally, we prove the security of FROST2 with key generation performed by an efficient distributed key generation protocol.
2021
ASIACRYPT
Chain Reductions for Multi-Signatures and the HBMS Scheme 📺
Mihir Bellare Wei Dai
Existing proofs for existing Discrete Log (DL) based multi-signature schemes give only weak guarantees if the schemes are implemented, as they are in practice, in 256-bit groups. This is because the underlying reductions, which are mostly in the standard model and from DL, are loose. We show that relaxing either the model or the assumption suffices to obtain tight reductions. Namely we give (1) tight proofs from DL in the Algebraic Group Model, and (2) tight, standard-model proofs from well-founded assumptions other than DL. We first do this for the classical 3-round schemes, namely $\BN$ and $\MuSig$. Then we give a new 2-round multi-signature scheme, $\MSB$, as efficient as prior ones, for which we do the same. These multiple paths to security for a single scheme are made possible by a framework of chain reductions, in which a reduction is broken into a chain of sub-reductions involving intermediate problems. Overall our results improve the security guarantees for DL-based multi-signature schemes in the groups in which they are implemented in practice.
2020
EUROCRYPT
Security under Message-Derived Keys: Signcryption in iMessage 📺
Mihir Bellare Igors Stepanovs
At the core of Apple's iMessage is a SignCryption scheme that involves symmetric encryption of a message under a key that is derived from the message itself. To capture this, we formalize a primitive we call Encryption under Message-Derived Keys (EMDK). We prove security of the EMDK scheme underlying iMessage. We use this to prove security of the SignCryption scheme itself, with respect to definitions of SignCryption we give that enhance prior ones to cover issues peculiar to messaging protocols. Our provable-security results are quantitative, and we discuss the practical implications for iMessage.
2020
EUROCRYPT
Separate Your Domains: NIST PQC KEMs, Oracle Cloning and Read-Only Indifferentiability 📺
It is convenient and common for schemes in the random oracle model to assume access to multiple random oracles (ROs), leaving to implementations the task --we call it oracle cloning-- of constructing them from a single RO. The first part of the paper is a case study of oracle cloning in KEM submissions to the NIST Post-Quantum Cryptography standardization process. We give key-recovery attacks on some submissions arising from mistakes in oracle cloning, and find other submissions using oracle cloning methods whose validity is unclear. Motivated by this, the second part of the paper gives a theoretical treatment of oracle cloning. We give a definition of what is an "oracle cloning method" and what it means for such a method to "work," in a framework we call read-only indifferentiability, a simple variant of classical indifferentiability that yields security not only for usage in single-stage games but also in multi-stage ones. We formalize domain separation, and specify and study many oracle cloning methods, including common domain-separating ones, giving some general results to justify (prove read-only indifferentiability of) certain classes of methods. We are not only able to validate the oracle cloning methods used in many of the unbroken NIST PQC KEMs, but also able to specify and validate oracle cloning methods that may be useful beyond that.
2019
CRYPTO
Nonces Are Noticed: AEAD Revisited 📺
Mihir Bellare Ruth Ng Björn Tackmann
We draw attention to a gap between theory and usage of nonce-based symmetric encryption, under which the way the former treats nonces can result in violation of privacy in the latter. We bridge the gap with a new treatment of nonce-based symmetric encryption that modifies the syntax (decryption no longer takes a nonce), upgrades the security goal (asking that not just messages, but also nonces, be hidden) and gives simple, efficient schemes conforming to the new definitions. We investigate both basic security (holding when nonces are not reused) and advanced security (misuse resistance, providing best-possible guarantees when nonces are reused).
2019
ASIACRYPT
The Local Forking Lemma and Its Application to Deterministic Encryption
Mihir Bellare Wei Dai Lucy Li
We bypass impossibility results for the deterministic encryption of public-key-dependent messages, showing that, in this setting, the classical Encrypt-with-Hash scheme provides message-recovery security, across a broad range of message distributions. The proof relies on a new variant of the forking lemma in which the random oracle is reprogrammed on just a single fork point rather than on all points past the fork.
2018
JOFC
2018
PKC
Public-Key Encryption Resistant to Parameter Subversion and Its Realization from Efficiently-Embeddable Groups
We initiate the study of public-key encryption (PKE) schemes and key-encapsulation mechanisms (KEMs) that retain security even when public parameters (primes, curves) they use may be untrusted and subverted. We define a strong security goal that we call ciphertext pseudo-randomness under parameter subversion attack (CPR-PSA). We also define indistinguishability (of ciphertexts for PKE, and of encapsulated keys from random ones for KEMs) and public-key hiding (also called anonymity) under parameter subversion attack, and show they are implied by CPR-PSA, for both PKE and KEMs. We show that hybrid encryption continues to work in the parameter subversion setting to reduce the design of CPR-PSA PKE to CPR-PSA KEMs and an appropriate form of symmetric encryption. To obtain efficient, elliptic-curve-based KEMs achieving CPR-PSA, we introduce efficiently-embeddable group families and give several constructions from elliptic-curves.
2017
PKC
2017
CRYPTO
2016
EUROCRYPT
2016
EUROCRYPT
2016
EUROCRYPT
2016
CRYPTO
2016
CRYPTO
2016
TCC
2016
TCC
2016
ASIACRYPT
2016
ASIACRYPT
2015
JOFC
2015
JOFC
2015
PKC
2015
PKC
2015
PKC
2015
EUROCRYPT
2014
CRYPTO
2014
CRYPTO
2014
EUROCRYPT
2014
PKC
2014
JOFC
2014
CRYPTO
2014
ASIACRYPT
2013
CRYPTO
2013
EUROCRYPT
2012
EUROCRYPT
2012
EUROCRYPT
2012
CRYPTO
2012
CRYPTO
2012
ASIACRYPT
2012
ASIACRYPT
2012
JOFC
On-line Ciphers and the Hash-CBC Constructions
We initiate a study of on-line ciphers. These are ciphers that can take input plaintexts of large and varying lengths and will output the i th block of the ciphertext after having processed only the first i blocks of the plaintext. Such ciphers permit length-preserving encryption of a data stream with only a single pass through the data. We provide security definitions for this primitive and study its basic properties. We then provide attacks on some possible candidates, including CBC with fixed IV. We then provide two constructions, HCBC1 and HCBC2, based on a given block cipher E and a family of computationally AXU functions. HCBC1 is proven secure against chosen-plaintext attacks assuming that E is a PRP secure against chosen-plaintext attacks, while HCBC2 is proven secure against chosen-ciphertext attacks assuming that E is a PRP secure against chosen-ciphertext attacks.
2011
TCC
2011
CRYPTO
2011
ASIACRYPT
2010
TCC
2010
CRYPTO
2010
EUROCRYPT
2009
ASIACRYPT
2009
JOFC
2009
EUROCRYPT
2009
EUROCRYPT
2008
ASIACRYPT
2008
JOFC
2008
JOFC
2008
CRYPTO
2007
CRYPTO
2007
PKC
2006
ASIACRYPT
2006
CRYPTO
2006
EUROCRYPT
2005
CRYPTO
2005
CRYPTO
2004
ASIACRYPT
2004
CRYPTO
2004
EUROCRYPT
2004
EUROCRYPT
2004
EUROCRYPT
2004
FSE
2003
EUROCRYPT
2003
EUROCRYPT
2003
PKC
2003
JOFC
2002
ASIACRYPT
2002
CRYPTO
2002
EUROCRYPT
2002
JOFC
2001
ASIACRYPT
2001
CRYPTO
2001
EUROCRYPT
2001
EUROCRYPT
2001
PKC
2000
ASIACRYPT
2000
ASIACRYPT
2000
ASIACRYPT
2000
ASIACRYPT
2000
EUROCRYPT
2000
EUROCRYPT
1999
CRYPTO
1999
CRYPTO
1999
CRYPTO
1999
CRYPTO
1999
FSE
1999
JOFC
1998
CRYPTO
1998
CRYPTO
1998
CRYPTO
1998
EUROCRYPT
1998
EUROCRYPT
1997
CRYPTO
1997
CRYPTO
1997
EUROCRYPT
1997
EUROCRYPT
1996
CRYPTO
1996
EUROCRYPT
1996
JOFC
1995
CRYPTO
1994
CRYPTO
1994
CRYPTO
1994
EUROCRYPT
1993
CRYPTO
1992
CRYPTO
1992
CRYPTO
1989
CRYPTO
1989
CRYPTO
1989
CRYPTO
1988
CRYPTO

Program Committees

Eurocrypt 2023
Asiacrypt 2022
PKC 2018
Crypto 2017
Crypto 2013
Crypto 2011
TCC 2007
Asiacrypt 2006
Crypto 2003
Crypto 2000 (Program chair)
Eurocrypt 1999
Crypto 1996
Eurocrypt 1995
Crypto 1993

Coauthors

Michel Abdalla (6)
Tolga Acar (1)
William Aiello (1)
Jee Hea An (3)
Benedikt Auerbach (1)
Matilda Backendal (1)
Mira Belenkiy (1)
Daniel J. Bernstein (1)
Alexandra Boldyreva (8)
Zvika Brakerski (1)
Ran Canetti (1)
David Cash (3)
Dario Catalano (2)
Lenore Cowen (1)
Giovanni Di Crescenzo (1)
Elizabeth Crites (1)
Wei Dai (2)
Hannah Davis (2)
Anand Desai (2)
Zoë Diamadi (1)
Rafael Dowsley (2)
Marc Fischlin (2)
Georg Fuchsbauer (2)
Juan A. Garay (1)
Oded Goldreich (3)
Shafi Goldwasser (5)
Roch Guérin (1)
Felix Günther (2)
Shai Halevi (1)
Viet Tung Hoang (6)
Dennis Hofheinz (2)
Joseph Jaeger (1)
Markus Jakobsson (1)
Daniel Kane (1)
Sriram Keelveedhi (6)
Joe Kilian (1)
Eike Kiltz (5)
Lars R. Knudsen (2)
Tadayoshi Kohno (4)
Chelsea Komlo (1)
Hugo Krawczyk (2)
Ted Krovetz (1)
Tanja Lange (2)
Lucy Li (1)
Mary Maller (1)
John Malone-Lee (2)
Sarah Meiklejohn (1)
Silvio Micali (4)
Daniele Micciancio (3)
Rachel Miller (1)
Sara K. Miner (1)
Chanathip Namprempre (8)
Moni Naor (1)
Gregory Neven (7)
Ruth Ng (1)
Maya Nyayapati (1)
Adam O'Neill (2)
Pascal Paillier (2)
Adriana Palacio (4)
Kenneth G. Paterson (2)
Chris Peikert (1)
Krzysztof Pietrzak (1)
Bertram Poettering (2)
David Pointcheval (4)
Tal Rabin (1)
Thomas Ristenpart (6)
Todor Ristov (2)
Ronald L. Rivest (1)
Phillip Rogaway (17)
Amit Sahai (2)
Alessandra Scafuro (1)
Matteo Scarlata (1)
Gil Segev (1)
Michael Semanko (1)
Hovav Shacham (1)
Haixia Shi (2)
Sarah Shoup (1)
Asha Camper Singh (1)
Jessica Staddon (1)
Douglas Stebila (2)
Igors Stepanovs (6)
Björn Tackmann (3)
Stefano Tessaro (6)
Susan Thomson (2)
Salil P. Vadhan (1)
Alexander Vardy (1)
Ramarathnam Venkatesan (1)
David Wagner (1)
Bogdan Warinschi (1)
Brent Waters (4)
Scott Yilek (4)
Moti Yung (3)
Chenzhi Zhu (1)