Case 9:18-cv-80176-BB Document 277-1 Entered on FLSD Docket 08/27/2019 Page 1 of 4
UNITED STATES DISTRICT COURT
SOUTHERN DISTRICT OF FLORIDA
CASE NO. 18-CIV-80176-Bloom/Reinhart
IRA KLEIMAN, as personal representative of
the estate of David Kleiman, and
W&K INFO DEFENSE RESEARCH, LLC,
Plaintiffs,
v.
CRAIG WRIGHT,
Defendant.
___________________________________/
Appendix to Opinion
Case 9:18-cv-80176-BB Document 277-1 Entered on FLSD Docket 08/27/2019 Page 2 of 4
Shamir’s (n,k) threshold scheme is based on the mathematical concepts of polynomial
interpolation and modular arithmetic.1 A polynomial equation is a function in one variable (here,
the variable is x) with the following form:
f(x)=ao + a1x + a2x2 + a3x3 + . . . . akxk
The largest power of x (here, k) is the “degree” of the polynomial. A polynomial function in one
variable can be plotted as a curve in a two-dimensional coordinate plane. For example, a
polynomial function of degree 1 plots as a straight line. A polynomial function of degree 2 (also
known as a quadratic function) plots as a parabola. The precise shape of the curve depends on the
coefficients assigned to the powers of x (that is, the values for a0, a1, a2, etc.). Polynomial
interpolation is the technique of computing these coefficients so that the curve passes through a
known set of points in a plane.2
Modular arithmetic, sometimes known as “clock arithmetic,” can be thought of as the
mathematics of remainders.3 For example, on a clock, the only numbers that represent the hours
of the day are 1-12. After the 12th hour of the day, we restart the count with the number 1 (which
is the remainder after deducting 12 from 13). No number greater than 12 exists in this system. In
mathematical terms, the number that comes after 12 is not 13 (because 13 does not exist); it is “1
1
Adi Shamir, How to Share a Secret, Communications of the ACM, Vol 22, No. 11 (November
1979), p. 613.
2
MIT OpenCourseWare. Lecture notes to Chapter 3 of Numerical Analysis (Course 18.330), p.1
(“Interpolation is the problem of fitting a smooth curve through a given set of points, generally
as the graph of a function.”). [Link]
numerical-analysis-spring-2012/lecture-notes/MIT18_330S12_Chapter3.pdf.
3
[Link]
science/cryptography/modarithmetic/a/what-is-modular-arithmetic.
Case 9:18-cv-80176-BB Document 277-1 Entered on FLSD Docket 08/27/2019 Page 3 of 4
modulo 12” (abbreviated “1 mod 12”). This pattern repeats. So, the numbers that would otherwise
correspond to 25, 37, 49, 61 etc. are all equivalent to 1 mod 12.
Shamir’s (n,k) threshold scheme allows a person to use polynomial interpolation to encrypt
a number in a way that can only be decrypted by simultaneously using multiple keys. The number
of keys necessary for decryption is one more than the degree of the underlying polynomial.
Therefore, for a linear function (degree 1), two keys are necessary. For a quadratic polynomial
(degree 2), three keys are necessary.
So, to require k keys, start with a polynomial of order k-1. Then, select a finite field of
prime order p, where p is greater than k and greater than the secret number you are trying to hide.4
Here’s an example. Use the quadratic polynomial f(x)= ao + a1x + a2x2 over the finite field
consisting of the integers less than or equal to 4 – {0,1,2,3,4}. This field is denoted F5.
(1) Set a0 equal to the number you want to hide. Here, we will designate “3” as the
hidden data.
(2) Assign an integer coefficient of your choice from the finite field to each of the other
“a” terms of the polynomial. We assign a1=2 and a2=1, which gives the polynomial
function: f(x)= 3 + 2x + x2
(3) Compute f(x) for at least k values of x, where x is not equal to zero:
Ex: for x=1 f(x)=6, which is 1 mod 5
for x=2 f(x)=11, which is 1 mod 5
for x=3 f(x)=18, which is also 3 mod 5
for x=4 f(x)=27, which is 2 mod 5
(4) Designate the ordered pairs corresponding to (x, f(x)):
(1, 1) ie., when x=1, f(x) is 1 mod 5
(2, 1) ie., when x=2, f(x) is 1 mod 5
4
A finite field is a type of alegebraic structure. The number of elements of the field is its “order.”
The order of a finite field must be a prime number or a power of a prime (usually represented as
p). Michael Artin, Algebra, 1st Ed. (1991) p. 510, theorem 6.4.
2
Case 9:18-cv-80176-BB Document 277-1 Entered on FLSD Docket 08/27/2019 Page 4 of 4
(3, 3) ie., when x=3, f(x) is 3 mod 5
(4, 2) ie., when x=4, f(x) is 2 mod 5
The ordered pairs (1, 1), (2,1), (3,3), and (4,2) are the decryption keys. Anyone who has 3 or more
of these keys can compute the hidden value of a0 by plugging in the values of x and f(x), then
solving the simultaneous equations:
For (1,1), the polynomial becomes: 1= ao + a1 + a2
For (3,3), the polynomial becomes: 3= ao + 3a1 + 9a2 which is equivalent to 3= ao + 3a1 +
4a2 mod 5
For (4,2), the polynomial becomes: 2= ao + 4a1 + 16a2, which is equivalent to 2= ao + 4a1
+ a2, mod 5
You now have three equations in three variables, which can be solved using simple linear
algebra.5 The solution gives a0=3, which is the number we wanted to encrypt.
5
See generally, Gilbert Strang, Introduction to Linear Algebra, 4th Edition, (2009), Chapter 2
(explaining how to solve a system of linear equations).
3