Antonio Faonio

Assistant Professor at EURECOM

Myself I joined EURECOM as assistant professor on July 2020. I was a postdoctoral researcher at IMDEA Software Institute, where I was super lucky to work with prof. Dario Fiore from Jannuary 2017 to July 2020. I was a postdoctoral researcher at CTIC, Aarhus University since December 2014 working mostly with prof. Jesper Buus Nielsen until Dec 2016.
I got a Ph.D. in Computer Science at "Sapienza" Univ. of Rome. my advisor was prof. Giuseppe Ateniese.
The name of my thesis is: "Leakage-Resilient Identification Schemes and Signatures".
My main interest is in Cryptography both applied and theoretical.

!! I have an open position for a PhD student !!
The candidate will work on Cryptography (non-malleability, pairing-based cryptography, tamper-and-leakage resilience, zero-knowledge and all those funny stuff). Contact me if you are interested!

Personal Email:
Official Email:
ORCID ID: 0000-0002-7152-6478
My PGP keys
Key IDs :
4835AA19 D20F856C (
FFAF293C 9DEA377F (

On the insecurity of PGP: PGP is ''not secure'' (this is not even the only known attack), but as far as I know, it is still the best option for secure emails.

[+] Publications and preprints:

   [+] Auditable Asymmetric Password Authenticated Public Key Establishment, manuscript, (with Claudio Soriente, Maria Isabel Vasco and Hien Troung) eprint

Non-repudiation of user messages is a desirable feature in a number of online applications, but requires digital signatures and certified public keys. Unfortunately, the use of cryptographic keys often results in poor usability as users must either carry around their private keys (e.g., in a smart-card) or store them in all of their devices. An user-friendly alternative, adopted by several companies and national administrations, is to have a “cloud-based PKI certificate”. In a nutshell, each user has a certified key-pair stored at a server in the cloud; users authenticate to the server—via passwords or one-time codes—and ask it to sign messages on their behalf. However, moving the key-pair from user private storage to the cloud kills non-repudiation. In fact, a user can always deny having signed a message, by claiming that the signature was produced by the allegedly malicious server without her consent.
In this paper we provide a solution that keeps the usability of the cloud-based approach without losing non-repudiation. In particular, we introduce a new ideal functionality in the Universal Composability framework that we call Auditable Asymmetric Password Authenticated Public Key Establishment (A2PAKE). The functionality is password-based and allows to generate asymmetric key-pairs, where the public key is output to all the parties, but the secret key is the pri- vate output of a single one (e.g., the user). Further, the functionality is auditable, i.e., given a public key output by the functionality, a server can prove to a third party (i.e., a judge) that the corresponding secret key is held by a specific user. Thus, if the user signs messages with that secret key, then signatures are non-repudiable. We provide an efficient instantiation based on distributed oblivious pseudo-random functions. We also develop a prototype implementation of our instantiation and use it to evaluate its performance in realistic settings.

   [+] Submission Subversion-Resilient Enhanced Privacy ID manuscript, (with Dario Fiore, Luca Nizzardo and Claudio Soriente)

Anonymous attestation for secure hardware platforms leverages tailored group signature schemes and assumes the hardware to be trusted. Yet, there is an ever increasing concern on the trustworthiness of hardware components and embedded systems. A subverted hardware may, for example, use its signatures to exfiltrate identifying information or even the signing key.
In this paper we focus on Enhanced Privacy ID (EPID) — a popular anonymous attestation scheme used in commodity secure hardware platforms like Intel SGX. We define and instantiate a subversion resilient EPID scheme (or SR-EPID). In a nutshell, SR-EPID provides the same functionality and security guarantees of the original EPID, despite potentially subverted hardware. In our design, a “sanitizer” ensures no covert channel between the hardware and the outside world both during enrollment and during attestation (i.e., when signatures are produced).
We design a practical SR-EPID scheme secure against adaptive corruptions and based on a novel combination of malleable NIZKs and hash functions modeled as random oracles. Our approach has a number of advantages over alternative designs. Namely, the sanitizer bears no secret information—hence, a memory leak does not erode security. Further, the role of sanitizer may be distributed in a cascade fashion among several parties so that sanitization becomes effective as long as one of the parties has access to a good source of randomness. Also, we keep the signing protocol non-interactive, thereby minimizing latency during signature generation.

   [+] Structure-Preserving and Re-randomizable RCCA-secure Public Key Encryption and its Applications , ASIACRYPT'19, (with Dario Fiore and Javier Herranz and Carla Ràfols) eprint

Re-randomizable RCCA-secure public key encryption (Rand-RCCA PKE) schemes reconcile the property of re-randomizability of the ciphertexts with the need of security against chosen-ciphertexts attacks. In this paper we give a new construction of a Rand-RCCA PKE scheme that is perfectly re-randomizable. Our construction is structure-preserving, can be instantiated over Type-3 pairing groups, and achieves better computation and communication efficiency than the state of the art perfectly re-randomizable schemes (e.g., Prabhakaran and Rosulek, CRYPTO'07). Next, we revive the Rand-RCCA notion showing new applications where our Rand-RCCA PKE scheme plays a fundamental part: (1) We show how to turn our scheme into a publicly-verifiable Rand-RCCA scheme; (2) We construct a malleable NIZK with a (variant of) simulation soundness that allows for re-randomizability; (3) We propose a new UC-secure Verifiable Mix-Net protocol that is secure in the common reference string model. Thanks to the structure-preserving property, all these applications are efficient. Notably, our Mix-Net protocol is the most efficient universally verifiable Mix-Net (without random oracle) where the CRS is an uniformly random string of size independent of the number of senders. The property is of the essence when such protocols are used in large scale.

   [+] Practical Continuously Non-Malleable Randomness-Encoders in the Random Oracle Model, manuscript

In a recent paper Kanukurthi, Obbattu and Sekar (Euro- Crypt’18) introduced the concept of non-malleable randomness encoders (NMREs) as a relaxation of the beautiful notion of non-malleable codes of Dziembowski, Pietrzak and Wichs (ICS’10). A randomness encoder allows to encode a random key and obtaining a codeword, the non mal- leability property states that by tampering once with the codeword the adversary does not learn anything about the encoded key. In this paper we consider the natural extension to continuous non- malleability (Faust et al. TCC’14) where the adversary can tamper with the codeword many times. In particular, we give two extremely efficient constructions in the split-state model. In this model we assume that the codeword is divided in two pieces, and that the tampering functions can alter the two pieces independently. Our constructions are proved secure in the random oracle model.

   [+] Continuously Non-Malleable Secret Sharing for General Access Structures, TCC'19, (with Gianluca Brian and Daniele Venturi) eprint

We study leakage-resilient continuously non-malleable secret sharing, as recently intro- duced by Faonio and Venturi (CRYPTO 2019). In this setting, an attacker can continuously tamper and leak from a target secret sharing of some message, with the goal of producing a modified set of shares that reconstructs to a message related to the originally shared value. Our contributions are two fold.
• In the plain model, assuming one-to-one one-way functions, we show how to obtain noisy-leakage-resilient continuous non-malleability for arbitrary access structures, in case the attacker can continuously leak from and tamper with all of the shares inde- pendently.
• In the common reference string model, we show how to obtain a new flavor of secu- rity which we dub bounded-leakage-resilient continuous non-malleability under joint k-selective partitioning. In this model, the attacker is allowed to partition the target n shares into k non-overlapping subsets, and then can continuously leak from and tamper with the shares within each subset jointly. Our construction works for arbitrary ac- cess structures, and assuming (doubly enhanced) trapdoor permutations and collision- resistant hash functions, we achieve a concrete instantiation for $k \in O(n/ \log n)$.
Prior to our work, there was no secret sharing scheme achieving continuous non-malleability against joint tampering, and the only known scheme for independent tampering was tailored to threshold access structures.

   [+] Non-Malleable Secret Sharing in the Computational Setting: Adaptive Tampering, Noisy-Leakage Resilience, and Improved Rate,CRYPTO'19, (with Daniele Venturi) eprint

We revisit the concept of *non-malleable* secret sharing (Goyal and Kumar, STOC 2018) in the computational setting. In particular, under the assumption of one-to-one one-way functions, we exhibit a *computationally* private, *threshold* secret sharing scheme satisfying all of the following properties. -) Continuous non-malleability: No computationally-bounded adversary tampering independently with all the shares can produce mauled shares that reconstruct to a value related to the original secret. This holds even in case the adversary can tamper *continuously*, for an *unbounded* polynomial number of times, with the same target secret sharing, where the next sequence of tampering functions, as well as the subset of shares used for reconstruction, can be chosen *adaptively* based on the outcome of previous reconstructions. -) Resilience to noisy leakage: Non-malleability holds even if the adversary can additionally leak information independently from all the shares. There is no bound on the length of leaked information, as long as the overall leakage does not decrease the min-entropy of each share by too much. -) Improved rate: The information rate of our final scheme, defined as the ratio between the size of the message and the maximal size of a share, asymptotically approaches 1 when the message length goes to infinity. Previous constructions achieved information-theoretic security, sometimes even for arbitrary access structures, at the price of *at least one* of the following limitations: (i) Non-malleability only holds against one-time tampering attacks; (ii) Non-malleability holds against a bounded number of tampering attacks, but both the choice of the tampering functions and of the sets used for reconstruction is non-adaptive; (iii) Information rate asymptotically approaching zero; (iv) No security guarantee in the presence of leakage.

   [+] Rate-Optimizing Compilers for Continuously Non-Malleable Codes, ACNS 2019, (with Sandro Coretti and Daniele Venturi) eprint

We study the *rate* of so-called *continuously* non-malleable codes, which allow to encode a message in such a way that (possibly adaptive) continuous tampering attacks on the codeword yield a decoded value that is unrelated to the original message. Our results are as follows: -) For the case of bit-wise independent tampering, we establish the existence of rate-one continuously non-malleable codes with information-theoretic security, in the plain model. -) For the case of split-state tampering, we establish the existence of rate-one continuously non-malleable codes with computational security, in the (non-programmable) random oracle model. We further exhibit a rate-1/2 code and a rate-one code in the common reference string model, but the latter only withstands *non-adaptive* tampering. It is well known that computational security is inherent for achieving continuous non-malleability in the split-state model (even in the presence of non-adaptive tampering). Continuously non-malleable codes are useful for protecting *arbitrary* cryptographic primitives against related-key attacks, as well as for constructing non-malleable public-key encryption schemes. Our results directly improve the efficiency of these applications.

   [+] Optimistic Mixing, Revisited , manuscript, (with Dario Fiore) eprint

Mixing Networks are protocols that allow a set of senders to send messages anonymously. Such protocols are fundamental building blocks to achieve privacy in a variety of applications, such as anonymous e-mail, anonymous payments, and electronic voting. Back in 2002, Golle \etal~proposed a new concept of mixing network, called optimistic mixing, that allows for fast mixing when all the parties execute the protocol honestly. %following sentence may be removed if space is needed If, on the other hand, one or more mix-servers cheat, then the attack is recognized and one can back up to a different, slow mix-net. Unfortunately, Abe and Imai (ACISP'03) and independently Wikstr\"om (SAC'03) showed several major flaws in the optimistic protocol of Golle \etal~ In this work, we give another look at optimistic mixing networks. Our contribution is mainly threefold. First, we give formal definitions for optimistic mixing in the UC model. Second, we propose a compiler for obtaining a UC-secure mixing network by combining an optimistic mixing with a traditional mixing protocol as backup mixing. Third, we propose an efficient UC-secure realization of optimistic mixing based on the DDH assumption in the non-programmable random oracle model. As a key ingredient of our construction, we give a new randomizable replayable-CCA secure public key encryption (PKE) that outperforms in efficiency all previous schemes. We believe this result is of independent interest.

   [+] Efficient Fully-Leakage Resilient One-More Signature Schemes , CT-RSA 2019 eprint

In a recent paper Faonio, Nielsen and Venturi (ICALP 2015) gave new constructions of leakage-resilient signature schemes. The signature schemes proposed remain unforgeable against an adversary leaking arbitrary information on the entire state of the signer, including the random coins of the signing algorithm. The main feature of their signature schemes is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. The notion, put forward by Nielsen, Venturi, and Zottarel (PKC 2014), define a \emph{slack parameter} $\gamma$ which, roughly speaking, describes how gracefully the security degrades. Unfortunately, the standard model signature scheme of Faonio, Nielsen and Venturi has slack parameter that depends on number of signature queried by the adversary. In this paper we show two new constructions in the standard model where the above limitation is avoided. Specifically, the first scheme we propose achieves slack parameter $O(1/\spar)$ where $\spar$ is the security parameter and it is based on standard number theoretic assumptions, the second scheme achieves optimal slack parameter (i.e. $\gamma=1$) and it is based on knowledge of the exponent assumptions. Our constructions are efficient and have leakage rate $1-o(1)$, most notably our second construction has signature size of only $8$ group elements which makes it the leakage-resilient signature scheme with the shortest signature size known to the best of our knowledge.

   [+] Continuous Non-Malleable Codes with Split-State Refresh. ACNS 2018, (with Jesper Buus Nielsen, Mark Simkin, and Daniele Venturi)

Non-malleable codes for the split-state model allow to encode a message into two parts, such that arbitrary independent tampering on each part, and subsequent decoding of the corresponding modified codeword, yields either the same as the original message, or a completely unrelated value. Continuously non-malleable codes further allow to tolerate an unbounded (polynomial) number of tampering attempts, until a decoding error happens. The drawback is that, after an error happens, the system must self-destruct and stop working, otherwise generic attacks become possible. In this paper we propose a solution to this limitation, by leveraging a split-state refreshing procedure. Namely, whenever a decoding error happens, the two parts of an encoding can be locally refreshed (i.e.,\ without any interaction), which allows to avoid the self-destruct mechanism. An additional feature of our security model is that it captures directly security against continual leakage attacks. We give an abstract framework for building such codes in the common reference string model, and provide a concrete instantiation based on the external Diffie-Hellman assumption. Finally, we explore applications in which our notion turns out to be essential. The first application is a signature scheme tolerating an arbitrary polynomial number of split-state tampering attempts, without requiring a self-destruct capability, and in a model where refreshing of the memory happens only after an invalid output is produced. This circumvents an impossibility result from a recent work by Fuijisaki and Xagawa (Asiacrypt 2016). The second application is a compiler for tamper-resilient RAM programs. In comparison to other tamper-resilient compilers, ours has several advantages, among which the fact that, for the first time, it does not rely on the self-destruct feature.

   [+] Non-Malleable Codes with Split-State Refresh. PKC 2017, (with Jesper Buus Nielsen) eprint

Non-Malleable Codes for the split state model allow to encode a mes- sage into two parts such that arbitrary independent tampering on the parts either destroys completely the content or maintains the message untouched. If the code is also leakage resilient it allows limited independent leakage from the two parts. We propose a model where the two parts can be refreshed independently. We give an abstract framework for building codes for this model, instantiate the construction under the external Diffie-Hellman assumption and give applications of such split-state refreshing. An advantage of our new model is that it allows arbitrarily many tamper attacks and arbitrarily large leakage over the life-time of the systems as long as occasionally each part of the code is refreshed. Our model also tolerates that the refreshing occasionally is leaky or tampered with.

   [+] Efficient Public-Key Cryptography with Bounded Leakage and Tamper Resilience. ASIACRYPT 2016, (with Daniele Venturi) eprint

We revisit the question of constructing public-key encryption and signature schemes with security in the presence of bounded leakage and tampering memory attacks. For signatures we obtain the first construction in the standard model; for public-key encryption we obtain the first construction free of pairing (avoiding non-interactive zero-knowledge proofs). Our constructions are based on generic building blocks, and, as we show, also admit efficient instantiations under fairly standard number-theoretic assumptions.
The model of bounded tamper resistance was recently put forward by Damgård {\em et al.} (Asiacrypt 2013) as an attractive path to achieve security against arbitrary memory tampering attacks without making hardware assumptions (such as the existence of a protected self-destruct or key-update mechanism), the only restriction being on the number of allowed tampering attempts (which is a parameter of the scheme). This allows to circumvent known impossibility results for unrestricted tampering (Gennaro {\em et al.}, TCC 2010), while still being able to capture realistic tampering attacks.

   [+] Fully Leakage-Resilient Codes PKC 2017, (with Jesper Buus Nielsen) eprint

Leakage resilient codes (LRCs) are probabilistic encoding schemes that guarantee message hiding even under some bounded leakage on the codeword. We introduce the notion of \emph{fully} leakage resilient codes (FLRCs), where the adversary can leak some λ0 bits from the encoding process, i.e., the message and the randomness involved during the encoding process. In addition the adversary can as usual leak from the codeword. We give a simulation-based definition requiring that the adversary's leakage from the encoding process and the codework can be simulated given just λ0 bits of leakage from the message. For λ0=0 our new simulation-based notion is equivalent to the usual game-based definition. A FLRC would be interesting in its own right and would be useful in building other leakage-resilient primitives in a composable manner. We give a fairly general impossibility result for FLRCs in the popular split-state model, where the codeword is broken into independent parts and where the leakage occurs independently on the parts. We show that if the leakage is allowed to be any poly-time function of the secret and if collision-resistant hash functions exist, then there is no FLRC for the split-state model. The result holds only when the message length can be linear in the security parameter. However, we can extend the impossibility result to FLRCs for constant-length messages under assumptions related to differing-input obfuscation. These results show that it is highly unlikely that we can build FLRCs for the split-state model when the leakage can be any poly-time function of the secret state. We then give two feasibility results for weaker models. First, we show that for \NC0-bounded leakage from the randomness and arbitrary poly-time leakage from the parts of the codeword the inner-product construction proposed by Daví \etal (SCN'10) and successively improved by Dziembowski and Faust (ASIACRYPT'11) is a FLRC for the split-state model. Second, we provide a compiler from any LRC to a FLRC in the common reference string model for any fixed leakage family of small cardinality. In particular, this compiler applies to the split-state model but also to many other models.

   [+] Predictable Arguments of Knowledge. PKC 2017, (with Jesper Buus Nielsen and Daniele Venturi) eprint

We initiate a formal investigation on the power of {\em predictability} for argument of knowledge systems for \NP. Specifically, we consider private-coin argument systems where the answer of the prover can be predicted, given the private randomness of the verifier; we call such protocols Predictable Arguments of Knowledge (PAoK).
Our study encompasses a full characterization of PAoK, showing that such arguments can be made extremely laconic, with the prover sending a single bit, and assumed to have only one round (i.e.,\ two messages) of communication without loss of generality.
We additionally explore PAoK satisfying additional properties (including zero-knowledge and the possibility of re-using the same challenge across multiple executions with the prover), present several constructs of PAoK relying on different cryptographic tools, and discuss applications to cryptography.

   [+] Leakage-Resilient Identification Schemes from Zero-Knowledge Proofs of Storage. IMACC 2015. (with Giuseppe Ateniese and Seny Kamara) eprint

We provide a framework for constructing leakage-resilient identification(ID) protocols in the bounded retrieval model (BRM) from proofs of storage(PoS) that hide partial information about the file. More precisely, we describe a generic transformation from any zero-knowledge PoS to a leakage-resilient ID protocol in the BRM. We then describe a ZK-PoS based on RSA which, under our transformation, yields the first ID protocol in the BRM based on RSA (in the ROM). The resulting protocol relies on a different computational assumption and is more efficient than previously-known constructions.

   [+] Mind Your Coins: Fully Leakage-Resilient Signatures with Graceful Degradation. ICALP 2015. (with Jesper Buus Nielsen and Daniele Venturi). eprint - Journal Version

We construct new leakage-resilient signature schemes. Our schemes remain unforgeable against an adversary leaking arbitrary (yet bounded) information on the entire state of the signer (sometimes known as *fully* leakage resilience), including the random coin tosses of the signing algorithm.
The main feature of our constructions is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. This property was recently put forward by Nielsen, Venturi, and Zottarel (PKC 2014) to deal with settings in which the secret key is much larger than the size of a signature. One remarkable such case is the so-called Bounded-Retrieval Model (BRM), where one intentionally inflates the size of the secret key while keeping constant the signature size and the computational complexity of the scheme.
Our main constructions have leakage rate 1−o(1) , and are proven secure in the standard model. We additionally give a construction in the BRM, relying on a random oracle. All of our schemes are described in terms of generic building blocks, but also admit efficient instantiations under fairly standard number-theoretic assumptions. Finally, we explain how to extend some of our schemes to the setting of noisy leakage, where the only restriction on the leakage functions is that the output does not decrease the min-entropy of the secret key by too much.

   [+] Certified Bitcoins. ACNS 2014. (With Giuseppe Ateniese, Bernardo Magri, Breno de Medeiros) eprint

Bitcoin is a peer-to-peer (p2p) electronic cash system that uses a distributed timestamp service to record transactions in a public ledger (called the Blockchain). A critical component of Bitcoin’s success is the decentralized nature of its architecture, which does not require or even support the establishment of trusted authorities. Yet the absence of certification creates obstacles to its wider acceptance in e-commerce and official uses. We propose a certification system for Bitcoin that offers: a) an opt-in guarantee to send and receive bitcoins only to/ from certified users; b) control of creation of bitcoins addresses (certified users) by trusted authorities. Our proposal may encourage the adoption of Bitcoin in different scenarios that require an officially recognized currency, such as tax payments—often an integral part of e-commerce transactions.

   [+] Proofs of Space: When Space Is of the Essence. SCN 2014 (With Giuseppe Ateniese, Ilario Bonacina, Nicola Galesi) eprint

Proofs of computational effort were devised to control denial of service attacks. Dwork and Naor (CRYPTO ’92), for example, proposed to use such proofs to discourage spam. The idea is to couple each email message with a proof of work that demonstrates the sender performed some computational task. A proof of work can be either CPU-bound or memory-bound. In a CPU-bound proof, the prover must compute a CPU-intensive function that is easy to check by the verifier. A memory-bound proof, instead, forces the prover to access the main memory several times, effectively replacing CPU cycles with memory accesses. In this paper we put forward a new concept dubbed proof of space. To compute such a proof, the prover must use a specified amount of space, i.e., we are not interested in the number of accesses to the main memory (as in memory-bound proof of work) but rather on the amount of actual memory the prover must employ to compute the proof. We give a complete and detailed algorithmic description of our model. We develop a comprehensive theoretical analysis which uses combinatorial tools from Complexity Theory (such as pebbling games) which are essential in studying space lower bounds.

[+] Reviewer:

PC member of LatinCrypt 2021.
PC member of Financial Cryptography and Data Security 2021 (FC'21) .
PC member of International Workshop on Security (IWSEC 2021).
PC member of Financial Cryptography and Data Security 2020 (FC'20) .
PC member of International Workshop on Security (IWSEC 2020).
PC member of Financial Cryptography and Data Security 2019 (FC'19) .
PC member of International Workshop on Security (IWSEC 2019).
PC member of The 2018 IEEE International Conference on Blockchain (Blockchain-2017).
I served as an external reviewer for these conferences:

I served as a reviewer for these journals:
 IET Information Security,IEEE Transactions on Dependable and Secure Computing, Teo. Comp. Sci..

[+] Stuff:

I am a runner and I always bring my running shoes and gears with me. If we were at the same conference and you would like to go for a running, ping me, I would be happy to beat the street together!

Illustration by Tania Manzanal Cerda

Style Sheet from the IBM-VGA8 font from the Ultimate Oldschool PC Font Pack.