RubikFHE: Solving a Rubik's Cube Under CKKS

RubikFHE solves a Rubik’s cube that the server never sees. The client encrypts the colors of the 54 stickers under CKKS, the server evaluates a fixed circuit on the ciphertexts, and the client decrypts a sequence of moves that solves its cube. This article only describes that circuit: how solving a cube becomes a branch-free computation, how it is laid out in the slots, and where the bootstrappings go.

A solver without branches

Usual solvers search. Thistlethwaite, Kociemba or IDA* all look up the current state in a table and choose the next move from the result. Under encryption the server can neither index a table with an encrypted value nor branch on one: whatever it computes, it computes for every possible cube, and the circuit must have the same shape for all of them.

RubikFHE uses a stabilizer chain of the cube group instead. It tracks 18 cubies in a fixed order: 11 edges (UR, UF, UL, UB, DR, DF, DL, DB, FR, FL, BL), then 7 corners (URF, UFL, ULB, UBR, DFR, DLF, DBL). The last edge and the last corner need no stage: once the others are home, they are too. Stage $i$ brings cubie $i$ home without disturbing the cubies placed before it.

When stage $i$ starts, its cubie is at one of $|\Omega_i|$ oriented locations: 24 for the first edge (12 positions, 2 orientations each), 22 for the second, down to 4 for the last tracked edge, then 24, 21, …, 3 for the corners. For each location $a$ there is a public correction $c_{i,a}$, a move word that sends the cubie home and fixes every cubie placed before it. The product of the orbit sizes is the order of the cube group, $43\,252\,003\,274\,489\,856\,000$, so every legal cube is solved by exactly one sequence of 18 corrections.

The corrections are computed once, in the clear, with Schreier–Sims. Each one is the shortest word of at most six moves when there is one, and otherwise comes from a plaintext solver. All the words of stage $i$ are padded with no-op tokens to the longest of them, $L_i$, which ranges from 3 for the first edges to 33. The output is always 378 tokens, each a code from 0 (no-op) to 18 (one of the 18 face turns).

Write the location of cubie $r$ as a one-hot vector $x_r \in \{0,1\}^{24}$, and let $s = x_i$, restricted to the orbit, be the selector of stage $i$. The stage computes

$$t_{i,\ell} = \sum_{a} s_a \cdot \mathrm{code}(c_{i,a})_\ell, \qquad x_r' = \sum_{a} s_a \, P_{i,a}\, x_r \quad (r > i),$$

where $P_{i,a}$ is the $24 \times 24$ permutation matrix of $c_{i,a}$ acting on edge or corner locations. Exactly one $s_a$ equals 1, so the stage emits the word the plaintext solver would pick and applies the matching correction to every later cubie. The tokens are linear in the selector and the update is bilinear in the selector and the state: one multiplicative level per stage, with no comparison and no lookup.

Encoding the stickers

Cubie $r$ sits at oriented location $x$ exactly when the first facelet of $x$ shows the cubie’s first color and the next facelet shows its second color. Two adjacent stickers, read in the cubie’s reference order, are enough to identify an edge or a corner and its orientation. So $x_r[x] = u \cdot v$, where $u$ and $v$ are one-hot sticker bits that the client copies to public positions. The client encrypts these two ciphertexts and does no cube reasoning; the server’s first operation is their product.

One stage in the slots

With $N = 2^{16}$, a ciphertext has $2^{15}$ slots, split into 32 blocks of $32 \times 32$. Each tracked cubie owns a block: its 24-entry vector is stored along one axis and copied along the other. Edges take the even blocks and corners the odd ones, so the 18 cubies fit in 22 blocks and the whole state is a single ciphertext. A stage then runs:

1. A mask isolates the block of cubie $i$, and an inner sum copies it into all 32 blocks.
2. A linear transform with public diagonals turns the selector into the transition matrix $S[y \to z] = \sum_a s_a [\pi_a(y) = z]$ in every block, where $\pi_a$ is the action of $c_{i,a}$ on edges in the edge blocks and on corners in the corner blocks.
3. One product with the state puts $S[y \to z] \cdot x_r[y]$ at position $(y, z)$ of block $r$.
4. Folding along $y$ with rotations and additions leaves $x_r'[z]$ along the other axis. A mask and a replication restore the block layout. The two axes swap roles at every stage, so the circuit never needs a transpose, and the same fold already contains the next selector.

The tokens are the replicated selector times a plaintext of codes, summed into one token ciphertext per orientation. A stage costs a plaintext product for the gather (24 bits, the precision of the public plaintexts), a ciphertext product (35 bits, the scale) and a mask (24 bits): 83 bits of modulus.

The bootstrapping schedule

A fresh ciphertext has 524 bits of modulus, and the product $u \cdot v$ leaves 489. The first stage also pays 24 bits to isolate its selector, so after four stages 133 bits remain: the 35 bits of the scale plus the 98 bits the bootstrapping needs to read its input. Stage 4 cannot run on that, so the state is bootstrapped. A refreshed ciphertext has 489 bits again, sized for exactly four more stages. The bootstrappings therefore fall before stages 4, 8, 12 and 16: four per solve, each on a single ciphertext since the whole state lives in one. The last stage only emits tokens, a single plaintext product, so the final segment needs no fifth bootstrapping.

The selector and the state carry the same error into a bilinear map, so the error on the one-hot values roughly doubles at every stage, and accumulates. Under the secure parameters, the state error grows from about $3 \cdot 10^{-7}$ after the first stage to $3 \cdot 10^{-4}$ by the fourth. A bootstrapping that only restores the modulus would carry this error forward. Each bootstrapping here also rounds the values back to 0 and 1, which squares the error: the state starts every new segment at about $3 \cdot 10^{-6}$.

Four stages per bootstrapping is a memory choice as much as a noise one. It keeps the working modulus of the bootstrapping at 1009 bits, below about 1060 bits, where every bootstrapping key needs three gadget digits instead of two. That saves a third of the key memory, which is worth more than the extra bootstrappings that narrower ciphertexts require.

Getting the moves back

A final fold collects the tokens at fixed positions of the two output ciphertexts. The client decrypts them, rounds 378 slots to integers (the worst error is about $2 \cdot 10^{-3}$, far from the $1/2$ that would flip a code), drops the no-ops and merges consecutive turns of the same face. On the server, every cube costs the same 18 stages and 4 bootstrappings, including an already solved one, which simply decrypts to 378 no-ops.