Title: “Be more and be merry: enhancing data and user authentication in collaborative settings”

Advisors: Andrei Sabelfeld (Chalmers) and Dario Fiore (iMdea)

Opponent: Bart Preneel

Committee members: Claudio Orlandi, Damien Vergnaud, Martin Hell.

[Download pdf version of the thesis], [preliminary slides]

DATE: September 7th, 2018

TIME: from 10.00am

LOCATION: room ED (5th floor) EDIT Building (easy entrance from Hörsalsvägen 11), Chalmers University, Johanneberg Campus, Gothenburg, Sweden. [how to reach the room]

List of appended papers included in the thesis

1. Multi-Key Homomorphic Authenticators (AsiaCrypt 2016)

Authors: D.Fiore, A. Mitrokotsa, L. Nizzardo, E. Pagnin. Full version

Abstract. Homomorphic authenticators enable a client to authenticate a large dataset, outsource it along with authenticators to an untrusted server in such a way that, at any later point in time, the client can ask the server to compute an arbitrary function on the dataset. The server performs the computation on the chosen data as well as on the corresponding authenticators, and returns to the client the answer value together with a short authenticator vouching for the correctness of the given output for the required function and the chosen dataset. In this paper, we extend this primitive so that it not only works on data authenticated by a single user, but rather handels secure computation on authenticators produced with different secret keys. As an application scenario, one can consider distributed networks of sensors. For instance, each sensor is in charge of collecting data about air pollution in a certain area of a city, it sends its data to a Cloud server, and then a central control unit asks the Cloud to compute on the data collected by the sensors (e.g., to obtain the average value of air pollution in a large area).

2. Matrioska: A Compiler for Multi-Key Homomorphic Signatures (to appear at SCN 2018)

Authors: D.Fiore, E. Pagnin.

Abstract: Abstract. Multi-Key Homomorphic Signatures (MK-HS) enable clients in a system to sign and upload messages to an untrusted server. At any later point in time, the server can perform a computation C on data provided by t different clients, and return the output y and a short signature vouching for the correctness of y as the output of the function C on the signed data. Interestingly, MK-HS enable verifiers to check the validity of the signature using solely the public keys of the signers whose messages were used in the computation. Moreover, the signatures are succinct, namely their size depends at most linearly in the number of clients, and only logarithmically in the total number of inputs of C. Existing MK-HS are constructed based either on standard assumptions over lattices (Fiore et al., ASIACRYPT’16), or on non-falsifiable assumptions (SNARKs) (Lai et al., ePrint’16). In this paper, we investigate connections between single-key and multi-key homomorphic signatures. We propose a generic compiler, called Matrioska, which turns any (sufficiently expressive) single-key homomorphic signature scheme into a multi-key scheme. Matrioska establishes a formal connection between these two primitives and is the first alternative to the only known construction under standard falsifiable assumptions. Our result relies on a novel technique that exploits the homomorphic property of a single-key HS scheme to compress an arbitrary number of signatures from t different users into only t signatures.

3. Anonymous Server-Aided Verification of Signatures (LatinCrypt 2017)

Authors: E. Pagnin, A. Mitrokotsa, K. Tanaka. Full version

Abstract. Server-Aided Verification (SAV) is a method that can be employed to speed up the process of verifying signatures by letting the verifier outsource part of its computation load to a third party. Achieving fast and reliable verification under the presence of an untrusted server is an attractive goal in cloud computing and internet of things scenarios. In this paper, we describe a simple framework for SAV where the interaction between a verifier and an untrusted server happens via a single-round protocol. We propose a security model for SAV that refines existing ones and includes the new notions of SAV-anonymity and extended unforgeability. In addition, we apply our definitional framework to provide the first generic transformation from any signature scheme to a single-round SAV scheme that incorporates verifiable computation. Our compiler identifies two independent ways to achieve SAV-anonymity: computationally, through the privacy of the verifiable computation scheme, or unconditionally, through the adaptibility of the signature scheme. Finally, we define three novel instantiations of SAV schemes obtained through our compiler. Compared to previous works, our proposals are the only ones which simultaneously achieve existential unforgeability and soundness against collusion.

4. Two-hop Distance-Bounding Protocols: Keep your Friends Close (IEEE Transactions on Mobile Computing 2018)

Authors: A. Yang, E. Pagnin, A. Mitrokotsa, G. Hancke, D. Wong. Full version

Abstract. Distance-bounding (DB) protocols are cross-layer authentication protocols that are based on the round-trip-time of challenge-response exchanges and can be employed to guarantee physical proximity and combat relay attacks. However, traditional DB protocols rely on the assumption that the prover is in the communication range of the verifier, which might not be the case in multiple access control scenarios in ubiquitous computing environments or when we need to verify the proximity of our two-hop neighbour in an ad-hoc network. In this paper, we extend traditional DB protocols to a two-hop setting i.e. when the prover is out of the communication range of the verifier and thus, they both need to rely on an untrusted in-between entity to verify proximity. We present a formal framework that captures the most representative classes of existing DB protocols and provide a general method to extend traditional DB protocols to the two-hop case. We analyse the security of two-hop DB protocols and identify connections with the security issues of the corresponding one-hop case. Finally, we demonstrate the correctness of our security analysis and the efficiency of our model by transforming five existing DB protocols to the two-hop setting and we evaluate their performance with simulations.

5. On the Leakage of Information in Biometric Authentication (Indocrypt 2014)

Authors: E. Pagnin, C. Dimitrakakis, A. Abidin, A. Mitrokotsa. Full version

Abstract. In biometric authentication protocols, a user is authenticated or granted access to a service if her fresh biometric trait matches the reference biometric template stored on the service provider. This matching process is usually based on a suitable distance which measures the similarities between the two biometric templates. In this paper, we prove that, when the matching process is performed using a specific family of distances (which includes distances such as the Hamming and the Euclidean distance), then information about the reference template is leaked. This leakage of information enables a hill-climbing attack that, given a sample that matches the template, could lead to the full recovery of the biometric template (i.e. centre search attack) even if it is stored encrypted. We formalise this “leakage of information” in a mathematical framework and we prove that centre search attacks are feasible for any biometric template defined in Z_q^n (q >= 2) after a number of authentication attempts linear in n. Furthermore, we investigate brute force attacks to find a biometric template that matches a reference template, and hence can be used to run a centre search attack. We do this in the binary case and identify connections with the set-covering problem and sampling without replacement.

6. Revisiting Yasuda et al.’s Biometric Authentication Protocol: Are you Private Enough? (CANS 2017)

Authors: E. Pagnin, J. Liu, A. Mitrokotsa

Abstract. Biometric Authentication Protocols (BAPs) have increasingly been employed to guarantee reliable access control to places and services. However, it is well-known that biometric traits contain sensitive information of individuals and if compromised could lead to serious security and privacy breaches. Yasuda et al. [23] proposed a distributed privacy-preserving BAP which Abidin et al. [1] have shown to be vulnerable to biometric template recovery attacks under the presence of a malicious computational server. In this paper, we fix the weaknesses of Yasuda et al.’s BAP and present a detailed instantiation of a distributed privacy-preserving BAP which is resilient against the attack presented in [1]. Our solution employs Backes et al.’s [4] verifiable computation scheme to limit the possible misbehaviours of a malicious computational server.