Patent ID: 8615084
Filing Date: 2013-12-24
Classification: H04L

Abstract:
1. A method comprising: creating a plurality of moduli, wherein the plurality of moduli comprises a plurality of random bit strings; determining, by a computer system, a bit length to use to construct an extended secret bit string, wherein the bit length of the extended secret bit string is at least one bit shorter than a product of a first number of the plurality of moduli and at least one bit longer than a product of a second number of the plurality of moduli, and wherein the first number is a number of shares to reconstruct a secret bit string, and the second number is the first number minus one; generating, by the computing system, a first bit string comprising a bit length at least one bit longer than a number of bits in the secret bit string, the first bit string corresponding to a first polynomial and the secret bit string corresponding to a second polynomial; generating a second bit string comprising the bit length of the extended bit string minus the bit length of the first bit string, wherein the second bit string corresponds to a third polynomial; determining a product of the first bit string and the second bit string as polynomials to form the extended secret bit string, the extended secret bit string corresponding to a fourth polynomial; adding the secret bit string to the product; and generating a plurality of shares to distribute from the extended secret bit string.