We present a secret sharing scheme whose security can be reduced to the hardness of the Learning With Errors (LWE) problem. This is a strong property since the LWE problem is believed to be very hard, as hard as worst-case lattice problems hence offering security in the quantum world. The scheme has certain technical advantages: it requires only basic operations and it allows sharing several secrets at the same time.

1. C. A. Asmuth and J. Bloom. A modular approach to key safeguarding. IEEE Transactions on Information Theory, IT-29(2):208–210, 1983.
2. G. Blakley. Safeguarding cryptographic keys. In Proc. AFIPS 1979 Natl. Computer Conf., N.Y., vol. 48, pp. 313-317, 1979.
3. D. Cash, D. Hofheinz, E. Kiltz, and C. Peikert. Bonsai trees, or how to delegate a lattice basis. In EUROCRYPT 2010.
4. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In Proc. 40th ACM Symp. on Theory of Computing (STOC), pages 197–206. 2008.
5. H. Krawczyk. Secret sharing made short. In D. R. Stinson, editor, Advances in Cryptology - CRYPTO ’93, volume 773 of Lecture Notes in Computer Science, pages 136–146. Springer-Verlag, 1994.
6. M. Mignotte. How to share a secret. In T. Beth, editor, Cryptography- Proceedings of the Workshop on Cryptography, Burg Feuerstein, 1982, volume 149 of Lecture Notes in Computer Science, pages 371–375. Springer-Verlag, 1983.
7. C. Peikert, V. Vaikuntanathan, and B. Waters. A framework for efficient and composable oblivious transfer. In CRYPTO, pages 554–571. 2008.
8. O. Regev. On lattices, learning with errors, randomlinear codes, and cryptography. Journal of the ACM, 56(6):34, 2009. Preliminary version in STOC’05.
9. O. Regev. The Learning With Errors Problem, Invited survey in CCC 2010.
10. A. Shamir. How to share a secret. Communications of the ACM 22 (1979) 612.

secret sharing learning with errors lattices