How to Scatter a Secret?
Résumé
A mechanical probe station is a laboratory device used to physically acquire signals from the internal nodes of a chip. The station allows positioning of thin probing needles on the chip's surface, either using humanly operated manipulators or automatically.
To protect a bit k against probing, one usually encodes k as ℓ bit-shares {s j }0≤j≤ℓ−1 where {s j }0≤j≤ℓ−2 are random and s ℓ−1 = k ⊕ s 0⊕, … ⊕s ℓ−2. If each s i is stored at a different RAM location, the opponent needs to probe all the ℓ cells to learn k.
Let k = {k 0, …, k n−1} be an n-bit key recorded in an n × ℓ matrix as {s i, j }0 ≤ i ≤ n − 1, 0 ≤ j ≤ ℓ−1. To force the attacker to probe scattered data, we look for a function f mapping {i, j} to geometrical {x, y} coordinates such that, for u ≠ v, the minimal distance between r i,u and r i,v is as large as possible.
This paper solves this problem by exploiting the module structure of . We infer a theoretical lower bound on f's scattering capacity and compare the algorithm's performance with an approximate upper bound. The result is quite satisfying.