Cryptography allows us to do magical things ranging from private communication over a public channel to securely evaluating functions among distrusting parties. For the real-world implementation of these tasks, efficiency is usually one of the most desirable objectives. In this work, we advance our understanding of efficient cryptographic constructions on several fronts.<div><br></div><div>Non-malleable codes are a natural generalization of error-correcting codes. It provides a weaker yet meaningful security guarantee when the adversary may tamper with the codeword such that error-correcting is impossible. Intuitively, it guarantees that the tampered codeword either encodes the original message or an unrelated one. This line of research aims to construct non-malleable codes with a high rate against sophisticated tampering families. In this work, we present two results. The first one is an explicit rate1 construction against all tampering functions with a small locality. Second, we present a rate-1/3 construction for three-split-state tampering and two-lookahead tampering.</div><div><br></div><div>In multiparty computation, fair computation asks for the most robust security, namely, guaranteed output delivery. That is, either all parties receive the output of the protocol, or no party does. By relying on oblivious transfer, we know how to construct MPC protocols with optimal fairness. For a long time, however, we do not know if one can base optimal fair protocol on weaker assumptions such as one-way functions. Typically, symmetric-key primitives (e.g., one-way functions) are much faster than public-key primitives (e.g., oblivious transfer). Hence, understanding whether one-way functions enable optimal fair protocols has a significant impact on the efficiency of such protocols. This work shows that it is impossible to construct optimal fair protocols with only black-box uses one-way functions. We also rule out constructions based on public-key encryptions and f-hybrids, where f is any incomplete function.</div><div><br></div><div>Collective coin-tossing considers a coin-tossing protocol among n parties. A Byzantine adversary may adaptively corrupt parties to bias the output of the protocol. The security ε is defined as how much the adversary can change the expected output of the protocol. In this work, we consider the setting where an adversary corrupts at most one party. 10 Given a target security ε, we wish to understand the minimum number of parties n required to achieve ε-security. In this work, we prove a tight bound on the optimal security. In particular, we show that the insecurity of the well-known threshold protocol is at most two times the optimal achievable security. </div>

No description available.

Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.<p><p>Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification.<p><p>La première primitive est la "mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il est possible d'avoir une sécurité lorsque les deux parties sont soumises à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opérations gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien.<p><p>Nous examinons ensuite une primitive cryptographique plus faible, le "tirage faible à pile ou face", dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.<p><p>La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement qu'en effectuant des requêtes sur chacune des variables de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique.<p><p>Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes.<p><p>Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessitent le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs.<p><p>Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème Index-Erasure, un problème de génération d'état quantique lié au célèbre problème Isomorphisme-de-Graphes. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

No description available.