Common Notation

Equivocal LWE

Propose Edit

Updated:

Equivocal LWE was introduced by Cini, Lai, and Woo in 2025 [1]. The assumption is designed to model model the BDGM framework [2] while abstracting away complications like the choice of the symmetric key encryption or encoding.

As the assumption is quite complex and closely related to a specific type of construction, it belongs to a category of cryptographic assumptions criticised in a position paper on cryptographic assumptions by Goldwasser and Kalai [3].

Definition

We provide the informal but more intuitive definition given by Cini et al in Section 1.3 [1]. \(\newcommand{msg}{\mathsf{msg}}\newcommand{\SKE}{\mathsf{SKE}}\newcommand{sk}{\mathsf{sk}}\newcommand{Enc}{\mathsf{Enc}}\newcommand{ctxt}{\mathsf{ctxt}}\)

Equivocal LWE\(_{\mathcal{R},q,h,k,d,p,t,s,\chi,\mathsf{SKE},\mathsf{Encode},\mathcal{E}}\)

Let \(\SKE = (\Enc, \mathsf{Dec})\) be a symmetric-key encryption scheme, let \(\mathsf{Encode}: \mathcal{S} \rightarrow \mathcal{R}_q^{p \ceil{\log q} \times k}\) be a deterministic encoding algorithm, and let \(\mathcal{E}\) be a distribution over \(\mathcal{R}_q^{t \times k}\). The circuit \(\Phi\) maps \(\mathcal{C}_\mathsf{tag}\) to \(\mathcal{R}_q^{p \times h} \times \mathcal{R}_q^{h \times k}\) and needs to be efficiently computable.

  1. \(\adv\) chooses messages \(\msg_0, \msg_1, \msg_\mathsf{pad}\), and a circuit \(\Phi\).
  2. Generate an \(\SKE\) secret key \(\sk\). Encrypt \(\msg_\mathsf{pad}\) as \(\mat{P} \leftarrow \SKE.\Enc(\sk, \msg_\mathsf{pad})\).
  3. Sample an equivocal matrix \(\mat{B} \sample \mathcal{E}\) and mask \(\mathsf{Encode}(\sk)\) with the LWE sample \(\mat{C} = \mat{R}\mat{B} + \mat{E} + \mathsf{Encode}(\sk) \bmod q\), where \(\mat{R} \sample \mathcal{R}_q^{p \ceil{\log q} \times t}\) and \(\mat{E} \sample D_{\mathcal{R},\chi}^{p \ceil{\log q} \times k}\).
  4. For each \(i \in \set{0,1}\) do:
    • Encrypt \(\msg_i\) as \(\ctxt_i \leftarrow \SKE.\Enc(\sk, \msg_i)\).
    • Run the circuit \(\Phi\) on \(\ctxt_i\) to obtain \((\mat{H}_i, \mat{M}_i)\).
    • Compute \(\mat{L}_i^T = \mat{G}^{-1}(\mat{H} + \vec{1}^T \otimes \mat{P})\). Let \(\mat{W}_i = \mat{L}_i \mat{C} + \mat{M}_i\). Assert that \(\norm{\mat{W}_i - \mat{L}_i \mat{R} \mat{B} \bmod q} \leq s\).
  5. Assert that \(\mat{M}_0 = \mat{M}_1\).
  6. Choose \(b \sample \set{0,1}\). Let \(\vec{w}_{b,i}\) denote the row columns of \(\mat{W}_b\). Equivocate \(\mat{L}_b \mat{R}\) via \(\bar{\mat{R}}_i \mat{B} \sample \left(D_{\Lambda_q(\mat{B}),s,\vec{w}_{b,j}}\right)_{j \in [h]}\) to obtain \(\mat{R}_b\) satisfying \(\mat{R}_b \mat{B} \approx \mat{L}_b\mat{R}\mat{B}\).
  7. Given \(\mat{B}\), \(\mat{C}\), \(\mat{P}\), \(\ctxt_b\), and \(\mat{R}_b\), an adversary is asked to distinguish between \(b=0\) and \(b=1\).

The assumption crucially relies on the notion of equivocality. For this, they define an induced distribution of equivocate for their primal trapdoor for \((\mat{B}, \mathsf{td}) \sample \mathsf{pTrapGen}(1^t, 1^k, q)\) and any \(\vec{r} \in \mathcal{R}_q^t\), \(\vec{c} \in \mathcal{R}_q^k\), \(s>0\) satisfying \(\norm{\vec{c}^T - \vec{r}^T \mat{B} \bmod q} \leq s\):

\[\set{\vec{r} \mat{B} \bmod q \mid \vec{r} \leftarrow \mathsf{Equivocate}(\mathsf{td}, \vec{r}, \vec{c}, s)} \approx D_{\Lambda_q(\mat{B}),s,\vec{c}}.\]

The Induced Distribution of Equivocate property in their primal trapdoor definition is equivalent to requiring that the equivocated LWE error satisfies

\[\left\{ \vec{e} \space \middle| \space \begin{array}{l} \vec{r} \leftarrow \mathsf{Equivocate}(\mathsf{td}, \vec{r}, \vec{c}, s) \\ \vec{e}^T = \vec{c}^T - \vec{r}^T \mat{B} \bmod q \end{array} \right\} \approx D_{\Lambda_q(\mat{B})+\vec{c},s} \bmod q\]

for \(\vec{r}\), \(\vec{c}\) satisfying the same constraints. This is because \(\vec{c}^T - D_{\Lambda_q(\mat{B}),s,\vec{c}} = D_{\Lambda_q(\mat{B}) + \vec{c}, s}\).

Hardness

Cini et al. [1] explore Equivocal LWE mainly via three cryptanalytic attempts: No-hint attacks, trivial distinguishing attacks based on differing quality of hints, and “zero-ising” attacks. A high-level description of these attack strategies can be found in Section 1.4 of [1].

Constructions built from Equivocal LWE

  • Indistinguishable Obfuscation [1]
  • Registered Attribute-Based Encryption [4]

References

  • [1]Valerio Cini, Russell W. F. Lai, and Ivy K. Y. Woo. 2025. Lattice-Based Obfuscation from NTRU and Equivocal LWE. In Advances in Cryptology - CRYPTO 2025 - 45th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2025, Proceedings, Part VII (Lecture Notes in Computer Science), 2025. Springer, 39–72. Retrieved from https://ia.cr/2025/1129
  • [2]Zvika Brakerski, Nico Döttling, Sanjam Garg, and Giulio Malavolta. 2020. Candidate iO from Homomorphic Encryption Schemes. In Advances in Cryptology - EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10-14, 2020, Proceedings, Part I (Lecture Notes in Computer Science), 2020. Springer, 79–109. Retrieved from https://ia.cr/2020/394
  • [3]Shafi Goldwasser and Yael Tauman Kalai. 2016. Cryptographic Assumptions: A Position Paper. In Theory of Cryptography - 13th International Conference, TCC 2016-A, Tel Aviv, Israel, January 10-13, 2016, Proceedings, Part I (Lecture Notes in Computer Science), 2016. Springer, 505–522. Retrieved from https://ia.cr/2015/907
  • [4]Shayeef Murshid, Ramprasad Sarkar, and Mriganka Mandal. 2025. Registered Attribute-Based Encryption with Publicly Verifiable Certified Deletion, Everlasting Security, and More. IACR Cryptol. ePrint Arch. 2025, (2025), 2314. Retrieved from https://ia.cr/2025/2314