Hint-LWE standard

Propose Edit

Updated:

The assumption is a natural relaxed version of the classical LWE assumption where the adversary is also given linear noisy information about the secret \(\vec{s}\) and the error \(\vec{e}\). It was first introduced by Mera, Karmakar, Marc, and Soleimanian [1] in the ring setting and later extended in 2023 by Kim, Lee, Seo, and Song [2], to formalise it to the well-known Hint-MLWE assumption.

It is important to note that this assumption has been generalised as the Leaky LWE assumption, enabling a more powerful reduction with \(\mathbf{s}\) and \(\mathbf{e}\) that follow different distributions, with a semi-adaptive choice of the hints. However, since this assumption is frequently used in practice, we provide an independent instance in this Zoo.

Definition

We provide a description of the decisional version for each assumption.

Hint-LWE\(^{\ell,(\chi_{i})_{i \in [\ell]}, \mathcal{\mathcal{H}}}_{n,m,q,\chi}\)

Recall the standard LWE parameters \(n, q, m> 0\) with a distribution \(\chi\) over \(\ZZ^{m+n}\). We consider \(\ell > 0\) hints each with an associated distribution \(\chi_1, \dots, \chi_\ell\) over \(\ZZ^{m+n}\) and a set of hint-matrices \(\mathcal{H}\) over \(\ZZ^{(m+n) \times (m+n)}\).

Consider the original LWE construction for a random matrix \(\mat{A} \leftarrow \mathcal{U}(\ZZ_q^{m\times n})\) and \(\mathbf{r} := \begin{bmatrix}\mathbf{s} \\ \mathbf{e}\end{bmatrix} \leftarrow \chi\). We construct \(\ell\) hints as \(\mathbf{z}_i = \mat{H}_i \mathbf{r} + \mathbf{y}_i\), where \(\mat{H}_i \in \mathcal{H}\) and \(\mathbf{y}_i\leftarrow \chi_i\).

An adversary is asked to distinguish between the LWE distribution \((\mat{A}, \vec{b} = \mat{A}\vec{s} + \vec{e} \bmod q)\) and a uniformly random distribution over \(\ZZ_q^{m \times n} \times \ZZ_q^m\) given \(\ell\) honest hints \(\mat{z}_i\) and the involved hint-matrices \(\mat{H}_i\).

Hint-RLWE\(^{\ell,(\chi_{i})_{i \in [\ell]}, \mathcal{\mathcal{H}}}_{m,q,\chi,\mathcal{R}}\)

Recall the standard R-LWE parameters \(n, q, m> 0\) and \(\mathcal{R}\) with a distribution \(\chi\) over \(\mathcal{R}^{1+m}\). We consider \(\ell > 0\) hints each with an associated distribution \(\chi_1, \dots, \chi_\ell\) over \(\mathcal{R}^{1+m}\) and a set of hint-matrices \(\mathcal{H}\) over \(\mathcal{R}^{(1+m) \times (1+m)}\).

Consider the original R-LWE construction for a random polynomial \(\vec{a} \leftarrow \mathcal{U}(\mathcal{R}_q^{m})\) and \(\mathbf{r} := \begin{bmatrix}s \\ \mathbf{e}\end{bmatrix} \leftarrow \chi\). We construct \(\ell\) hints as \(\mathbf{z}_i = \mat{H}_i \mathbf{r} + \mathbf{y}_i\), where \(\mat{H}_i \in \mathcal{H}\) and \(\mathbf{y}_i\leftarrow \chi_i\).

An adversary is asked to distinguish between the LWE distribution \((\mat{a}, \vec{b} = s\cdot\vec{a} + \vec{e} \bmod q)\) and a uniformly random distribution over \(\mathcal{R}_q^{m} \times \mathcal{R}_q^m\) given \(\ell\) honest hints \(\mat{z}_i\) and the involved hint-matrices \(\mat{H}_i\).

Hint-MLWE\(^{\ell,(\chi_{i})_{i \in [\ell]}, \mathcal{H}}_{n,m,q,\chi,\mathcal{R}}\)

Recall the standard M-LWE parameters \(n, q, m> 0\) and \(\mathcal{R}\) with a distribution \(\chi\) over \(\mathcal{R}^{m+n}\). We consider \(\ell > 0\) hints each with an associated distribution \(\chi_1, \dots, \chi_\ell\) over \(\mathcal{R}^{m+n}\) and a set of hint-matrices \(\mathcal{H}\) over \(\mathcal{R}^{(m+n) \times (m+n)}\).

Consider the original M-LWE construction for a random matrix \(\mat{A} \leftarrow \mathcal{U}(\mathcal{R}_q^{m\times n})\) and \(\mathbf{r} := \begin{bmatrix}\mathbf{s} \\ \mathbf{e}\end{bmatrix} \leftarrow \chi\). We construct \(\ell\) hints as \(\mathbf{z}_i = \mat{H}_i \mathbf{r} + \mathbf{y}_i\), where \(\mat{H}_i \in \mathcal{H}\) and \(\mathbf{y}_i\leftarrow \chi_i\).

An adversary is asked to distinguish between the LWE distribution \((\mat{A}, \vec{b} = \mat{A}\vec{s} + \vec{e} \bmod q)\) and a uniformly random distribution over \(\mathcal{R}_q^{m \times n} \times \mathcal{R}_q^m\) given \(\ell\) honest hints \(\mat{z}_i\) and the involved hint-matrices \(\mat{H}_i\).

Variants

Coset-Hint-MLWE\(^{\ell,(\vec{r}_i)_{i \in [\ell]}, \sigma, \beta}_{n,m,q,\chi,\mathcal{R}}\)

Lapiha and Prest [3] presented this variant of Hint-MLWE, where the error of the hints are sampled from a lattice coset.

Let \(\textsf{Decomp}_\beta\) be the signed decomposition in base \(\beta\). They consider a special instance of Hint-MLWE\(^{\ell,(\chi_{i})_{i \in [\ell]}, \mathcal{H}_\beta}_{n,m,q,\chi,\mathcal{R}}\) where \(\mathcal{H}_\beta := \set{ h_0 \vert (h_0,h_1) \leftarrow \textsf{Decomp}_\beta(x) \text{ for } x \in \mathcal{R}_q }\).

Consider the original M-LWE construction for a random matrix \(\mat{A} \leftarrow \mathcal{U}(\mathcal{R}_q^{m\times n})\) and secrets \(\begin{bmatrix}\mat{S} \\ \mat{E}\end{bmatrix} \leftarrow \chi^m\). Let \(\mat{R} = \begin{bmatrix}\mat{E} & \mat{I}_m \\ \mat{0} & \mat{S} \\ \mat{0} & \mat{I}_m\end{bmatrix}.\) Let \(\mat{A}_1 = \begin{bmatrix} \mat{I}_m \| \mat{A} \| \beta\mat{I}_m - \mat{B} \end{bmatrix}\), and sample a pseudorandom matrix \(\mat{A}_2\) along with a short basis trapdoor \(\mat{T_{A_2}}\) targeting \(\mat{0}\), i.e. \(\mat{A_2}\mat{T_{A_2}} = \mathbf{0}\). Then construct \(\ell\) hints of the form:

  • Sample a random element \(\mathbf{u}_i\) in \(\mathcal{R}_q^m\) and compute \(\vec{c}_i \leftarrow \textsf{Decomp}_\beta(\vec{u}_i)\),
  • Sample \((\vec{y}_i,\vec{x}_i) \leftarrow \mathcal{D}_{\Lambda_q^{\vec{r}_i - \mat{A}_1\mathbf{R} \mathbf{c}_i}([\mat{A}_1 \| \mathbf{A}_2]), \sigma}\),
  • Finally construct \(\mathbf{z}_i = (\mathbf{R}\vec{c}_i + \mathbf{y}_i,\vec{x}_i)\).

An adversary is asked to distinguish between the LWE distribution \((\mat{A}, \vec{B} = \mat{A}\vec{S} + \vec{E} \bmod q)\) and a uniformly random distribution over \(\mathcal{R}_q^{m \times n} \times \mathcal{R}_q^{m\times m}\) given \(\ell\) honest hints \(\mat{z}_i\) and the public elements involved \(\mat{A}_2, \vec{c}_i\).

Lapiha and Prest [3] gave a reduction from Hint-MLWE\(^{\ell,(\mathcal{D}_\sigma)_{i \in [\ell]}, \mathcal{H}_\beta}_{n,m,q,\chi,\mathcal{R}}\) to Coset-Hint-MLWE\(^{\ell,(\vec{r}_i)_{i \in [\ell]}, \sigma, \beta}_{n,m,q,\chi,\mathcal{R}}\) which works for \(m\) secrets. The core idea of this assumption is to sample the hint-errors from a lattice coset, depending on the hint \(\vec{c}_i\) and the initial randomness \(\vec{u}_i\). The definition is not generic but it may be useful for constructing advanced primitives, where the error might be dependant on the hint-matrix chosen.

Hardness

Originally, the initial proof was given in [2] but it was later modified to broaden the range of possible applications by [4][5]. In this setting, we consider that the matrices \(\mat{H}_i\) are uniformly sampled from \(\mathcal{H}\), not chosen by the adversary. The reduction also only works for secrets and noise that follow Discrete Gaussian Distribution with judiciously chosen standard deviations.

Theorem from [4], which also holds for LWE (\(d=1\)) and R-LWE (\(n=1\)): Hint-MLWE\(^{\ell,(\mathcal{D}_{\mathbf{c}_i,\mathbf{\Sigma}_i})_{i \in [\ell]}, \mathcal{\mathcal{H}}}_{n,m,q,\mathcal{D}_{\mathbf{c},\mathbf{\Sigma}},\mathcal{R}}\) is at least as hard as short secret M-LWE\(_{n,m,q,\mathcal{D}_\sigma,\mathcal{R}}\). The private variables follow (elliptical) Gaussian distributions due to convolution of discrete Gaussian distribution.

The idea of the proof is to construct \(\ell\) honest hints associated with a new secret \(\mathbf{s}'\). By choosing the parameters appropriately, the set of the generated hints is close to the one generated based on the original MLWE secret \(\mathbf{s}\) plus a “samplable” perturbation \(\mathbf{t}\). At the end of the reduction, upon receiving \((\mat{A},\vec{b})\) the challenger uses the Hint-MLWE solving algorithm on input \((\mat{A},\vec{b} + [\mat{A} \| \mat{I}_{m-n}]\mat{t},\mathbf{H}_i,\mathbf{z}_i)\).

The hardness was also proven for non-noisy leakages for some specific regimes (when \(\chi_i = \emptyset\)) by [6].

Constructions built from Hint-MLWE

  • NIZK and commit-and-prove protocols [2][7]
  • Signatures such as Racoon [8], Plover [9]
  • Threshold signatures (with additionnal properties) [4][5][10][11]
  • Polynomial commitment schemes [12]
  • KEM (with properties): Katana [13], [3]

The adaptive case has been studied in [14] and [15].

  • Leaky LWE yields a generalisation of Hint-MLWE extending the notion of linear leakages over the secret/error pair and allowing for a wider range of hints.

References

  • [1]Jose Maria Bermudo Mera, Angshuman Karmakar, Tilen Marc, and Azam Soleimanian. 2022. Efficient Lattice-Based Inner-Product Functional Encryption. In Public-Key Cryptography - PKC 2022 - 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual Event, March 8-11, 2022, Proceedings, Part II (Lecture Notes in Computer Science), 2022. Springer, 163–193. Retrieved from https://ia.cr/2021/046
  • [2]Duhyeong Kim, Dongwon Lee, Jinyeong Seo, and Yongsoo Song. 2023. Toward Practical Lattice-Based Proof of Knowledge from Hint-MLWE. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part V (Lecture Notes in Computer Science), 2023. Springer, 549–580. Retrieved from https://ia.cr/2023/623
  • [3]Oleksandra Lapiha and Thomas Prest. 2025. A Lattice-Based IND-CCA Threshold KEM from the BCHK+ Transform. 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 III (Lecture Notes in Computer Science), 2025. Springer, 461–494. Retrieved from https://ia.cr/2025/1958
  • [4]Thomas Espitau, Guilhem Niot, and Thomas Prest. 2024. Flood and Submerse: Distributed Key Generation and Robust Threshold Signature from Lattices. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VII (Lecture Notes in Computer Science), 2024. Springer, 425–458. Retrieved from https://ia.cr/2024/959
  • [5]Rafaël Del Pino, Shuichi Katsumata, Mary Maller, Fabrice Mouhartem, Thomas Prest, and Markku-Juhani O. Saarinen. 2024. Threshold Raccoon: Practical Threshold Signatures from Standard Lattice Assumptions. 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 II (Lecture Notes in Computer Science), 2024. Springer, 219–248. Retrieved from https://ia.cr/2024/184
  • [6]Haoxiang Jin, Feng-Hao Liu, Zhedong Wang, and Dawu Gu. 2025. Discrete Gaussians Modulo Sub-Lattices: New Leftover Hash Lemmas for Discrete Gaussians. In Public-Key Cryptography - PKC 2025 - 28th IACR International Conference on Practice and Theory of Public-Key Cryptography, Røros, Norway, May 12-15, 2025, Proceedings, Part II (Lecture Notes in Computer Science), 2025. Springer, 301–330. Retrieved from https://ia.cr/2024/1695
  • [7]Antoine Douteau and Adeline Roux-Langlois. 2025. Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE. In Progress in Cryptology - INDOCRYPT 2025 - 26th International Conference on Cryptology in India, Bhubaneshwar, India, December 14-17, 2025, Proceedings (Lecture Notes in Computer Science), 2025. Springer, 119–144. Retrieved from https://ia.cr/2025/2239
  • [8]Rafaël del Pino, Shuichi Katsumata, Thomas Prest, and Mélissa Rossi. 2024. Raccoon: A Masking-Friendly Signature Proven in the Probing Model. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part I (Lecture Notes in Computer Science), 2024. Springer, 409–444. Retrieved from https://ia.cr/2024/1291
  • [9]Muhammed F. Esgin, Thomas Espitau, Guilhem Niot, Thomas Prest, Amin Sakzad, and Ron Steinfeld. 2024. Plover: Masking-Friendly Hash-and-Sign Lattice Signatures. 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, 316–345. Retrieved from https://ia.cr/2024/401
  • [10]Shuichi Katsumata, Michael Reichle, and Kaoru Takemure. 2024. Adaptively Secure 5 Round Threshold Signatures from MLWE/MSIS and DL with Rewinding. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part VII (Lecture Notes in Computer Science), 2024. Springer, 459–491. Retrieved from https://ia.cr/2024/1033
  • [11]Rafaël Del Pino, Shuichi Katsumata, Guilhem Niot, Michael Reichle, and Kaoru Takemure. 2025. Unmasking TRaccoon: A Lattice-Based Threshold Signature with An Efficient Identifiable Abort Protocol. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part VI (Lecture Notes in Computer Science), 2025. Springer, 423–456. Retrieved from https://ia.cr/2025/849
  • [12]Intak Hwang, Jinyeong Seo, and Yongsoo Song. 2024. Concretely Efficient Lattice-Based Polynomial Commitment from Standard Assumptions. In Advances in Cryptology - CRYPTO 2024 - 44th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2024, Proceedings, Part X (Lecture Notes in Computer Science), 2024. Springer, 414–448. Retrieved from https://ia.cr/2024/306
  • [13]Yevgeniy Dodis, Daniel Jost, Shuichi Katsumata, Thomas Prest, and Rolfe Schmidt. 2025. Triple Ratchet: A Bandwidth Efficient Hybrid-Secure Signal Protocol. 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, 302–331. Retrieved from https://ia.cr/2025/078
  • [14]Katharina Boudgoust and Hannah Keller. 2025. Module Learning with Errors with Truncated Matrices. In Post-Quantum Cryptography - 16th International Workshop, PQCrypto 2025, Taipei, Taiwan, April 8-10, 2025, Proceedings, Part I (Lecture Notes in Computer Science), 2025. Springer, 255–277. Retrieved from https://ia.cr/2025/120
  • [15]Russell W. F. Lai, Monisha Swarnakar, and Ivy K. Y. Woo. 2025. Leaky LWE: Learning with Errors with Semi-Adaptive Secret- and Error-Leakage. IACR Commun. Cryptol. 2, 3 (2025), 21. https://doi.org/10.62056/AH89KSUC2