Paper 2023/1373

Reframing And Extending The Random Probing Expandibility To Make Probing-Secure Compilers Tolerate A Constant Noise

Abstract

In the context of circuits leaking the internal state, there are various models to analyze what the adversary can see, like the $p$-random probing model in which the adversary can see the value of each wire with probability $p$. In this model, for a fixed $p$, it's possible to reach an arbitrary security by 'expanding' a stateless circuit via iterated compilation, reaching a security of $2^{-\kappa}$ with a polynomial size in $\kappa$. The existing proofs of the expansion work by first compiling the gadgets multiple times, and then by compiling the circuit with the resulting gadgets while assuming the worst from the original circuit. Instead, we reframe the expansion as a security reduction from the compiled circuit to the original one. Additionally, we extend it to support a broader range of encodings, and arbitrary probabilistic gates with an arbitrary number of inputs and outputs. This allows us to obtain two concrete results: (i) At the cost of an additional size factor $\mathcal{O}(\log(d)^3)$, any $d$-probing secure compiler can be used to produce stateless circuits with security $2^{-d}$ against any adversary that sees all wires with a constant SD-noise of $2^{-7.41}/p$, where $p$ is the characteristic of the circuit's field. (ii) Any $n$-shares compiler with $(t,f)$-RPE gadgets needs $t+1$ (which in practice is $\lceil\frac{n}{2}\rceil$) randoms in the random gadget instead of $n$.

Note: This revision contains general readibility improvements. This includes a changed title to better suit the paper; additional images to show the relationship of the various definitions and lemmas; a changed name for the new RPS defition to avoid homonyms; the concrete compilers were moved outside the proofs; a brief conclusion was added; some concepts were clarified better; ...