Code Based Secret Sharing Schemes: Applied Combinatorial Coding Theory

Description

Secret sharing schemes form one of the most important topic in Cryptography. These protocols are used in many areas, applied mathematics, computer science, electrical engineering. A secret is divided into several pieces called shares. Each share is given to a user of the system. Each user has no information about the secret, but the secret can be retrieved by certain authorized coalition of users. This book is devoted to such schemes inspired by Coding Theory. The classical schemes of Shamir, Blakley, Massey are recalled. Survey is made of research in Combinatorial Coding Theory they trigerred, mostly self-dual codes, and minimal codes. Applications to engineering like image processing, and key management of MANETs are highlighted. Contents Foreword Preface 1. Foundations 1.1. Access Structures 1.2. Secret-Sharing Schemes and Examples 1.3. Alternative Definitions 1.4. Security Models 1.5. Shamir Scheme and Applications 1.6. Basics of Coding Theory 1.7. Code-Based Constructions of Secret-Sharing Schemes 1.7.1. Construction 1 1.7.2. Construction 2 1.8. Multisecret-Sharing Schemes References 2. Massey Scheme 2.1. On the Number of Minimal Codewords 2.1.1. Introduction 2.1.2. Maximum number of minimal codewords 2.1.2.1. Upper bounds 2.1.2.2. Lower bounds 2.1.2.3. Tabulating M(n, k) 2.1.2.4. Asymptotic analysis 2.1.3. Minimum number of minimal codewords 2.1.3.1. Matroid bounds 2.1.3.2. Tables 2.2. Secret Sharing Schemes Based on Self-dual Codes 2.2.1. Massey scheme and self-dual codes 2.2.1.1. Preliminaries 2.2.1.2. Massey scheme for secret sharing 2.2.1.3. Access structure for self-dual codes 2.2.1.4. Minimum access structure for binary self-dual codes 2.2.1.5. Example of a scheme based on the Golay Code 2.2.1.6. Examples of optimal Type I and Type II codes 2.2.1.7. Minimum access structure for Type III and Type IV codes 2.2.1.8. Joint weight enumerators and Jacobi polynomials 2.2.1.9. Invariants 2.2.2. An extension of Massey scheme 2.2.2.1. General SSS based on linear codes 2.2.2.2. Access structure 2.2.2.3. Relation between access structure and joint weight enumerator 2.2.2.4. Binary self-dual codes 2.2.2.5. Invariant theory References 3. Blakley Secret-Sharing Scheme 3.1. Linear Codes 3.1.1. LCD codes 3.2. Ramp Secret-Sharing Schemes 3.3. Multisecret-Sharing Schemes Based on Linear Codes 3.3.1. Scheme description 3.3.2. Secret distribution 3.3.3. Secret recovery 3.4. Statistics on Coalitions 3.4.1. Security analysis 3.4.2. Information theoretic efficiency 3.4.3. Comparison with other schemes 3.4.4. Conclusion and open problems 3.5. A New Approach to Construct a Secret-Sharing Scheme Based on Blakley’s Method 3.5.1. Proposed scheme 3.5.2. Security analysis 3.5.3. Conclusion 3.6. Some Multisecret-Sharing Schemes over Finite Fields 3.6.1. Notation 3.6.2. Scheme description 3.6.3. Statistics on coalitions 3.6.4. Security analysis 3.6.5. Information theoretic efficiency 3.6.6. Comparison with other schemes 3.6.7. Conclusions References 4. Alternative Schemes 4.1. Codes and Coset Decoding 4.1.1. Coset decoding 4.1.2. Coset leader 4.2. Multisecret-Sharing Schemes and Error Correcting Codes 4.2.1. Scheme description 4.2.2. Statistics on coalitions 4.2.3. Democracy in secret-sharing 4.2.4. Comparison with other schemes 4.2.5. Conclusion 4.3. A New Secret-Sharing Scheme Based on Polynomials over Finite Fields 4.3.1. Polynomials over finite fields 4.3.2. The scheme 4.3.3. Properties and security 4.3.4. Conclusion 4.4. Roots of Irreducible Polynomials 4.4.1. Traces and norms 4.4.2. Secret-sharing schemes 4.4.3. The schemes 4.4.4. First scheme 4.4.5. Second scheme 4.4.6. Conclusion 4.5. Secret-Sharing Schemes and Syndrome Decoding 4.5.1. Syndrome decoding 4.5.2. Why use syndrome decoding? 4.5.3. Conclusion 4.6. Secret Sharing, Zero Sum Sets, and Hamming Codes 4.6.1. Algebraic preliminaries 4.6.2. Integer residue rings 4.6.3. Zero-sum sets 4.6.3.1. Generalization to rings 4.6.4. Secret-sharing schemes 4.6.5. The scheme 4.6.6. Coding interpretation 4.6.7. Random choice attack 4.6.8. Information rate 4.6.9. Comparison with other schemes 4.6.10. Combination with Shamir’s scheme 4.6.11. Conclusions 4.7. The Least Squares Solutions in Code-Based Multisecret-Sharing Scheme 4.7.1. Introduction 4.7.2. Preliminaries 4.7.2.1. Linearcodes 4.7.2.2. Multisecret-sharing schemes 4.7.2.3. Ramp secret-sharing schemes 4.7.2.4. Symmetric matrices 4.7.2.5. Generalized inverses of matrices over a finite field 4.7.2.6. Least squares solutions 4.7.3. Multisecret-sharing schemes and least-squares solutions in linear codes 4.7.3.1. Scheme description 4.7.3.2. Statistics on coalitions 4.7.3.3. Security analysis 4.7.4. Comparison with other schemes 4.7.5. Conclusion and open problems References 5. Applications 5.1. On Key Distribution in MANETs 5.1.1. Identity-based cryptography in MANETs 5.1.1.1. Description 5.1.1.2. Pairings 5.1.1.3. Features of IBC schemes in MANETs 5.1.2. Secret-sharing schemes without trusted party 5.1.2.1. Secure secret-sharing schemes 5.1.2.2. ECDKG protocol 5.1.2.3. Properties and improvements 5.1.2.4. Protocol using a bivariate polynomial 5.1.3. Hierarchical threshold secret sharing 5.1.4. Conclusion 5.2. Absolute Time for Round-Based Timestamping Schemes 5.2.1. Introduction 5.2.1.1. Absolute versus relative temporal authentication 5.2.1.2. Existing timestamping schemes 5.2.1.3. Contribution 5.2.1.4. Related works 5.2.1.5. Organization 5.2.2. Preliminary 5.2.2.1. Notations 5.2.2.2. Cryptographic tools 5.2.3. Timestamping scheme and its security requirements 5.2.3.1. Timestamping schemes 5.2.3.2. Security requirements 5.2.4. Construction 5.2.4.1. Timestamping scheme 5.2.4.2. Main features 5.2.4.3. Totally ordered timestamping scheme with skip-list 5.2.5. Security analysis 5.2.5.1. Security preconditions 5.2.5.2. Back and forward-dating attacks 5.2.5.3. Other attacks 5.2.6. Eliminating trust in the TSA 5.2.6.1. Setup 5.2.7. Conclusion 5.3. An Image Secret-Sharing Method Based on Shamir Secret Sharing 5.3.1. Review of Shamir’s secret-sharing scheme 5.3.2. Proposed method 5.3.3. Application of some secret sharing schemes 5.3.4. Proposed scheme 5.3.5. Secret retrieval procedure 5.3.6. Advantages 5.3.7. Security analysis 5.3.8. Conclusion References Index