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 due to hardware side-channels, the $p$-random probing model has an adversary who can see the value of each wire with probability $p$. In this model, for a fixed $p$, it is 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$. An artifact of the existing proofs of the expansion is that the worst security is assumed for the input circuit. This means that a pre-compiled input circuit loses all the security guarantees of the first compilation. We reframe the expansion, and we prove it 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 prove the following statement: Given a stateless circuit on a field with characteristic $\rho$, and given a $d$-probing secure compiler for some integer $d$, we can produce a circuit with security $2^{-d}$ against any adversary that sees all wires with a constant SD-noise of $2^{-7.41}/\rho$, at the cost of an additional size factor $O(\log(d)^3)$.

Note: This revision has general readibility improvements. In particular, the definition of ERPE was changed purely for readibility reasons, and its explanation was changed and expanded. Yet the paper was shrunk nearly by half and made less dispersive by removing simple proofs and secondary lemmas, by making the remaining proofs more compact, and by keeping only the informal statement of various properties only used in proofs.