Linear Secret Sharing Schemes from Error Correcting Codes and Universal Hash Functions

详细信息    查看全文

• 作者：Ronald Cramer (15) (16)
  Ivan Bjerre Damg氓rd (17)
  Nico D枚ttling (17)
  Serge Fehr (15)
  Gabriele Spini (15) (16) (18)
  
  15. CWI ; Amsterdam ; Netherlands
  16. Mathematical Institute ; Leiden University ; Leiden ; Netherlands
  17. Department of Computer Science ; Aarhus University ; Aarhus C ; Denmark
  18. Institut de Math茅matiques de Bordeaux ; University of Bordeaux ; UMR 5251 ; Talence ; France
  
• 关键词：Linear Secret Sharing Schemes ; Linear Time Sharing ; Robust Secret Sharing
• 刊名：Lecture Notes in Computer Science
• 出版年：2015
• 出版时间：2015
• 年：2015
• 卷：9057
• 期：1
• 页码：313-336
• 全文大小：333 KB
• 参考文献：1. Cascudo, I., Damg氓rd, I., David, B., Giacomelli, I., Nielsen, J.B., Trifiletti, R.: Additively homomorphic uc commitments with optimal computational overhead (2014) (manuscript)
  2. Cascudo, I, Chen, H, Cramer, R, Xing, C Asymptotically Good Ideal Linear Secret Sharing with Strong Multiplication over Any Fixed Finite Field. In: Halevi, S eds. (2009) Advances in Cryptology - CRYPTO 2009. Springer, Heidelberg, pp. 466-486 CrossRef
  3. Cevallos, A, Fehr, S, Ostrovsky, R, Rabani, Y Unconditionally-Secure Robust Secret Sharing with Compact Shares. In: Pointcheval, D, Johansson, T eds. (2012) Advances in Cryptology 鈥?EUROCRYPT 2012. Springer, Heidelberg, pp. 195-208 CrossRef
  4. Chen, H, Cramer, R, Goldwasser, S, Haan, R, Vaikuntanathan, V Secure Computation from Random Error Correcting Codes. In: Naor, M eds. (2007) Advances in Cryptology - EUROCRYPT 2007. Springer, Heidelberg, pp. 291-310 CrossRef
  5. Cramer, R, Damg氓rd, IB, Fehr, S On the Cost of Reconstructing a Secret, or VSS with Optimal Reconstruction Phase. In: Kilian, J eds. (2001) Advances in Cryptology - CRYPTO 2001. Springer, Heidelberg, pp. 503-523 CrossRef
  6. Cramer, R, Damg氓rd, IB, Maurer, UM General Secure Multi-party Computation from any Linear Secret-Sharing Scheme. In: Preneel, B eds. (2000) Advances in Cryptology - EUROCRYPT 2000. Springer, Heidelberg, pp. 316-334 CrossRef
  7. Cramer, R, Dodis, Y, Fehr, S, Padr贸, C, Wichs, D Detection of Algebraic Manipulation with Applications to Robust Secret Sharing and Fuzzy Extractors. In: Smart, NP eds. (2008) Advances in Cryptology 鈥?EUROCRYPT 2008. Springer, Heidelberg, pp. 471-488 CrossRef
  8. Damg氓rd, I., David, B., Giacomelli, I., Nielsen, J.B.: Compact vss and efficient homomorphic uc commitments. Cryptology ePrint Archive, Report 2014/370 (2014) (to appear in AsiaCrypt 2014)
  9. Druk, E., Ishai, Y.: Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications. In: ITCS, pp. 169鈥?82 (2014)
  10. Garay, JA, Ishai, Y, Kumaresan, R, Wee, H On the Complexity of UC Commitments. In: Nguyen, PQ, Oswald, E eds. (2014) Advances in Cryptology 鈥?EUROCRYPT 2014. Springer, Heidelberg, pp. 677-694 CrossRef
  11. Guruswami, V, Indyk, P (2005) Linear-time encodable/decodable codes with near-optimal rate. IEEE Transactions on Information Theory 51: pp. 3393-3400 CrossRef
  12. Guruswami, V., Rudra, A.: Explicit capacity-achieving list-decodable codes. In: STOC, pp. 1鈥?0 (2006)
  13. Guruswami, V, Wang, C (2013) Linear-algebraic list decoding for variants of reed-solomon codes. IEEE Transactions on Information Theory 59: pp. 3257-3268 CrossRef
  14. Guruswami, V., Xing, C.: Optimal rate list decoding of folded algebraic-geometric codes over constant-sized alphabets. In: SODA, pp. 1858鈥?866 (2014)
  15. Impagliazzo, R., Levin, L.A., Luby, M.: Pseudo-random generation from one-way functions (extended abstracts). In: Proceedings of the 21st Annual ACM Symposium on Theory of Computing, Seattle, Washigton, USA, May 14鈥?7, pp. 12鈥?4 (1989)
  16. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge from secure multiparty computation. In: Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11鈥?3, pp. 21鈥?0 (2007)
  17. Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Cryptography with constant computational overhead. In: STOC, pp. 433鈥?42 (2008)
  18. Ishai, Y, Prabhakaran, M, Sahai, A Founding Cryptography on Oblivious Transfer 鈥?Efficiently. In: Wagner, D eds. (2008) Advances in Cryptology 鈥?CRYPTO 2008. Springer, Heidelberg, pp. 572-591 CrossRef
  19. Krawczyk, H Secret Sharing Made Short. In: Stinson, DR eds. (1994) Advances in Cryptology - CRYPTO 鈥?3. Springer, Heidelberg, pp. 136-146 CrossRef
  20. Mansour, Y., Nisan, N., Tiwari, P.: The computational complexity of universal hashing. In: Proceedings: Fifth Annual Structure in Complexity Theory Conference, Universitat Polit猫cnica de Catalunya, Barcelona, Spain, July 8鈥?1, p. 90 (1990)
  21. Massey, J.L.: Some applications of coding theory in cryptography. In: Codes and Ciphers: Cryptography and Coding IV, pp. 33鈥?7 (1995)
  22. Mitzenmacher, M, Upfal, E (2005) Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York CrossRef
  23. Shamir, A (1979) How to share a secret. Commun. ACM 22: pp. 612-613 CrossRef
  24. Spielman, D.A.: Linear-time encodable and decodable error-correcting codes. In: Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, Las Vegas, Nevada, USA, 29 May-1 June, pp. 388鈥?97 (1995)
  
• 作者单位：Advances in Cryptology - EUROCRYPT 2015
• 丛书名：978-3-662-46802-9
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349

文摘

We present a novel method for constructing linear secret sharing schemes (LSSS) from linear error correcting codes and linear universal hash functions in a blackbox way. The main advantage of this new construction is that the privacy property of the resulting secret sharing scheme essentially becomes independent of the code we use, only depending on its rate. This allows us to fully harness the algorithmic properties of recent code constructions such as efficient encoding and decoding or efficient list-decoding. Choosing the error correcting codes and universal hash functions involved carefully, we obtain solutions to the following open problems: A linear near-threshold secret sharing scheme with both linear time sharing and reconstruction algorithms and large secrets (i.e. secrets of size \(\Omega (n)\) ). Thus, the computational overhead per shared bit in this scheme is constant. An efficiently reconstructible robust secret sharing scheme for \(n/3 \le t corrupted players (for any constant \(\epsilon > 0\) ) with shares of optimal size \(O(1 + \lambda / n)\) and secrets of size \(\Omega (n + \lambda )\) , where \(\lambda \) is the security parameter.