Security of NewHope Under Partial Key Exposure

Recently, the work of Bolboceanu et al. (Asiacrypt ’19) and the work of Dachman Soled et al. (Mathcrypt ’19) have studied a leakage model that assumes leakage of some fraction of the NTT coordinates of the secret key in RLWE cryptosystems (or equivalently, intentionally sampling secrets with some fraction of NTT coordinates set to 0). This can be viewed as a partial key exposure problem, since for efficiency purposes, secret keys in RLWE cryptosystems are typically stored in their NTT representation. We extend this study by analyzing the security of the NewHope key exchange scheme under partial key exposure of 1∕8-fraction of the NTT coordinates of the parties’ secrets. We adopt the formalism of the decision Leaky-RLWE (Leaky-DRLWE) assumption introduced in the work of Dachman Soled et al. (Mathcrypt ’19), which posits that given leakage on a sufficiently small fraction of NTT coordinates of the secret, the remaining coordinates of the output remain indistinguishable from uniform. We note that the assumption in the work of Dachman Soled et al. (Mathcrypt ’19) is strictly weaker than the corresponding assumption in the work of Bolboceanu et al. (Asiacrypt ’19), which requires that the entire output remain indistinguishable from uniform. We show that, assuming that Leaky-DRLWE is hard for 1∕8-fraction of leakage, the shared key v (which is then hashed using a random oracle) is computationally indistinguishable from a random variable with average min-entropy 237, conditioned on the transcript and leakage, whereas without leakage the min-entropy is 256. Note that 2 ⋅ 1738 number of bits of information are leaked in this leakage model, and so the fact that any entropy remains in the shared 256-bit key is non-trivial.