Hard learning problems have recently attracted significant attention within the cryptographic community, both as a versatile assumption on which to build various protocols, and as a potentially sound basis for lightweight (possibly side-channel and fault resistant) implementations. Yet, in this second case, a recurrent drawback of primitives based on the Learning Parity with Noise and Learning With Errors problems is their additional randomness requirements to generate noise or errors. In parallel, the move towards nanoscale devices renders modern implementations increasingly prone to various types of errors. As a result, inexact computing has emerged as a new paradigm to efficiently deal with the challenges raised by such erroneous computations, and mitigate the cost and power consumption overheads they cause. In this paper, we show that these cryptographic and electronic challenges can actually be turned into new opportunities, and provide an elegant solution one to the other. That is, we show that inexact implementations of inner product computations lead to a natural way to define new Learning with Physical Noise or Error assumptions, paving the way to more efficient and physically secure implementations, with potential interest for securing emerging Internet of Things applications.

A recent trend in cryptography is to formally show the leakage resilience of cryptographic implementations in a given leakage model. One of the most prominent leakage model—the so-called bounded leakage model—assumes that the amount of leakage that an adversary receives is a-priori bounded. Unfortunately, it has been pointed out by several works that the assumption of bounded leakages is hard to verify in practice. A more realistic assumption is to consider that leakages are sufficiently noisy, following the engineering observation that real-world physical leakages are inherently perturbed by physical noise. While already the seminal work of Chari et al. (in: CRYPTO, pp 398–412, 1999 ) study security of side-channel countermeasures in the noisy model, only recently Prouff and Rivain (in: Johansson T, Nguyen PQ (eds) EUROCRYPT, volume 7881 of lecture notes in 931 computer science, pp 142–159, Springer, 2013 ) offer a full formal analysis of the masking countermeasure in a physically motivated noise model. In particular, the authors show that a block-cipher implementation that uses the Boolean masking scheme is secure against a very general class of noisy leakage functions. While this is an important step toward better understanding the security of masking schemes, the analysis of Prouff and Rivain has several shortcomings including in particular requiring leak-free gates. In this work, we provide an alternative security proof in the same noise model that overcomes these challenges. We achieve this goal by a new reduction from noisy leakage to the important model of probing adversaries (Ishai et al. in: CRYPTO, pp 463–481, 2003 ). This reduction is the main technical contribution of our work that significantly simplifies the formal security analysis of masking schemes against realistic side-channel leakages.