Antonio Faonio

Post Doc Fellow at IMDEA Software

Myself I am a postdoctoral researcher at IMDEA Software Institute, working with prof. Dario Fiore since Jannuary 2017. 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.

Personal Email: afaonio@gmail.com , 0x00af@paranoici.org
Official Email: antonio.faonio@imdea.org
ORCID ID: 0000-0002-7152-6478
My PGP keys
Key IDs :
4835AA19 D20F856C (00af@keybase.io)
642897FE 64A81CD9 (afaonio@gmail.com)
B7751DB1 F9C08B54 (0x00af@paranoici.org)
8B57A5D2 9B6ABB10 (antonio.faonio@imdea.org)

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.

Starting from February 21st, me and Dario Fiore have been teaching a seminar on Foundations of Cryptography.
The course can be officially taken by students of UPM and URJC. More information about the course can be found here .

[+] Publications and preprints:

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

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 ,manuscript manuscript

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. to appear in 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:

I served as an external reviewer for these conferences:
 CCS ('13,'18), CRYPTO('14,'17,'18), FC'18, USENIX'15, ASIACRYPT ('15,'16,'17,'18), TCC ('16-A,'16-B,'17), EUROCRYPT ('16,'18), PKC ('16,'18), AFRICACRYPT '16.

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

I was in the Program Committee of The 2018 IEEE International Conference on Blockchain (Blockchain-2018).

I am always glad to review papers, so if you need just drop me a mail (I am happier if you encrypt and sign it).

[+] Research and CV:

My CV and my Research Statement

[+] Stuff:

You can find me on keybase which is supercool, I got some invitations if you want to have an account there, I am happy to invite you!

I enjoy dancing Lindy Hop, so if we were in the same conference and you wondered to have a couple of swing outs, I would be happy to be your dancing fella. If you don't know what I am talking about watch this.

Illustration by Tania Manzanal Cerda