On Aug 8, 2015, at 11:40 AM, David McClain <DBM@REFINED-AUDIOMETRICS.COM> wrote:

Here’s another snippet of code that I use from time to time. The idea is (N,M)-way Secret Sharing, where there are N fragments of a secret key, and it takes (M <= N) of them to come together before it can be reconstructed. I do this by computing an (M-1)’th order random polynomial over the field used by the underlying crypto, which goes through my secret Y value at the origin X = 0, and pass out N randomly chosen points along that polynomial curve to friendly parties.

Nothing can be obtained about the secret, nominally the ordinate value at the origin of coordinates, until at least M of these ordinates come together. Lagrange interpolation over the field is used to recompute the ordinal value at the chosen secret key location (nominally defaults to the origin, but you can choose anywhere for yourself).

(defun ecc-make-lagrange-interpolator (shares)

  (labels ((lprod (x xs)

             (reduce (lambda (prod x2)

                       (mult-mod *ecc-r* prod (sub-mod *ecc-r* x2 x)))

                     xs

                     :initial-value 1)))

    (lambda (x0)

      (labels ((term (sum share)

                 (um:bind* ((:struct-accessors crypto-share (x y) share)

                            (xs (mapcar 'crypto-share-x (remove share shares))))

                   (ecc-add sum

                            (ecc-mul y (div-mod *ecc-r*

                                                (lprod x0 xs)

                                                (lprod x xs)) )) )))

        (reduce #'term shares

                :initial-value (ecc-infinity) )))))

(defun ecc-solve-lagrange (shares &optional (x 0))

  (let ((fn (ecc-make-lagrange-interpolator shares)))

    (funcall fn x)))

It is so easy and clean to do in Lisp. The underlying arithmetic, shown here as Elliptic Curve arithmetic. But you can easily recode this to work over a Galois field, as shown here:

(defstruct crypto-share

  x y)

(defun make-gf-lagrange-interpolator (shares)

  (labels ((lprod (x xs)

             (reduce (lambda (prod x2)

                       (gf* prod (gf+ x2 x)))

                     xs

                     :initial-value 1)))

    (lambda (x0)

      (labels ((term (sum share)

                 (with-accessors ((x crypto-share-x)

                                  (y crypto-share-y)) share

                   (let ((xs (mapcar #'crypto-share-x (remove share shares))))

                     (gf+ sum

                          (gf* y (gf/ (lprod x0 xs)

                                      (lprod x xs)) )) ))) )

        (reduce #'term shares

                :initial-value 0))) ))

(defun solve-gf-lagrange (x0 &rest shares)

  (let ((fn (make-gf-lagrange-interpolator shares)))

    (funcall fn x0)))

In general, whatever field you choose to work over, you can take the same basic Lagrange interpolation skeletal structure shown here to compute a secret-sharing. You see the strong similarity between the Galois field version and the Elliptic Curve version. For Elliptic Curves, you need either a curve point (x,y) (different field than the interpolation polynomial), or else just use the X or the Y value of the ECC point, or an encoding of the point like an Elligator-2 value. Doesn’t really matter how you do it.

To be clear, a share is an (X, Y) pair on a 2-D manifold over some finite field. Knowing M of these points specifies exactly the (M-1)’th order polynomial that interpolates through those points. And your secret is the ordinate value at some special abscissa value along that interpolating polynomial.

No my idea at all. This goes back to Rivest as well. Very bright guy! Lisp makes it so easy to do.

- DM