Hollow LWE standard

Propose Edit

Updated:

Hollow LWE was introduced by Albrecht, Benčina, and Lai in 2025 [1] to realise an unbounded updatable public-key encryption scheme based on the hardness of Hollow LWE and Permutation Code Equivalence (PCE). The problem introduces techniques from code-based cryptography into the lattice-based LWE assumption.

Definition

Before we can define Hollow LWE, we need to introduce the notation of a hull and define \(h\)-hollow matrices.

Let \(q\) be prime and \(n \geq k > 0\). An \([n,k]\)-linear code \(\mathfrak{C}\) over \(\ZZ_q\) of length \(n\) and dimension \(k\) is a \(k\)-dimensional vector subspace of \(\ZZ_q^n\). It is typically represented by a full-rank generator matrix \(\mat{G} \in \ZZ_q^{n \times k}\) whose columns generate \(\mathfrak{C}\). A code may equivalently be represented as the kernel of its parity check matrix \(\mat{H} \in \ZZ_q^{n \times (n-k)}\), i.e. \(\vec{v} \in \mathfrak{C} \Leftrightarrow \vec{v}^T \cdot \mat{H} = \vec{0}\). The code generated by \(\mat{H}\) is called the dual code \(\mathfrak{C}^\bot = \set{\vec{y} \in \ZZ_q^n; \forall \vec{x} \in \mathfrak{C} : \vec{x}^T \cdot \vec{y} = 0}\). The intersection of a code with its dual is called the hull of \(\mathfrak{C}\), i.e. \(\text{hull}(\mathfrak{C}) = \mathfrak{C} \cap \mathfrak{C}^\bot\).

\(h\)-hollow

Let \(n \geq k > 0\) and \(q\) be a prime power. We call a code \(\mathfrak{C}\) \(h\)-hollow if it has hull dimsion \(h\). A matrix \(\mat{A} \in \ZZ_q^{n \times k}\) is called \(h\)-hollow if it is full-rank and generates a \([n, k]\)-linear \(h\)-hollow code over \(\ZZ_q\).

Hollow LWE\(_{k,n,q,\mathsf{D},\chi,h}\)

Let matrix \(\mat{A} \in \ZZ_q^{m \times n}\) be chosen uniformly at random under the constraint that \(\mat{A}\) is \(h\)-hollow. Let the secret vector \(\vec{s} \in \ZZ_q^n\) be chosen according to distribution \(\mathsf{D}\) and noise vector \(\vec{e} \in \ZZ_q^m\) be sampled from the error distribution \(\chi\). An adversary is asked to distinguish between the Hollow LWE distribution \((\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod q)\) and a uniformly random distribution over \(\ZZ_q^{m \times n} \times \ZZ_q^m\).

Hardness

In Theorem 1 of [1], the authors reduce LWE\(_{k,n,q,\mathsf{D},\chi}\) to Hollow LWE\(_{k-h,n,q,\mathsf{D},\chi,h}\). Therefore, Hollow LWE is at least as hard as LWE in dimension \(k-h\).

Constructions built from Hollow LWE

  • Unbounded Updatable Public-Key Encryption [1]
  • LWE reduces to Hollow LWE, ensuring the additional promise of \(h\)-hollow matrices \(\mat{A}\) does not compromise its hardness.
  • Permutation Code Equivalence (PCE) and its hull-based attacks in interplay with LWE inspired Hollow LWE.

References

  • [1]Martin R. Albrecht, Benjamin Benčina, and Russell W. F. Lai. 2025. Hollow LWE: A New Spin - Unbounded Updatable Encryption from LWE and PCE. In Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques Madrid, Spain, May 4-8, 2025, Proceedings, Part VIII (Lecture Notes in Computer Science), 2025. Springer, 363–392. Retrieved from https://ia.cr/2025/340