Secret Sharing Schemes and Advanced Encryption Standard

October 1, 2016

Naval Postgraduate School, Monterrey, California

There are many secret sharing schemes and variations available to hide and reconstruct the given secret. Shamir’s Secret Sharing Scheme, making use of linear Lagrange interpolation on the dealer-generated polynomial, was used to reconstruct the secret from the stipulated threshold number of participants’ shares. Such a scheme had been widely analyzed by mathematicians and computer scientists for potential weaknesses in the reconstruction of the secret by an external eavesdropper.

The objective of this research was to present a variation of Shamir’s threshold secret sharing scheme by manipulating the dealer-generated polynomial into a simplified version such that any eavesdropper can reconstruct the secret by gaining two public shares, instead of the stipulated threshold level. The envisaged improvements would then be evaluated for any impact on side-channel effects on the Advanced Encryption Standards.

Existing and famous mathematical conjectures (including Pillai’s conjecture, the Fermat-Catalan conjecture, and Hall’s conjecture) were built upon to seek a potential weakness in the security of the current secret sharing scheme. Essentially, the analysis aimed to reduce the order of difficulty in reconstructing the secret. Assuming that the dealer-generated polynomial is monic, it is then deconstructed by applying a composite linear function in which two additional variables are introduced.

In general, assuming that the original form of the dealer-generated polynomial is f(x) = a₀ +a₁x+a₂x² +…+a_k-1x^k-1, by composing it with the linear function g(x) = x+α, the eventual form of the dealer-generated polynomial can be manipulated to be in the form of f(x) = (x+α)^k -b₀, where both α and b₀ are the two newly introduced variables. The challenge then is reduced to finding the values of both α and b₀.

It was postulated that an eavesdropper would be able to recover the secret by simply obtaining two public shares, namely (x₁,y₁) and (x₂,y₂), from the multitude of available public shares, and this could be achieved by determining the numerical boundaries for the variable α. Specifically, all encompassing cases, without loss of generality, were considered to ensure that all possibilities were not neglected. The start state would be to take the difference between the two y-values that were easily obtained. From there on, it is just a matter of manipulating the inequalities to screen out the boundaries of α. Once the boundaries of α were found, then it would be trivial to try out the available choices for α, and subsequently b₀, and eventually the secret.

While this methodology does not allow for the absolute reconstruction of the secret as compared to Lagrange interpolation, it presents an alternate methodology for an eavesdropper to retrieve the secret using shares that are significantly less than the required threshold number. The boundaries reduced the possibilities of the secret value from a near-infinite number to a manageable cardinality size that could be derived through exhaustive means. The crux is that as long as two shares are gathered together, the value of α can be derived easily through exhaustive means. Once the value of α is found, then it remains trivial to determine b₀ through the equation y_i = (x_i+α)^k-b₀, where (x_i,y_i) are known public shares. Subsequently, the secret is reconstructed to be f(0).

This work was done by Bing Yong Lim for the Naval Postgraduate School. NPS-0001