Common Notation

Learning with Physical Rounding (LWPR)

Propose Edit

Updated:

Learning with Physical Rounding (LWPR) was introduced by Duval, Méaux, Momin, and Standaert in 2021 [1]. The assumption is motivated by the security and efficiency of fresh re-keying, which is a countermeasure against side-channel analysis. The LWPR problem attempts to formalise this security in a practically-relevant model where the adversary can observe noise-free leakages. It can be viewed as a physical version of the Learning With Rounding problem, where the rounding is performed by a leakage function.

Definition

LWPR\(_{n,m,p,\mathsf{L}_g}\)

Let \(p\) be prime and \(\mathsf{L}_g: \ZZ_p^m \rightarrow \RR^d\) define a physical rounding function. Fix some \(\mat{K} \in \ZZ_p^{m \times (n+1)}\) and sample \(\vec{r} \sample \ZZ_p^n\). An adversary is asked to recover \(\mat{K}\) given samples from the distribution

\[\left( \vec{r}, \mathsf{L}_g \left( \mat{K} \cdot \begin{bmatrix} \vec{r} \\ 1 \end{bmatrix} \right) \right).\]

Hardness

The work of Duval et al. [1] analyses LWPR for the specific case of Hamming weight leakage. They provide a few insecure choices and propose a first cryptanalysis target. Subsequent work by Hoffmann, Méaux, Momin, Rotella, Standaert, and Udvarhelyi [2] generalise the security of LWPR beyond Hamming weight leakage functions by showing that security against algebraic cryptanalysis is preserved in the practical context of linear leakage functions (i.e., functions that can be expressed as a weighted sum of the bits manipulated by an implementation). These works contain several further findings that we omit here.

Constructions built from LWPR

Not explicitely, but fresh re-keying in key-homomorphic primitives should be among the candidates.

References

  • [1]Sébastien Duval, Pierrick Méaux, Charles Momin, and François-Xavier Standaert. 2021. Exploring Crypto-Physical Dark Matter and Learning with Physical Rounding Towards Secure and Efficient Fresh Re-Keying. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2021, 1 (2021), 373–401. Retrieved from https://ia.cr/2021/950
  • [2]Clément Hoffmann, Pierrick Méaux, Charles Momin, Yann Rotella, François-Xavier Standaert, and Balazs Udvarhelyi. 2023. Learning with Physical Rounding for Linear and Quadratic Leakage Functions. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part III (Lecture Notes in Computer Science), 2023. Springer, 410–439. Retrieved from https://ia.cr/2025/2226