No description available.

This doctoral dissertation presents contributions advancing the state-of-the-art of secure two-party computation (S2PC) — a cryptographic primitive that allows two mutually distrustful parties, with respective private inputs, to evaluate a function of their combined input, while ensuring privacy of inputs and outputs and integrity of the computation, externally indistinguishable from an interaction mediated by a trusted party. The dissertation shows that S2PC can be made more practical by means of innovative cryptographic techniques, namely by engineered use of commitment schemes with special properties, enabling more efficient protocols, with provable security and applicable to make systems more dependable. This is one further step toward establishing S2PC as a practical tool for privacy-preserving applications. The main technical contribution is a new protocol for S2PC of Boolean circuits, based on an innovative technique called forge-and-lose.1 Building on top of a traditional cut-and-choose of garbled circuits (cryptographic versions of Boolean circuits), the protocol improves efficiency by reducing by a factor of approximately 3 the needed number of garbled circuits. This significantly reduces a major communication component of S2PC with malicious parties, for circuits of practical size. The protocol achieves simulatable S2PC-with-commitments, producing random commitments of the circuit input and output bits of both parties. The commitments also enable direct linkage of several S2PCs in a malicious adversarial setting. As second result, the dissertation describes an improvement to the efficiency of one of the needed sub-protocols: simulatable two-party coin-flipping.1 The sub-protocol is based on a new universally composable commitment scheme that for bit-strings of increasing size can achieve an asymptotic communication-complexity rate arbitrarily close to 1. The dissertation then discusses how S2PC-with-commitments can enable in brokered identification systems a difficult-to-achieve privacy property — a kind of unlinkability.1 This mitigates a vector of potential mass surveillance by an online central entity (a hub), which is otherwise empowered in systems being developed at nation scale for authentication of citizens. When the hub mediates between identity providers and service providers the authentication of users, an adequate S2PC (e.g., of a block-cipher) can prevent the hub from learning user pseudonyms that would allow linking transactions of the same user across different services providers. 1 Parts of these contributions were previously presented at ASIACRYPT 2013, PETS 2015 and PKC 2016.

We investigate weak coin flipping, a fundamental cryptographic primitive where two distrustful parties need to remotely establish a shared random bit. A cheating party can try to bias the output bit towards a preferred value. For weak coin flipping the parties have known opposite preferred values. By a weak coin flipping protocol with bias ϵ we mean that neither player can force the outcome towards their preferred value with probability more than 1/2+ϵ. While it is known that classically, ϵ=1/2 (the worst possible), Mochon showed in 2007 that quantumly, weak coin flipping can be performed with arbitrarily small bias (near perfect). His non-constructive proof used the so-called point game formalism—a series of equivalent reductions which were introduced by Kitaev to study coin-flipping. He constructed point games with bias ϵ(k)=1/(4k+2) to prove the existence. The best known explicit protocol, however, had bias approaching ϵ(1)=1/6 (also due to Mochon, 2005). In the present work, we try to make the non-constructive part of the proof constructive, to wit, we make three main contributions towards the conversion of point-games into explicit protocols. First, we propose a framework—TIPG-to-Explicit-protocol Framework (TEF)—which simplifies the task of constructing explicit protocols. We use this framework to construct a protocol with bias ϵ(2)=1/10. We then give the exact formulae for the unitaries corresponding to the point-games due to Mochon, allowing us to describe (almost) perfect coin flipping protocols analytically, i.e. with bias ϵ(k) for arbitrarily large k. Finally, we introduce an algorithm we call the Elliptic Monotone Align (EMA) algorithm. This algorithm, together with TEF, lets us convert any point-game into an explicit protocol numerically. We conclude by giving another analytic construction of unitaries for Mochon's games using the ellipsoid picture introduced for the EMA algorithm. / Nous étudions le weak coin flipping, une primitive cryptographique fondamentale où deux parties méfiantes doivent établir à distance un bit aléatoire partagé. Un tricheur peut essayer de biaiser le bit de sortie vers une valeur préférée. Pour le weak coin flipping, les parties ont des valeurs préférées opposées. Par un protocole de weak coin flipping avec biais ϵ, nous entendons qu'aucun des deux joueurs ne peut forcer le résultat vers sa valeur préférée avec une probabilité supérieure à 1/2+ϵ. Alors que l'on sait que classiquement, ϵ=1/2 (le pire possible), Mochon a montré en 2007 qu'un weak coin flipping quantique peut être effectué avec un biais arbitrairement faible (presque parfait). Sa preuve non constructive a utilisé le formalisme dit du jeu de points (point games)—une série de réductions équivalentes qui ont été introduites par Kitaev pour étudier le coin flipping. Il a construit des jeux de points avec un biais ϵ(k)=1/(4k+2) pour en prouver l'existence. Le protocole explicite le plus connu, cependant, avait un biais approchant ϵ(1)=1/6 (également dû à Mochon, 2005). Dans le présent travail, nous essayons de rendre la partie non constructive de la preuve constructive, c'est-à-dire que nous apportons trois contributions principales à la conversion des jeux de points en protocoles explicites. Premièrement, nous proposons un cadre—TIPG-to-Explicit-protocol Framework (TEF)—qui simplifie la tâche de construction de protocoles explicites. Nous utilisons ce cadre pour construire un protocole avec un biais ϵ(2)=1/10. Nous donnons ensuite les formules exactes des unitaires correspondant aux jeux de points dus à Mochon, ce qui nous permet de décrire analytiquement des protocoles de coin flipping (presque) parfaits, c'est-à-dire avec un biais ϵ(k) pour un k arbitrairement grand. Enfin, nous introduisons un algorithme que nous appelons le Elliptic Monotone Align (EMA) Algorithm. Cet algorithme, associé à TEF, nous permet de convertir numériquement tout jeu de points en un protocole explicite. Nous concluons en donnant une autre construction analytique des unitaires pour les jeux de Mochon en utilisant l'image ellipsoïdale introduite pour l'algorithme EMA. / Doctorat en Sciences de l'ingénieur et technologie / info:eu-repo/semantics/nonPublished

<div>Multiparty computation refers to a scenario in which multiple distinct yet connected parties aim to jointly compute a functionality. Over recent decades, with the rapid spread of the internet and digital technologies, multiparty computation has become an increasingly important topic. In addition to the integrity of computation in such scenarios, it is essential to ensure that the privacy of sensitive information is not violated. Thus, secure multiparty computation aims to provide sound approaches for the joint computation of desired functionalities in a secure manner: Not only must the integrity of computation be guaranteed, but also each party must not learn anything about the other parties' private data. In other words, each party learns no more than what can be inferred from its own input and its prescribed output.</div><div><br></div><div> This thesis considers secure two-party computation over arithmetic circuits based on additive secret sharing. In particular, we focus on efficient and secure solutions for fundamental functionalities that depend on the equality of private comparands. The first direction we take is providing efficient protocols for two major problems of interest. Specifically, we give novel and efficient solutions for <i>private equality testing</i> and multiple variants of <i>secure wildcard pattern matching</i> over any arbitrary finite alphabet. These problems are of vital importance: Private equality testing is a basic building block in many secure multiparty protocols; and, secure pattern matching is frequently used in various data-sensitive domains, including (but not limited to) private information retrieval and healthcare-related data analysis. The second direction we take towards a performance improvement in equality-based secure two-party computation is via introducing a generic functionality-independent secure preprocessing that results in an overall computation and communication cost reduction for any subsequent protocol. We achieve this by providing the first precise functionality formulation and secure protocols for replacing original inputs with much smaller inputs such that this replacement neither changes the outcome of subsequent computations nor violates the privacy of sensitive inputs. Moreover, our input-size reduction opens the door to a new approach for efficiently solving Private Set Intersection. The protocols we give in this thesis are typically secure in the semi-honest adversarial threat model.</div>

Private set intersection(PSI) is a two party protocol where both parties possess a private set and at the end of the protocol, one party (client) learns the intersection while other party (server) learns nothing. Motivated by some interesting practical applications, several provably secure and efficient PSI protocols have appeared in the literature in recent past. Some of the proposed solutions are secure in the honest-but-curious (HbC) model while the others are secure in the (stronger) malicious model. Security in the latter is traditionally achieved by following the classical approach of attaching a zero knowledge proof of knowledge (ZKPoK) (and/or using the so-called cut-and-choose technique). These approaches prevent the parties from deviating from normal protocol execution, albeit with significant computational overhead and increased complexity in the security argument, which includes incase of ZKPoK, knowledge extraction through rewinding. We critically investigate a subset of the existing protocols. Our study reveals some interesting points about the so-called provable security guarantee of some of the proposed solutions. Surprisingly, we point out some gaps in the security argument of several protocols. We also discuss an attack on a protocol when executed multiple times between the same client and server. The attack, in fact, indicates some limitation in the existing security definition of PSI. On the positive side, we show how to correct the security argument for the above mentioned protocols and show that in the HbC model the security can be based on some standard computational assumption like RSA and Gap Diffie-Hellman problem. For a protocol, we give improved version of that protocol and prove security in the HbC model under standard computational assumption. For the malicious model, we construct two PSI protocols using deterministic blind signatures i.e., Boldyreva’s blind signature and Chaum’s blind signature, which do not involve ZKPoK or cut-and-choose technique. Chaum’s blind signature gives a new protocol in the RSA setting and Boldyreva’s blind signature gives protocol in gap Diffie-Hellman setting which is quite similar to an existing protocol but it is efficient and does not involve ZKPoK.