On the design and security of a lattice-based threshold secret sharing scheme

Document Type: ORIGINAL RESEARCH PAPER

Authors

1 Information Systems and Security Lab (ISSL), Department of Electrical Engineering, Sharif University of Technology, Tehran, Iran

2 Electronics Research Institute, Sharif University of Technology, Tehran, Iran

Abstract

In this paper, we introduce a method of threshold secret sharing scheme (TSSS) in which secret reconstruction is based on Babai's nearest plane algorithm. In order to supply secure public channels for transmitting shares to parties, we need to ensure that there are no quantum threats to these channels. A solution to this problem can be utilization of lattice-based cryptosystems for these channels which requires designing lattice-based TSSSs. We investigate the effect of lattice dimension on the security and correctness of the proposed scheme. Moreover, we prove that for a fixed lattice dimension the proposed scheme is asymptotically correct. We also give a quantitative proof of security from information theoretic viewpoint.

Keywords


[1] O. Goldreich, S. Goldwasser, and S. Halevi. "Public-key cryptosystems from lattice reduction problems." Advances in Cryptology CRYPTO'97, pp. 112-131, Springer Berlin Heidelberg, 1997.

[2] J. Hoffstein, J. Pipher, and J.H. Silverman. "NTRU: A ring-based public key cryptosystem." In International Algorithmic Number Theory Symposium, pp. 267-288. Springer Berlin Heidelberg, 1998.

[3] O. Regev, "On lattices, learning with errors, random linear codes, and cryptography." Journal of the ACM (JACM) vol. 56, no. 6, p. 34, 2009.

[4] A. Shamir, "How to share a secret." Communications of the ACM 22, no. 11, pp.612-613, 1979.

[5] G.R. Blakeley, "Safeguarding cryptographic keys." Proc. of the National Computer Conference, vol. 48, pp. 313-317, 1979.

[6] C. Asmuth, and J. Bloom. "A modular approach to key safeguarding." IEEE transactions on information theory, vol.30, no. 2, pp. 208-210, 1988.

[7] L. J. Pang, and Y.M. Wang. "A new multi-secret sharing scheme based on Shamir's secret sharing." Applied Mathematics and Computation, vol. 167, no. 2, pp. 840-848, 2005.

[8] K. M Martin, J. Pieprzyk, R. Safavi-Naini, and H. Wang, "Changing thresholds in the absence of secure channels." In Australasian Conference on Information Security and Privacy, pp. 177-191, Springer Berlin Heidelberg, 1999.

[9] T. P. Pedersen, "Non-interactive and informationtheoretic secure verifiable secret sharing." In Annual International Cryptology Conference, pp. 129-140. Springer Berlin Heidelberg, 1991.

[10] D. Chaum, C. Crépeau, and I. Damgard. "Multiparty unconditionally secure protocols." In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 11-19. ACM, 1988.

[11] K. Q. Nguyen and J. Traoré. "An online public auction protocol protecting bidder privacy." In Australasian Conference on Information Security and Privacy, pp. 427-442, Springer Berlin Heidelberg, 2000.

[12] B. Schoenmakers, "A simple publicly verifiable secret sharing scheme and its application to electronic voting." In Annual International Cryptology Conference, pp. 148-164. Springer Berlin Heidelberg, 1999.

[13] Thien, Chih-Ching, and Ja-Chen Lin. "Secret image sharing." Computers & Graphics, vol. 26, no. 5, pp. 765-770, 2002.

[14] H. A. Khorasgani, S. Asaad, T. Eghlidos, & M. R. Aref. "A lattice-based threshold secret sharing scheme". In 11th International ISC Conference on. Information Security and Cryptology (ISCISC), pp. 173-179, 2014.

[15] R. El Bansarkhani, and M. Meziani. "An efficient lattice-based secret sharing construction." In IFIP International Workshop on Information Security Theory and Practice, pp. 160-168. Springer Berlin Heidelberg, 2012.

[16] A. Georgescu, "A LWE-based secret sharing scheme." IJCA Special Issue on Network Security and Cryptography, NSC, no. 3, pp. 27-29, 2011.

[17] S. Asaad, H.A. Khorasgani, T. Eghlidos and M. R. Aref, "Sharing secret using lattice construction", In Telecommunications (IST), 7th International Symposium on, pp. 901-906, 2014.

[18] R. Steinfeld, J. Pieprzyk, and H. Wang. "Latticebased threshold changeability for standard Shamir secret-sharing schemes."Information Theory, IEEE Transactions on, vol. 53, no. 7, pp. 2542-2559, 2007.

[19] L. Babai, "On Lovász lattice reduction and the nearest lattice point problem." Combinatorica, vol. 6, no. 1, pp. 1-13, 1986.

[20] A. K. Lenstra, H. W. Lenstra, and L. Lovász. "Factoring polynomials with rational coefficients." Mathematische Annalen, vol. 261, no. 4, pp. 515-534, 1982.

[21] D. Micciancio, S. Goldwasser. "Complexity of Lattice Problems, A Cryptographic Perspective." 1st Ed., Springer, 2002.