Editing Secret sharing (section)

==Multi-secret and space efficient (batched) secret sharing==
An information-theoretically secure ''k''-of-''n'' secret-sharing scheme generates ''n'' shares, each of size at least that of the secret itself, leading to the total required storage being at least ''n''-fold larger than the secret. In multi-secret sharing designed by [[Matthew K. Franklin]] and [[Moti Yung]],<ref>{{cite book |last1=Franklin |first1=Matthew |last2=Yung |first2=Moti |title=Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 |chapter=Communication complexity of secure computation (Extended abstract) |date=4 May 1992 |pages=699–710 |doi=10.1145/129712.129780 |isbn=0897915119 |s2cid=7486402 |doi-access=free }} (also available at [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.34.2764])</ref> multiple points of the polynomial host secrets; the method was found useful in numerous applications from coding to [[Secure multi-party computation|multi-party computations]]. In space efficient secret sharing, devised by Abhishek Parakh and [[Subhash Kak]], each share is roughly the size of the secret divided by {{nowrap|''k'' − 1}}.<ref>{{cite journal |last1=Parakh |first1=Abhishek |last2=Kak |first2=Subhash |title=Space efficient secret sharing for implicit data security |journal=Information Sciences |date=January 2011 |volume=181 |issue=2 |pages=335–341 |doi=10.1016/j.ins.2010.09.013}}</ref>

This scheme makes use of repeated polynomial interpolation and has potential applications in secure information dispersal on the Web and in
[[sensor networks]]. This method is based on data partitioning involving the roots of a polynomial in finite field.<ref>{{cite journal |last1=Parakh |first1=Abhishek |last2=Kak |first2=Subhash |title=Online data storage using implicit security |journal=Information Sciences |date=September 2009 |volume=179 |issue=19 |pages=3323–3331 |doi=10.1016/j.ins.2009.05.013}}</ref> Some vulnerabilities of related ''space efficient'' secret sharing schemes were pointed out later.<ref>{{cite journal | last1=Sahasranand |first1=K.R. |last2=Nagaraj | first2=Nithin | last3=Rajan | first3 = S. | title=How not to share a set of secrets | date=March 2010 |arxiv=1001.1877 |journal=International Journal of Computer Science and Information Security}}</ref> They show that a scheme based on interpolation method cannot be used to implement a {{nowrap|(''k'', ''n'')}} scheme when the ''k'' secrets to be distributed are inherently generated from a polynomial of degree less than {{nowrap|''k'' − 1}}, and the scheme does not work if all of the secrets to be shared are the same, etc.<ref>{{cite journal |last1=Liu |first1=Yanhong |last2=Zhang |first2=Futai |last3=Zhang |first3=Jie |title=Attacks to some verifiable multi-secret sharing schemes and two improved schemes |journal=Information Sciences |date=February 2016 |volume=329 |pages=524–539 |doi=10.1016/j.ins.2015.09.040}}</ref>