title: Protocoles avec Sécurité Inconditionnelle issus de Techniques de la Théorie des Codes
text: The challenge lies in adding this cheater detection feature to the original protocol without increasing its complexity significantly. To achieve this, we introduce a carefully-designed dispute control system that allows players to proceed with the execution of the protocol in cases where the original SPDZ protocol 141 has to abort, so that eventually our protocol produces the correct output or malicious players are identified. This allows us to obtain the following. In case no cheating takes place, our protocol is as efficient as the original SPDZ protocol which has no cheater detection. In case cheating does take place, there may be some additional overhead, which is still reasonable in size though, and since the cheater knows he will be caught, this is actually unlikely to occur in typical application scenarios.
  
  142
  
  Samenvatting
  
  Dit proefschrift maakt bijdragen aan vier deelgebieden in de cryptografie, met nadruk op de verbanden met de coderingstheorie (ofwel, de theorie van de foutcorrigerende codes). We maken gebruiken van coderingstheoretische technieken om cryptografische protocollen zowel te analyseren als te construeren met nieuwe en verbeterde eigenschappen. Secret sharing is een belangrijk onderwerp in de moderne cryptografie, en het vormt de grondslag voor veel van de besproken begrippen on deze dissertatie. Een secret-sharingschema heeft als input een geheime waarde en geeft als output n shares. Deze shares hebben de eigenschap dat een kleine deelverzameling ervan geen enkele informatie geeft over de geheime input (privacy), maar dat met een voldoende grote deelverzameling het geheim kan worden achterhaald (reconstructie). Secret sharing heeft talrijke toepassingen in de cryptografie. Bijvoorbeeld, secret sharing met toegevoegde eigenschappen zoals lineariteit en multiplicativiteit vormt een fundamentele bouwsteen voor secure multiparty computation ofwel MPC. Met behulp van MPC kunnen n partijen de functie-waarde f (x1,..., xn ) van een functie f op geheime inputs x1,..., xn correct uitrekenen zonder daarbij de inputs te hoeven uitwisselen; die blijven namelijk geheim. Voorts heeft secret sharing een aantal directe toepassingen. De meest oorspronkelijke daarvan is betrouwbare en veilige gedistribueerde opslag van sensitieve informatie; hierbij geeft secret sharing een oplossing voor het singlepoint-of-failure probleem van traditionele opslag-methoden. Een secret sharing schema kan ook worden gezien als oplossing voor de volgende niet-interactieve variant van perfectly secure message transmission. Stel dat Alice veilig een bericht wil sturen naar Bob en daarvoor beschikking heeft over n communicatiekanalen, en zodat een aanvaller Eve enkele van deze kanalen kan afluisteren dan wel blokkeren. Op basis van secret sharing is het eenvoudig om een methode te geven die Alice in staat stelt om een bericht naar Bob te sturen zonder dat Eve informatie verkrijgt over de inhoud van het bericht. Tevens kan Eve het bericht naar Bob niet blokkeren, ook niet als zij alle communi143 catiekanalen blokkeert waarover ze controle heeft. Het herstellen van data uit onvolledige informatie vormt een overeenkomst tussen secret sharing en coderingstheorie. Het is daarom wellicht niet verwonderlijk dat er tussen deze twee gebieden sprake is van een lang en vruchtbaar samenspel. Bijvoorbeeld, Massey heeft een constructie van secret sharing uit lineaire foutcorrigerende codes voorgesteld en heeft laten zien hoe de eigenschappen van het secret-sharing schema begrepen kunnen worden in termen van de eigenschappen van de onderliggende code. Hieruit volgt bijvoorbeeld het bestaan van secret-sharing schema’s waarin de reconstructie bepaald wordt door de minimum afstand van de code en waarin de privacy bepaald wordt door de minimum afstand van de duale code. Er zijn voorbeelden van goede codes waarvan de duale code tevens goed is, zoals Reed-Solomon codes of random gekozen lineaire codes. Echter, het is thans een open probleem of er goede codes bestaan die een goede duale code hebben en die tevens zeer efficiënte (dat wil zeggen, linear-time) encodeeren decodeer-algoritmen toelaten. Dit probleem wordt omzeild in dit proefschrift door een nieuw verband te leggen tussen secret-sharing en codes, die als resultaat heeft dat de privacy van het cryptografische protocol niet meer afhangt van de duale van de onderliggende code, maar in plaats daarvan bepaald wordt door de rate van de onderliggende code en de parameters van een familie van lineaire universele hash functies. Dit geeft mogelijkheden om het potentieel van de meest recente codes volledig te exploiteren en daarmee verbeterde protocollen te genereren. We lichten dit toe met twee toepassingen. De ene toepassing maakt gebruik van codes waarvan de codering en decodering kan worden berekend in lineaire tijd. Hierdoor is het mogelijk een familie van secret-sharing schema’s te construeren waarbij zowel het delen van de shares als het reconstrueren van geheime data geschiedt in slechts lineaire tijd. De andere toepassing construeert robuuste secret-sharing schema’s met behulp van codes met zogeheten lijstdecodering. Zulke protocollen zijn zelfs – hoewel met een kleine foutkans – in staat het gedeelde geheim te reconstrueren wanneer enkele van de shares incorrect zijn. De familie van protocollen uit deze toepassing optimaliseert de trade-off tussen de hoeveelheid extra data die toegevoegd moet worden aan de shares om robuustheid te behouden en de foutkans van de reconstructie van het gedeelde geheim. Het volgende onderwerp van studie is perfectly secure message transmission (PSMT). In tegenstelling tot de niet-interactieve variant die eerder aangehaald is, wordt nu aangenomen dat Bob ook in staat is om berichten terug naar Alice te sturen over de n bestaande communicatiekanalen. De aanvaller Eve heeft nog steeds t < n van deze kanalen onder controle, en kan daarmee berichten afluisteren en veranderen naar willekeur. Opmerkelijk is dat wederzijdse communicatie de veiligheid verhoogt, aangezien het in dit scenario mogelijk is om 144 perfecte privacy en reconstrueerbaarheid te bemachtigen zolang t < n/2. In het niet-interactieve geval kan dit alleen als t < n/3. In dit proefschrift wordt een nieuw protocol gepresenteerd voor t < n/2 dat twee rondes heeft. Het gebruik van technieken die gebaseerd zijn op zogenaamde syndrome computation maakt een conceptueel simpelere aanpak mogelijk die tevens leidt tot verbeterde efficiëntie, namelijk een multiplicatieve factor n besparing in totale communicatie in het speciale geval van een constante bit-lengte secret. PSMT kan gegeneraliseerd worden naar scenario’s waarin Alice en Bob toegang hebben tot een complexere communicatie infrastructuur. Bijvoorbeeld, in secure network coding zijn ze verbonden door een netwerk dat gemodelleerd wordt door een gerichte, acyclische graaf met een enkele source knoop zonder inkomende takken en een enkele sink knoop zonder uitgaande takken. Alice kan data verzenden via de source en Bob ontvangt data via de sink, waarbij de tussenliggende knopen lineaire transformaties toepassen op de inkomende takken en resultaten uitsturen over de uitgaande takken. Nog steeds wordt aangenomen dat Eve een zeker aantal van de kabels van het netwerk onder haar controle heeft. In eerdere studies wordt normaliter aangenomen dat communicatie in secure network coding maar één richting opgaat. In dit proefschrift stellen wij daarentegen ook interactieve protocollen voor die – analoog aan PSMT – door de communicatie in beide richtingen veilig blijven bij een groter aantal gecontroleerde netwerkkabels. De enige conditie is namelijk dat t < C/2 (vergelijken met t < C/3 in het niet-interactieve geval), waar C een invariant is van de netwerk topologie, de zogeheten connectivity. We beschrijven namelijk twee protocollen, beide aanpassingen van het schema voor PSMT. De eerste heeft twee fasen, terwijl de tweede er drie heeft en aangepast kan worden aan een situatie met meerdere ontvangers. Deze twee protocollen zijn bestand tegen het theoretisch maximale aantal aangedane netwerkkabels en blijven veilig, ongeacht de bewerkingen van de netwerkknooppunten. Tenslotte verleggen we de focus naar secure multi-party computation, wat wordt afgekort naar MPC. Hierbij gaat het over n partijen – ook wel spelers genoemd – die elk een geheime inputwaarde xi hebben. Het doel is om de uitkomst van een zekere functie f (x1,..., xn ) correct te berekenen met deze geheime waarden als input, zodat de spelers hun inputs geheim houden. Het recente werk van Damård et al. beschrijft een protocol dat zelfs met n − 1 kwaadaardige spelers veilig blijft. Dit zogeheten SPDZ-protocol is geroemd vanwege zijn efficiëntie en de mogelijkheid in de praktijk te kunnen worden gebruikt. Dit SPDZ-protocol heeft echter als nadeel dat al één enkele kwaadaardige partij de hele gezamenlijke berekening kan doen mislukken. Dit 145 houdt onder andere in dat de eerlijke partijen genoodzaakt zijn de berekening af te breken en de uitkomst niet hebben, terwijl de kwaadaardige partij wellicht wel deze uitkomst kan leren van de gedeelde informatie. Sterker nog, deze oneerlijke partij kan dit doen zonder dat de andere partijen erachter kunnen komen wie de veroorzaker was. In deze dissertatie wordt het SPDZ-protocol verbeterd zodat er de mogelijkheid bestaat om de kwaadaardige partij, die de berekening doet afbreken, te kunnen identificeren. Bijgevolg zullen partijen niet de drang hebben vals te spelen als zij dit verbeterde protocol gebruiken. Een kwaadwillige kan namelijk worden geı̈dentificeerd en vervolgens uit de groep gezet worden. De hoofduitdaging was om identificatie van kwaadwilligen aan het SPDZprotocol toe te voegen, zonder dat de algehele complexiteit significant verhoogd wordt. Om dit te bewerkstelligen, voeren we een nauwkeurig ontworpen dispute control systeem in dat de partijen in staat stelt om de executie van het protocol doorgang te laten vinden in gevallen waarin het oorspronkelijke SPDZ protocol een “abort” zou dienen te declareren, met de eigenschap dat de correcte output wordt gegenereerd of dat in ieder geval malicieuze spelers geı̈dentificeerd worden. Voorts, de protocol die wordt beschreven in deze dissertatie is – mits het protocol correct wordt uitgevoerd – even efficiënt als het SPDZ-protocol. Wanneer er wél sprake is van valsspelerij, kan het protocol een relatief redelijk kleine vertraging oplopen. Omdat kwaadwilligen kunnen worden opgespoord met dit protocol, is het echter niet waarschijnlijk dat deze vertraging werkelijk voorkomt in de praktijk.
  
  146 Résumé
  
  Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d’abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la cryptographie actuelle. Dans la variante à laquelle on s’intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu’Ève n’apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu’elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d’informations partielles), ce n’est pas surprenant qu’ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l’étude d’un schéma de partage de secret à partir d’un code correcteur. L’inconvénient de cette analyse est que la confidentialité d’un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu’il pourrait ne pas être possible d’obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les 147 deux domaines, telle que la confidentialité d’un schéma de partage de secrets n’est plus contrôlée par le dual du code sous-jacent. Cela nous permet d’exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas ; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s’effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu’à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c’est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d’erreur. La famille que nous présentons optimise le compromis structurel entre les données additionnelles qui doivent être ajoutées aux parts pour obtenir la robustesse et la probabilité d’une erreur dans la reconstruction, atteignant la meilleur valeur possible. Une variante interactive du partage de secret est donnée par la transmission parfaitement sécurisée de message, connue sous son acronyme anglais PSMT pour perfectly secure message transmission. On imagine maintenant que Bob aussi soit autorisé à envoyer des messages à Alice sur plusieurs canaux, et qu’Ève soit capable de lire les données envoyées sur les canaux qu’elle contrôle aussi que de les remplacer par des élément de son choix. La communication à deux sens améliore la sécurité : il est possible d’obtenir confidentialité et exactitude parfaites tant qu’Ève contrôle moins de la moitié des canaux, tandis que dans le cas non interactif, ceci peut être atteint seulement si elle contrôle moins d’un tiers des canaux. On présente dans cette thèse un nouveau protocole qui marche en deux étapes et pour le maximum possible de canaux corrompus ; son importance pour le sujet est due à deux aspects. Premièrement, son efficacité est améliorée par rapport aux constructions précédemment connues, spécialement quand le secret à transmettre ne consiste qu’en un bit unique. Deuxièmement, il se différencie des travaux précédents en évitant les lourdes méthodes classiques et en utilisant au contraire des techniques plus simples issues de la théorie des codes. La PSMT se peut généraliser à des scénarios de communication plus complexes. Par exemple, dans le codage sécurisé de réseau ou secure network coding Alice est connectée avec Bob par une infrastructure de communication plus compliquée, qui consiste en un réseau de câbles et de nœuds qui transforment et transmettent les données reçues ; on suppose toujours qu’Ève contrôle (c’est-à-dire, écoute et manipule) certains câbles dans le réseau. Seulement la communication unilatérale a été étudiée auparavant dans le 148 codage sécurisé de réseau. On contribue au sujet en présentant des protocoles interactifs ; comme dans les scénarios précédents, cela nous permet d’obtenir des procédés sûrs pour un plus grand nombre de câbles corrompus. Plus précisément, on présente deux protocoles adaptés de notre construction de PSMT ; le premier marche en deux étapes, tandis que le seconde marche en trois, mais peut être adapté à un scénario où plusieurs destinataires (ou “Bobs”) sont présents. Nos deux protocoles tolèrent le plus grand nombre possible de câbles corrompus, et restent sûrs quelle que soit la façon dont les nœuds du réseau transforment les données reçues. Finalement, on se concentre sur le calcul sécurisé multi-parties, ou MPC de son nom en anglais. Dans le MPC, n utilisateurs détiennent des entrées privées x1,..., xn respectivement et veulent calculer la valeur f (x1,..., xn ) d’une fonction f sur leurs entrées, tout en garantissant l’exactitude du calcul aussi que la confidentialité des données d’entrée. Une construction récente est le protocole SPDZ réalisé par Damgård et al., remarquable par son exécution très rapide et ses intéressantes possibilités d’implémentation. Un inconvénient du protocole SPDZ est sa vulnérabilité à un attaque par déni de service: même un seul utilisateur malveillant peut causer un échec du calcul, ce qui veut dire que les utilisateur honnêtes doivent abandonner le calcul sans en apprendre le résultat, tandis que l’utilisateur malveillant pourrait l’apprendre. Qui plus est, un tel utilisateur malveillant peut monter ce type d’attaques sans qu’il puisse être identifie comme malhonnête. On améliore le protocole SPDZ pour obtenir l’identification des utilisateurs malhonnêtes : un tel utilisateur qui fait intentionnellement échouer le protocole sera identifié comme malveillant. Par conséquent, dans des scénarios classiques du monde réel, les utilisateurs auront peu de motivation pour tricher, et si quelqu’un triche malgré tout, l’utilisateur malhonnête peut être identifié et expulsé du procédé et le calcul exécuté une autre fois, jusqu’à ce qu’il réussisse. Le défi est d’ajouter cette fonctionnalité de détection des tricheurs au protocole originel sans augmenter significativement sa complexité. Si personne ne triche, notre nouveau protocole est aussi efficace que le protocole SPDZ originel qui ne possède pas de détection de tricheurs. En revanche, si quelqu’un triche, il est possible que le coût augmente – mais de manière raisonnable, et comme le tricheur sait qu’il sera attrapé, il est par ailleurs improbable que cela se passe dans des typiques scénarios réels.
  
  149 150
  
  Acknowledgments First of all, I would like to thank my advisors Ronald Cramer, Serge Fehr and Gilles Zémor for their guidance throughout this PhD. Ronald constantly shared his great knowledge of cryptography and his many new ideas with me, while pushing me to look for the mathematics underlying cryptographic topics. Serge’s constant presence and help has been invaluable at every stage of my doctorate; his steady flow of research ideas and feedback has been fundamental for the development of my scientific skills. And finally, thanks to Gilles for the long and fruitful discussions that gave me new perspectives on the interplay between Coding Theory and Cryptography; moreover, his relentless help in every sort of practical matters has been fundamental throughout my doctorate. I am also grateful to the members of the Doctorate Committee for taking the time to read my thesis; a special thank to Yuval Ishai and Berry Schoenmakers for agreeing to write a report according to Bordeaux regulations. I would also like to thank the friends and colleagues at CWI, both within and outside the Crypto group, for the discussions on math (or crypto, or coding) and for the great moments we had together; and of course, many thanks to all my friends, in the Netherlands, in Bordeaux, back in Italy and in the many countries united by the Erasmus program, for their support and for all the fun times we had. Last but not least: grazie a tutta la mia famiglia, per essere sempre stata presente e avermi sostenuto (a volte anche con un oceano in mezzo) durante gli anni di questo dottorato.
  
  151 152 Curriculum
  
  Vitae
  
  Gabriele Spini was born in Sondrio, Italy, on June 19, 1989. He grew up in the nearby town of Morbegno, and obtained his high school diploma from Liceo Scientifico P. Nervi in 2008. He then started his bachelor studies in Mathematics at the University of Milan, Italy (Università degli Studi di Milano), graduating cum laude in 2011. Subsequently, he was accepted in the Algant-Master program, spending the first year (2011-2012) at the University of Milan, and the second year (20122013) at the University of Bordeaux, France – then Université de Bordeaux 1. Gabriele obtained his master’s degree from both universities in 2013; his thesis, with title “A study of quantum error-correcting codes derived from platonic tilings”, was written under the supervision of Gilles Zémor. In 2013, Gabriele was awarded an Algant-Doc PhD position at Leiden University and the University of Bordeaux, under the supervision of Ronald Cramer, Serge Fehr and Gilles Zémor; most of his research was carried out at the Centrum Wiskunde & Informatica (CWI) of Amsterdam, the Netherlands. In 2017, he obtained a post-doc position within the Cryptology research group of CWI, Amsterdam.
  
  Publications I. G. Spini and G. Zémor, Perfectly Secure Message Transmission in Two Rounds, Proceedings of the 14th IACR Theory of Cryptography Conference (TCC), Beijing, PRC, Springer LNCS Volume 9985, pages 286–304, October 2016. II. G. Spini and S. Fehr, Cheater Detection in SPDZ Multiparty Computation, Proceedings of the 9th International Conference on Information153 Theoretic Security (ICITS), Tacoma, WA, United States, Springer LNCS Volume 10015, pages 151–176, August 2016 III. G. Spini and G. Zémor, Universally Secure Network Coding with Feedback, Proceedings of the IEEE International Symposium on Information Theory (ISIT), Barcelona, Spain, pages 2339–2343, July 2016. IV. R. Cramer, I. B. Damgård, N. Döttling, S. Fehr and G. Spini, Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions, Proceedings of the 34th Annual IACR EUROCRYPT, Sofia, Bulgaria, Springer LNCS, Volume 9057, Part II, pages 313–336, April 2015. 154.