Nonlinear secret sharing immune against cheating

The paper investigates the design of secret sharing that is immune against cheating (as defined by the Tompa-Woll attack). We examine secret sharing with binary shares and secrets. Bounds on the probability of successful cheating are given for two cases. The first case relates to secret sharing based on bent functions and results in a non-perfect scheme. The second case considers perfect secret sharing built on highly nonlinear balanced Boolean functions.

On cheating immune secret sharing

The paper addresses the cheating prevention in secret sharing. We consider secret sharing with binary shares. The secret also is binary. This model allows us to use results and constructions from the well developed theory of cryptographically strong boolean functions. In particular, we prove that for given secret sharing, the average cheating probability over all cheating vectors and all original vectors, i.e., 1/n 2n ∑c=1...n ∑α∈V n ρc,α , denoted by ρ, satisfies ρ ≥ ½, and the equality holds if and only if ρc,α satisfies ρc,α= ½ for every cheating vector δc and every original vector α. In this case the secret sharing is said to be cheating immune. We further establish a relationship between cheating-immune secret sharing and cryptographic criteria of boolean functions.This enables us to construct cheating-immune secret sharing.

Dual compressible hybrid quantum secret sharing schemes based on extended unitary operations

A crucial issue with hybrid quantum secret sharing schemes is the amount of data that is allocated to the participants. The smaller the amount of allocated data, the better the performance of a scheme. Moreover, quantum data is very hard and expensive to deal with, therefore, it is desirable to use as little quantum data as possible. To achieve this goal, we first construct extended unitary operations by the tensor product of n, n ≥ 2, basic unitary operations, and then by using those extended operations, we design two quantum secret sharing schemes. The resulting dual compressible hybrid quantum secret sharing schemes, in which classical data play a complementary role to quantum data, range from threshold to access structure. Compared with the existing hybrid quantum secret sharing schemes, our proposed schemes not only reduce the number of quantum participants, but also the number of particles and the size of classical shares. To be exact, the number of particles that are used to carry quantum data is reduced to 1 while the size of classical secret shares also is also reduced to l−2 m−1 based on ((m+1, n′)) threshold and to l−2 r2 (where r2 is the number of maximal unqualified sets) based on adversary structure. Consequently, our proposed schemes can greatly reduce the cost and difficulty of generating and storing EPR pairs and lower the risk of transmitting encoded particles.

From Classical to Quantum Secret Sharing

Dans ce mémoire, nous nous pencherons tout particulièrement sur une primitive cryptographique connue sous le nom de partage de secret. Nous explorerons autant le domaine classique que le domaine quantique de ces primitives, couronnant notre étude par la présentation d’un nouveau protocole de partage de secret quantique nécessitant un nombre minimal de parts quantiques c.-à-d. une seule part quantique par participant. L’ouverture de notre étude se fera par la présentation dans le chapitre préliminaire d’un survol des notions mathématiques sous-jacentes à la théorie de l’information quantique ayant pour but primaire d’établir la notation utilisée dans ce manuscrit, ainsi que la présentation d’un précis des propriétés mathématique de l’état de Greenberger-Horne-Zeilinger (GHZ) fréquemment utilisé dans les domaines quantiques de la cryptographie et des jeux de la communication. Mais, comme nous l’avons mentionné plus haut, c’est le domaine cryptographique qui restera le point focal de cette étude. Dans le second chapitre, nous nous intéresserons à la théorie des codes correcteurs d’erreurs classiques et quantiques qui seront à leur tour d’extrême importances lors de l’introduction de la théorie quantique du partage de secret dans le chapitre suivant. Dans la première partie du troisième chapitre, nous nous concentrerons sur le domaine classique du partage de secret en présentant un cadre théorique général portant sur la construction de ces primitives illustrant tout au long les concepts introduits par des exemples présentés pour leurs intérêts autant historiques que pédagogiques. Ceci préparera le chemin pour notre exposé sur la théorie quantique du partage de secret qui sera le focus de la seconde partie de ce même chapitre. Nous présenterons alors les théorèmes et définitions les plus généraux connus à date portant sur la construction de ces primitives en portant un intérêt particulier au partage quantique à seuil. Nous montrerons le lien étroit entre la théorie quantique des codes correcteurs d’erreurs et celle du partage de secret. Ce lien est si étroit que l’on considère les codes correcteurs d’erreurs quantiques étaient de plus proches analogues aux partages de secrets quantiques que ne leur étaient les codes de partage de secrets classiques. Finalement, nous présenterons un de nos trois résultats parus dans A. Broadbent, P.-R. Chouha, A. Tapp (2009); un protocole sécuritaire et minimal de partage de secret quantique a seuil (les deux autres résultats dont nous traiterons pas ici portent sur la complexité de la communication et sur la simulation classique de l’état de GHZ).

Secret Sharing Schemes Using Visual Cryptography

Secret sharing schemes allow a secret to be shared among a group of participants so that only qualified subsets of participants can recover the secret. A visual cryptography scheme (VCS) is a special kind of secret sharing scheme in which the secret to share consists of an image and the shares consist of xeroxed transparencies which are stacked to recover the shared image. In this thesis we have given the theoretical background of Secret Sharing Schemes and the historical development of the subject. We have included a few examples to improve the readability of the thesis. We have tried to maintain the rigor of the treatment of the subject. The limitations and disadvantages of the various forms secret sharing schemes are brought out. Several new schemes for both dealing and combining are included in the thesis. We have introduced a new number system, called, POB number system. Representation using POB number system has been presented. Algorithms for finding the POB number and POB value are given.We have also proved that the representation using POB number system is unique and is more efficient. Being a new system, there is much scope for further development in this area.

A secret sharing scheme based on exponentiation in Galois fields

To provide more efficient and flexible alternatives for the applications of secret sharing schemes, this paper describes a threshold sharing scheme based on exponentiation of matrices in Galois fields. A significant characteristic of the proposed scheme is that each participant has to keep only one master secret share which can be used to reconstruct different group secrets according to the number of threshold values.

Further results on strongbox secured secret sharing schemes

We extend our earlier work on ways in which defining sets of combinatorial designs can be used to create secret sharing schemes. We give an algorithm for classifying defining sets or designs according to their security properties and summarise the results of this algorithm for many small designs. Finally, we discuss briefly how defining sets can be applied to variations of the basic secret sharing scheme.

A flaw in the use of minimal defining sets for secret sharing schemes

It is shown that in some cases it is possible to reconstruct a block design D uniquely from incomplete knowledge of a minimal defining set for D. This surprising result has implications for the use of minimal defining sets in secret sharing schemes.

On Proactive Verifiable Secret Sharing Schemes

The paper has been presented at the International Conference Pioneers of Bulgarian Mathematics, Dedicated to Nikola Obreshkoff and Lubomir Tschakaloff , Sofia, July, 2006. The material in this paper was presented in part at the 11th Workshop on Selected Areas in Cryptography (SAC) 2004

Lattice-based threshold changeability for standard shamir sectret-sharing schemes

We consider the problem of increasing the threshold parameter of a secret-sharing scheme after the setup (share distribution) phase, without further communication between the dealer and the shareholders. Previous solutions to this problem require one to start off with a nonstandard scheme designed specifically for this purpose, or to have communication between shareholders. In contrast, we show how to increase the threshold parameter of the standard Shamir secret-sharing scheme without communication between the shareholders. Our technique can thus be applied to existing Shamir schemes even if they were set up without consideration to future threshold increases. Our method is a new positive cryptographic application for lattice reduction algorithms, inspired by recent work on lattice-based list decoding of Reed-Solomon codes with noise bounded in the Lee norm. We use fundamental results from the theory of lattices (geometry of numbers) to prove quantitative statements about the information-theoretic security of our construction. These lattice-based security proof techniques may be of independent interest.

G(its)(2) VSR: An Information Theoretic Secure Verifiable Secret Redistribution Protocol for Long-term Archival Storage

Protocols for secure archival storage are becoming increasingly important as the use of digital storage for sensitive documents is gaining wider practice. Wong et al.[8] combined verifiable secret sharing with proactive secret sharing without reconstruction and proposed a verifiable secret redistribution protocol for long term storage. However their protocol requires that each of the receivers is honest during redistribution. We proposed[3] an extension to their protocol wherein we relaxed the requirement that all the recipients should be honest to the condition that only a simple majority amongst the recipients need to be honest during the re(distribution) processes. Further, both of these protocols make use of Feldman's approach for achieving integrity during the (redistribution processes. In this paper, we present a revised version of our earlier protocol, and its adaptation to incorporate Pedersen's approach instead of Feldman's thereby achieving information theoretic secrecy while retaining integrity guarantees.

An extended verifiable secret redistribution protocol for archival systems

Existing protocols for archival systems make use of verifiability of shares in conjunction with a proactive secret sharing scheme to achieve high availability and long term confidentiality, besides data integrity. In this paper, we extend an existing protocol (Wong et al. [9]) to take care of more realistic situations. For example, it is assumed in the protocol of Wong et al. that the recipients of the secret shares are all trustworthy; we relax this by requiring that only a majority is trustworthy.

Batch Verification of Validity of Bids in Homomorphic E-auction

Bid opening in e-auction is efficient when a homomorphic secret sharing function is employed to seal the bids and homomorphic secret reconstruction is employed to open the bids. However, this high efficiency is based on an assumption: the bids are valid (e.g., within a special range). An undetected invalid bid can compromise correctness and fairness of the auction. Unfortunately, validity verification of the bids is ignored in the auction schemes employing homomorphic secret sharing (called homomorphic auction in this paper). In this paper, an attack against the homomorphic auction in the absence of bid validity check is presented and a necessary bid validity check mechanism is proposed. Then a batch cryptographic technique is introduced and applied to improve the efficiency of bid validity check.

Experimenting with an intrusion detection system for encrypted networks

Network-based Intrusion Detection Systems (NIDSs) analyse network traffic to detect instances of malicious activity. Typically, this is only possible when the network traffic is accessible for analysis. With the growing use of Virtual Private Networks (VPNs) that encrypt network traffic, the NIDS can no longer access this crucial audit data. In this paper, we present an implementation and evaluation of our approach proposed in Goh et al. (2009). It is based on Shamir's secret-sharing scheme and allows a NIDS to function normally in a VPN without any modifications and without compromising the confidentiality afforded by the VPN.