[Resource Topic] 2023/1373: Reframing And Extending The Random Probing Expansion

Welcome to the resource topic for 2023/1373

Reframing And Extending The Random Probing Expansion

Authors: Giuseppe Manzoni


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.

ePrint: https://eprint.iacr.org/2023/1373

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .