Paper 2017/929
How to Securely Compute with Noisy Leakage in Quasilinear Complexity
Dahmun Goudarzi, Antoine Joux, and Matthieu Rivain
Abstract
Since their introduction in the late 90's, sidechannel attacks have been considered as a major threat against cryptographic implementations. This threat has raised the need for formal leakage models in which the security of implementations can be proved. At Eurocrypt 2013, Prouff and Rivain introduced the noisy leakage model which has been argued to soundly capture the physical reality of power and electromagnetic leakages. In their work, they also provide the first formal security proof for a masking scheme in the noisy leakage model. However their work has two important limitations: (i) the security proof relies on the existence of a leakfree component, (ii) the tolerated amount of information in the leakage (aka leakage rate) is of $O(1/n)$ where $n$ is the number of shares in the underlying masking scheme. The first limitation was nicely tackled by Duc, Dziembowski and Faust one year later (Eurocrypt 2014). Their main contribution was to show a security reduction from the noisy leakage model to the conceptually simpler randomprobing model. They were then able to prove the security of the wellknown IshaiSahaiWagner scheme (Crypto 2003) in the noisy leakage model. The second limitation was addressed last year in a paper by Andrychowicz, Dziembowski and Faust (Eurocrypt 2016). The proposed construction achieves security in the strong adaptive probing model with a leakage rate of $O(1/\log n)$ at the cost of a $O(n^2 \log n)$ complexity. The authors argue that their result can be translated into the noisy leakage model with a leakage rate of $O(1)$ by using secret sharing based on algebraic geometric codes. They further argue that the efficiency of their construction can be improved by a linear factor using packed secret sharing but no details are provided. In this paper, we show how to compute in the presence of noisy leakage with a leakage rate up to $\tilde{O}(1)$ in complexity $\tilde{O}(n)$. We use a polynomial encoding allowing quasilinear multiplication based on the fast Number Theoretic Transform (NTT). We first show that our scheme is secure in the randomprobing model with leakage rate $O(1/\log n)$. Using the reduction by Duc et al. this result can be translated in the noisy leakage model with a $O(1/\mathbb{F}^2 \log n)$ leakage rate. However, as in the work of Andrychowicz et al., our construction also requires $\mathbb{F} = O(n)$. In order to bypass this issue, we refine the granularity of our computation by considering the noisy leakage model on logical instructions} that work on constantsize machine words. We provide a generic security reduction from the noisy leakage model at the logicalinstruction level to the randomprobing model at the arithmetic level. This reduction allows us to prove the security of our construction in the noisy leakage model with leakage rate $\tilde{O}(1)$.
Metadata
 Available format(s)
 Publication info
 Preprint. MINOR revision.
 Keywords
 SideChannel AttacksNoisy Leakage ModelProvable SecurityMasking SchemeQuasilinear Complexity
 Contact author(s)
 matthieu rivain @ gmail com
 History
 20170925: received
 Short URL
 https://ia.cr/2017/929
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/929, author = {Dahmun Goudarzi and Antoine Joux and Matthieu Rivain}, title = {How to Securely Compute with Noisy Leakage in Quasilinear Complexity}, howpublished = {Cryptology ePrint Archive, Paper 2017/929}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/929}}, url = {https://eprint.iacr.org/2017/929} }