Secret-Power Ring-LWE (SP-RLWE)

Propose Edit

Updated:

The Secret-Power Ring-LWE (SP-RLWE) assumption was introduced by Agrawal, Bhushan, Couteau, and Riahinia in 2026 [1]. It states that a modified version of LWE – which exponentiates the secret across samples and only introduces randomness through freshly sampled errors – remains hard to solve. They introduce this assumption to provide a public-key pseudorandom correlation function for oblivious transfer.

Definition

SP-RLWE\(_{q,\chi_\mu,\chi_e,m,\mathcal{R}}\)

Let \(\chi_\mu\) and \(\chi_e\) be distributions over \(\mathcal{R}\). Sample an invertible element \(\mu \sample \chi_\mu\), elements \(M, \mathcal{M}, \mathcal{M}_i \sample \mathcal{R}_q\), and \(e, e_i \sample \chi_e\) for all \(i \in [m]\). An adversary is asked to distinguish between the distribution

\[\left( M, M \cdot \mu + e, \set{M \cdot (1/\mu)^i + e_i}_{i \in [m]} \right) \text{ and } \left( M, \mathcal{M}, \set{\mathcal{M}_i}_{i \in [m]} \right).\]

Variants

Weak SP-RLWE\(_{q,\chi_\mu,\chi_e,m,\mathcal{R}}\)

Let \(\chi_\mu\) and \(\chi_e\) be distributions over \(\mathcal{R}\). Sample an invertible element \(\mu \sample \chi_\mu\), elements \(M \sample \mathcal{R}_q\), and \(e, e_i \sample \chi_e\) for all \(i \in [m]\). Given \(\set{M \cdot (1/\mu)^i + e_i}_{i \in [m]}\), an adversary is asked to distinguish between the distribution

\[(M \cdot \mu + e) \text{ and } \mathcal{U}\left( \mathcal{R}_q \right).\]

The construction in [1] relies on a slightly weaker assumption, which does not assume that the terms \(M \cdot (1/\mu)^i + e_i\) are computationally indistinguishable from uniform.

The following variants were introduced by Ishai, Li, and Lin in [2] and they claim it to be a specialisation of Power Ring-LWE. However, these assumptions are significantly closer to Secret-Power Ring-LWE and therefore listed here. These assumptions were also utilised in [3]. Their hardness was not discussed in any paper.

Specialised Secret-Power Ring-LWE\(_{m,q,\chi_s,\chi_e,\mathcal{R}}\)

Let \(\chi_s, \chi_e\) be distributions over \(\mathcal{R}\). Sample \(\vec{a} \sample \mathcal{R}_q^m\), \(s \sample \chi_s\), \(\vec{e}_0, \vec{e}_1 \sample \chi_e^m\). An adversary is asked to distinguish between the distribution

\[\set{ \vec{a}, s \cdot \vec{a} + \vec{e}_0, s^2 \cdot \vec{a} + \vec{e}_1 }_\lambda \text{ and } \mathcal{U}\left(\mathcal{R}_q^m\right) \times \mathcal{U}\left(\mathcal{R}_q^m\right) \times \mathcal{U}\left(\mathcal{R}_q^m\right).\]

Specialised Circular-Secret-Power Ring-LWE\(_{m,p,q,\chi_s,\chi_e,\mathcal{R}}\)

Let \(\chi_s, \chi_e\) be distributions over \(\mathcal{R}\). Sample \(\vec{a} \sample \mathcal{R}_q^m\), \(s \sample \chi_s\), \(\vec{e}_0, \vec{e}_1 \sample \chi_e^m\). An adversary is asked to distinguish between the distribution

\[\set{ \vec{a}, s \cdot \vec{a} + \vec{e}_0, s^2 \cdot \vec{a} + \vec{e}_1 + \frac{q}{p} \cdot s }_\lambda \text{ and } \mathcal{U}\left(\mathcal{R}_q^m\right) \times \mathcal{U}\left(\mathcal{R}_q^m\right) \times \mathcal{U}\left(\mathcal{R}_q^m\right).\]

Hardness

The authors of [1] describe their cryptanalytic attempts to break the assumption in Section 4. They state that “aside from low norm linear dependencies, we do not know any other attacks from the literature that exploit correlations between secrets” and that they could not achieve any non-trivial attacks. In their parameter set, the modulus \(q\) is superpolynomial but they state that they believe “the assumption to plausibly hold in any parameter setting where the standard ring-LWE assumption holds (perhaps up to a tiny speedup of \(\sqrt{m}\), \(m\) being the maximum degree of \(\mu−1\), by adapting the generic attack of [4] on power-DDH to the ring-LWE setting)”.

Constructions built from SP-RLWE

  • Public-key pseudorandom correlation function [1]

References

  • [1]Shweta Agrawal, Kaartik Bhushan, Geoffroy Couteau, and Mahshid Riahinia. 2026. Post-Quantum Public-Key Pseudorandom Correlation Functions for OT. Retrieved from https://ia.cr/2026/877
  • [2]Yuval Ishai, Hanjun Li, and Huijia Lin. 2025. A Unified Framework for Succinct Garbling from Homomorphic Secret Sharing. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part IV (Lecture Notes in Computer Science), 2025. Springer, 390–425. Retrieved from https://ia.cr/2025/442
  • [3]Zhe Li, Chaoping Xing, Yizhou Yao, Chen Yuan, and Mengmeng Zhou. 2025. Succinct Line-Point Zero-Knowledge Arguments from Homomorphic Secret Sharing. In Advances in Cryptology - ASIACRYPT 2025 - 31st International Conference on the Theory and Application of Cryptology and Information Security, Melbourne, VIC, Australia, December 8-12, 2025, Proceedings, Part V (Lecture Notes in Computer Science), 2025. Springer, 578–609. Retrieved from https://ia.cr/2025/1866
  • [4]Jung Hee Cheon. 2006. Security Analysis of the Strong Diffie-Hellman Problem. In Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28 - June 1, 2006, Proceedings (Lecture Notes in Computer Science), 2006. Springer, 1–11. https://doi.org/10.1007/11761679_1