Antonio Faonio

Post Doc Fellow at Aarhus University

Personal Email: ,
New Official Email:
Old Official Email: (Please do not use this one anymore! Soon it will expire!)
ORCID ID: 0000-0002-7152-6478
My PGP keys
Key IDs :
4835AA19 D20F856C (
642897FE 64A81CD9 (
B7751DB1 F9C08B54 (
8B57A5D2 9B6ABB10 (

I am a postdoctoral researcher at IMDEA Software Institute, working with prof. eDario 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.

[+] Publications and preprints:

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

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

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

I am always glad to review papers, so if you need just drop me a mail (I am happier if you encrypt 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.

Follow a couple of timestamp of sha256sum project.pdf for ongoing projects:
2017-02-14 - Project CNMC-R sha256 a510d6d22e5ba493f8beeea68f16bf3cb1ca97a7c5bcba9e85f437bdf847e980- Mind Bloowing