## CryptoDB

### Michel Abdalla

#### Publications

**Year**

**Venue**

**Title**

2021

ASIACRYPT

Algebraic Adversaries in the Universal Composability Framework
Abstract

The algebraic-group model (AGM), which lies between the generic group model and the standard model of computation, provides a means by which to analyze the security of cryptosystems against so-called algebraic adversaries. We formalize the AGM within the framework of universal composability, providing formal definitions for this setting and proving an appropriate composition theorem.
This extends the applicability of the AGM to more-complex protocols, and lays the foundations for analyzing algebraic adversaries in a composable fashion.
Our results also clarify the meaning of composing proofs in the AGM with other proofs and they highlight a natural form of independence between idealized groups that seems inherent to the AGM and has not been made formal before---these insights also apply to the composition of game-based proofs in the AGM.
We show the utility of our model by proving several important protocols universally composable for algebraic adversaries, specifically: (1) the Chou-Orlandi protocol for oblivious transfer, and (2) the SPAKE2 and CPace protocols for password-based authenticated key exchange.

2021

ASIACRYPT

Security Analysis of CPace
Abstract

In response to standardization requests regarding password-authenticated key exchange (PAKE) protocols, the IRTF working group CFRG has setup a PAKE selection
process in 2019, which led to the selection of the CPace protocol in the balanced setting, in which parties share a common password. In subsequent standardization efforts, the CPace protocol further developed, yielding a protocol family whose actual security guarantees in practical settings are not well understood. In this paper, we provide a comprehensive security analysis of CPace in the universal composability framework. Our analysis is realistic in the sense that it captures adaptive corruptions and refrains from modeling CPace's MapToPoint function that maps field elements to curve points as an idealized function. In order to extend our proofs to different CPace variants optimized for specific elliptic-curve ecosystems, we employ a new approach which represents the assumptions required by the proof as libraries accessed by a simulator. By allowing for the modular replacement of assumptions used in the proof, this new approach avoids a repeated analysis of unchanged protocol parts and lets us efficiently analyze the security guarantees of all the different CPace variants. As a result of our analysis, all of the investigated practical CPace variants enjoy adaptive UC security.

2020

CRYPTO

Functional Encryption for Attribute-Weighted Sums from k-Lin
📺
Abstract

We present functional encryption schemes for attribute-weighted sums, where encryption takes as input N attribute-value pairs (x_i,z_i) where x_i is public and z_i is private; secret keys are associated with arithmetic branching programs f, and decryption returns the weighted sum \sum_{i=1}^N f(x_i) z_i while leaking no additional information about the z_i's. Our main construction achieves
(1) compact public parameters and key sizes that are independent of N and the secret key can decrypt a ciphertext for any a-priori unbounded N;
(2) short ciphertexts that grow with N and the size of z_i but not x_i;
(3) simulation-based security against unbounded collusions;
(4) relies on the standard k-linear assumption in prime-order bilinear groups.

2020

CRYPTO

Universally Composable Relaxed Password Authenticated Key Exchange
📺
Abstract

Protocols for password authenticated key exchange (PAKE) allow two parties who share only a weak password to agree on a cryptographic key. We revisit the notion of PAKE in the universal composability (UC) framework, and propose a relaxation of the PAKE functionality of Canetti et al. that we call lazy-extraction PAKE (lePAKE). Our relaxation allows the ideal-world adversary to postpone its password guess until after a session is complete. We argue that this relaxed notion still provides meaningful security in the password-only setting. As our main result, we show that several PAKE protocols that were previously only proven secure with respect to a ``game-based'' definition of security can be shown to UC-realize the lePAKE functionality in the random-oracle model. These include SPEKE, SPAKE2, and TBPEKE, the most efficient PAKE schemes currently known.

2020

ASIACRYPT

Inner-Product Functional Encryption with Fine-Grained Access Control
📺
Abstract

We construct new functional encryption schemes that combine the access control functionality of attribute-based encryption with the possibility of performing linear operations on the encrypted data. While such a primitive could be easily realized from fully fledged functional encryption schemes, what makes our result interesting is the fact that our schemes simultaneously achieve all the following properties. They are public-key, efficient and can be proved secure under standard and well established assumptions (such as LWE or pairings). Furthermore, security is guaranteed in the setting where adversaries are allowed to get functional keys that decrypt the challenge ciphertext. Our first results are two functional encryption schemes for the family of functions that allow users to embed policies (expressed by monotone span programs) in the encrypted data, so that one can generate functional keys to compute weighted sums on the latter. Both schemes are pairing-based and quite generic: they combine the ALS functional encryption scheme for inner products from Crypto 2016 with any attribute-based encryption schemes relying on the dual-system encryption methodology. As an additional bonus, they yield simple and elegant multi-input extensions essentially for free, thereby broadening the set of applications for such schemes. Multi-input is a particularly desirable feature in our setting, since it gives a finer access control over the encrypted data, by allowing users to associate different access policies to different parts of the encrypted data. Our second result builds identity-based functional encryption for inner products from lattices. This is achieved by carefully combining existing IBE schemes from lattices with adapted, LWE-based, variants of ALS. We point out to intrinsic technical bottlenecks to obtain richer forms of access control from lattices. From a conceptual point of view, all our results can be seen as further evidence that more expressive forms of functional encryption can be realized under standard assumptions and with little computational overhead.

2019

PKC

Decentralizing Inner-Product Functional Encryption
Abstract

Multi-client functional encryption (MCFE) is a more flexible variant of functional encryption whose functional decryption involves multiple ciphertexts from different parties. Each party holds a different secret key and can independently and adaptively be corrupted by the adversary. We present two compilers for MCFE schemes for the inner-product functionality, both of which support encryption labels. Our first compiler transforms any scheme with a special key-derivation property into a decentralized scheme, as defined by Chotard et al. (ASIACRYPT 2018), thus allowing for a simple distributed way of generating functional decryption keys without a trusted party. Our second compiler allows to lift an unnatural restriction present in existing (decentralized) MCFE schemes, which requires the adversary to ask for a ciphertext from each party. We apply our compilers to the works of Abdalla et al. (CRYPTO 2018) and Chotard et al. (ASIACRYPT 2018) to obtain schemes with hitherto unachieved properties. From Abdalla et al., we obtain instantiations of DMCFE schemes in the standard model (from DDH, Paillier, or LWE) but without labels. From Chotard et al., we obtain a DMCFE scheme with labels still in the random oracle model, but without pairings.

2019

ASIACRYPT

Algebraic XOR-RKA-Secure Pseudorandom Functions from Post-Zeroizing Multilinear Maps
Abstract

Due to the vast number of successful related-key attacks against existing block-ciphers, related-key security has become a common design goal for such primitives. In these attacks, the adversary is not only capable of seeing the output of a function on inputs of its choice, but also on related keys. At Crypto 2010, Bellare and Cash proposed the first construction of a pseudorandom function that could provably withstand such attacks based on standard assumptions. Their construction, as well as several others that appeared more recently, have in common the fact that they only consider linear or polynomial functions of the secret key over complex groups. In reality, however, most related-key attacks have a simpler form, such as the XOR of the key with a known value. To address this problem, we propose the first construction of RKA-secure pseudorandom function for XOR relations. Our construction relies on multilinear maps and, hence, can only be seen as a feasibility result. Nevertheless, we remark that it can be instantiated under two of the existing multilinear-map candidates since it does not reveal any encodings of zero. To achieve this goal, we rely on several techniques that were used in the context of program obfuscation, but we also introduce new ones to address challenges that are specific to the related-key-security setting.

2019

ASIACRYPT

From Single-Input to Multi-client Inner-Product Functional Encryption
Abstract

We present a new generic construction of multi-client functional encryption (MCFE) for inner products from single-input functional inner-product encryption and standard pseudorandom functions. In spite of its simplicity, the new construction supports labels, achieves security in the standard model under adaptive corruptions, and can be instantiated from the plain DDH, LWE, and Paillier assumptions. Prior to our work, the only known constructions required discrete-log-based assumptions and the random-oracle model. Since our new scheme is not compatible with the compiler from Abdalla et al. (PKC 2019) that decentralizes the generation of the functional decryption keys, we also show how to modify the latter transformation to obtain a decentralized version of our scheme with similar features.

2019

JOFC

On the Tightness of Forward-Secure Signature Reductions
Abstract

In this paper, we revisit the security of factoring-based signature schemes built via the Fiat–Shamir transform and show that they can admit tighter reductions to certain decisional complexity assumptions such as the quadratic-residuosity, the high-residuosity, and the $$\phi $$ ϕ -hiding assumptions. We do so by proving that the underlying identification schemes used in these schemes are a particular case of the lossy identification notion introduced by Abdalla et al. at Eurocrypt 2012. Next, we show how to extend these results to the forward-security setting based on ideas from the Itkis–Reyzin forward-secure signature scheme. Unlike the original Itkis–Reyzin scheme, our construction can be instantiated under different decisional complexity assumptions and has a much tighter security reduction. Moreover, we also show that the tighter security reductions provided by our proof methodology can result in concrete efficiency gains in practice, both in the standard and forward-security setting, as long as the use of stronger security assumptions is deemed acceptable. Finally, we investigate the design of forward-secure signature schemes whose security reductions are fully tight.

2018

CRYPTO

Multi-Input Functional Encryption for Inner Products: Function-Hiding Realizations and Constructions Without Pairings
📺
Abstract

We present new constructions of multi-input functional encryption (MIFE) schemes for the inner-product functionality that improve the state of the art solution of Abdalla et al. (Eurocrypt 2017) in two main directions.First, we put forward a novel methodology to convert single-input functional encryption for inner products into multi-input schemes for the same functionality. Our transformation is surprisingly simple, general and efficient. In particular, it does not require pairings and it can be instantiated with all known single-input schemes. This leads to two main advances. First, we enlarge the set of assumptions this primitive can be based on, notably, obtaining new MIFEs for inner products from plain DDH, LWE, and Decisional Composite Residuosity. Second, we obtain the first MIFE schemes from standard assumptions where decryption works efficiently even for messages of super-polynomial size.Our second main contribution is the first function-hiding MIFE scheme for inner products based on standard assumptions. To this end, we show how to extend the original, pairing-based, MIFE by Abdalla et al. in order to make it function hiding, thus obtaining a function-hiding MIFE from the MDDH assumption.

2015

EPRINT

2015

EPRINT

2015

CRYPTO

2015

ASIACRYPT

2014

JOFC

2008

JOFC

2007

EPRINT

Generalized Key Delegation for Hierarchical Identity-Based Encryption
Abstract

In this paper, we introduce a new primitive called identity-based encryption with wildcard key derivation (WKD-IBE, or "wicked IBE") that enhances the concept of hierarchical identity-based encryption (HIBE) by allowing more general key delegation patterns. A secret key is derived for a vector of identity strings, where entries can be left blank using a wildcard. This key can then be used to derive keys for any pattern that replaces wildcards with concrete identity strings. For example, one may want to allow the university's head system administrator to derive secret keys (and hence the ability to decrypt) for all departmental sysadmin email addresses sysadmin@*.univ.edu, where * is a wildcard that can be replaced with any string. We provide appropriate security notions and provably secure instantiations with different tradeoffs in terms of ciphertext size and efficiency. We also present a generic construction of identity-based broadcast encryption (IBBE) from any WKD-IBE scheme. One of our instantiation yields an IBBE scheme with constant ciphertext size.

2006

EPRINT

Identity-Based Encryption Gone Wild
Abstract

In this paper we introduce a new primitive called identity-based encryption with wildcards, or WIBE for short. It allows to encrypt messages to a whole range of users simultaneously whose identities match a certain pattern. This pattern is defined through a sequence of fixed strings and wildcards, where any string can take the place of a wildcard in a matching identity. Our primitive can be applied to provide an intuitive way to send encrypted email to groups of users in a corporate hierarchy. We propose a full security notion and give efficient implementations meeting this notion under different pairing-related assumptions, both in the random oracle model and in the standard model.

2005

CRYPTO

2005

EPRINT

Searchable Encryption Revisited: Consistency Properties, Relation to Anonymous IBE, and Extensions
Abstract

We identify and fill some gaps with regard to consistency (the extent to which false positives are produced) for public-key encryption with keyword search (PEKS). We define computational and statistical relaxations of the existing notion of perfect consistency, show that the scheme of Boneh et al. in Eurocrypt 2004 is computationally consistent, and provide a new scheme that is statistically consistent. We also provide a transform of an anonymous IBE scheme to a secure PEKS scheme that, unlike the previous one, guarantees consistency. Finally, we suggest three extensions of the basic notions considered here, namely anonymous HIBE, public-key encryption with temporary keyword search, and identity-based encryption with keyword search.

2004

EPRINT

Password-Based Authenticated Key Exchange in the Three-Party Setting
Abstract

Password-based authenticated key exchange are protocols which are designed to be secure even when the secret key or password shared between two users is drawn from a small set of values. Due to the low entropy of passwords, such protocols are always subject to on-line guessing attacks. In these attacks, the adversary may succeed with
non-negligible probability by guessing the password shared between two users during its on-line attempt to impersonate one of these users. The main goal of password-based authenticated key exchange protocols is to restrict the adversary to this case only. In this paper, we consider password-based authenticated key exchange in the three-party scenario, in which the users trying to establish a secret do not share a password between themselves but only with a trusted server. Towards our goal, we recall some of the existing security notions for password-based authenticated key exchange protocols and introduce new ones that are more suitable to the case of generic constructions. We then present a natural generic construction of a three-party protocol, based on any two-party authenticated key exchange protocol, and prove its security without making use of the Random Oracle model. To the best of our knowledge, the new protocol is the first provably-secure password-based protocol in the three-party setting.

2002

EUROCRYPT

2002

EPRINT

From Identification to Signatures via the Fiat-Shamir Transform: Minimizing Assumptions for Security and Forward-Security
Abstract

The Fiat-Shamir paradigm for transforming
identification schemes into signature schemes has been popular since
its introduction because it yields efficient signature schemes, and
has been receiving renewed interest of late as the main tool in
deriving forward-secure signature schemes.
We find minimal (meaning
necessary and sufficient) conditions on the identification scheme to
ensure security of the signature scheme in the random oracle model,
in both the usual and the forward-secure cases.
Specifically we show that the signature scheme is secure
(resp. forward-secure) against chosen-message attacks in the random
oracle model if and only if the underlying identification
scheme is secure (resp. forward-secure) against impersonation under
passive (i.e.. eavesdropping only) attacks, and has its
commitments drawn at random from a large space. An extension is
proven incorporating a random seed into the Fiat-Shamir transform so
that the commitment space assumption may be removed.

2000

ASIACRYPT

2000

EPRINT

A New Forward-Secure Digital Signature Scheme
Abstract

We improve the Bellare-Miner (Crypto '99) construction of signature
schemes with forward security in the random oracle model. Our scheme
has significantly shorter keys and is, therefore, more practical. By
using a direct proof technique not used for forward-secure schemes
before, we are able to provide better security bounds for the original
construction as well as for our scheme.
Bellare and Miner also presented a method for constructing such schemes
without the use of the random oracle. We conclude by proposing an
improvement to their method and an additional, new method for accomplishing
this.

2000

EPRINT

Forward Security in Threshold Signature Schemes
Abstract

We consider the usage of forward security with threshold
signature schemes. This means that even if more than the
threshold number of players are compromised, some security remains:
it is not possible to forge signatures relating to the past. In
this paper, we describe the first forward-secure threshold
signature schemes whose parameters (other than signing or verifying
time) do not vary in length with the number of time periods in the
scheme. Both are threshold versions of the Bellare-Miner
forward-secure signature scheme, which is Fiat-Shamir-based. One
scheme uses multiplicative secret sharing, and tolerates mobile
eavesdropping adversaries. The second scheme is based on polynomial
secret sharing, and we prove it forward-secure based on the security
of the Bellare-Miner scheme. We then sketch modifications which
would allow this scheme to tolerate malicious adversaries. Finally,
we give several general constructions which add forward security to
any existing threshold scheme.

1999

EPRINT

DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem
Abstract

scheme, DHAES. The scheme is as efficient as ElGamal encryption, but has
stronger security properties. Furthermore, these security properties are proven
to hold under appropriate assumptions on the underlying primitive.
We show that DHAES has not only the ``basic'' property of secure encryption
(namely privacy under a chosen-plaintext attack) but also achieves privacy
under both non-adaptive and adaptive chosen-ciphertext attacks. (And hence
it also achieves non-malleability.)
DHAES is built in a generic way from lower-level primitives: a symmetric
encryption scheme, a message authentication code, group operations in an
arbitrary group, and a cryptographic hash function. In particular, the
underlying group may be an elliptic-curve group or the multiplicative
group of integers modulo a prime number.
The proofs of security are based on appropriate assumptions about the
hardness of the Diffie-Hellman problem and the assumption that the
underlying symmetric primitives are secure. The assumptions are
all standard in the sense that no random oracles are involved.
We suggest that DHAES provides an attractive starting point for developing
public-key encryption standards based on the Diffie-Hellman assumption.

#### Program Committees

- Eurocrypt 2019
- PKC 2018 (Program chair)
- Eurocrypt 2016
- PKC 2015
- Crypto 2015
- PKC 2014
- Asiacrypt 2013
- PKC 2012
- Eurocrypt 2011
- Asiacrypt 2011
- Crypto 2010
- PKC 2008
- Eurocrypt 2007

#### Coauthors

- Jee Hea An (2)
- Manuel Barbosa (2)
- Sonia Belaïd (2)
- Mihir Bellare (9)
- Fabrice Benhamouda (19)
- James Birkett (1)
- Olivier Blazy (1)
- Jens-Matthias Bohli (1)
- Florian Bourse (2)
- Xavier Boyen (1)
- Tatiana Bradley (1)
- Emmanuel Bresson (1)
- Angelo De Caro (2)
- Dario Catalano (9)
- Céline Chevalier (3)
- Olivier Chevassut (3)
- Alexander W. Dent (3)
- Dario Fiore (4)
- Pierre-Alain Fouque (7)
- Romain Gay (4)
- Junqing Gong (1)
- Björn Haase (1)
- Julia Hesse (1)
- Stanislaw Jarecki (1)
- Jonathan Katz (2)
- Eike Kiltz (4)
- Markulf Kohlweiss (1)
- Tadayoshi Kohno (3)
- Tanja Lange (3)
- Julian Loss (1)
- Vadim Lyubashevsky (3)
- John Malone-Lee (6)
- Sara K. Miner (1)
- Chanathip Namprempre (3)
- Gregory Neven (9)
- Pascal Paillier (3)
- Alain Passelègue (7)
- Kenneth G. Paterson (2)
- Duong Hieu Phan (1)
- David Pointcheval (20)
- Mariana Raykova (1)
- Leonid Reyzin (2)
- Phillip Rogaway (1)
- Jacob C. N. Schuldt (1)
- Haixia Shi (3)
- Nigel P. Smart (3)
- Rainer Steinwandt (1)
- Mehdi Tibouchi (2)
- Bogdan Ursu (2)
- Maria Isabel Gonzalez Vasco (1)
- Hendrik Waldner (1)
- Hoeteck Wee (2)
- Jiayu Xu (2)