Power Ring-LWE (P-RLWE)

Propose Edit

Updated:

The Power Ring-LWE (P-RLWE) assumption was introduced by Abram, Roy, and Scholl in 2024 [1]. Inspired by Power-DDH , the assumption states that a modified version of LWE – which exponentiates a single element \(a\) across all samples and only introduces randomness through freshly sampled errors – remains hard to solve. They introduce this assumption to provide a construction for succinct homomorphic secret sharing.

Definition

P-RLWE\(_{q,\chi,m,\mathcal{R}}\)

Let \(\mathcal{R}_q = \ZZ_q[X] / I\langle f(X) \rangle\), where \(f\) is a monic polynomial and let \(\Gamma\) and \(\chi\) be distributions over \(\mathcal{R}_q\). Sample \(a \sample \Gamma\), \(w \sample \mathcal{R}_q\), \(e_i \sample \chi\), and \(v_i \sample \mathcal{R}_q\) for \(i \in [m]\). An adversary is asked to distinguish between the distribution

\[\left( a, \set{a^i \cdot w^i + e_i}_{i \in [m]} \right) \text{ and } \left( a, \set{v_i}_{i \in [m]} \right).\]

Please note that the assumption described above follows the original definition from [1]. Other papers [2][3] claim to specialise this assumption, call it Power Ring-LWE, and define a circular version of it. However, their assumption does not capture the nature of Abram, Roy, and Scholl’s definition and is closer to Secret-Power Ring-LWE. Thus, we list them on the Secret-Power Ring-LWE page as variants.

Hardness

The hardness of this assumption is not discussed in any form.

Constructions built from P-RLWE

  • Public-Key Bilinear Homomorphic Secret Sharing [1]

References

  • [1]Damiano Abram, Lawrence Roy, and Peter Scholl. 2024. Succinct Homomorphic Secret Sharing. In Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part VI (Lecture Notes in Computer Science), 2024. Springer, 301–330. Retrieved from https://ia.cr/2024/814
  • [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