Secret sharing is a fundamental notion for secure cryptographic design. In a secret sharing scheme, a set of participants shares a secret among them such that only pre-specified subsets of these shares can get together to recover the secret. This dissertation introduces a neural network approach to solve the problem of secret sharing for any given access structure. Other approaches have been used to solve this problem. However, the yet known approaches result in exponential increase in the amount of data that every participant need to keep. This amount is measured by the secret sharing scheme information rate. This work is intended to solve the problem with better information rate.

Nowadays all existing public key cryptosystems are classified into three categories relied on different mathematical foundations. The first one is based on the difficulty of factoring the product of two big prime numbers. The representatives are the RSA and the Rabin cryptosystems. The second one such as the ElGamal cryptosystem is based on the discrete logarithm problem. The last one is based on the NP-completeness of the knapsack problem. The first two categories survived crypto attacks, whereas the last one was broken and there has been no attempt to use such a cryptosystem. In order to save the last category, Kiriyama proposed a new public key cryptosystem based on the non-linear knapsack problem, which is an NP-complete problem. Due to the non-linear property of the non-linear knapsack problem, this system resists all known attacks to the linear knapsack problem. Based on his work, we extend our research in several ways. Firstly, we propose an encrypted secret sharing scheme. We improve the security of shares by our method over other existing secret sharing schemes. Simply speaking, in our scheme, it would be hard for outsiders to recover a secret even if somehow they could collect all shares, because each share is already encrypted when it is generated. Moreover, our scheme is efficient. Then we propose a multiple identities authentication scheme, developed on the basis of the non-linear knapsack scheme. It verifies the ownership of an entity's several identities in only one execution of our scheme. More importantly, it protects the privacy of the entities from outsiders. Furthermore, it can be used in resource-constrained devices due to low computational complexity. We implement the above schemes in the C language under the Linux system. The experimental results show the high efficiency of our schemes, due to low computational complexity of the non-linear knapsack problem, which works as the mathematical foundation of our research.

In this work, we study some generalized multipartite access structures and linear secret sharing schemes for their realizations. Given a multipartite set of participants with m compartments (or levels) and m conditions to be satisfied by an authorized set, we firstly examine the intermediary access structures arousing from the natural case concerning that any c out of m of these conditions suffice, instead of requiring anyone or all of the m conditions simultaneously, yielding to generalizations for both the compartmented and hierarchical cases. These are realized essentially by employing a series of Lagrange interpolations and a simple frequently-used connective tool called access structure product, as well as some known constructions for existing ideal schemes. The resulting schemes are non-ideal but perfect. We also consider nested multipartite access structures, where we let a compartment to be defined within another, so that the access structure is composed of some multipartite substructures. We extend formerly employed bivariate interpolation techniques to multivariate interpolation, in order to realize such access structures. The generic scheme we consider is perfect with a high probability such as 1-O(1/q) on a finite field F_q. In particular, we propose a non-nested generalization for the conventional compartmented access structures, which depicts a stronger way of controlling the additional participants.

Une large quantité de données personnelles sont partagées en temps réel par des utilisateurs en ligne, utilisant de plus en plus des terminaux mobiles avec connexion sans-fil. L'industrie s'efforce d'accumuler et d'analyser ces données pour fournir de nouveaux services ou des améliorations. La recherche fournit un effort équivalent pour permettre de traiter ces données de façon sécurisée et protectrice de la vie privée. Les problèmes de performance des communications temps réels sur terminaux mobiles sur un canal sans-fil sont aussi étudiés. Les codes à effacement sont un moyen courant d'améliorer ces performances. Le secret sharing est un mécanisme permettant de partager des données privées, ne les révélant qu'à un groupe d'utilisateur choisi. Dans cette thèse, nous lions théoriquement les secret sharing schemes et les codes à effacement, pour fournir une source plus riche de solutions aux deux problèmes. Notre objectif est de fournir des solutions ayant le niveau de sécurité souhaité, tout en restant efficace et implémentable. Les contributions de cette thèse sont les suivantes. Nous évaluons l'applicabilité d'une nouvelle classe de codes à effacements à Maximum Distance Séparable (MDS) pour transférer du contenu temps réel à des terminaux mobiles, et nous démontrons que le code systématique réduit grandement la complexité d'exécution et la taille nécessaire des tampons en comparaison du code non systématique, faisant de lui un bon candidat pour une application mobile. Nous proposons un nouveau Layered secret sharing scheme pour le partage en temps réel de données sur des réseaux sociaux (OSNs pour Online Social Network). Le procédé permet de partager automatiquement un profile dans un groupe défini dans un OSN, en utilisant un multi-secret sharing scheme formé de multiples couches. Le procédé ne dépend nullement d'un tiers de confiance. Comparé à un partage simple de chaque attributs (pouvant être un texte, une image ou une vidéo), le procédé ne divulgue aucune information à propos de ce qui est partagé, pas même le nombre de ceux-ci, et il induit une augmentation relativement faible du temps de calcul et des données à envoyer. Finalement, nous étudions les liens entre les codes MDS et les secret sharing schemes, ayant pour motivation l'inefficacité du très populaire Shamir secret sharing scheme. Nous établissons les liens théoriques entre les deux domaines et nous proposons une nouvelle construction de strong ramp schemes à partir de codes MDS. Ceci permet d'utiliser les codes MDS existants et efficaces pour des applications de partage de secret et de calculs distribués et sécurisés. Nous évaluons et montrons une réduction significative de temps de calcul et du coût de communication en utilisant un strong ramp scheme, en comparaison avec le procédé de Shamir. / Data from both individuals and companies is increasingly aggregated and analysed to provide new and improved services. There is a corresponding research effort to enable processing of such data in a secure and privacy preserving way, in line with the increasing public concerns and more stringent regulatory requirements for the protection of such data. Secure Multi-Party Computation (MPC) and secret sharing are mechanisms that can enable both secure distribution and computations on private data. In this thesis, we address the inefficiencies of these mechanisms by utilising results from a theoretically related rich area, erasure codes. We derive links between erasure codes and secret sharing, and use Maximum Distance Separable (MDS) codes as a basis to provide real-time applications relying on private user's data, revealing this data only to the selected group (which can be empty). The thesis has three contributions. A new class of erasure code called on-the-fly coding, have been introduced for their improvements in terms of recovery delay and achievable capacity. However little is known about the complexity of the systematic and non-systematic variants of this code, notably for live multicast transmission of multimedia content which is their ideal use case. The evaluation of both variants demonstrate that the systematic code outperforms the non-systematic one in regard to both the buffer sizes and the computation complexity. Then, we propose a new Layered secret sharing scheme and its application to Online Social Network (OSN). In current OSN, access to the user's profile information is managed by the service provider based on a limited set of rules. The proposed scheme enables automated profile sharing in OSN's groups with fine grained privacy control, via a multi-secret sharing scheme comprising of layered shares, without relying on a trusted third party. We evaluate the security of the scheme and the resulting profile's level of protection in an OSN scenario. Finally, after showing that erasure codes are efficient for real-time applications and that the security offered by secret sharing schemes can be applied to real-case applications, we derive the theoretical links between MDS codes and secret sharing to enable the implementation of efficient secret sharing scheme built from MDS codes. To illustrate this efficiency, we implement two of these schemes and evaluate their benefits in regard to computation and communication costs in an MPC application.

Šio darbo tikslas – apžvelgti šiuo metu naudojamas klasikines viešojo rakto šifravimo ir skaitmeninio parašo sistemas bei naujos kartos Signcryption kriptosistemą ir atlikti dedikuotos pasirašymo ir šifravimo kriptosistemos efektyvumo palyginimą su pasirašymo arba šifravimo kriptosistemų kompozicija bei pasiūlyti praktinio pritaikymą naujos kartos Signcryption kriptosistemai. Darbe apžvelgtos šios kriptosistemos: 1. RSA (Rivest, Shamir, Adleman) – klasikinė viešojo rakto pasirašymo arba šifravimo kriptosistema, kurios saugumas paremtas didelių skaičių faktorizacijos uždavinio sprendimo sudėtingumu, 2. ElGamalio – klasikinė viešojo rakto pasirašymo arba šifravimo kriptosistema, kurios saugumas paremtas diskretaus logaritmo problemos sprendimo sudėtingumu, 3. Signcryption – naujos kartos viešojo rakto pasirašymo ir šifravimo kriptosistema, realizuota modifikuotos ElGamalio skaitmeninio parašo schemos pagrindu. Minėtos kriptosistemos apžvelgtos teoriškai, sukurta praktinė jų realizacija ir apžvelgti rezultatai bei palygintas jų efektyvumas, kuris apibrėžiamas dviem parametrais: 1. Pranešimo pasirašymo, šifravimo, dešifravimo ir parašo patikrinimo operacijų trukmė, 2. Perduodamos perteklinės informacijos kiekis – pranešimo ilgio padidėjimas atlikus pasirašymo ir šifravimo operacijas. Taip pat apžvelgtos kriptosistemų realizacijoje naudotos papildomos funkcijos bei algoritmai, tokie kaip AES blokiniai šifrai, SHA maišos funkcijų šeima, HMAC kontrolinis parašas bei pasiūlyti du... [toliau žr. visą tekstą] / This submission called “Efficient encryption and digital signature schemes” consists of three parts. I. In Part I theoretical analysis of popular public key cryptosystems RSA (Rivest, Shamir, Adleman) with security based on the large integer factorization problem and ElGamal with security based on the discrete logarithm problem, along with new cryptographic primitive termed as "signcryption" proposed by Y. Zheng which simultaneously fulfills both the functions of digital signature and public key encryption in a logically single step, and with a cost significantly smaller than that required by "signature followed by encryption" using popular public key cryptosystem composition is done. For the completeness of analysis description of supplemental algorithms and functions such as AES block cipher, SHA hash functions, HMAC keyed hash function is present. II. In Part II the results of the practical implementation done in Python programming language are analyzed. Effectiveness is described by two factors: 1. Total computation time of signing – encryption – decryption – verification operations; 2. Communication overhead – signed and encrypted message length increase compared to the original plaintext. III. In Part III two effective Signcryption implementation algorithms are proposed: secret sharing without threshold and (k, n) threshold schemes. Results of analysis prove Signcryption being secure and extremely effective signature and encryption cryptosystem. It has very low... [to full text]

This thesis considers the problem of finitely iterated rational secret sharing. We describe how to evaluate this problem using game theory and finitely iterated prisoner’s dilemma. The players each have a private horizon that the other player does not know. The only thing that a player knows about their opponent’s private horizon is a common upper bound. The description of a synchronous and asynchronous finitely iterated secret sharing protocol with private information is followed by a game theoretic proof of the viability of such protocols. / Graduate

Notre travail sur le partage de secret se base sur les points de vue théoriques de la Théorie de l'Information de Shannon et de la Complexité de Kolmogorov. Nous allons expliquer comment ces trois sujets intimement liés.Les inégalité d'information jouent un rôle centrale dans ce manuscrit. Ce sont les inégalités pour l'entropie de Shannon, mais correspondent aussi aux inégalités pour la complexité de Kolmogorov.La complexité de Kolmogorov formalise l'idée d'aléatoire pour les chaînes de caractère. Ce sont là deux raisons qui justifient à elles seules la notion de partage de secret algorithmique dans le cadre de la Théorie Algorithmique de l'information (si l'on sait partager un secret aléatoire, on peut partager n'importe quel secret).Originalement étudié par sa définition combinatoire, le partage de secret a été plus tard généralisé par sa formulation par les quantités définies dans la théorie de l'information. Cette étape a permis l'utilisation des inégalités d'information et s'est révélée très importante dans la caractérisation desschémas de partage de secret efficaces.L'étude des inégalités d'information n'en est qu'à ses débuts. Nous y contribuons en introduisant la notion d'inégalité essentiellement conditionnelles, qui montre une fois de plus que ces inégalités ne sont pas encore complètement comprises. / Our work deals with secret sharing in the theoretical point of views of Shannon's Information Theory and Kolmogorov's Algorithmic Information Theory. We are going to explain how these three subjects are naturally deeply intertwined.Information inequalities play a central role in this text. They are the inequalities for Shannon entropy, but also they are in exact correspondence with the inequalities for Kolmogorov complexity. Kolmogorov complexity formalizes the idea of randomness for strings.These two reasons alone justify to consider the notion of secret sharing in the Algorithmic framework (if one can share a random secret one can share anything).Originally, secret sharing was first studied under the combinatorial lens, only later was it more generally formalized using information-theoretic measures. This step allowed the use of information inequalities which revealed to bevery important to understand the existence of secret-sharing schemes with respect to efficiency.The investigation of information inequalities is at its debut. We contribute to the subject by introducing the notion of essentially conditional inequalities, which shows once again that information inequalities are yet not fully understood.

Radio Frequency Identification (RFID) technology has been expanded to be used in different fields that need automatic identifying and verifying of tagged objects without human intervention. RFID technology offers a great advantage in comparison with barcodes by providing accurate information, ease of use and reducing of labour cost. These advantages have been utilised by using passive RFID tags. Although RFID technology can enhance the efficiency of different RFID applications systems, researchers have reported issues regarding the use of RFID technology. These issues are making the technology vulnerable to many threats in terms of security and privacy. Different RFID solutions, based on different cryptography primitives, have been developed. Most of these protocols focus on the use of passive RFID tags. However, due to the computation feasibility in passive RFID tags, these tags might be vulnerable to some of the security and privacy threats. , e.g. unauthorised reader can read the information inside tags, illegitimate tags or cloned tags can be accessed by a reader. Moreover, most consideration of reserchers is focus on single tag authentication and mostly do not consider scenarios that need multi-tag such as supply chain management and healthcare management. Secret sharing schemes have been also proposed to overcome the key management problem in supply chain management. However, secret sharing schemes have some scalability limitations when applied with high numbers of RFID tags. This work is mainly focused on solving the problem of the security and privacy in multi-tag RFID based system. In this work firstly, we studied different RFID protocols such as symmetric key authentication protocols, authentication protocols based on elliptic curve cryptography, secret sharing schemes and multi-tag authentication protocols. Secondly, we consider the significant research into the mutual authentication of passive RFID tags. Therefore, a mutual authentication scheme that is based on zero-knowledge proof have been proposed . The main object of this work is to develop an ECC- RFID based system that enables multi-RFID tags to be authenticated with one reader by using different versions of ECC public key encryption schemes. The protocol are relied on using threshold cryptosystems that operate ECC to generate secret keys then distribute and stored secret keys among multi RFID tags. Finally, we provide performance measurement for the implementation of the proposed protocols.

<p>Finnegan Lab System is a graphical computer program for learning how secret sharing works. With its focus on the algorithms and the data streams, the user does not have to consider machine-specific low-level details. It is highly modularised and is not restricted to secret sharing, but can easily be extended with new functions, such as building blocks for Feistel networks or signal processing. </p><p>This thesis describes what secret sharing is, the development of a new lab system designed for secret sharing and how it can be used.</p>

With growing trend in "cloud computing" and increase in the data moving into the Internet, the need to store large amounts of data by service providers such as Google, Yahoo and Microsoft has increased over time. Now, more than ever, there is a need to efficiently and securely store large amounts of data. This thesis presents an implementation of a Ramp Scheme that confidentially splits a data file into a configurable number of parts or shares of equal size such that a subset of those shares can recover the data entirely. Furthermore, the implementation supports a threshold for data compromise and data verification to verify that the data parts have not been tampered with. This thesis addresses two key problems faced in large-scale data storage, namely, data availability and confidentiality.