I’m a quantitative developer at BlockTech in Amsterdam.
My academic background is in mathematics and theoretical computer science, with a focus on cryptography. I completed my doctoral research at the Max Planck Institute for Security and Privacy, earning a PhD in Mathematics (summa cum laude) under the supervision of Giulio Malavolta.
Before that, I earned an MSc in Computer Science from the University of Virginia and a BSc in Computer Science from Sharif University of Technology.
Publications
Authors are listed alphabetically, following the convention in cryptography.
-
Ahmadreza Rahimi
PhD thesis · 2024
-
Pedro Branco, Russell W. F. Lai, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi, Ivy K. Y. Woo
ASIACRYPT 2024
Traitor Tracing Without Trusted Authority from Registered Functional Encryption
Pedro Branco, Russell W. F. Lai, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi, Ivy K. Y. Woo
ASIACRYPT 2024
Abstract
Traitor-tracing systems allow identifying the users who contributed to building a rogue decoder in a broadcast environment. In a traditional traitor-tracing system, a key authority is responsible for generating the global public parameters and issuing secret keys to users. All security is lost if the key authority itself is corrupt. This raises the question: Can we construct a traitor-tracing scheme, without a trusted authority? In this work, we propose a new model for traitor-tracing systems where, instead of having a key authority, users could generate and register their own public keys. The public parameters are computed by aggregating all user public keys. Crucially, the aggregation process is public, thus eliminating the need of any trusted authority. We present two new traitor-tracing systems in this model based on bilinear pairings. Our first scheme is proven adaptively secure in the generic group model. This scheme features a transparent setup, ciphertexts consisting of $6\sqrt{L}+4$ group elements, and a public tracing algorithm. Our second scheme supports a bounded collusion of traitors and is proven selectively secure in the standard model. Our main technical ingredients are new registered functional encryption (RFE) schemes for quadratic and linear functions which, prior to this work, were known only from indistinguishability obfuscation. To substantiate the practicality of our approach, we evaluate the performance of a proof of concept implementation. For a group of $L = 1024$ users, encryption and decryption take roughly 50ms and 4ms, respectively, whereas a ciphertext is of size 6.7KB.
-
Danilo Francati, Daniele Friolo, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi, Daniele Venturi
ASIACRYPT 2023
Registered (Inner-Product) Functional Encryption
Danilo Francati, Daniele Friolo, Monosij Maitra, Giulio Malavolta, Ahmadreza Rahimi, Daniele Venturi
ASIACRYPT 2023
Abstract
Registered encryption (Garg, Hajiabadi, Mahmoody, and Rahimi, TCC'18) is an emerging encryption paradigm that tackles the key-escrow problem associated with identity-based encryption by replacing the private-key generator with a much weaker entity known as the key curator. The key curator holds no secret information, and is responsible to: (i) update the master public key whenever a new user registers its own public key to the system; (ii) provide helper decryption keys to the users already in the system, in order to make them still able to decrypt. For practical purposes, task (i) and (ii) need to be efficient, in the sense that the size of the public parameters, of the master public key, and of the helper decryption keys, as well as the running time for key generation and user registration, and the number of updates, must be small (ideally, logarithmic in the number of users in the system). In this paper, we generalize the notion of registered encryption to the setting of functional encryption (FE). Our contributions are twofold: On the theoretical side, we show that registered FE exists assuming indistinguishability obfuscation and somewhere statistically binding hash functions. On the practical side, we show an efficient construction of registered FE for the special case of inner-product predicates, over asymmetric bilinear groups. We prove the security of such a scheme in the generic group model.
-
Behzad Abdolmaleki, Saikrishna Badrinarayanan, Rex Fernando, Giulio Malavolta, Ahmadreza Rahimi, Amit Sahai
ASIACRYPT 2023
Two-Round Concurrent 2PC from Sub-Exponential LWE
Behzad Abdolmaleki, Saikrishna Badrinarayanan, Rex Fernando, Giulio Malavolta, Ahmadreza Rahimi, Amit Sahai
ASIACRYPT 2023
Abstract
Secure computation is a cornerstone of modern cryptography and a rich body of research is devoted to understanding its round complexity. In this work, we consider two-party computation (2PC) protocols (where both parties receive output) that remain secure in the realistic setting where many instances of the protocol are executed in parallel (concurrent security). We obtain a two-round concurrent-secure 2PC protocol based on a single, standard, post-quantum assumption: The subexponential hardness of the learning-with-errors (LWE) problem. Our protocol is in the plain model, i.e., it has no trusted setup, and it is secure in the super-polynomial simulation framework of Pass (EUROCRYPT 2003). Since two rounds are minimal for (concurrent) 2PC, this work resolves the round complexity of concurrent 2PC from standard assumptions. As immediate applications, our work establishes feasibility results for interesting cryptographic primitives such as the first two-round password authentication key exchange (PAKE) protocol in the plain model and the first two-round concurrent secure computation protocol for quantum circuits (2PQC).
-
Nico Döttling, Dimitris Kolonelos, Russell W. F. Lai, Chuanwei Lin, Giulio Malavolta, Ahmadreza Rahimi
EUROCRYPT 2023
Efficient Laconic Cryptography from Learning With Errors
Nico Döttling, Dimitris Kolonelos, Russell W. F. Lai, Chuanwei Lin, Giulio Malavolta, Ahmadreza Rahimi
EUROCRYPT 2023
Abstract
This work shows that non-black-box techniques are not necessary for basic laconic cryptography primitives. We propose a completely algebraic construction of laconic encryption, a notion that we introduce in this work, which serves as the cornerstone of our framework. We prove that the scheme is secure under the standard Learning With Errors assumption (with polynomial modulus-to-noise ratio). We provide proof-of-concept implementations for the first time for laconic primitives, demonstrating the construction is indeed practical: For a database size of $2^{50}$, encryption and decryption are in the order of single digit milliseconds.
Laconic encryption can be used as a black box to construct other laconic primitives. Specifically, we show how to construct:
- Laconic oblivious transfer
- Registration-based encryption scheme
- Laconic private-set intersection protocol
All of the above have essentially optimal parameters and similar practical efficiency. Furthermore, our laconic encryption can be preprocessed such that the online encryption step is entirely combinatorial and therefore much more efficient.
Using similar techniques, we also obtain identity-based encryption with an unbounded identity space and tight security proof (in the standard model).
-
Noemi Glaeser, Dimitris Kolonelos, Giulio Malavolta, Ahmadreza Rahimi
ACM CCS 2023
Efficient Registration-Based Encryption
Noemi Glaeser, Dimitris Kolonelos, Giulio Malavolta, Ahmadreza Rahimi
ACM CCS 2023
Abstract
Registration-based encryption (RBE) was recently introduced as an alternative to identity-based encryption (IBE), to resolve the key-escrow problem: In RBE, the trusted authority is substituted with a weaker entity, called the key curator, who has no knowledge of any secret key. Users generate keys on their own and then publicly register their identities and their corresponding public keys to the key curator. RBE is a promising alternative to IBE, retaining many of its advantages while removing the key-escrow problem, the major drawback of IBE. Unfortunately, all existing constructions of RBE use cryptographic schemes in a non black-box way, which makes them prohibitively expensive. It has been estimated that the size of an RBE ciphertext would be in the order of terabytes (though no RBE has even been implemented).
In this work, we propose a new approach to construct RBE, from standard assumptions in bilinear groups. Our scheme is black-box and it is concretely highly efficient---a ciphertext is 914 bytes. To substantiate this claim, we implemented a prototype of our scheme and we show that it scales to millions of users. The public parameters of the scheme are on the order of kilobytes. The most expensive operation (registration) takes at most a handful of seconds, whereas the encryption and decryption runtimes are on the order of milliseconds. This is the first-ever implementation of an RBE scheme and demonstrates that the practical deployment of RBE is already possible with today's hardware.
-
Candidate Trapdoor Claw-Free Functions from Group Actions with Applications to Quantum Protocols
2022Navid Alamati, Giulio Malavolta, Ahmadreza Rahimi
TCC 2022
Candidate Trapdoor Claw-Free Functions...
Navid Alamati, Giulio Malavolta, Ahmadreza Rahimi
TCC 2022
Abstract
Trapdoor Claw-free Functions (TCFs) are two-to-one trapdoor functions where it is computationally hard to find a claw, i.e., a colliding pair of inputs. TCFs have recently seen a surge of renewed interest due to new applications to quantum cryptography: as an example, TCFs enable a classical machine to verify that some quantum computation has been performed correctly. In this work, we propose a new family of (almost two-to-one) TCFs based on conjectured hard problems on isogeny-based group actions. This is the first candidate construction that is not based on lattice-related problems and the first scheme (from any plausible post-quantum assumption) with a deterministic evaluation algorithm. To demonstrate the usefulness of our construction, we show that our TCF family can be used to devise a computational test of qubit, which is the basic building block used in general verification of quantum computations.
-
Mohammad Mahmoody, Wei Qi, Ahmadreza Rahimi
TCC 2022
Lower Bounds for the Number of Decryption Updates...
Mohammad Mahmoody, Wei Qi, Ahmadreza Rahimi
TCC 2022
Abstract
A major drawback of RBE, compared with IBE, is that in order to decrypt, parties might need to periodically request so-called decryption updates from the KC. Current RBE schemes require $\Omega(\log n)$ number of updates after $n$ registrations, while the public parameter is of length $\poly(\log n)$. Clearly, it would be highly desirable to have RBEs with only, say, a constant number of updates. This leads to the following natural question: are so many (logarithmic) updates necessary for RBE schemes, or can we decrease the frequency of updates significantly?
In this paper, we prove an almost tight lower bound for the number of updates in RBE schemes, as long as the times that parties receive updates only depend on the registration time of the parties, which is a natural property that holds for all known RBE constructions. More generally, we prove a trade-off between the number of updates in RBEs and the length of the public parameter for any scheme with fixed update times. Indeed, we prove that for any such RBE scheme, if there are $n \geq \binom{k+d}{d+1}$ identities that receive at most $d$ updates, the public parameter needs to be of length $\Omega(k)$. As a corollary, we find that RBE systems with fixed update times and public parameters of length $\poly (\log n)$ require $\Omega(\log n/\log\log n)$ decryption updates, which is optimal up to an $O(\log\log n)$ factor.
-
Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi, Sruthi Sekar
PKC 2019
Registration-Based Encryption from Standard Assumptions
Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi, Sruthi Sekar
PKC 2019
Abstract
The notion of Registration-Based Encryption (RBE) was recently introduced by Garg, Hajiabadi, Mahmoody, and Rahimi (TCC 2018) with the goal of removing the private-key generator (PKG) from IBE. Specifically, RBE allows encrypting to identities using a (compact) master public key, like how IBE is used, with the benefit that the PKG is substituted with a weaker entity called ``key curator'' who has no knowledge of any secret keys. Here individuals generate their secret keys on their own and then publicly register their identities and their corresponding public keys to the key curator. Finally, individuals obtain ``rare'' decryption-key updates from the key curator as the population grows. In their work, they gave a construction of RBE schemes based on the combination of indistinguishability obfuscation and somewhere statistically binding hash functions. However, they left open the problem of constructing RBE schemes based on standard assumptions.
In this work, we resolve the above problem and construct RBE schemes based on standard assumptions (e.g., CDH or LWE). Furthermore, we show a new application of RBE in a novel context. In particular, we show that anonymous variants of RBE (which we also construct under standard assumptions) can be used for realizing abstract forms of anonymous messaging tasks in simple scenarios in which the parties communicate by writing messages on a shared board in a synchronized way.
-
Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi
TCC 2018
Registration-Based Encryption: Removing Private-Key Generator from IBE
Sanjam Garg, Mohammad Hajiabadi, Mohammad Mahmoody, Ahmadreza Rahimi
TCC 2018
Abstract
In this work, we introduce the notion of registration-based encryption (RBE for short) with the goal of removing the trust parties need to place in the private-key generator in an IBE scheme. In an RBE scheme, users sample their own public and secret keys. There will also be a ``key curator'' whose job is only to aggregate the public keys of all the registered users and update the ``short'' public parameter whenever a new user joins the system. Encryption can still be performed to a particular recipient using the recipient's identity and any public parameters released subsequent to the recipient's registration. Decryption requires some auxiliary information connecting users' public (and secret) keys to the public parameters. Because of this, as the public parameters get updated, a decryptor may need to obtain ``a few'' additional auxiliary information for decryption.
More formally, if $n$ is the total number of identities and $\lambda$ is the security parameter, we require the following.
- Efficiency requirements: (1) A decryptor only needs to obtain updated auxiliary information for decryption at most $O(\log n)$ times in its lifetime, (2) each of these updates are computed by the key curator in time $\operatorname{poly}(\lambda,\log n)$, and (3) the key curator updates the public parameter upon the registration of a new party in time $\operatorname{poly}(\lambda,\log n)$. Properties (2) and (3) require the key curator to have random access to its data.
- Compactness requirements: (1) Public parameters are always at most $\operatorname{poly}(\lambda,\log n)$ bits, and (2) the total size of updates a user ever needs for decryption is $\operatorname{poly}(\lambda,\log n)$ bits.
We present feasibility results for constructions of RBE based on indistinguishability obfuscation. We further provide constructions of weakly efficient RBE, in which the registration step is done in $\operatorname{poly}(\lambda,n)$, based on CDH, Factoring or LWE assumptions. Note that registration is done only once per identity, and the more frequent operation of generating updates for a user, which can happen more times, still runs in time $\operatorname{poly}(\lambda,\log n)$. We leave open the problem of obtaining standard RBE (with $\operatorname{poly}(\lambda,\log n)$ registration time) from standard assumptions.
Newest first