Sharing a secret using polynomials over polynomials

A method and system distributes N shares of a secret among cooperating entities by representing the secret as a secret polynomial, and forming a splitting polynomial with the secret polynomial as one or more of the coefficients. In one embodiment, the method represents the secret as a secret polynomial over GF(q), where q is a prime number or a power of a prime number. A splitting polynomial of degree (K−1) over GF(qm) is constructed, where K is the number of shares to reconstruct the secret and m is a positive integer. The coefficients of the splitting polynomial are formed with the secret polynomial and random information. The method further evaluates the splitting polynomial at N points with arithmetic defined on GF(qm) to generate the N shares of the secret.

TECHNICAL FIELD

Embodiments of the present invention relate to cryptographic techniques, and more specifically, to sharing a secret among cooperating parties.

CROSS-REFERENCE TO RELATED APPLICATIONS

The present application is related to co-filed patent application Ser. Nos. 12/200,896 and 12/200,897, both filed Aug. 28, 2008, which are assigned to the same assignee as the present application.

BACKGROUND

In cryptography, secret sharing refers to any method for distributing a secret among a group of participants, each of which is allocated one or more shares of the secret. The secret can only be reconstructed when a required number of shares are combined together; individual shares are of no use on their own.

A secure secret sharing scheme distributes shares so that anyone with fewer than the required shares has no extra information about the secret than someone with zero shares. Some secret sharing schemes allow the secret to be reconstructed by a subset of the total number of generated shares. Thus, a secret can be reconstructed even when some of the share are lost or when some of the share holders are absent.

In general, known secret sharing techniques are defined in the integer ring, which involve manipulation of integers of large sizes. Large integers are not suitable for computer operations. Thus, there is a need to develop a secret sharing technique that overcomes the above inherent limitation of the known techniques.

DETAILED DESCRIPTION

A method and system distributes N shares of a secret among cooperating entities by representing the secret as a secret polynomial, and forming a splitting polynomial with the secret polynomial as one or more of the coefficients. In one embodiment, the method represents the secret as a secret polynomial over GF(q), where q is a prime number or a power of a prime number. A splitting polynomial of degree (K−1) over GF(qm) is constructed, where K is the number of shares to reconstruct the secret and m is a positive integer. The coefficients of the splitting polynomial are formed with the secret polynomial and random information. The method further evaluates the splitting polynomial at N points with arithmetic defined on GF(qm) to generate the N shares of the secret.

An exemplary use of the secret sharing technique is a multi-factor key escrow system, where shares from a master key are given to a set of federated entities such that a subset of these shares can be used to reconstruct the master key. For example, an employee of a company in a high-security position (e.g., a corporate controller, or a human resources specialist) may have a master password that protects a secret key they need to use to authenticate on their corporate workstation. Ordinarily, this master key is only used by this employee. However, if something were to happen to this employee, his/her replacement would need to be able to gain access to this master key. As the master key provides its owner access to sensitive data, the company cannot just give a backup copy of the master key to someone for safe keeping (e.g., it would be disastrous if a disgruntled employee was able to cut himself a million dollar severance check). Thus, the master key can be split up into multiple shares, so that a share is held by each of several trusted employees. A minimum number of these trusted employees would need to present their shares and reconstruct the secret (i.e., the master key). Illustratively, one share may go to the employee's boss, and other shares may be distributed to other department heads or managers.

It should be borne in mind, however, that all of these and similar terms are to be associated with the appropriate physical quantities and are merely convenient labels applied to these quantities. Unless specifically stated otherwise, as apparent from the following discussion, it is appreciated that throughout the description, discussions utilizing terms such as “representing”, “constructing”, “generating”, “using”, “splitting”, or the like, refer to the action and processes of a computer system, or similar electronic computing device, that manipulates and transforms data represented as physical (electronic) quantities within the computer system's registers and memories into other data similarly represented as physical quantities within the computer system memories or registers or other such information storage, transmission or display devices.

FIG. 1illustrates an exemplary cryptosystem100in which embodiments of the present invention may operate. The cryptosystem100includes a plurality of recipients101and a distributor103coupled by a network102, which may be a public network (e.g., Internet) or a private network (e.g., Ethernet or a Local Area Network (LAN)). In one embodiment, each of the distributor103and recipients101is a computing system that manages secret information. Alternatively, the distributor103may be a computing system and each recipient101may be a storage device for receiving and storing one or more shares of a secret. The distributor103is locally coupled to data storage105in which a secret106is stored. Data storage105may include one or more storage devices (e.g., the computer-readable medium described above) that are local to the distributor103and/or remote from the distributor103. In alternative embodiments, the secret106may be stored in the main memory of the distributor103. In one embodiment, the secret106may be a cryptographic key, a password, or any secret data to be jointly held in escrow by the recipients101.

The secret106may be a number, a bit string, an ASCII coded text or other representations that can be converted into a sequence of numbers, with each number an element of GF(q), where q is a prime number or a positive power of a prime number. In polynomial notation, such a number sequence can be represented as a polynomial having m coefficients in GF(q). The polynomial representing the secret is herein referred to as a “secret polynomial” over GF(q). The degree of the secret polynomial is selected to be large enough to represent the secret106, e.g., at least as large as the length of the sequence of numbers that represents the secret106. For example, if the secret is a 256-bit bulk cipher key, and q=89, the degree of the secret polynomial is at least 40, and the 256-bit secret can be represented as a 39thdegree secret polynomial with coefficients in GF(89).

According to one embodiment of the present invention, coefficients of the secret polynomial over GF(q) can be combined with random information to construct another polynomial (referred as a “splitting polynomial”) over GF(qm). The order of the field GF(qm) (i.e., the number of elements in the field), which is qm, can be any prime power that is large enough to provide the necessary coefficients for the splitting polynomial. To avoid the possibility of a brute force attack, the order of the field is generally chosen to be larger than the number of allowable secrets. Thus, for a 256-bit secret and q=89, m is generally chosen to be 40 or larger. However, it is understood that the mathematics work with a smaller field (e.g., m<40 for q=89) and the operations will be faster, at the cost of some security. The generation of the splitting polynomial will be described in greater detail with reference toFIGS. 2 and 3.

The security implication of using a smaller field can be explained as follows. Assume that an attacker has all but one of the required shares for reconstruction. The attacker can attempt to “guess” the value of a missing share by picking an element from the field GF(qm) as the evaluation point, and then reconstructing the secret with every possible value from GF(qm) as the result. This is a work factor of qm—if this is smaller than the size of the set of all possible secrets, it is faster than a straight brute-force attack against the secret directly. In other words, if a 256-bit secret is to be shared in a (4, 3) scheme using GF(89m), and if the smallest possible m (=14) is chosen, an attacker in possession of two shares only needs to try 8914different combinations (8914<291<2256). An attacker with even a single share in this example is still better off than just trying to guess the secret directly—the complexity of a single share reconstruction is 8928, which is less than 2182.

To safeguard the secret106, the distributor103generates a plurality of shares of the secret106and distributes one or more shares to each of the recipients101through the network102. The secret106can be reconstructed from a subset of the distributed shares. In one embodiment, the cryptosystem100also includes a reconstructor104to reconstruct the secret106using the distributed shares. The reconstructor104collects the received shares of the secret to form interpolating polynomials, and linearly combines the interpolating polynomials to recover the splitting polynomial. The original secret can be extracted from the splitting polynomial. A person of ordinary skill in the art would appreciate that the reconstructor104may be a separate computing system as shown inFIG. 1, or, alternatively, may reside in the same computing system as the distributor103or any of the recipients101. In one embodiment, the distributor103, the recipients101and/or the reconstructor104may be, for example, servers, personal computers (PCs), mobile phones, palm-sized computing devices, personal digital assistants (PDAs), or the like.

In one embodiment, the distributor103includes a first polynomial constructor131, a second polynomial constructor132, and a polynomial operating unit133to generate the shares. The reconstructor104includes a receiving interface141to collect shares of the secret106from the recipients101, an interpolating unit142to reconstruct a splitting polynomial from the collected shares, and an extraction unit143to extract the secret from the splitting polynomial. Each of the first polynomial constructor131, the second polynomial constructor132, the polynomial operating unit133, the interpolating unit142, and the extraction unit143includes arithmetic processing units, such as adders, multipliers, random element generators, subtractors, dividers, etc., as well as memory circuitry, such as registers, RAM, etc., to perform mathematical calculations. The operations of these components will be described in greater detail below in connection withFIGS. 2-4.

In one embodiment, the distributor103distributes the shares of the secret to the recipients101using a transport-safe coding. An embodiment of the transport-safe coding transcodes (converts) the input to elements of a finite field GF(q) (where q is a prime number or a power of a prime number), in which operations of a cryptographic algorithm (e.g., secret sharing) is performed. The result of the cryptographic algorithm, which contains elements of GF(q), can be mapped directly to a transport-safe code for transporting via a communication protocol that is not safe for transporting binary values. For example, the input data stream can be transcoded into a polynomial over GF(67) if the subsequent cryptographic algorithm operates over GF(67n). After the cryptographic function is performed, the output (which is still a set of integers in the range 0-66) can be mapped into a transport character set of 67 characters. By contrast, if a standard transport coding (e.g., base-64) is used, additional conversions would be needed for transmission (as well as reception) of the data stream. With base-64 coding, the input would first have to be transcoded to a polynomial over GF(67) for the cryptographic operations. The result of the cryptographic operations would have to be converted back to a binary form, which is then transcoded to base 64 for transport.

In one embodiment where the output data stream consists of a sequence of elements from a set of q printable characters, the base q may be a prime number or a power of a prime less than 94, e.g., q may be any of the following numbers: 2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41, 43, 47, 49, 53, 59, 61, 64, 67, 71, 73, 79, 81, 83, and 89. The number 94 comes from the fact that there are 94 printable characters (such as, for example, ASCII characters). With an appropriate choice of the base q, the index values generated in the transport-safe coding can be used as the coefficients of a polynomial that represents the secret over GF(q), and the shares (containing elements of GF(q)) generated from the secret can be directly used for transport. Thus, when the secret sharing is used in tandem with the transport-safe coding, the prime number or prime power q that constructs GF(q) for secret sharing is often chosen to be the same as the base q for the transport-safe coding. However, it is understood that the secret sharing described herein does not need to be combined with transport-safe coding.

FIG. 2illustrates a flow diagram of one embodiment of a method200for generating a plurality of shares from a secret (e.g., the secret106). The method200may be performed by the processing logic526ofFIG. 5that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions on a computer readable storage medium executable by a processing device), or a combination thereof. In one embodiment, the method200is performed by the distributor103ofFIG. 1.

Referring toFIG. 2, at block210, the method200begins with the distributor103determining the total number (N) of shares to be generated and the number (K) of shares for reconstruction. Alternatively, the determination may be made by a user or an administrator of the distributor103, based on the available computing or storage resources and the available number of recipients101that can jointly hold the shares of the secret. At block220, if the secret is stored in a format other than an element of GF(q), the distributor103converts the secret into an element of GF(q). The first polynomial constructor131of the distributor103converts the secret into a secret polynomial=cdxd+ . . . +c2x2+c1x+c0. Each of the coefficients in the sequence (cd, . . . , c1, c0) is an integer in the range of (0, q−1). The secret can be converted from its original format to the sequence of coefficients by a number of different techniques. For example, if the original secret is a decimal number, the sequence of coefficients (cd, . . . , c1, c0) can be generated by repeatedly dividing the secret by q and retaining the reminders and the last quotient. If the original secret is a binary bit string, the sequence of coefficients (cd, . . . , c1, c0) can be generated by converting consecutive subsequences of the secret bit string individually. Illustratively, if q is 67, each 6 bits of the secret bit string can be grouped together to produce a coefficient that is less than 67. If p is 89, each 32 bits of the secret bit string can be grouped together to produce 5 elements of the output at a time (e.g., by repeatedly dividing the 32-bit value by 89 and retaining the remainders).

At block230, the distributor103determines the parameter m for the field GF(qm), over which a splitting polynomial for the secret is to be constructed. In one embodiment, m is chosen such that the field of characteristics q is large enough to represent the largest secret. For a secret that is represented as (cd, . . . , c1, c0), m is chosen at least as large as (d+1). For a 256-bit secret and q=89, m is chosen to be 40 or larger. The determination of the parameter m may alternatively be performed by a system administrator based on the size of the secret, the available computing resources, the desired computing speed, and the security requirements. To achieve faster computing speed, m may be chosen to be smaller than (d+1) at the expense of reduced security.

At block240, the second polynomial constructor132of the distributor103constructs a splitting polynomial over GF(qm) of degree (K−1), using the secret polynomial computed at block230and additional random elements of GF(qm). In an embodiment, the splitting polynomial may be constructed as: Ak-1Yk-1+Ak-2+ . . . +A1Y+A0, where the secret polynomial (cdxd+ . . . +c2x2+c1x+c0) is used as one of the coefficients for the splitting polynomial (e.g., A0). The other coefficients are generated as random elements of GF(qm). In alternative embodiments, the coefficients (cd, . . . , c1, c0) of the secret polynomial may be split between two or more terms of the splitting polynomial. As an example, assume that d=3 and m is chosen to be 2. The coefficients of the above splitting polynomial may be chosen as: A1=(c3x+c2), A0=(c1x+c0), and A3and A2being random elements of GF(q2). The mapping from Aito Cimay be different from what is shown in the above examples. For example, instead of mapping the secret to lower degree terms of the splitting polynomial, the secret may be mapped to one or more higher degree terms of the splitting polynomial. An alternative method for constructing a splitting polynomial is described with reference toFIG. 3.

Continuing to block250, the distributor103selects a primitive polynomial over GF(q) of degree m. A primitive polynomial over GF(q) of degree m is a polynomial with coefficients from GF(q) and roots in GF(qm), where each root is a primitive element of GF(qm). Such polynomials have characteristic properties that allow them to be identified (e.g., for a polynomial Pr of degree m, the smallest integer n that makes xn=1 (modulo Pr) true is qm−1). The primitive polynomial can be used to construct a representation of the field GF(qm). The primitive polynomial will be used to perform modulo operations during the generation of shares.

Continuing to block260, the polynomial operating unit133of the distributor103evaluates the splitting polynomial at N evaluation points, which are random elements of GF(qm). The evaluation is performed by arithmetic logic circuits of the polynomial operating unit133(e.g., adders, subtractors, multipliers and/or dividers, etc.), using arithmetic defined on GF(qm), modulo the primitive polynomial. The N evaluations generate N result values, each an element of GF(qm).

Continuing to block270, the distributor103generates N shares of the secret, with each share including one of the evaluation points and the corresponding result value. The distributor103then distributes the N shares to the recipients101and the method200terminates.

It is understood that the above operations may follow a different sequence from what is shown inFIG. 2. For example, the splitting polynomial may be constructed after the selection of the primitive polynomial.

In one embodiment, the computation performed by the above-described secret sharing technique uses arithmetic defined on GF(qm), which involves modular arithmetic over small primes. That is, polynomial operations are performed on numbers in the range of (0, q−1) to generate a result less than q. Addition in GF(qm) is defined as the term-by-term sum of the polynomial representation of the elements of GF(qm), using the rules for addition in GF(q). Multiplication in GF(qm) is defined as performing polynomial multiplication, where multiplication and addition on a term-by-term basis are as defined for GF(q), and then reducing the resulting polynomial to its remainder modulo the primitive polynomial that generates the polynomial basis for GF(qm). It is not necessary to keep track of the carries during the computation, as the addition of two corresponding polynomial terms (the same degree terms) generates no carry to a term of a higher degree (that is, the addition of the constant terms does not carry over to the 1stdegree term, the addition of the 1stdegree terms does not carry over to the 2nddegree terms, etc.). As a result, the computation can be efficiently run on constrained hardware (e.g., an embedded microcontroller), where at least some of the computation is handled by software. Software on the constrained hardware can be programmed to efficiently handle the computation of the polynomials, which involves single precision integer arithmetic over integers of a small size (limited by the size of q). If the embedded system is provided with sufficient memory (e.g., read-only memory) and the size of the base prime q is small, polynomial multiplications can be implemented with table lookups. For example, if q is 37, the lookup table size would be 37 by 37 (=1369).

The polynomial operations defined on GF(qm) can also be efficiently implemented in array processors for parallel processing. For example, multiplication of two polynomials can be implemented by processing elements of an array processor, each holding one coefficient of a first polynomial. Each time a processing element receives a coefficient of a second polynomial, it performs a multiply-and-add operation over small integers. A person of ordinary skill in the art would appreciate that other embodiments may exist for processing arithmetic operations defined on GF(qm).

FIG. 3illustrates a flow diagram of a method300for constructing a splitting polynomial, which is an alternative embodiment to the method200described at block240ofFIG. 2. The method300may be performed by the processing logic526ofFIG. 5that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions on a computer readable storage medium executable by a processing device), or a combination thereof. In one embodiment, the method300is performed by the second polynomial constructor132of the distributor103ofFIG. 1.

At block310, the second polynomial constructor132of the distributor103creates and publishes a polynomial P over GF(q) of degree b, where b is at least one greater than the largest secret to be represented. At block320, the second polynomial constructor132creates a random polynomial over GF(q) of degree (m*K−1−d). The polynomials P and R may or may not be coprime, and may or may not be irreducible. At block330, the second polynomial constructor132constructs an extended polynomial E as P*R+S (where S is the secret polynomial), modulo the primitive polynomial, using arithmetic defined on GF(qm). The extended polynomial E is a polynomial over GF(q) with degree (m*K−1). At block340, the second polynomial constructor132construct a splitting polynomial over GF(qm) of degree (K−1), using the (m*K) coefficients of the extended polynomial. In one embodiment, the (m*K) coefficients of the extended polynomial can be divided among the K terms of the splitting polynomial, such that each term gets one or more coefficients of the extended polynomial. For example, the coefficients of the extended polynomial can be evenly divided among the K terms of the splitting polynomial, such that each term gets m elements of GF(q). In the embodiment ofFIG. 3, random information is incorporated into the extended polynomial, instead of directly used as individual coefficients of the splitting polynomial (as described at block240ofFIG. 2). The method300then terminates.

Having described the techniques for share generation, the following descriptions explain, in detail, an embodiment of the technique for reconstructing the secret from K of the N distributed shares.FIG. 4illustrates a flow diagram of an embodiment of a method400for reconstructing the secret from a subset of the distributed shares. The method400may be performed by the processing logic526ofFIG. 5that may comprise hardware (e.g., circuitry, dedicated logic, programmable logic, microcode, etc.), software (such as instructions on a computer readable storage medium executable by a processing device), or a combination thereof. In one embodiment, the method400is performed by the reconstructor104ofFIG. 1.

Referring toFIG. 4, at block410, the receiving interface141of the reconstructor140receives K shares of the secret, each of the K shares including a pair of values (x, y), where x is an evaluation point and y is the corresponding result value, as described above with reference toFIG. 2. At block420, the interpolating unit142of the reconstructor140constructs K interpolating polynomials (e.g., Lagrange form basis polynomials) to interpolate the K pairs of (x, y). Each interpolating polynomial is a polynomial over GF(qm) of degree (K−1). The construction of the interpolating polynomials is performed using arithmetic defined on GF(qm), modulo the primitive polynomial. As will be illustrated in an example below, the construction of the interpolating polynomials uses the K evaluation points. At block430, the interpolating unit142computes a linear combination of the interpolating polynomials using the K result values. The result of the linear combination is the splitting polynomial used for secret sharing. At block440, the extraction unit143of the reconstructor104extracts the secret from one or more of the coefficients of the splitting polynomial and the method400terminates.

As an example, assume that K=2, and the K shares of the secrets are (x0, y0) and (x1, y1). Two Lagrange form basis polynomials are constructed as: L0(x)=(x−x1)/(x0−x1) and L1(x)=(x−x0)/(x1−x0), and the linear combination of the two polynomials is: y0L0(x)+y1L1(x). The construction of Lagrange form basis polynomials is known in the art, so details of the construction in a generalized format are not described herein. It is understood that the interpolation of the points described above can be performed by alternative techniques, such as Newton polynomials, Chebyshev polynomials, Berstein polynomials, a system of linear equations, or other techniques commonly known in the field of numerical analysis.

The following description illustrates an example of the secret sharing and reconstruction technique described above. In this example, the number of generated shares N=4, and the number of shares for secret reconstruction K=3. The secret to be shared is 8675309 (decimal), which can be converted into a secret polynomial 12x3+27x2+20x+34 over GF(89). A splitting polynomial is constructed as a polynomial over the field GF(895). The field is chosen such that the order of the field (895) is greater than the size of the secret. A primitive polynomial, which generates the field, is chosen to be x5+74x+86.

To share this secret such that three shares are required to reconstruct it, the degree of the splitting polynomial is chosen to be 2 (=K−1). That is, the splitting polynomial has three coefficients. Using the secret polynomial as one of the coefficients, two additional elements of GF(895) are needed to construct the splitting polynomial. These two additional elements can be generated as random elements of GF(895), or equivalently, polynomials over GF(89) of degree 4 or less and having random coefficients in GF(89). For example, the two coefficients may be: 74x4+66x3+11x2+21x+28 and 25x4+34x+55x2+61x+12. It is understood that the alternative embodiment ofFIG. 3may also be used to generate the splitting polynomial.

Using the three coefficients, a splitting polynomial can be constructed as:
S(Y)=(74x4+66x3+11x2+21x+28)Y2+(25x4+34x3+55X2+61x+12)Y+(12x3+27x2+20x+34).

To generate four shares, four random non-zero elements of GF(895) are generated as evaluation points, at which the splitting polynomial S(Y) is evaluated. The following elements (x1, x2, x3, x4) are used as an example: 87x4+23x3+62x2+79x+52, 3x4+60x3+3x2+18x+13, 76x4+74x3+79x+24x+68, and 50x4+8x3+16x2+7x+73.

Evaluating S(Y) at each of these elements of GF(895) produces four result values (y1, y2, y3, y4). Each evaluating point and its corresponding result value form a share. Thus, the following four shares are generated:
1stshare (x1,y1): (87x4+23x3+62x2+79x+52,79x4+76x3+47x2+35x+77),
2ndshare (x2,y2): (3x4+60x3+3x2+18x+13,58x4+63x3+39x2+29x+34),
3rdshare (x3,y3): (76x4+74x3+79X2+24x+68,5x4+51x3+57x2+16x+31), and
4thshare (x4,y4): (50x4+8x3+16x2+7x+73,66x4+26x3+15x2+63x+16).

To reconstruct the secret, three shares are collected (e.g., the first three shares). First, the Lagrange basis polynomials are constructed (where “*” indicates multiplication):

These basis polynomials are then multiplied by their corresponding result values to produce:
y1*L1(Y)=(8x4+29x3+53x2+34x+4)Y2+(84x4+13x3+44x2+76x+84)Y+(23x4+72x3+27x2+41x+45),
y2*L2(Y)=(52x4+52x3+63x2+58x+10)Y2+(74x4+74x3+70x2+15x+15)Y+(49x4+17x3+11x2+81x+44), and
y3*L3(Y)=(14x4+74x3+73x2+18x+14)Y2+(45x4+36x3+30X2+59x+2)Y+(17x4+12x3+78x2+76x+34).

These polynomials are then added to yield:

y1*L1(Y)+y2*L2(Y)+y3*L3(Y)=(74x4+66x3+11x2+21x+28)Y2+(25x4+34x3+55x2+61x+12)Y+(12x3+27x2+20x+34)==S(Y), which is the splitting polynomial. In this example, the secret polynomial can be extracted from the constant term, which is 12x3+27x2+20x+34. Evaluating the secret polynomial at 89 by using operations as defined on the integers yields the original secret, which is 8675309 in decimal representation.

The secondary memory518may include a machine-readable storage medium (or more specifically a computer-readable storage medium)531on which is stored one or more sets of instructions (e.g., software522) embodying any one or more of the methodologies or functions described herein. The software522may also reside, completely or at least partially, within the main memory504and/or within the processing device502during execution thereof by the computer system500, the main memory504and the processing device502also constituting machine-readable storage media. The software522may further be transmitted or received over a network520via the network interface device508.