Optimal Amplification of Noisy Leakages

摘要

During the last 15 years there have been intensive research efforts in constructing cryptographic algorithms resilient to the side-channel leakage. The most fundamental part of every such construction are the leakage-resilient encoding schemes. Usually the cryptographic secrets encoded by them are assumed to belong to some finite group (G,+). The most common encoding scheme is the n-out-of-n additive secret sharing: a secret X is encoded as (X_1,...,X_n) such that X_1 + ...X_n = X. Intuitively, if an adversary receives only small partial independent information about each X_i then his information about X should be even smaller, and should decrease (i.e. the noise should amplify) when n grows. However, of course, the concrete parameters (the amount of leakage that can be tolerated, and the number of shares needed to achieve a given level of security) depend on the exact model that is used. One of the most prominent models used in this area is the so-called noisy-leakage model (Chari et al., CRYPTO'99, and Prouff and Rivain, EUROCRYPT'13), which is believed to correspond well to the real-life engineering experience, where the information that the adversary receives is always "noisy". In the Prouff and Rivain model the amount of information that the noise provides is measured using a parameter 5 that is equal to 0 when the noise is "full", and equal to 1 when there is no noise. It is natural to ask how small 5 needs to be to achieve the amplification of noise (in the additive encoding scheme described above). Until now it was known that such amplification can be achieved for δ ＜ 1/16. In this paper we show that: 1. in the prime order groups G it suffices that δ ＜ 1 - 1/|G|, 2. in general it suffices that 6 ＜ 1/2. We also prove that these bounds are optimal. We then analyze the number n of shares needed to achieve security ∈ of the encoded value X (where ∈ is also defined in terms of "noisy information" that the adversary obtains about X). We give close lower and upper bounds on this value (that differ only in factor polylogarithmic in |G|). We achieve our results using techniques from the additive combinatorics, the harmonic analysis, and the convex optimization.