Secret Sharing in APL

Published: Jul 22, 2025.

Introduction

Years ago, my first exposure to array-based programming was the J Language. I never got around to learning it enough to write anything but one-liners. Recently I got sucked into the original array language, APL, after seeing it mentioned on Hacker News many times. APL is one of the few languages that fundamentally rewires your brain. While it may have limited practical utility today, it’s enormous fun to learn to think about problems in a completely new way. I wanted to write an actual program in APL and chose to implement the polynomial-based secret sharing algorithm described in Jeremy Kun’s excellent book A Programmers Introduction to Mathematics.

The code in this post is written in Dyalog APL.

Polynomials

Let’s start with a basic theorem about polynomials: Given \(n+1\) points, there is a unique \(n\) degree polynomial that passes through all of them. The proof of this is in Chapter 1 of Jeremy Kun’s book, or can be found all over the internet by searching for “polynomial interpolation”. The actual polynomial for a set of points is described by a clever construction known as the Lagrange polynomial. If \((x_i, y_i)\) are the given points, the polynomial is:

\[ f(x) = \sum_{i=0}^{n} y_i \left(\prod_{j \ne i}\frac{x - x_j}{x_i - x_j}\right)\]

Our first task is to implement polynomial construction in APL. We’ll represent the \(n+1\) points as a 2-row matrix. For example, here are some points for the polynomial \(f(x) = x^2\).

p ← 2 3 ⍴ 4 5 9 16 25 81
p

Output:

4  5  9
16 25 81

We can break down the formula into a couple of parts: on the outside there is an inner-product of the \(y_i\) vector with a vector of polynomials that we’ll call \(l_j(x)\), following the lead of the Wikipedia article on Lagrange polynomials.

The key pattern to notice is that each \(l_j(x)\) is meant to be non-zero when \(x = x_j\) and zero everywhere else. Thus in every term one of the \(x\)’s is “special”. In APL we can express this by considering all rotations of the \(x_j\) vector (1⌷⍺) and treating the first element as the special one.

{⍵⌽x}¨(⍳≢x)-1⊣x←1⌷p

Output

┌─────┬─────┬─────┐
│4 5 9│5 9 4│9 4 5│
└─────┴─────┴─────┘

We can now write a function that given a set of points evaluates the interpolated polynomial at a certain \(x\) (p poly x). The key statement is: given the array of rotations (r), compute the \(l_j(x)\) by applying the function ({×/(pt-1↓⍵)÷(1↓⍵-⊃⍵)}) to all of them, then further evaluate the entire polynomial at the given point (pt).

]dinput
poly←{
  x←1⌷⍺
  y←2⌷⍺
  r←{⍵⌽x}¨(⍳≢x)-1
  ⊃⊃{
      pt←⍵
      l←{×/(pt-1↓⍵)÷(1↓⍵-⊃⍵)}¨r
      y+.×l
  }⊂⍵
}

We can confirm our implementation is correct by evaluating p at a few different points.

p poly 3 8 7 1

Output:

9 64 49 1

Splitting a secret

We can use the uniqueness property of a polynomial to split a secret into 𝑛 pieces such that it can only be reconstructred if all the \(n\) pieces are available. This makes it ideal for situations such as the location of pirate treasure that should only be found if all the descendants of the pirate look for it together.

It works like this: let \(s\) be an integer that you wish to keep secret. To split it into \(n\) pieces, generate a polynomial with \(n-1\) random co-efficients, with the co-efficient for \(x_0\) being \(s\). For example, if we wish to split the secret into three parts, the polynomial would be:

\[f(x) = a_2x^2 + a_1x + s\]

where \(a_2\) and \(a_1\) are generated randomly. Notice that this polynomial has the property that \(f(0) = s\).

If you now compute \(f(1)\), \(f(2)\), and \(f(3)\) and distribute them to your secret keepers, they can in the future come together and reconstruct the exact same polynomial by putting their pieces together and recover the secret by computing \(f(0)\).

In APL

First we need a utility function that evaluates a polynomial represented as an array of co-efficients (e.g., (4 2 7) means \(4x^2 + 2x + 7\)). This is evalAt.

evalAt←{(⍵*(⍳≢⍺)-1)+.×⍺}
(4 2 7) evalAt 1

13

We can generate n random co-efficients by using “deal” (?) – the 256 just keeps things readable by limiting co-efficients to the range 0-256.

5 ? 256

164 227 148 250 241

So to split a secret, say 157 into three parts we can do:

p1←{r evalAt ⍵}¨⍳3⊣(r←157,2?256)
p1

398 649 910

Given these three pieces, we can combine them together to interpolate the polynomial and recover the secret by evaluating it at \(0\).

s1←(2 3)⍴(1 2 3)⍪p1
s1 poly 0

157

To split a string secret into \(𝑛\) pieces we just need two more things:

1. Turn a string into an array of numbers by using the ⎕UCS function.
2. Apply the above splitting algorithm to each letter of the string.

Each of the \(n\) pieces of the secret will now be an array of integers with each integer corresponding to one piece of the polynomial for one letter of the string.

]dinput
splitSecret←{
    evalAt←{(⍵*(⍳≢⍺)-1)+.×⍺}
    ⍝ d rpoly <str>
    d←⍺-1
    rpoly←{(⎕UCS ⍵)⍪(⍺,≢⍵)⍴(⍺×≢⍵)?256}
    r←d rpoly ⍵
    ↑{r evalAt ⍵}¨⍳⍺
}

3 splitSecret 'Marlinspike Hall'

374  414  336 263 161  477 241  339  385 206  387  339 160  534  496  390
1139  879  902 420 309 1344 491  778  761 323 1109 1064 292 1385 1260  926
2372 1492 1812 579 549 2711 865 1429 1233 458 2267 2207 468 2650 2400 1716

Reconstructing the secret

Reconstruction of the secret is relatively simpler. We need to consider each column in the secret matrix above as values of \(f(1)\), \(f(2)\), … of an unknown polynomial. By constructing the polynomial and evaluating \(f(0)\) we recover one letter of the string. Applying the same method to all the columns we recover the whole string.

]dinput
joinSecret←{
    d←⊃⍴⍵         ⍝ degree
    ⎕UCS{ps←(2 d)⍴((⍳d),⍵)
        ps poly 0  ⍝ f(0) for each letter
    }⍤1⊣⍉⍵
}

secret ← 3 splitSecret '20|37|42|N|70|52|15|W'
secret

365  486  429  443  232  354  387  435  505  414  363  314  434  249  499  316
836 1404 1102 1167  751  656 1172 1114 1396 1016  682  891 1292  604 1447  960
1463 2802 2143 2223 1612 1030 2407 2087 2797 1884 1081 1786 2622 1189 2897 1982

joinSecret secret

20|37|42|N|70|52|15|W

Reflections on APL

I’ve learned two things from this brief foray into APL. First, APL makes you think of very different computational processes. In SICP there is a distinction made between a procedure, the collection of symbols that make up the code, and a process, which is a dynamic creature conjured up by the procedure.

In a pure functional language the processes are all recursive. In an imperative language like C the “process” is essentially a Turing machine (or the Von Neumann machine). APL makes you imagine a new kind of process – that of functions applied to arrays, the arrays sliced, transposed, and manipulated in a hundred ways.

Second, maybe APL can give you more insight into the problem. It took me a whole day of intermittent thinking to come up with the 20 lines or so code to implement secret sharing. If nothing else, it’s nice to spend most of one’s time thinking about a problem rather than typing code. I’ve seen some amazingly concise APL programs (like this Game of Life) and I suspect that the benefit of “thinking over typing” becomes even more pronounced as the program complexity grows.

I also think that being forced to come up with the “all rotations of \(x_i\)” trick made me better understand the Lagrange polynomial formula. In Python I would have just typed in the i != j formula and forgotten why it works in a couple of days. Having to write code while thinking of the entire \(x_i\) array made the pattern more clear to me. We’ll see if I remember it in six months. 🤷

If you want to learn some APL, Getting Started with APL has the all resources you need.

Afterword

I wrote this code in Aug 2021 and published it here in Jul 2025. In the intervening four years I had not looked at this code nor written any more APL. Predictably, none of this code makes any sense to me.

Granted, I only spent a few days learning APL and that’s not enough time to fully rewire my brain. However, I’ve learnt maybe two dozen languages to this level over the course of 20 years of programming, and I can definitely read a simple program like this in all of them.

Array programming is an obviously useful paradigm, especially for Machine Learning, as proven by the success of libraries like NumPy and PyTorch, but I can’t buy the argument that the terse syntax of languages like APL, J, or K is a good idea, no matter how much I try.