( 16th August 2019 )
One of these techniques, known as secret sharing made short, combines Rabin's information dispersal algorithm (IDA) with Shamir's secret sharing. Data is first encrypted with a randomly generated key, using a symmetric encryption algorithm. Next this data is split into N pieces using Rabin's IDA. This IDA is configured with a threshold, in a manner similar to secret sharing schemes, but unlike secret sharing schemes the size of the resulting data grows by a factor of (number of fragments / threshold). For example, if the threshold were 10, and the number of IDA-produced fragments were 15, the total size of all the fragments would be (15/10) or 1.5 times the size of the original input. In this case, this scheme is 10 times more efficient than if Shamir's scheme had been applied directly on the data. The final step in secret sharing made short is to use Shamir secret sharing to produce shares of the randomly generated symmetric key (which is typically on the order of 16?32 bytes) and then give one share and one fragment to each shareholder.
A related approach, known as AONT-RS, applies an All-or-nothing transform to the data as a pre-processing step to an IDA. The All-or-nothing transform guarantees that any number of shares less than the threshold is insufficient to decrypt the data.
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 that the secret. In multi-secret sharing designed by Matthew K. Franklin and Moti Yung, multiple points of the polynomial host secrets; the method was found useful in numerous applications from coding to multi-party computations. In space efficient secret sharing, devised by Abhishek Parakh and Subhash Kak, each share is roughly the fraction (k-1) of the size of the secret.
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. Some vulnerabilities of related space efficient secret sharing schemes were pointed out later. They show that a scheme based on interpolation method cannot be used to implement a (k, n) scheme when the k secrets to be distributed are inherently generated from a polynomial of degree less than k 1, and the scheme does not work if all of the secrets to be shared are the same, etc.
Other uses and applications
A secret sharing scheme can secure a secret over multiple servers and remain recoverable despite multiple server failures. The dealer may act as several distinct participants, distributing the shares among the participants. Each share may be stored on a different server, but the dealer can recover the secret even if several servers break down as long as they can recover at least t shares; however, crackers that break into one server would still not know the secret as long as fewer than t shares are stored on each server.
This is one of the major concepts behind the Vanish computer project at the University of Washington, where a random key is used to encrypt data, and the key is distributed as a secret across several nodes in a P2P network. In order to decrypt the message, at least t nodes on the network must be accessible; the principle for this particular project being that the number of secret-sharing nodes on the network will decrease naturally over time, therefore causing the secret to eventually vanish. However, the network is vulnerable to a Sybil attack, thus making Vanish insecure.
Any shareholder who ever has enough information
Note also that any shareholder who ever has enough information to decrypt the content at any point is able to take and store a copy of X. Consequently, although tools and techniques such as Vanish can make data irrecoverable within their own system after a time, it is not possible to force the deletion of data once a malicious user has seen it. This is one of the leading conundrums of Digital Rights Management.
A dealer could send t shares, all of which are necessary to recover the original secret, to a single recipient. An attacker would have to intercept all t shares to recover the secret, a task which is more difficult than intercepting a single file, especially if the shares are sent using different media (e.g. some over the Internet, some mailed on CDs).
For large secrets, it may be more efficient to encrypt the secret and then distribute the key using secret sharing. Secret sharing is an important primitive in several protocols for secure multiparty computation.
Comments