<p>Fully homomorphic encryption allows computations to be made on encrypted data without decryption, while preserving data integrity. This feature is desirable in a variety of applications such as banking, search engine and database querying, and some cloud computing services. Despite not knowing the plaintext content of the data, a remote server performing the computation would still be aware of the functions being applied to the data. To address the issue, this thesis proposes a method of encrypting circuits and executing encrypted instructions, by combining fully homomorphic encryption and digital logic theory. We use the classic RISC Archtecture as a foundation of our work, and the result of our algorithm is essentially an encrypted programming language, where a remote server is capable of executing program code that was written and encrypted by a local client.</p> / Master of Science (MS)

Yes / With the advent of Wireless Sensor Networks (WSN) and its immense popularity in a wide range of applications, security has been a major concern for these resource-constraint systems. Alongside security, WSNs are currently being integrated with existing technologies such as the Internet, satellite, Wi-Max, Wi-Fi, etc. in order to transmit data over long distances and hand-over network load to more powerful devices. With the focus currently being on the integration of WSNs with existing technologies, security becomes a major concern. The main security requirement for WSN-integrated networks is providing end-to-end security along with the implementation of in-processing techniques of data aggregation. This can be achieved with the implementation of Homomorphic encryption schemes which prove to be computationally inexpensive since they have considerable overheads. This paper addresses the ID-issue of the commonly used Castelluccia Mykletun Tsudik (CMT) [12] homomorphic scheme by proposing an ID slotting mechanism which carries information pertaining to the security keys responsible for the encryption of individual sensor data. The proposed scheme proves to be 93.5% lighter in terms of induced overheads and 11.86% more energy efficient along with providing efficient WSN scalability compared to the existing scheme. The paper provides analytical results comparing the proposed scheme with the existing scheme thus justifying that the modification to the existing scheme can prove highly efficient for resource-constrained WSNs.

Nachhaltige und ethisch vertretbare Beschaffung und Produktion gehören zu den großen Herausforderungen, die aus dem rasanten Klimawandel und der wachsenden Weltbevölkerung resultieren. Die Erneuerbare-Energien-Richtlinie II der EU und das deutsche Lieferkettensorgfaltspflichtengesetz sind nur zwei Beispiele für die Vielzahl von Gesetzen und Vorschriften, die Standards für nachhaltige und ethisch vertretbare Beschaffung und Produktion vorgeben. Sie implizieren einen Bedarf an Transparenz, Rückverfolgbarkeit und Verifizierbarkeit von Lieferketten und Transaktionen. Öffentliche Verifikationen von Transaktionen entlang von Lieferketten ermöglichen es Dritten, die Einhaltung von Standards und Richtlinien und den Wahrheitsgehalt von Nachhaltigkeitsversprechen zu überprüfen. Folglich kann die öffentliche Überprüfbarkeit Kunden, öffentlichen Stellen und Nichtregierungsorganisationen dabei helfen, Verstöße und Betrug in Lieferketten aufzudecken. Dies wiederum kann dazu beitragen, den Druck zur Einhaltung geltender Standards und Vorschriften zu erhöhen. Transaktionen in Lieferketten basieren oft auf vertraulichen Informationen, wie beispielsweise Mengen und Preise. Die Transparenz derartiger Daten könnte auf Geschäftsgeheimnisse schließen lassen, was direkten Einfluss auf die Wettbewerbsvorteile der beteiligten Firmen hätte. Die Vereinbarkeit von Transparenz und Vertraulichkeit scheint jedoch auf den ersten Blick widersprüchlich zu sein. Diese Dissertation stellt sich der Herausforderung, die öffentliche Verifizierbarkeit von Transaktionen in Lieferketten unter Wahrung der Vertraulichkeit zu ermöglichen. Ausgehend von zwei Fallbeispielen für Lieferketten-Verifikationen werden zunächst Anforderungen an Lösungen untersucht und fünf Forschungsfragen abgeleitet. Anschließend wird eine universelle Lösung entworfen, welche Transparenz und Vertraulichkeit in Einklang bringt. Das vorgestellte Systemmodell ermöglicht sichere öffentliche Verifikationen durch den Einsatz von Fully Homomorphic Encryption (FHE) und Proxy Re-Encryption (PRE). Um die Eignung des Systemmodells für eine Vielzahl realer Szenarien zu verdeutlichen, werden in dieser Dissertation Protokolle für verschiedene Verifikationsfunktionen entworfen. Dies umfasst die Verifikation von Bilanzen, motiviert durch den Handel mit nachhaltigem Palmöl, sowie die Verifikation von Verhältnissen, veranschaulicht durch die Verarbeitung verschiedener Arten von Kobalt. Durch theoretische und empirische Untersuchungen wird nachgewiesen, dass die Protokolle sichere öffentliche Verifikationen für realitätsnahe Szenarien in praktikabler Zeit ermöglichen. Im Weiteren werden die Sicherheitseigenschaften und -implikationen des vorgeschlagenen Systemmodells und der Protokolle untersucht. Dies beinhaltet eine formale Analyse des Risikos, vertrauliche Informationen im Falle wiederholter, gleicher Verifikationen preiszugeben. Aufgrund der Anfälligkeit gegenüber derartigen Angriffen beim Verwenden probabilistischer Output Obfuscation, wird das Paradigma der Data-Dependent Deterministic Obfuscation (D3O) vorgestellt. D3O ist ein universelles Konzept und damit unabhängig vom Anwendungsfall der Lieferketten-Verifikation. Daher kann es in einer Vielzahl weiterer Protokolle für sichere Berechnungen eingesetzt werden, um das Abfließen vertraulicher Informationen zu reduzieren. / Sustainable and ethical sourcing and production are major challenges that arise from rapid climate change and our growing world population. The EU's Renewable Energy Directive II and the German Supply Chain Act are just two examples of the multitude of laws and regulations that define standards for sustainable and ethical sourcing and production. They imply a need for supply chain transparency, traceability, and verification. Public verification of supply chain transactions gives any third-party verifier the chance to evaluate compliance and the correctness of claims based on supply chain transaction details. Therefore, public verification can help customers, buyers, regulators, and non-governmental organizations uncover non-compliance and fraud committed by supply chain actors. This, in turn, can help increase the pressure to comply with applicable standards and regulations. Supply chain transactions often involve confidential data like amounts or prices. Transparency of such data could leak trade secrets and affect companies' competitive advantages. However, reconciling transparency with confidentiality seems contradictory at first glance. This thesis takes up the challenge of enabling privacy-preserving public verification of confidential supply chain transactions. Given two exemplary real-world use cases for supply chain verification, the thesis first investigates requirements for valid solutions and infers five research questions. It then designs a universal solution that combines transparency with confidentiality. The proposed system model achieves privacy-preserving public verification by employing the cryptographic techniques of fully homomorphic encryption (FHE) and proxy re-encryption (PRE). To demonstrate the suitability of the system model for a large variety of lifelike supply chain verification scenarios, the thesis designs privacy-preserving protocols for different verification functions. This includes the verification of balances, using the trade in sustainable palm oil as an example, as well as the verification of ratios, motivated by different forms of cobalt sourcing. These protocols are evaluated both theoretically and empirically. Through extensive empirical evaluation, the proposed protocols prove to enable privacy-preserving public verification for the mentioned supply chain scenarios in practical time. Additionally, this thesis investigates the security implications of the proposed system model and protocols and formally analyzes the risk of leaking information through repeated similar verifications. Based on the identified vulnerability to such attacks in the case of probabilistically obfuscated protocol outputs, the thesis introduces and investigates the paradigm of data-dependent deterministic obfuscation (D3O). D3O is a universal concept that is independent of the field of supply chain verification. It can reduce the leakage of confidential information in a large class of privacy-preserving protocols.

In the Master’s thesis were described privacy protection problems while using cloud technologies. Some of the problems can be solved with help of homomorphic encryption, data splitting or searchable encryption. These techniques were described and compared by provided security, privacy protection and efficiency. The data splitting technique was chosen and implemented in the C language. Afterwards a performance of the implemented solution was compared to AES encryption/decryption performance. An application for secured data storing in cloud was designed and implemented. This application is using the implemented data splitting technique and third-party application CloudCross. The designed application provides command line interface (CLI) and graphical user interface (GUI). GUI extends the capabilities of CLI with an ability to register cloud and with an autodetection of registered clouds. The process of uploading/downloading the data to/from cloud storage is transparent and it does not overload the user with technical details of used data splitting technique.

L’avènement de l’ère digitale a changé la façon dont les individus communiquent à travers le monde, et a amené de nouvelles problématiques en terme de vie privée. La notion d’anonymat la plus répandue pour les communications sur Internet consiste à empêcher tout acteur du réseau de connaître à la fois l’expéditeur d’un message et son destinataire. Bien que ce niveau de protection soit adéquat pour l’utilisateur d’Internet moyen, il est insuffisant lorsqu’un individu peut être condamné pour le simple envoi de documents à une tierce partie. C’est le cas en particulier des lanceurs d’alerte, prenant des risques personnels pour informer le public de pratiques illégales ou antidémocratiques menées par de grandes organisations. Dans cette thèse, nous envisageons un niveau d’anonymat plus fort, où l’objectif est de dissimuler le fait même qu’un utilisateur envoie ou reçoive des données. Pour cela, nous délaissons l’architecture client-serveur couramment utilisée dans les réseaux anonymes, en faveur d’une architecture entièrement distribuée et homogène, où chaque utilisateur remplit également le rôle de serveur relai, lui permettant de dissimuler son propre trafic dans celui qu’il relai pour les autres. Dans cette optique, nous proposons un nouveau protocole pour les communications pairs à pairs sur Internet. À l’aide de récents outils de preuves cryptographiques, nous prouvons que ce protocole réalise les propriétés d’anonymat désirées. De plus, nous montrons par une étude pratique que, bien que le protocole induise une grande latence dans les communications, il assure un fort anonymat, même pour des réseaux de petite taille. / With the development of online communications in the past decades, new privacy concerns have emerged. A lot of research effort have been focusing on concealing relationships in Internet communications. However, most works do not prevent particular network actors from learning the original sender or the intended receiver of a communication. While this level of privacy is satisfactory for the common citizen, it is insufficient in contexts where individuals can be convicted for the mere sending of documents to a third party. This is the case for so-called whistle-blowers, who take personal risks to alert the public of anti-democratic or illegal actions performed by large organisations. In this thesis, we consider a stronger notion of anonymity for peer-to-peer communications on the Internet, and aim at concealing the very fact that users take part in communications. To this end, we deviate from the traditional client-server architecture endorsed by most existing anonymous networks, in favor of a homogeneous, fully distributed architecture in which every user also acts as a relay server, allowing it to conceal its own traffic in the traffic it relays for others. In this setting, we design an Internet overlay inspired from previous works, that also proposes new privacy-enhancing mechanisms, such as the use of relationship pseudonyms for managing identities. We formally prove with state-of-the-art cryptographic proof frameworks that this protocol achieves our privacy goals. Furthermore, a practical study of the protocol shows that it introduces high latency in the delivery of messages, but ensures a high anonymity level even for networks of small size.

Les schémas de Chiffrement Complètement Homomorphe (FHE) permettent de manipuler des données chiffrées avec grande flexibilité : ils rendent possible l'évaluation de fonctions à travers les couches de chiffrement. Depuis la découverte du premier schéma FHE en 2009 par Craig Gentry, maintes recherches ont été effectuées pour améliorer l'efficacité, atteindre des nouveaux niveaux de sécurité, et trouver des applications et liens avec d'autres domaines de la cryptographie. Dans cette thèse, nous avons étudié en détail ce type de schémas. Nos contributions font état d'une nouvelle attaque de récuperation des clés au premier schéma FHE, et d'une nouvelle notion de sécurité en structures hierarchiques, évitant une forme de trahison entre les usagers tout en gardant la flexibilité FHE. Enfin, on décrit aussi des implémentations informatiques. Cette recherche a été effectuée au sein du Laboratoire de Mathématiques de Versailles avec le Prof. Louis Goubin. / Fully Homomorphic Encryption schemes allow public processing of encrypted data. Since the groundbreaking discovery of the first FHE scheme in 2009 by Craig Gentry, an impressive amount of research has been conducted to improve efficiency, achieve new levels of security, and describe real applications and connections to other areas of cryptography. In this Dissertation, we first give a detailed account on research these past years. Our contributions include a key-recovery attack on the ideal lattices FHE scheme and a new conception of hierarchic encryption, avoiding at some extent betrayal between users while maintaining the flexibility of FHE. We also describe some implementations. This research was done in the Laboratoire de Mathématiques de Versailles, under supervision of Prof. Louis Goubin.

Sensor networks are innovative wireless networks consisting of a large number of low-cost, resource-constrained sensor nodes that collect, process, and transmit data in a distributed and collaborative way. There are numerous applications for wireless sensor networks, and security is vital for many of them. However, sensor nodes suffer from many constraints, including low computation capability, small memory, limited energy resources, susceptibility to physical capture, and the lack of infrastructure, all of which impose formidable security challenges and call for innovative approaches. In this thesis, we present our research results on three important aspects of securing sensor networks: lightweight entity authentication, distributed node clone detection, and secure data aggregation. As the technical core of our lightweight authentication proposals, a special type of circulant matrix named circulant-P2 matrix is introduced. We prove the linear independence of matrix vectors, present efficient algorithms on matrix operations, and explore other important properties. By combining circulant-P2 matrix with the learning parity with noise problem, we develop two one-way authentication protocols: the innovative LCMQ protocol, which is provably secure against all probabilistic polynomial-time attacks and provides remarkable performance on almost all metrics except one mild requirement for the verifier's computational capacity, and the HB$^C$ protocol, which utilizes the conventional HB-like authentication structure to preserve the bit-operation only computation requirement for both participants and consumes less key storage than previous HB-like protocols without sacrificing other performance. Moreover, two enhancement mechanisms are provided to protect the HB-like protocols from known attacks and to improve performance. For both protocols, practical parameters for different security levels are recommended. In addition, we build a framework to extend enhanced HB-like protocols to mutual authentication in a communication-efficient fashion. Node clone attack, that is, the attempt by adversaries to add one or more nodes to the network by cloning captured nodes, imposes a severe threat to wireless sensor networks. To cope with it, we propose two distributed detection protocols with difference tradeoffs on network conditions and performance. The first one is based on distributed hash table, by which a fully decentralized, key-based caching and checking system is constructed to deterministically catch cloned nodes in general sensor networks. The protocol performance of efficient storage consumption and high security level is theoretically deducted through a probability model, and the resulting equations, with necessary adjustments for real application, are supported by the simulations. The other is the randomly directed exploration protocol, which presents notable communication performance and minimal storage consumption by an elegant probabilistic directed forwarding technique along with random initial direction and border determination. The extensive experimental results uphold the protocol design and show its efficiency on communication overhead and satisfactory detection probability. Data aggregation is an inherent requirement for many sensor network applications, but designing secure mechanisms for data aggregation is very challenging because the aggregation nature that requires intermediate nodes to process and change messages, and the security objective to prevent malicious manipulation, conflict with each other to a great extent. To fulfill different challenges of secure data aggregation, we present two types of approaches. The first is to provide cryptographic integrity mechanisms for general data aggregation. Based on recent developments of homomorphic primitives, we propose three integrity schemes: a concrete homomorphic MAC construction, homomorphic hash plus aggregate MAC, and homomorphic hash with identity-based aggregate signature, which provide different tradeoffs on security assumption, communication payload, and computation cost. The other is a substantial data aggregation scheme that is suitable for a specific and popular class of aggregation applications, embedded with built-in security techniques that effectively defeat outside and inside attacks. Its foundation is a new data structure---secure Bloom filter, which combines HMAC with Bloom filter. The secure Bloom filter is naturally compatible with aggregation and has reliable security properties. We systematically analyze the scheme's performance and run extensive simulations on different network scenarios for evaluation. The simulation results demonstrate that the scheme presents good performance on security, communication cost, and balance.

Sensor networks are innovative wireless networks consisting of a large number of low-cost, resource-constrained sensor nodes that collect, process, and transmit data in a distributed and collaborative way. There are numerous applications for wireless sensor networks, and security is vital for many of them. However, sensor nodes suffer from many constraints, including low computation capability, small memory, limited energy resources, susceptibility to physical capture, and the lack of infrastructure, all of which impose formidable security challenges and call for innovative approaches. In this thesis, we present our research results on three important aspects of securing sensor networks: lightweight entity authentication, distributed node clone detection, and secure data aggregation. As the technical core of our lightweight authentication proposals, a special type of circulant matrix named circulant-P2 matrix is introduced. We prove the linear independence of matrix vectors, present efficient algorithms on matrix operations, and explore other important properties. By combining circulant-P2 matrix with the learning parity with noise problem, we develop two one-way authentication protocols: the innovative LCMQ protocol, which is provably secure against all probabilistic polynomial-time attacks and provides remarkable performance on almost all metrics except one mild requirement for the verifier's computational capacity, and the HB$^C$ protocol, which utilizes the conventional HB-like authentication structure to preserve the bit-operation only computation requirement for both participants and consumes less key storage than previous HB-like protocols without sacrificing other performance. Moreover, two enhancement mechanisms are provided to protect the HB-like protocols from known attacks and to improve performance. For both protocols, practical parameters for different security levels are recommended. In addition, we build a framework to extend enhanced HB-like protocols to mutual authentication in a communication-efficient fashion. Node clone attack, that is, the attempt by adversaries to add one or more nodes to the network by cloning captured nodes, imposes a severe threat to wireless sensor networks. To cope with it, we propose two distributed detection protocols with difference tradeoffs on network conditions and performance. The first one is based on distributed hash table, by which a fully decentralized, key-based caching and checking system is constructed to deterministically catch cloned nodes in general sensor networks. The protocol performance of efficient storage consumption and high security level is theoretically deducted through a probability model, and the resulting equations, with necessary adjustments for real application, are supported by the simulations. The other is the randomly directed exploration protocol, which presents notable communication performance and minimal storage consumption by an elegant probabilistic directed forwarding technique along with random initial direction and border determination. The extensive experimental results uphold the protocol design and show its efficiency on communication overhead and satisfactory detection probability. Data aggregation is an inherent requirement for many sensor network applications, but designing secure mechanisms for data aggregation is very challenging because the aggregation nature that requires intermediate nodes to process and change messages, and the security objective to prevent malicious manipulation, conflict with each other to a great extent. To fulfill different challenges of secure data aggregation, we present two types of approaches. The first is to provide cryptographic integrity mechanisms for general data aggregation. Based on recent developments of homomorphic primitives, we propose three integrity schemes: a concrete homomorphic MAC construction, homomorphic hash plus aggregate MAC, and homomorphic hash with identity-based aggregate signature, which provide different tradeoffs on security assumption, communication payload, and computation cost. The other is a substantial data aggregation scheme that is suitable for a specific and popular class of aggregation applications, embedded with built-in security techniques that effectively defeat outside and inside attacks. Its foundation is a new data structure---secure Bloom filter, which combines HMAC with Bloom filter. The secure Bloom filter is naturally compatible with aggregation and has reliable security properties. We systematically analyze the scheme's performance and run extensive simulations on different network scenarios for evaluation. The simulation results demonstrate that the scheme presents good performance on security, communication cost, and balance.

Les protocoles de dissémination de contenus randomisés sont une alternative bon marché et pouvant monter en charge aux systèmes centralisés. Cependant, il est bien connu que ces protocoles souffrent en présence de comportements individualistes, i.e., de participants qui cherchent à recevoir un contenu sans contribuer en retour à sa propagation. Alors que le problème des participants égoïstes a été bien étudié dans la littérature, les coalitions de participants égoïstes ont été laissés de côté. De plus, les manières actuelles permettant de limiter ou tolérer ces comportements exigent des noeuds qu'ils enregistrent leurs interactions, et rendent public leur contenu, ce qui peut dévoiler des informations gênantes. De nos jours, il y a consensus autour du besoin de renforcer les possibilités de contrôle des usagers de systèmes informatiques sur leurs données personnelles. Cependant, en l'état de nos connaissances, il n'existe pas de protocole qui évite de divulguer des informations personnelles sur les utilisateurs tout en limitant l'impact des comportements individualistes.Cette thèse apporte deux contributions.Tout d'abord, nous présentons AcTinG, un protocole qui empêche les coalitions de noeuds individualistes dans les systèmes pair-à-pair de dissémination de contenus, tout en garantissant une absence de faux-positifs dans le processus de détection de fautes. Les utilisateurs de AcTinG enregistrent leurs interactions dans des enregistrements sécurisés, et se vérifient les uns les autres grâce à une procédure d'audit non prédictible, mais vérifiable a posteriori. Ce protocole est un équilibre de Nash par construction. Une évaluation de performance montre qu'AcTinG est capable de fournir les messages à tous les noeuds malgré la présence de coalitions, et présente des propriétés de passage à l'échelle similaires aux protocoles classiques de dissémination aléatoire.Ensuite, nous décrivons PAG, le premier protocole qui évite de dévoiler des informations sur les usagers tout en les contrôlant afin d'éviter les comportements égoïstes. PAG se base sur une architecture de surveillance formée par les participants, ainsi que sur des procédures de chiffrement homomorphiques. L'évaluation théorique de ce protocole montre qu'obtenir le détail des interactions des noeuds est difficile, même en cas d'attaques collectives. Nous évaluons ce protocole en terme de protection de l'intimité des interactions et en terme de performance en utilisant un déploiement effectué sur un cluster de machines, ainsi que des simulations qui impliquent jusqu'à un million de participants, et enfin en utilisant des preuves théoriques. Ce protocole a un surcoût en bande-passante inférieur aux protocoles de communications anonymes existants, et est raisonnable en terme de coût cryptographique. / Gossip-based content dissemination protocols are a scalable and cheap alternative to centralised content sharing systems. However, it is well known that these protocols suffer from rational nodes, i.e., nodes that aim at downloading the content without contributing their fair share to the system. While the problem of rational nodes that act individually has been well addressed in the literature, textit{colluding} rational nodes is still an open issue. In addition, previous rational-resilient gossip-based solutions require nodes to log their interactions with others, and disclose the content of their logs, which may disclose sensitive information. Nowadays, a consensus exists on the necessity of reinforcing the control of users on their personal information. Nonetheless, to the best of our knowledge no privacy-preserving rational-resilient gossip-based content dissemination system exists.The contributions of this thesis are twofold.First, we present AcTinG, a protocol that prevents rational collusions in gossip-based content dissemination protocols, while guaranteeing zero false positive accusations. AcTing makes nodes maintain secure logs and mutually check each others' correctness thanks to verifiable but non predictable audits. As a consequence of its design, it is shown to be a Nash-equilibrium. A performance evaluation shows that AcTinG is able to deliver all messages despite the presence of colluders, and exhibits similar scalability properties as standard gossip-based dissemination protocols.Second, we describe PAG, the first accountable and privacy-preserving gossip protocol. PAG builds on a monitoring infrastructure, and homomorphic cryptographic procedures to provide privacy to nodes while making sure that nodes forward the content they receive. The theoretical evaluation of PAG shows that breaking the privacy of interactions is difficult, even in presence of a global and active opponent. We assess this protocol both in terms of privacy and performance using a deployment performed on a cluster of machines, simulations involving up to a million of nodes, and theoretical proofs. The bandwidth overhead is much lower than existing anonymous communication protocols, while still being practical in terms of CPU usage.

In the Master’s thesis were described privacy protection problems while using cloud technologies. Some of the problems can be solved with help of homomorphic encryption, data splitting or searchable encryption. These techniques were described and compared by provided security, privacy protection and efficiency. The data splitting technique was chosen and implemented in the C language. Afterwards a performance of the implemented solution was compared to AES encryption/decryption performance. An application for secured data storing in cloud was designed and implemented. This application is using the implemented data splitting technique and third-party application CloudCross. The designed application provides command line interface (CLI) and graphical user interface (GUI). GUI extends the capabilities of CLI with an ability to register cloud and with an autodetection of registered clouds. The process of uploading/downloading the data to/from cloud storage is transparent and it does not overload the user with technical details of used data splitting technique.