# Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE

Antoine Douteau, Adeline Roux-Langlois

► To cite this version:

Antoine Douteau, Adeline Roux-Langlois. Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE. Progress in Cryptology – INDOCRYPT 2025, Dec 2025, Bhubaneshwar, India. pp.119-144, 10.1007/978-3-032-13301-4_6. hal-05410080

HAL Id: hal-05410080

https://hal.science/hal-05410080v1

Submitted on 10 Dec 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Rejection-Free Framework of Zero-Knowledge Proof Based on Hint-MLWE

Antoine Douteau and Adeline Roux-Langlois

Université Caen Normandie, ENSICAEN, CNRS, Normandie Univ, GREYC
UMR6072, F-14000 Caen, France

antoine.douteau@unicaen.fr, adeline.roux-langlois@cnrs.fr

**Abstract.** Commit-and-prove zero-knowledge proofs are a generalized version of zero-knowledge protocols that permit proving relations over the committed elements in addition testifying to its knowledge of the initial message. For example, the existing framework (LNP, Crypto22) allows a user to prove that the secret element committed satisfies quadratic relations with bounded norm ($\ell_2$ or $\ell_\infty$). Security of these frameworks, regarding the zero knowledge property, is mainly assumed by the use of rejection sampling introduced by Lyubashevsky (Asiacrypt09). The main problems with rejection sampling are non-constant time execution and the cost of protecting this step from side-channel attacks.

Our contribution is a new framework of proof for zero-knowledge property that proves knowledge and quadratic relations over lattices without basing the security over rejection sampling. The security of our framework is based on the recent Hint-MLWE (KLSS, Crypto23) assumption. This variant of MLWE gives additional hints about the secret in addition to the original input, and is shown to be as hard as its associated MLWE instance when secrets follow discrete Gaussian distributions.

**Keywords:** Lattices, Zero-Knowledge Protocol, Commit-and-prove, Hint-MLWE, Rejection sampling

## 1 Introduction

Lattices have been a well-studied and cryptanalysed mathematical tools that have made it possible to build several optimised, efficient and resistant cryptographic constructions for current standards, but also for future advanced primitives. Originally, fundamental lattice assumptions such as the Closest Vector Problem or the Shortest Vector Problem are NP-hard [Ajt98, GMSS99] but the mathematical aspect of lattices inspired relaxed assumptions more cryptographic-oriented, known as the Learning with Errors (LWE) problem [Reg05] and its dual Short Integer Solution (SIS) from [Ajt96]. They reduce to these problems but also benefit to be “average-case” unlike the fundamental assumptions. In a global way in cryptography, lack of structure and redundancy can have a negative impact on efficiency and on having reasonable schemes in both size and running time. This is why the constructions often exploit Module Lattices originally defined
in [LS15] that work over polynomials. This special structure is used on ML-DSA and ML-KEM [DKL$^+$18, BDK$^+$18] as ML stands for Module Lattices, over their assumptions Module-LWE and Module-SIS, variants of LWE and SIS.

**Signatures over Lattices.** The first framework of signature scheme over lattices [GPV08] exploits a private trapdoor, allowing the signer to invert a one-way function, usually called **Hash-and-Sign**. The second main framework relies on the Fiat-Shamir paradigm [FS87] which performs a transformation of a zero-knowledge protocol to a non-interactive instance, secured on the Random Oracle Model (ROM). The idea is to prove knowledge of a specific element, and being zero-knowledge means that the execution of the protocol does not give any additional information on the secret element. The FSp transposes this proof in a single execution without interactivity between a prover and a verifier. The transcript generated defines the signature; the final verification steps are identical.

**Rejection Sampling.** One of the initial ideas over lattices was considered by Lyubashevsky in [Lyu09] in the FS with aborts idea: it allows the prover to send various elements strongly related to the secret committed into the transcript. To ensure the zero-knowledge property, those elements need to be carefully chosen after passing a rejection step successfully. The method is called rejection sampling as those temporary elements need to be resampled in case of failure. The main advantage is that it allows the prover to control the distribution of the leaks. Since the proving phase aborts with a non-negligible probability, it does not run in constant time. This method is used in several constructions over lattices, isogenies and error-correcting codes [DG19, BKP20, LNP22, BDK$^+$23, DKL$^+$18].

**Commit-and-Prove System of Proofs.** In order to be useful in practice and permit more than just proving the knowledge of a secret element, the notion of zero-knowledge commit-and-prove proofs [CLOS02] extends the definition of zero-knowledge proofs and allows proving additional information and relations about a committed element. This system of proofs can be modified regarding the Fiat-Shamir (with aborts) paradigm in order to construct efficient advanced signature schemes. The recent framework [LNP22] generalizes a method of construction of this protocol in order to additionally prove polynomial relations over the secret and norm bounds of those structure. This allows for example to prove knowledge of a MSIS element or a MLWE secret. The framework also comes with different applications (verifiable encryption, group signature) and is used (a posteriori) in various constructions [LN22, AKSY22, BLNS23, NS24] to take advantage of its versatility. The overall security of the commitment scheme relies on module assumptions, and the zero-knowledge property is established using different optimized rejection sampling mechanisms [Lyu09, DDLL13, LNS21].

**Constraints of Rejection Sampling.** In a general manner, the rejection sampling method is theoretically proven to be secure, but several flaws have
been discovered in [EFGT17, DFPS23, BBD$^{+23}$], affecting most of the actual rejection-based constructions over both lattices and isogenies constructions. A major disadvantage is that the proving phase does not run in constant time, making implementation and security difficult, as in [GHJ$^{+22}$], which tackles earlier proposals for error-correcting code systems HQC and BIKE [AAB$^{+22}$, ABB$^{+22}$]. Those attacks are called *side-channel attacks* and enable an attacker the ability to extract information by analyzing the physical device running the algorithm.

One of the main methods for protecting against side-channel attacks is to use secret-sharing also called *masking* [ISW03, PR13]. This countermeasure implies a decomposition of an element in different shares. The masking countermeasure needs to be used over all the functions and variables that involve secret elements, including the rejection sampling. The masking of rejection sampling has been studied in depth in [MGTF19, BBE$^{+18}$, EFGT17, CGL$^{+24}$], as the leakage of execution information from the proving phase would conceptually contradict the goal of rejection sampling. Despite it has been optimized, masking is particularly expensive: in the recent paper [CGL$^{+24}$] that analyze the second level of security of ML-DSA, the action of masking an execution multiplies the running time by at least 33 (for the first level of security). In a further comparison, the masked rejection sampling step alone takes 3× longer than the total duration of a single (rejection-free) unmasked instance of ML-DSA.

Rejection sampling can also be an issue regarding some constructions with multiple executions of a protocol, such as for the Polynomial Commitment from [HSS24] where its rejection rate would increase exponentially. Then, another perspective would be to completely remove the use of rejection sampling without significantly affecting the overall size of the construction in which it is used.

## 1.1 Contribution

Our contribution is to build a new commit-and-prove framework of proof for zero-knowledge property on lattices, without performing rejection sampling, based on the new construction from [HSS24]. The security of our framework is based on the Hint-MLWE assumption, introduced in [KLSS23]. This variant of MLWE gives additional hints about the secret, and is shown to be as hard as its associated MLWE instance when secret elements follow discrete Gaussian distributions.

Our key idea is to exploit this new assumption in the [LNP22] framework over the new Modified-Ajtai commitment scheme from [HSS24], as it only focused on constructing a polynomial commitment using the Hint-MLWE assumption, we generalize their idea in order to construct and implement a concrete commit-and-prove framework of proof. In a first step, we modify the framework of [LNP22] with the special Gaussianisation process from [HSS24], allowing the proof of knowledge of a secret vector of polynomials s without any restriction on their bounds, unlike the original [LNP22] framework. In a second step, our framework gives to the prover the ability to prove multiple quadratic and linear relations over both $\mathcal{R}_p$ and $\mathbb{Z}_p$ exploiting the automorphism $\sigma_{-1}$ without additionally committing to it. We also provide the implementation of our modified framework based on the recent LaZer Library [LSS24]. As the structure is
relatively close to the original paper [LNP22], the code structure complies with LaZer standards and has been implemented in such a way that it can be used in addition to the original library. As the main contribution lies in the elimination of rejection sampling, which implies a modification of the execution times of the different functions, we add a concrete comparison between instances of [LNP22] using [LSS24] and our implementation on similar parameter sets in Table 3. We provide a static analysis of the complexity, which shows that an instance of the proving phase is at most 4 times longer than a single [LNP22], resulting in faster executions, as the rejection rate increases, but slower (less than 4 times) for other phases. It also affects the size of the transcripts, which are ≈ 3 times larger. Our construction provides an alternative of [LNP22] that runs in constant time. The code is available in the attached file and in this repository.

<table><caption>Table 1: The first part of the Table explains the size of the transcripts in kilobytes. In the second part, the results show our benchmarks for the mean running time of each phase. The 5 different sets of parameters are detailed in Table 2. In the comparison, the running time of the Prove part of [LNP22] using the [LSS24] implementation takes into account several executions due to rejection sampling.</caption><thead><tr><th colspan="7">Size of the transcripts (in kilobytes KB)</th></tr><tr><th>Protocol</th><th>Protocol/Phase</th><th>Param. 1</th><th>Param. 2</th><th>Param. 3</th><th>Param. 4</th><th>Param. 5</th></tr></thead><tbody><tr><td rowspan="3">[LNP22]</td><td>Opening proof</td><td>13.22</td><td>20.77</td><td>30.53</td><td>×</td><td>41.05</td></tr><tr><td>+ 3 Quad.</td><td>13.93</td><td>21.86</td><td>31.31</td><td>×</td><td>41.68</td></tr><tr><td>+ 3 Eval.</td><td>15.16</td><td>22.96</td><td>32.09</td><td>×</td><td>42.93</td></tr><tr><td rowspan="3">Ours</td><td>Opening proof</td><td>24.23</td><td>45.69</td><td>103.19</td><td>37.33</td><td>96.52</td></tr><tr><td>+ 3 Quad.</td><td>24.83</td><td>46.76</td><td>103.95</td><td>38.08</td><td>97.12</td></tr><tr><td>+ 3 Eval.</td><td>25.42</td><td>47.82</td><td>104.70</td><td>38.83</td><td>97.72</td></tr><tr><th colspan="7">Mean times (in million cycles)</th></tr><tr><td rowspan="4">[LNP22]</td><td>KeyGen</td><td>7.63</td><td>10.32</td><td>19.32</td><td>×</td><td>39.35</td></tr><tr><td>Commit</td><td>7.29</td><td>20.89</td><td>31.33</td><td>×</td><td>39.42</td></tr><tr><td>Prove</td><td>324.22</td><td>352.22</td><td>4289.68</td><td>×</td><td>4462.29</td></tr><tr><td>Verify</td><td>18.54</td><td>39.17</td><td>1744.10</td><td>×</td><td>1629.12</td></tr><tr><td rowspan="4">Ours</td><td>KeyGen</td><td>19.01</td><td>47.04</td><td>66.30</td><td>29.55</td><td>62.01</td></tr><tr><td>Commit</td><td>19.86</td><td>86.54</td><td>102.47</td><td>45.73</td><td>67.15</td></tr><tr><td>Prove</td><td>59.45</td><td>134.26</td><td>4248.67</td><td>220.98</td><td>3961.24</td></tr><tr><td>Verify</td><td>41.74</td><td>96.79</td><td>3897.43</td><td>180.31</td><td>3624.34</td></tr></tbody></table>

## 1.2 Technical Overview

The initial idea of our construction is to provide a rejection-free framework of zero-knowledge proofs based on lattice assumptions. We start from [LNP22] based on the Ajtai commitment scheme on a module lattice $\mathcal{R}_p = \mathbb{Z}_p[X]/\langle\phi_d\rangle$ with its modulo $p$ and a power of 2 degree: $d$. The original construction proves knowledge of the message $s_1 \in \mathcal{R}_p^{m_1}$, along with a randomness $s_2 \in \mathcal{R}_p^{m_2}$ by computing the commitment $t_A = A_1s_1 + A_2s_2$ for uniformly sampled matrices $A_1 \in \mathcal{R}_p^{n \times m_1}$ and $A_2 \in \mathcal{R}_p^{n \times m_2}$. Considering an Hermite Normal Form of the matrix $A_2$ i.e. with an identity structure such that $A_2 = [I_n | A'_2]$ generates the
same lattice with a faster sampling, inducing a MLWE structure. This commitment scheme is relevant only if the norm of $s_i$ is bounded, as its binding security is based on the MSIS assumption. The hiding security is provided assuming a hard instance of MLWE with the second component involving the secret randomness $s_2$. The opening of the Ajtai commitment, coming from [Lyu12], needs to provide to the verifier the responses of the form $cs_i + y_i$ for a challenge $c$. Those elements can leak information on $s_i$ which is avoided using rejection sampling. We want to modify the commitment scheme in order to prevent the use of rejection sampling by having non-leaking responses. The recent assumption Hint-MLWE [KLSS23] is aimed at resolving this problem, saying that the responses (no matter their distribution) do not leak any information about $s_i$, in the specific case where $s_i$ follows a Gaussian distribution. This was used in [HSS24] where the authors construct the Modified-Ajtai commitment scheme with an opening satisfying the zero-knowledge property over Hint-MLWE. In order to prove knowledge of an element $s_1 \in \mathbb{R}_p^{m_1}$, they simply redefined the Ajtai commitment for a Gaussian encoded element $\tilde{s}_1 \in \mathbb{R}_p^{km_1}$ (linked to $s_1$) by transmitting $t_A = \tilde{A}_1\tilde{s}_1 + A_2s_2$. The overall security is also based on MSIS and MLWE, only the zero-knowledge property of the opening is modified from the original version by being shown over the hardness of Hint-MLWE instead of different instances of rejection sampling. This is done by the “Gaussianisation” process that encodes $s_1$ in base $b$ (i.e. $s_1 = \sum_{i \in [k-1]} \hat{s}_{1,i} b^i$). This process in done coordinate-wise (over the vector, and over the coefficients of the polynomials). Proceeding over the modulo $p$, the process can be made probabilistic as in [MP12, Theorem 4.1] and can be seen as $\hat{s} = G_{b,\sigma}^{-1} s$ mod $p$ for a positive $\sigma$ such that $G_b \hat{s} = s$ mod $p$ (deterministic) by denoting the gadget vector $G_b := I_{m_1} \otimes g_{b,k}^\top := I_{m_1} \otimes [1 \ b \ \dots \ b^{k-1}]$.

In order to provide a general framework, the authors of [LNP22] showed that the Ajtai commitment can be launched with additional BDLOP commitments from $[\text{BDL}^{+18}]$ of the form $t_B = Bs_2 + m$ for unbounded messages $m$ with the same randomness $s_2$. This commitment is called ABDLOP. As the commitment size is linear in the size of the message, the BDLOP part was intended to be used carefully. Another important point of the Modified-Ajtai commitment scheme is that the committed encodings are not bounded. In our case, we adapt this construction and join to it the same BDLOP construction forming the Rejection-Free ABDLOP commitment scheme. With the Gaussianisation, we commit to elements only by the Ajtai part; the (expensive) BDLOP part will only be used dynamically (used to commit elements during the execution), as both norm bounded and unbounded elements can be initially committed using the (rejection-free) Ajtai part of the commitment scheme. As in the original ABDLOP, the overall opening process is restricted to the one the Ajtai part by computing $m = t_B - Bs_2$. We also adapt the original opening process for a different challenge space $C$. This involves enlarging some parameters and slightly modifying the security proofs.

Proving only the knowledge of an element $s$ is not optimal. Commit-and-prove protocol such as the framework [LNP22] additionally allows proving that a secret satisfies a bunch of relations. The prover can ensure quadratic relations over $s$ but also over an automorphism $\sigma(s)$ (without additionally committing to
it). In a second step, they also provide the ability to the prover to prove norm bounds of these relations. Unlike [LNP22], we do not commit the initial message but a randomized encoded version of it, therefore we must modify the framework in consequence and show new adapted proofs of completeness. In [LNP22], they used the fact that a quadratic relation regarding a message **s** can be viewed as the result of the function $f(\mathbf{s}) = \mathbf{s}^\top \mathbf{R}_2 \mathbf{s} + \mathbf{r}_1^\top \mathbf{s} + r_0$. We adapt it to a new relation $\tilde{f}$ over the randomized encoding $\tilde{\mathbf{s}}$ such that $\tilde{f}(\tilde{\mathbf{s}}) = 0$ implies that $f(\mathbf{s}) = 0$. As we have the relation $\mathbf{s} = [\mathbf{I}_n \otimes \mathbf{g}_{b,k}^\top] \cdot \tilde{\mathbf{s}}$ over $\mathcal{R}_p$, we obtain the equality $\tilde{f}(\tilde{\mathbf{s}}) = \tilde{\mathbf{s}}^\top \cdot (\mathbf{R}_2 \otimes [\mathbf{g}_{b,k}^\top \otimes \mathbf{g}_{b,k}]) \cdot \tilde{\mathbf{s}} + [\mathbf{r}_1 \otimes \mathbf{g}_{b,k}^\top] \cdot \tilde{\mathbf{s}} + r_0 = f(\mathbf{s}) \bmod p$.

In [LNP22], their protocol allowed relations over **s** and any $\mathcal{R}$-automorphism of it with the only the commitment of **s**. In our case we only consider the conjugate automorphism $\sigma_{-1} : X \mapsto X^{-1}$, which has an important impact. The relevance is simple and comes from an easy tool from [LNP22, Lemma 2.4]; the constant coefficient of the trace application $\text{tr} : \sum_{i \in [n]} \sigma_{-1}(\mathbf{a}_i) \cdot \mathbf{b}_i$ is equal to $\langle \mathbf{a}, \mathbf{b} \rangle \in \mathbb{Z}_p$ for $\mathbf{a}, \mathbf{b} \in \mathcal{R}^n$. Then, it permits to prove relations over $\mathbb{Z}_p$ and not just over $\mathcal{R}_p$ by using the same mechanism as in [LNP22] that allows to prove that a relation has a zero constant coefficient. In our protocol, as for the quadratic relations, this is implied from the encoding protocol as we have $\sigma_{-1}(\tilde{\mathbf{s}}) = \tilde{\sigma}_{-1}(\mathbf{s})$. Putting everything together, we can launch a protocol of proof of knowledge with quadratic relations over $\mathcal{R}_p$ and/or $\mathbb{Z}_p$, exploiting [LNP22, Section 4].

## 1.3 Limitations

The original version of the protocol permits to prove relations over the secret and one of its automorphisms. In our case, we only specify the case of $\sigma_{-1}$ because we exploit an inherent structure of this automorphism. A generalization regardless of the automorphism may be useful but will involve modifying the Gaussianisation method and inevitably our entire construction. Along with the first limitation, intrinsically dependent on the Gaussianisation method, the protocol imposes a proof environment $\mathcal{R}_p$ where $p = b^k + 1$ a prime modulus. Together with our protocol, our challenge space restricts the choice of $k$ to the specific case of $k = 2$. Finding a new challenge space that does not restrict ourselves to this choice of $k$ together with the automorphism invariant condition $c = \sigma_{-1}(c)$ is an interesting open question. As the bounds of the security assumptions necessary depend on the choices of $b$ (and $k$), it restricts the choice of $p$ to be a prime higher than $\approx 2^{50}$. The last limitations is that we are not able to prove approximate norm bounds of relations over the secrets as it was build in the [LNP22] framework. At least, it is still possible to apply the [LNP22, Section 5] strategy by recomputing the secret from the encoding and perform rejection sampling. It would be interesting to prove those relations using the pros of our protocol in order to obtain a fully rejection-free proof.

## 1.4 Related works

As already mentioned, [LNP22] constructs a generalized framework for proving knowledge of an element **s** such that $f(\mathbf{s}) = 0$ for every $\mathbf{f} \in \mathcal{F}$. They prove
the zero-knowledge property assuming various instances of rejection sampling, without considering potential side-channels attacks neither the cost of protecting it with masking. In our generated framework, we provide a rejection-free alternative of [LNP22] inspired by techniques from [HSS24]. In this paper, the authors construct a polynomial commitment allowing a prover to commit to a polynomial $f$ and convincing a prover that $y = f(x)$ for public $y$ and $x$ without revealing $f$. They based their construction on a homomorphic decoding protocol. In our work, we exploit their techniques, but in order to commit to an element $x$ and convince a prover that $f(x) = 0$ for a public relation $f$ without revealing $x$.

We identify in the literature different alternatives for removing the rejection sampling [BCM21, DFPS22, DPS23]. In the first article, the authors propose an alternative to the Lyubashevsky Signature Scheme [Lyu09] by restricting the construction to deal with both secret keys and masks being distributed uniformly over a hypercube. They also conjecture that all the rejection sampling steps do not have the same impact and that it may be difficult to remove abortion steps while maintaining the correctness of the protocol. In the other papers, the authors exploits Gaussian convolution distributions: by choosing compensating covariance matrices, they manage to construct hints that do not leak information even without rejection sampling. These papers only focused on constructing a rejection-free signature scheme and not a commit-and-prove framework.

# 2 Preliminaries

## 2.1 Notations and Definitions

**Notations** For $n \in \mathbb{N}$, we define $[n] := \{0, \dots, n-1\}$. Lower-case $v$ letters mean elements of $\mathcal{R}$, $\vec{v}$ are the same elements viewed as vectors (of size $d$) of coefficients. Bold lower-case $v$ letters denote column-vectors with coefficients being elements of $\mathcal{R}$, and bold upper-case $A$ letters for matrices with coefficients in $\mathcal{R}$. We write $x \stackrel{\$}{\leftarrow} S$ when $x$ is uniformly sampled from a finite set $S$.

**Number Theory.** We denote $\mathbb{Z}_q := \mathbb{Z}/q\mathbb{Z}$, $K := \mathbb{Q}[X]/\langle\phi_d(X)\rangle$ where $\phi_d(X)$ denotes the $d$-cyclotomic polynomial (we restrict the choice of $d$ being a power of 2), and $\mathcal{R}$ its ring of integers $\mathcal{R} := \mathbb{Z}[X]/\langle\phi_d(X)\rangle$. Also we denote $\mathcal{R}_q := \mathcal{R}/q\mathcal{R}$. We specify the notation of the automorphism $\sigma := \sigma_{-1} \in \mathrm{Aut}(\mathcal{R}) : X \mapsto X^{-1}$.

**Norms.** For a vector of polynomials $\mathbf{f} = (f_0, \dots, f_{n-1}) \in \mathcal{R}^n$, the norm is the norm of each coefficient: $\|\mathbf{f}\|_q := \sqrt[q]{\sum_{i \in [n]} \|f_i\|_q^q}$, same for the infinite norm: $\|\mathbf{f}\|_{\infty} := \max_{i \in [n]} \|f_i\|_{\infty}$. For $\mathcal{M} \in \mathbb{C}^{n \times m}$, $\|\mathcal{M}\| := s_{\max}(\mathbf{A}) = \sqrt{|\lambda_{\max}(\mathcal{M}^{\top}\mathcal{M})|}$.

**Gadgets.** We remind the construction of the "gadget" vector and its standard definition for an integer $b$: $\mathbf{g}_{b,k}^{\top} = [1, b, \dots, b^{k-1}] \in \mathcal{R}^k$. We extend the definition over $n$ elements names as the gadget matrix $\mathbf{G}_{b,k,n} := \mathbf{I}_n \otimes \mathbf{g}_{b,k}^{\top} \in \mathcal{R}^{n \times nk}$. We
denote a probabilistic "inverse" $G_{b,\sigma}^{-1}$ allowing to generate a non-unique preimage $\hat{t}$ of $t$ such that $G\hat{t} = t$ i.e $\hat{t} \leftarrow D_{\Lambda_{\hat{t}}^{\top}(G),\sigma}$ as explained in [MP12, Theorem 4.1].

## 2.2 Lattices

**Lattices.** A lattice, denoted by $\Lambda$, is a discrete subgroup of $\mathbb{R}^n$ with additive operations. It can be defined by a basis $B = (\vec{b}_i)_{i \in [m]} \in \mathbb{R}^{n \times m}$ such that it is denoted by $\Lambda = \{ \sum_{i \in [m]} x_i \cdot \vec{b}_i \mid \vec{x} \in \mathbb{Z}^m \}$, where $m$ is its dimension. We defined its dual lattice $\Lambda^* := \{ x \mid \langle x, z \rangle \in \mathbb{Z} \ \forall z \in \Lambda \}$. We have $\Lambda = (\Lambda^*)^*$. We remind structured lattice using cyclotomic ring in Appendix B.1.

**Probability Distributions.** In our case, $D_{\Lambda, \vec{c}, \sigma}$ describe a discrete Gaussian distribution over $\Lambda$, centered in $\vec{c} \in \mathbb{R}^m$ with standard deviation $\sigma$ such that for any $\vec{x} \in \mathbb{R}^n$, $\rho_{\vec{c}, \sigma}(\vec{x}) := \exp\left(-\frac{\|\vec{x} - \vec{c}\|^2}{2\sigma^2}\right)$, and $D_{\Lambda, \vec{c}, \sigma}(\vec{x}) := \frac{\rho_{\vec{c}, \sigma}(\vec{x})}{\rho_{\vec{c}, \sigma}(\Lambda)}$ where $\rho_{\vec{c}, \sigma}(\Lambda) = \sum_{x \in \Lambda} \rho_{\vec{c}, \sigma}(\vec{x})$. We also define the sampling of a vector of an Elliptic Gaussian using an associated covariance matrix defined by a positive-definite matrix, denoted by $\Sigma := \sqrt{\Sigma}^\top \sqrt{\Sigma}$. The probability is now defined by: $\rho_{\sqrt{\Sigma}}(\vec{x}) = \exp(-\pi(\vec{x} - \vec{c})^\top \Sigma^{-1} (\vec{x} - \vec{c}))$. If $\Lambda$ is a structured lattice, we sample its vector of coefficients and embed it as a polynomial of $\mathbb{R}$. We write directly polynomials.

**Smoothing Parameter.** We remind the definition of the smoothing parameter from [MR07, Definition 3.1] as $\eta_{\varepsilon}(\Lambda)$, the smallest standard deviation $\sigma$ such that $\rho_{\frac{1}{\sigma}}(\Lambda^* \setminus \{0\}) \le \varepsilon$. The definition has been extended for covariance matrices in [Pei10, Definition 2.3] such that if $\eta_{\varepsilon}(\sqrt{\Sigma}^{-1}\Lambda) \le 1$ therefore $\sqrt{\Sigma} \ge \eta_{\varepsilon}(\Lambda)$.

**Lemma 2.1 ([KLSS23, Lemma 5]).** If $\|\Sigma^{-1}\| \le \frac{1}{\eta_{\varepsilon}(\Lambda)^2}$ then $\sqrt{\Sigma} \ge \eta_{\varepsilon}(\Lambda)$.

**Lemma 2.2 ([MR07, Lemma 4.4]).** Let $\Lambda$ a $n$-dimensional lattice, an ar-bitrary vector $\vec{c} \in \mathbb{R}^n$, $0 < \varepsilon < 1$ and $\sigma \ge \eta_{\varepsilon}(\Lambda)$. Let $\tilde{z} \leftarrow D_{\Lambda, \vec{c}, \sigma}$. Then: $\mathbb{P}[\|\tilde{z} - \vec{c}\| > \sigma\sqrt{n}] \le \frac{1+\varepsilon}{1-\varepsilon} \cdot 2^{-n}$. If $0 < \varepsilon < \frac{1}{3}$ then: $\mathbb{P}[\|\tilde{z} - \vec{c}\| > \sigma\sqrt{n}] \le 2^{-n+1}$.

In our construction, we will use [HSS24, Lemma 11] in the case of structured lattice with polynomials instead of vector of coefficients.

**Lemma 2.3 (Structured version of [HSS24, Lemma 11]).** Let $\mathcal{R}_p^n$ a $n$-dimensional lattice over the ring $\mathcal{R}$ and a modulo $p$. Let $\ell > 0$ an integer. Define $\Sigma \in \mathbb{R}^{nd \times nd}$ a covariance matrix, associated to a secret sampling. Define $\ell$ covariance matrices $\Sigma_i \in \mathbb{R}^{nd \times nd}$, generating $c_i \in \mathcal{R}_p$ and $C_i := \text{Rot}_{nd}(c_i)$.

If we suppose $\sqrt{(\Sigma^{-1} + \sum_{i \in [\ell]} C_i^T \Sigma_i^{-1} C_i)^{-1}} \ge \eta_{\varepsilon}(\mathbb{R}^n)$, then for any center $\vec{u} \in \mathbb{R}^n$, then the following two distributions over $(\mathbb{R}^n)^\ell$ are at statistical $2\varepsilon$:
$$ \left\{ \begin{array}{l} (\mathbf{z}_1, \dots, \mathbf{z}_\ell) \;\middle|\; \mathbf{s} \leftarrow \mathcal{D}_{\mathbf{u}+\mathbb{R}^n, \sqrt{\Sigma}, \mathbf{y}_i} \leftarrow \mathcal{D}_{-C_i \mathbf{u}+\mathbb{R}^n, \sqrt{\Sigma}_i}, \mathbf{z}_i = c_i \mathbf{s} + \mathbf{y}_i \right\}, \\ \\ (\mathbf{z}_1, \dots, \mathbf{z}_\ell) \;\middle|\; \mathbf{s}' \leftarrow \mathcal{D}_{\mathbb{R}^n, \sqrt{\Sigma}, \mathbf{y}_i} \leftarrow \mathcal{D}_{\mathbb{R}^n, \sqrt{\Sigma}_i}, \mathbf{z}_i = c_i \mathbf{s}' + \mathbf{y}_i \end{array} \right\}. $$

We use the simplified discrete convolution lemma, initially defined in [Pei10].

**Lemma 2.4 (Discrete Convolution Lemma from [HSS24, Lemma 7]).**
Let $\Sigma_1, \Sigma_2$ be positive-definite matrices. Let two $n$-dimensional lattices $\Lambda_1$ and $\Lambda_2$ such that $\Lambda_2 \subseteq \Lambda_1$. If $\sqrt{\Sigma_1} \ge \eta_\epsilon(\Lambda_1)$ and $\Sigma_3^{-1} := \Sigma_1^{-1} + \Sigma_2^{-1}$ satisfies $\sqrt{\Sigma_3} \ge \eta_\epsilon(\Lambda_2)$ for $0 < \epsilon < \frac{1}{2}$. Then, for arbitrary $\tilde{c}_1, \tilde{c}_2 \in \mathbb{R}^n$, the distribution of the convolution defined by $\mathcal{C} := \{\mathbf{x}_1 + \mathbf{x}_2 \mid \mathbf{x}_1 \leftarrow \mathcal{D}_{\Lambda_1, \tilde{c}_1, \sqrt{\Sigma_1}}, \mathbf{x}_2 \leftarrow \mathcal{D}_{\Lambda_2, \tilde{c}_2, \sqrt{\Sigma_2}}\}$ is within statistical distance $8\epsilon$ of $\mathcal{D}_{\Lambda_1, \tilde{c}_1+\tilde{c}_2, \sqrt{\Sigma_1+\Sigma_2}}$.

**Assumptions.** We remind the definitions of M(I)SIS and (Hint-)MLWE.

**Definition 2.1 (M(I)SIS [LS15]).** Given $n > 0$, $m(n)$, $B(n) > 0$ and a modulo $q(n)$ such that $B < q$. Consider a public and uniformly sampled matrix $\mathbf{A} \in \mathbb{R}_q^{n \times m}$, a target $\mathbf{t} \in \mathbb{R}_q^n$, the Module (Inhomogenous) Short Integer Solution $\text{MSIS}_{\mathbb{R},q,n,m,\beta}$ problem asks for a solution $\mathbf{x} \in \mathbb{R}_q^m$ with $0 < \|\mathbf{x}\| \le \beta$ that solves $\mathbf{A}\mathbf{x} = \mathbf{t}$ over $\mathbb{R}_q$. The $\text{MSIS}_{\mathbb{R},q,n,m,\beta}$ assumption is the special case where $\mathbf{t} = \mathbf{0}$.

**Definition 2.2 (MLWE [LS15, Definition 4.1]).** Given $n, \ell, m > 0$ and a distribution $\chi$ over $\mathbb{R}^{m+n}$. Consider a random matrix $\mathbf{A} \stackrel{\$}{\leftarrow} \mathbb{R}_q^{m \times n}$, a secret $\mathbf{r} \leftarrow \chi$ parsed as $[\mathbf{s}^\top, \mathbf{e}^\top]$ for the MLWE sample. The $\text{MLWE}_{\mathbb{R},q,n,m,\ell,\chi}$ problem asks to distinguish between an honest $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e})$ and $(\mathbf{A}, \mathbf{b})$ for $\mathbf{b} \stackrel{\$}{\leftarrow} \mathbb{R}_q^m$.

**Definition 2.3 (Hint-MLWE [KLSS23, Definition 7]).** Given $n, \ell, m > 0$ and distributions $\chi$, $\xi_1, \dots, \xi_\ell$ over $\mathbb{R}^{m+n}$ and $\Gamma$ is one over $\mathbb{R}$. Consider a random matrix $\mathbf{A} \stackrel{\$}{\leftarrow} \mathbb{R}_q^{m \times n}$, a secret $\mathbf{r} \leftarrow \chi$ parsed as $[\mathbf{s}^\top, \mathbf{e}^\top]$ for the MLWE sample. Consider $\ell$ hints as $\mathbf{z}_i = c_i \mathbf{r} + \mathbf{y}_i$, with $c_i \leftarrow \Gamma$ and $\mathbf{y}_i \leftarrow \xi_i$. The $\text{Hint-MLWE}_{\mathbb{R},q,n,m,\ell,\chi,\xi_1,\dots,\xi_\ell,\Gamma}$ problem asks to distinguish between an honest $(\mathbf{A}, \mathbf{A}\mathbf{s} + \mathbf{e}, (c_i)_{i \in [\ell]}, (\mathbf{z})_{i \in [\ell]}$ and $(\mathbf{A}, \mathbf{b}, (c_i)_{i \in [\ell]}, (\mathbf{z})_{i \in [\ell]}$ for $\mathbf{b} \stackrel{\$}{\leftarrow} \mathbb{R}_q^m$.

As shown above, the assumption is a relaxed alternative to the classical MLWE with $\ell$ linear hints over the secret element $\mathbf{r}$. The assumption was shown in [KLSS23] to be as hard as a MLWE instance in the restricted case where the element $\mathbf{r}$ and the masks $\mathbf{y}_i$ follow Gaussian distributions. We recall the hardness of Hint-MLWE from [ENP24] with Elliptic Gaussians distributions.

**Theorem 2.1 (Hardness of Hint-MLWE [ENP24, Theorem 2]).** Let $n, m, q$ and $\ell$ be positive integers and $\Gamma$ a distribution over $\mathbb{R}$. We define upper bounds $\beta_i$ such that $\beta_i^2 \ge \|c_i\|_1^2 > 0$, where each $c_i$ is sampled from $\Gamma$. For the covariance matrices $\Sigma_1, \Sigma_{2,1}, \dots, \Sigma_{2,\ell}$, we define $\sigma$ as $\frac{1}{\sigma^2} = 2(s_1(\Sigma_1^{-1}) + \sum_{i \in [\ell]} \beta_i^2 s_1(\Sigma_{2,i}^{-1}))$. If $\sigma \ge \sqrt{2} \cdot \eta_\epsilon(\mathbb{R}^{n+m})$, for some $0 < \epsilon \le \frac{1}{2}$, then there is an polynomial reduction from $\text{MLWE}_{\mathbb{R},q,n,m,\mathcal{D}}$ to $\text{Hint-MLWE}_{\mathbb{R},q,n,m,\ell,\mathcal{D}}$ that reduces the advantage by at most $2\epsilon$.
## 2.3 Ajtai and ABDLOP commitment schemes

**Ajtai commitment scheme** We remind the original Ajtai commitment scheme inspired from [Ajt96] and describe a Lyubashevsky-like proof of opening [Lyu12].

**Parameters** : Let $n \in \mathbb{N}$, $(\alpha_1, m_1) \in \mathbb{N}^2$ the message parameters and the others $m_2 \in \mathbb{N}$, $p \in \mathbb{N}$, $\sigma_2 \in \mathbb{R}^+$ are parametrised by $n$. $\mathcal{R}_p$ is a ring of degree $d$ (a power of 2). By defining $\mathcal{M}_{\alpha,m} := \{\|\mathbf{s}\|_2 \le \alpha \mid \mathbf{s} \in \mathcal{R}_p^m\}$, the message space is restricted to $\mathcal{M}_{\alpha_1,m_1}$ (with chosen $\alpha_1$) and randomness to $\mathcal{M}_{\alpha_2,m_2}$ for $\alpha_2 := \sigma_2\sqrt{m_2d}$.

- **Setup** $(1^{\lambda}) \to ck$: Given a security parameter $\lambda$, it generates a commitment key $ck = (\mathbf{A}_1, \mathbf{A}_2)$ where $\mathbf{A}_1 \stackrel{\$}{\leftarrow} \mathcal{R}_p^{n \times m_1}$ and $\mathbf{A}_2 \stackrel{\$}{\leftarrow} \mathcal{R}_p^{n \times m_2}$.

- **Commit** $(ck, \mathbf{s}_1, \sigma) \to (\mathbf{t}_A, \delta)$: Given a message $\mathbf{s}_1 \in \mathcal{M}_{\alpha_1, m_1}$ and $ck$ parsed as $(\mathbf{A}_1, \mathbf{A}_2)$. First, it samples $\mathbf{s}_2 \stackrel{\$}{\leftarrow} \mathcal{D}_{\mathcal{R}_p, \sigma_2}^{m_2}$ and verifies that $\mathbf{s}_2 \in \mathcal{M}_{\alpha_2, m_2}$. Then, it computes $\mathbf{t}_A = \mathbf{A}_1\mathbf{s}_1 + \mathbf{A}_2\mathbf{s}_2$ for the opening $\delta = (\mathbf{s}_1, \mathbf{s}_2)$.

An honest commitment can be viewed as an element of $\mathcal{R}_{\text{ajtai}}$:

$$ \mathcal{R}_{\text{ajtai}} := \left\{ \frac{(\mathbf{s}_1, \mathbf{s}_2) \in \mathcal{M}_{\alpha_1, m_1} \times \mathcal{M}_{\alpha_2, m_2}}{(\mathbf{A}_1, \mathbf{A}_2, \mathbf{t}_A) \in \mathcal{R}_p^{n \times m_1} \times \mathcal{R}_{p, \text{HNF}}^{n \times m_2} \times \mathcal{R}_p^n \mid \mathbf{A}_1 \mathbf{s}_1 + \mathbf{A}_2 \mathbf{s}_2 = \mathbf{t}_A} \right\}. $$

The binding property is based on MSIS$_{\mathcal{R},p,n,m_1+m_2,2\sqrt{\alpha_1^2+\alpha_2^2}}$. For the hiding property, a hard instance of MLWE$_{\mathcal{R},p,n,m_2,\mathcal{D}_{\sigma_2}}$ ensures indistinguishability of the hiding component $\mathbf{A}_2\mathbf{s}_2 = [\mathbf{I}_n \ \mathbf{A}'_2] \mathbf{s}_2$. Both rely on computational difficulty.

<figure><img src="image_2.png" /><figcaption>Fig. 1: Proof of Weak Opening of the Ajtai Commitment with a chosen $\alpha_i$</figcaption></figure>

**Challenge Space.** In the opening proof, we specify the same challenge space $\mathcal{C}$ than in [LNP22] using their Lemma 15 that ensures both the stability and the
smallness of element of $\mathcal{R}_p$ under a specific automorphism $\sigma_{-1} : X \mapsto X^{-1}$:

$$ \mathcal{C} := \left\{ c \in \mathcal{R}_p : \|c\|_1 \le \kappa, \sigma_{-1}(c) = c, \sqrt[2k]{\|\sigma(c^k) \cdot c^k\|_1} \le \eta \right\}. $$

For the opening, we must have a space $\bar{\mathcal{C}} := \{c-c' : c, c' \in \mathcal{C} \text{ where } c \ne c'\} \subseteq \mathcal{R}_q^\times$.

**Lemma 2.5 ([LNP22, Lemma 2.6]).** Let $p = 5 \mod 8$ being a prime. For any $c \in \mathcal{R}_p$ such that $c = \sigma(c)$. Then $c$ is invertible if and only if $c \ne 0$.

**Original proof of Opening of Lyubashevsky [Lyu12].** The process opens to an element of $\bar{\mathcal{R}}_{\text{ajtai}}$. We need to specify for a good choice of parameters that with overwhelming probability, we have $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{\mathcal{R}}_{\text{ajtai}} \Rightarrow (\bar{s}_1, \bar{s}_2) \in \mathcal{R}_{\text{ajtai}}$.

$$ \bar{\mathcal{R}}_{\text{ajtai}} := \left\{ \frac{(\bar{s}_1, \bar{s}_2, \bar{c}) \in \mathcal{M}_{\beta_1, m_1} \times \mathcal{M}_{\beta_2, m_2} \times \bar{\mathcal{C}} : (\mathbf{A}_1, \mathbf{A}_2, \mathbf{t}_A) \in \mathcal{R}_p^{n \times m_1} \times \mathcal{R}_{p, \text{HNF}}^{n \times m_2} \times \mathcal{R}_p^n \mid \mathbf{A}_1 \bar{s}_1 + \mathbf{A}_2 \bar{s}_2 = \mathbf{t}_A}{\mathbf{A}_1 \bar{s}_1 + \mathbf{A}_2 \bar{s}_2 = \mathbf{t}_A} \right\}. $$

Soundness and Completeness are shown for a good choice of parameters and standard deviations $\mathfrak{s}_i$ of the masks $y_i$. The zero-knowledge property is ensured assuming rejection sampling methods on the responses $z_i$. We remind the proof of opening of the Ajtai commitment scheme in Figure 1 with $\mathfrak{s}_i := \gamma_i \eta \alpha_i$ with $\gamma_i$ the rejection rate of the $i$-th rejection sampling. Consider a good ring $\mathcal{R}$ such that $m_i d - 1 \ge \lambda$ (the security parameter). By taking $\sigma_2 \le \eta_\epsilon (\mathcal{R}_p^{m_2})$, we restrict randomness to $\alpha_2 := \sigma_2 \sqrt{m_2 d}$. and set valid opening bounds $\beta_i := \mathfrak{s}_i \sqrt{2m_i d}$.

**ABDLOP Commitment Scheme [LNP22].** The Ajtai commitment suffers from two distinct limitations. First, the message space is restricted to bounded polynomials (by $\alpha_1$), second it does not permit transmitting and committing to additional elements dynamically (during the execution of the protocol). As the global aim of the framework is to prove various relations depending on each other, we need to extend the actual Ajtai commitment scheme to solve that point. In [LNP22], the authors join to it the BDLOP construction from [BDL$^+$18], giving the new ABDLOP commitment scheme, exploiting the same randomness $\mathfrak{s}_2$ for both components. The lower part of the commitment (the BDLOP instance) is only used for dynamic messages $\mathbf{m} \in \mathcal{R}_p^\ell$ depending on the execution of the protocol, as $\mathbf{B}$ can be extended and transmitted during the execution.

$$ \mathcal{R}_{\text{abdlop}} := \left\{ \frac{(\mathfrak{s}_1, \mathfrak{s}_2, \mathbf{m}) \in \mathcal{M}_{\alpha_1, m_1} \times \mathcal{M}_{\alpha_2, m_2} \times \mathcal{R}_p^\ell : (\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B)) \in \mathcal{R}_p^{n \times m_1} \times \mathcal{R}_{p, \text{HNF}}^{n \times m_2} \times \mathcal{R}_{p, \text{HNF}}^{\ell \times m_2} \times \mathcal{R}_p^{n+\ell} \mid \begin{array}{c} \mathbf{A}_1 \mathfrak{s}_1 + \mathbf{A}_2 \mathfrak{s}_2 = \mathbf{t}_A \\ \mathbf{B} \mathfrak{s}_2 + \mathbf{m} = \mathbf{t}_B \end{array} \right\}. $$

As explained in the original paper, for well chosen parameters, we have with overwhelming probability that $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{\mathcal{R}}_{\text{abdlop}} \Rightarrow (\bar{s}_1, \bar{s}_2, \mathbf{t}_B - \mathbf{B}\bar{s}_2) \in \mathcal{R}_{\text{abdlop}}$. The opening relies essentially on the Ajtai opening $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{\mathcal{R}}_{\text{ajtai}}$.

$$ \bar{\mathcal{R}}_{\text{abdlop}} := \left\{ \frac{(\bar{s}_1, \bar{s}_2, \bar{c}) \in \mathcal{M}_{\beta_1, m_1} \times \mathcal{M}_{\beta_2, m_2} \times \bar{\mathcal{C}} : (\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B)) \in \mathcal{R}_p^{n \times m_1} \times \mathcal{R}_{p, \text{HNF}}^{n \times m_2} \times \mathcal{R}_{p, \text{HNF}}^{\ell \times m_2} \times \mathcal{R}_p^{n+\ell} \mid \begin{array}{c} \mathbf{A}_1 \bar{s}_1 + \mathbf{A}_2 \bar{s}_2 = \mathbf{t}_A \\ \bar{\mathbf{m}} = \mathbf{t}_B - \mathbf{B}\bar{s}_2 \end{array} \right\}. $$
### 3 Another usage of the Gaussianisation process

To build a rejection sampling free commit-and-prove protocol, we start by modifying the ABDLOP commitment scheme used in [LNP22] using the Modified-Ajtai commitment joined with the Gaussianisation process from [HSS24]. We manage to base the zero-knowledge security over a hard instance of Hint-MLWE instead of various instances of rejection sampling.

**The [HSS24] Gaussianisation method.** The [HSS24, Section 3] method is used to construct an encoding following a Gaussian distribution centered in the secret encoding. First, it computes an encoding $\hat{s}$ of an element $s \in \mathcal{R}_p^m$ for $p = b^k + 1$, exploiting $\hat{s} = G_b^{-1}s \in \mathcal{R}_p^{km}$, a decomposition in base $b$. In a second step, the encoding is randomized by sampling a non-influent error. At the end, it generates an additional error $e \leftarrow \mathcal{D}_{\mathcal{R}^{km}, \sigma}$ to construct the final randomized encoding $\tilde{t} = \hat{t} + p_m e$, with $p_m := X^{md} - b$. We remind the [HSS24] Gaussianisation method in Appendix B.3.

#### 3.1 RF-ABDLOP Commitment scheme

Here, we adapt the idea of the Modified-Ajtai commitment scheme from [HSS24] that commit to an encoded element $\tilde{s}_1$ rather than $s_1$ directly to ABDLOP, giving the Rejection-Free ABDLOP commitment scheme defined with:

$$ \mathbb{R}_{\text{RF}} := \left\{ \begin{array}{@{}l@{}} \frac{(\mathbf{s}_1, \mathbf{s}_2, \mathbf{m}) \in \mathcal{R}_p^{m_1} \times \mathcal{M}_{\alpha_2, m_2} \times \mathcal{R}_p^{\ell}}{\left(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B)\right) \in \mathcal{R}_p^{n \times km_1} \times \mathcal{R}_{p, \text{HNF}}^{n \times m_2} \times \mathcal{R}_{p, \text{HNF}}^{\ell \times m_2} \times \mathcal{R}_p^{n+\ell}} \\ \left| \begin{array}{@{}l@{}} \mathbf{A}_1 \tilde{s}_1 + \mathbf{A}_2 \tilde{s}_2 = \mathbf{t}_A \\ \mathbf{B}s_2 + \mathbf{m} = \mathbf{t}_B \\ \tilde{s}_1 = \text{RandomizedEncode}(s_1, \sigma_1) \end{array} \right. \end{array} \right\}. $$

**Theorem 3.1 (Binding).** The Rejection-Free ABDLOP commitment scheme is binding if it satisfies for $\varepsilon = \text{negl}(\lambda)$, the following conditions: $\sigma_1 \ge \eta_e(\mathcal{R}^{km_1})$, $\sigma_2 \ge \eta_e(\mathcal{R}^{m_2})$, $km_1d - 1 \ge \lambda$, $m_2d - 1 \ge \lambda$ and the hardness of the assumption $\text{MSIS}_{\mathbb{R},p,n,km_1+m_2,2\sqrt{\alpha_1^2+\alpha_2^2}}$ for $\alpha_1 = (b+1)\sigma_1\sqrt{km_1d}$ and $\alpha_2 = \sigma_2\sqrt{m_2d}$.

*Proof.* Suppose having two accepted tuples $(\mathbf{s}_1, \mathbf{m}, \mathbf{s}_2)$ and $(\mathbf{s}'_1, \mathbf{m}', \mathbf{s}'_2)$ for a same commitment $\mathbf{t}_A, \mathbf{t}_B$. Then, we can recover $\mathbf{A}_1\mathbf{s}'_1 + \mathbf{A}_2\mathbf{s}'_2 := \mathbf{A}_1(\tilde{\mathbf{s}}_1 - \tilde{\mathbf{s}}'_1) + \mathbf{A}_2(\mathbf{s}_2 - \mathbf{s}'_2) = \mathbf{0}$. If the tuples are not equals, then we found a valid MSIS solution using Lemma 2.2 to bound $\| (\mathbf{s}'_1, \mathbf{s}'_2) \| \le 2\|(\tilde{\mathbf{s}}_1, \mathbf{s}_2)\| \le 2\sqrt{\|\tilde{\mathbf{s}}_1\|^2 + \|\mathbf{s}_2\|^2} \le 2\sqrt{\alpha_1^2 + \alpha_2^2}$ as we can also bound $\|\tilde{\mathbf{s}}_1\| = \|\hat{\mathbf{s}}_1 + \mathbf{p}_m e\| \le \|\mathbf{p}_m\| \cdot \|e\| \le (b+1)\sigma_1\sqrt{km_1d}$. $\square$

**Theorem 3.2 (Hiding).** $\text{MLWE}_{\mathbb{R},p,n+\ell,m_2,\mathcal{D}_{\sigma_2}}$ implies the hiding of RF-ABDLOP.

*Proof.* Hardness of MLWE implies $[\mathbf{A}_2^\top \mathbf{B}^\top]^\top \mathbf{s}_2 \approx_c \mathcal{U}(\mathcal{R}_p^{n+\ell})$, hence hiding. $\square$

Security parameters will change accordingly, as the length of the $\tilde{s}_1$ is $k$ times longer $s_1$. We choose parameters in order to have with overwhelming probability that $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{\mathbb{R}}_{\text{RF}} \Rightarrow (\text{Decode}(\bar{s}_1), \mathbf{t}_B - \mathbf{B}\bar{s}_2, \bar{s}_2) \in \mathbb{R}_{\text{RF}}$.
$$ \bar{R}_{RF} := \left\{ \begin{array}{l} \frac{(\bar{s}_1, \bar{s}_2, \bar{c}) \in \mathcal{R}_p^{km_1} \times \mathcal{M}_{\beta_2, m_2} \times \bar{C}}{\left(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B)\right) \in \mathcal{R}_p^{n \times km_1} \times \mathcal{R}_{p, \text{HNF}}^{n \times m_2} \times \mathcal{R}_p^{\ell \times m_2} \times \mathcal{R}_p^{n+\ell} \mid \begin{array}{c} \mathbf{A}_1 \bar{s}_1 + \mathbf{A}_2 \bar{s}_2 = \mathbf{t}_A \\ \bar{\mathbf{m}} = \mathbf{t}_B - \mathbf{B} \bar{s}_2 \end{array}} \end{array} \right\} $$

The proof of opening is ensured over well-chosen standard deviations of the mask $\mathbf{y}_i$. These masks follow discrete Gaussian distribution with standard deviations $\sqrt{2}\mathbf{s}_i$. In our work, the slight modification only concerns the challenge described in Section 2.3, which only affects the bounds related to the lattice assumptions, resulting in the following proofs. As the transmitted $\bar{s}_i$ follows a Gaussian distribution, the zero-knowledge property is now assumed over a hard instance of Hint-MLWE, using the transmitted $\mathbf{z}_i$ as hints.

The protocol is defined as a subpart of the future framework of proof, presented in Figure 2 for $\mathcal{F} = \emptyset$. The proof of opening follows the same construction as the one from the Ajtai commitment scheme presented in Figure 1.

**Theorem 3.3 (Completeness).** The proof of opening knowledge satisfies completeness if it satisfies for $\varepsilon = \text{negl}(\lambda)$ the following conditions: $\sigma_1, \sqrt{2}\mathbf{s}_1 \ge \eta_\varepsilon(\mathcal{R}^{km_1})$; $\sigma_2, \mathbf{s}_2 \ge \eta_\varepsilon(\mathcal{R}^{m_2})$ for the bounds $\beta_{\text{open},1} = (b+1)(\eta\sigma_1 + \sqrt{2}\mathbf{s}_1)\sqrt{km_1d}$ and $\beta_{\text{open},2} = (\eta\sigma_2 + \mathbf{s}_2)\sqrt{m_2d}$.

*Proof.* For the first verification step, $\|\mathbf{z}_i\| \le \beta_{\text{open},i}$ it is checked by Lemma 2.2 instantiated for the 4 conditions about the standard deviations. The norm of $\tilde{\mathbf{s}}_1$ is bounded the same way as in the proof of binding of the commitment scheme, for $\tilde{\mathbf{s}}_1$ and $\tilde{\mathbf{y}}_1$. The second verification step follows from the original construction. $\square$

**Theorem 3.4 (Knowledge Soundness).** Consider the parameters defined in Theorem 3.1. An extractor either produce a valid unique opening $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{R}_{RF}$ with non negligible probability or a $\text{MSIS}_{\mathcal{R},p,n,km_1+m_2,8\eta\sqrt{\beta_{\text{open},1}^2+\beta_{\text{open},2}^2}}$ solution.

*Proof.* Assuming the parameters, RF-ABDLOP is binding. Let's assume that the extractor finds two acceptable transcripts with a rewind before the challenge sampling. The two transcripts are $(\mathbf{w}, c, \tilde{\mathbf{z}}_1, \mathbf{z}_2)$ and $(\mathbf{w}, c', \tilde{\mathbf{z}}'_1, \mathbf{z}'_2)$ for a same commitment $(\mathbf{t}_A, \mathbf{t}_B)$. The proof follows the one from [LNP22, Lemma 3.1]. Define $\bar{c} := c' - c, \bar{\mathbf{z}}_i := \tilde{\mathbf{z}}'_i - \tilde{\mathbf{z}}_i$ and $\bar{s}_i := \frac{\bar{c}_i}{\bar{c}}$. As the transcripts were accepted, we have $\mathbf{A}_1\bar{s}_1 + \mathbf{A}_2\mathbf{s}_2 - c\mathbf{t}_A = \mathbf{A}_1\tilde{\mathbf{s}}'_1 + \mathbf{A}_2\mathbf{s}'_2 - c'\mathbf{t}_A$ that implies $\mathbf{A}_1\bar{s}_1 + \mathbf{A}_2\bar{s}_2 = \mathbf{t}_A$ then we will have $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{R}_{RF}$.

The unicity follows from [LNP22, Lemma 3.1], take $(\bar{s}_1, \bar{s}_2, \bar{c}), (\tilde{\mathbf{s}}'_1, \tilde{\mathbf{s}}'_2, \tilde{\mathbf{c}}') \in \bar{R}_{RF}$ for the same public parameters $(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, \mathbf{t}_A, \mathbf{t}_B)$. Take also $\bar{\mathbf{z}}_i$ and $\tilde{\mathbf{z}}'_i$ with the same construction as above. Then, we have $\mathbf{A}_1(\bar{s}_1 - \tilde{\mathbf{s}}'_1) + \mathbf{A}_2(\bar{s}_2 - \tilde{\mathbf{s}}'_2) = \mathbf{0}$, but here the $\text{MSIS}$ is not bounded. Therefore, we proceed as in [LNP22, Lemma 3.1], we construct another $\text{SIS}$ solution with $\mathbf{s}_i^* := (\bar{s}_i - \tilde{\mathbf{s}}'_i)\bar{c} \cdot \bar{c}' = \bar{\mathbf{z}}_i\bar{c}' - \tilde{\mathbf{z}}'_i\bar{c}$ where we exploit the verification step (of the norms of the responses) to prove the size of the solution: $\|(\mathbf{s}_1^*, \mathbf{s}_2^*)\| \le 2 \cdot 2\eta \cdot 2\|(\tilde{\mathbf{z}}_1, \mathbf{z}_2)\| \le 8\eta\sqrt{\beta_{\text{open},1}^2 + \beta_{\text{open},2}^2}$. $\square$
**Private information:**

Initial messages: $(\mathbf{s}_1, \mathbf{m}) \in \mathbb{R}_p^{m_1+\ell}$,

Sampled on instantiation: $\mathbf{s}_2 \leftarrow \mathcal{D}_{\mathbb{R}_p, \sigma_2}^{m_2}$, $\tilde{\mathbf{s}}_1 = \text{RandomizedEncode}(\mathbf{s}_1, \sigma_1) \in \mathbb{R}_p^{km_1}$.

**Public information:**

$\mathbf{A}_1 \in \mathbb{R}_p^{n \times k m_1}$, $\mathbf{A}_2 \in \mathbb{R}_p^{n \times m_2}$, $\mathbf{B} \in \mathbb{R}_p^{\ell \times m_2}$, $\mathbf{b}_1 \in \mathbb{R}_p^{m_2}$, $\sigma := \sigma_{-1} \in \text{Aut}(\mathbb{R}_p)$,

$$ \begin{bmatrix} \mathbf{A}_1 \\ \mathbf{0}^{\ell \times m_1} \end{bmatrix} \tilde{\mathbf{s}}_1 + \begin{bmatrix} \mathbf{A}_2 \\ \mathbf{B} \end{bmatrix} \mathbf{s}_2 + \begin{bmatrix} \mathbf{0} \\ \mathbf{m} \end{bmatrix} = \begin{bmatrix} \mathbf{t}_A \\ \mathbf{t}_B \end{bmatrix} \mod p, $$

$\tilde{\mathcal{F}} = \{f_i\}_{i \in [N]}$ a set of quadratic relations as in eq. (1) and (2) s.t $f_i(\mathbf{s}) = 0 \mod p$ with $\mathbf{s}^\top := (\mathbf{s}_1^\top, \sigma(\mathbf{s}_1)^\top, \mathbf{m}^\top, \sigma(\mathbf{m})^\top)$.

<figure><img src="image_3.png" /><figcaption>Fig. 2: Proof of knowledge of an element $(\mathbf{s}_1, \mathbf{m})$ along with the proof that for $f_i \in \mathcal{F}$ where $\mathcal{F}$ is a public set of linear and quadratic relations, we have $f_i(\psi(\mathbf{s}_1, \mathbf{m})) = 0$. The protocol can also be instantiated with $\mathcal{F} = \emptyset$ without the underlined elements of the transcript (and their construction) and the underlined verification steps.</figcaption></figure>
$$S_{\underline{\text{REL-AUT-F}}}(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, \mathbf{b}_1)$$

1. **Targets:** $\mathbf{t}_A, \mathbf{t}_B \stackrel{\$}{\leftarrow} \mathcal{R}_p^{n+\ell}$, **Challenges:** $c \stackrel{\$}{\leftarrow} \mathcal{C}$, $\mu = (\mu_i)_{i \in N} \stackrel{\$}{\leftarrow} \mathcal{R}_p^N$;

2. $\tilde{s}_1 \leftarrow \text{RandomizedEncode}(\mathbf{0}, \sigma_1)$, $s_2 \leftarrow \mathcal{D}_{\mathcal{R}_p, \sigma_2}^{m_2}$;

3. $\mathbf{y}_{\text{rand}} \stackrel{\$}{\leftarrow} \mathcal{R}_p^{m_1}, \tilde{\mathbf{y}}_1 \leftarrow \text{RandomizedEncode}(\mathbf{y}_{\text{rand}}, \sqrt{2}\tilde{s}_1)$, $\mathbf{y}_2 \leftarrow \mathcal{D}_{\mathcal{R}_p, s_2}^{m_2}$;

4. $\tilde{\mathbf{z}}_1 = c\tilde{s}_1 + \tilde{\mathbf{y}}_1$, $\mathbf{z}_2 = c\mathbf{s}_2 + \mathbf{y}_2$;

5. $\mathbf{w} = \mathbf{A}_1\tilde{\mathbf{z}}_1 + \mathbf{A}_2\mathbf{z}_2 - c\mathbf{t}_A$;

6. $\mathbf{f} := \sum_{i \in [N]} \mu_i f_i$, constructs $\tilde{\mathbf{f}}$ with $\mathbf{R}'_2$ and $\mathbf{r}'_1$ defined as in eq. (3);

$$\underline{\mathbf{y}} := \begin{bmatrix} \tilde{\mathbf{y}}_1 \\ \sigma(\tilde{\mathbf{y}}_1) \\ -\mathbf{B}\mathbf{y}_2 \\ \sigma(-\mathbf{B}\mathbf{y}_2) \end{bmatrix}, \quad \mathbf{z} := \begin{bmatrix} \tilde{\mathbf{z}}_1 \\ \sigma(\tilde{\mathbf{z}}_1) \\ c\mathbf{t}_B - \mathbf{B}\mathbf{z}_2 \\ \sigma(c\mathbf{t}_B - \mathbf{B}\mathbf{z}_2) \end{bmatrix};$$

8. $\mathbf{g}_0 := \mathbf{y}^\top\mathbf{R}'_2\mathbf{y} + \mathbf{b}_1^\top\mathbf{y}_2$;

9. $\mathbf{t}_1 = c^{-1} \cdot (\mathbf{z}^\top\mathbf{R}'_2\mathbf{z} + c\mathbf{z}^\top\mathbf{r}'_1 + c^2r_0 - \mathbf{g}_0 + \mathbf{b}_1^\top\mathbf{z}_2)$;

10. Output $(\mathbf{t}_A, \mathbf{t}_B, \mathbf{w}, c, \mathbf{z}_1, \mathbf{z}_2, \underline{\mu}, \mathbf{g}_0, \mathbf{t}_1)$.

<caption>Fig. 3: Definition of $S(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B})$ (without underlined elements) is the simulator for RF-ABDLOP in Theorem 3.5, the output is defined as the set of $\mathcal{H}_6$. Definition of $S_{\underline{\text{REL-AUT-F}}}(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, \mathbf{b}_1)$ generalizes the simulator in order to prove the simulatability in Theorem 4.5 for a set $\mathcal{F} = \{f_i\}_{i \in [N]}$.</caption>

**Theorem 3.5 (Simulatability).** The proof of opening knowledge protocol satisfies simulatability if the commitment scheme is initially hiding (assuming Theorem 3.2) and if for $\varepsilon = \text{negl}(\lambda)$, $\frac{1}{\zeta_1^2} := 2(\frac{1}{\sigma_1^2} + \frac{\eta^2}{s_1^2})$ and $\frac{1}{\zeta_2^2} := 2(\frac{1}{\sigma_2^2} + \frac{\eta^2}{2s_2^2})$ it satisfies the following conditions: $\sigma_1, \sqrt{2s_1} \ge \eta_\varepsilon(\mathcal{R}^{km_1})$; $s_1, 2\zeta_1 \ge \frac{\sqrt{2}}{(b-1)} \cdot \eta_\varepsilon(\mathbf{p}_{m_1}\mathcal{R}^{km_1})$; $\frac{\sigma_2}{\sqrt{2}}, s_2, \zeta_2 \ge \sqrt{2} \cdot \eta_\varepsilon(\mathcal{R}^{m_2})$ and MLWE$_{\mathcal{R},p,n,m_2,\zeta_2}$ is hard (this implies Hint-MLWE via Theorem 2.1), implying indistinguishability between an output of $S$ from Figure 3 and an honest transcript $\pi$ generated from $\mathbb{R}_{\text{RF}}$.

*Proof.* The proof essentially follows the original ones [KLSS23, HSS24] involving Hint-MLWE The idea is to prove that the statistical distance between an output of $S$ and $\pi$ is negligible. Let $(\mathbf{s}_1, \mathbf{s}_2, \mathbf{m}) \in \mathbb{R}_{\text{RF}}$ be the attacked message, chosen with knowledge of $\mathbf{p}\mathbf{p} := (\mathbf{A}_1, \mathbf{A}_2, \mathbf{B})$.

*Claim.* Assuming the commitment scheme is hiding, there is no polynomial distinguisher between elements sampled from $\mathcal{H}_0$ or $\mathcal{H}_1$.

*Proof.* The $\mathbf{s}_2$ element is the randomness of the commitment scheme, which changes between different launches. We simply put its sampling in the set in order to show that it can be artificially sampled by the simulator. Another modification is assuming the hiding of the lower part of the commitment scheme: it is hard to distinguish between 2 choosen message $\mathbf{m}$ and $\mathbf{0}$, we will simply omit the message in the following. $\square$
<figure><img src="image_4.png" /><figcaption>Fig. 4: Hybrid games the proof of the simulatability Theorem 3.5. Highlighted elements are those that are changed between each games.</figcaption></figure>
*Claim.* Assuming the commitment scheme is hiding, if there is a polynomial distinguisher between elements sampled from $\mathcal{H}_1$ or $\mathcal{H}_2$ therefore there exists a polynomial solver of the Hint-MLWE$_{\mathcal{R},p,n,m_2,1,\sigma_2,s_2,C}$ problem for the secret $s_2$.

*Proof.* Suppose we have $\mathcal{B}$ an efficient polynomial probabilistic adversary distinguishing $\mathcal{H}_0$ and $\mathcal{H}_1$ for any choice of pp with non-negligible advantage. We construct an efficient polynomial probabilistic algorithm solving Hint-MLWE$_{\mathcal{R},p,n,m_2,1,\sigma_2,s_2,C}$. Denote the Hint-MLWE instance received by the challenger $(\mathbf{A}, \mathbf{u}, \mathbf{c}, \mathbf{z})$: We will proceed as follows:

1. $\mathbf{A}_2 := [\mathbf{I}_n | \mathbf{A}] \in \mathcal{R}_p^{n \times m_2}, \mathbf{A}_1 \stackrel{\$}{\leftarrow} \mathcal{R}_p^{n \times m_1}, \mathbf{B}' \stackrel{\$}{\leftarrow} \mathcal{R}_p^{\ell \times n}, \mathbf{B} := \mathbf{B}'\mathbf{A}_2,$

2. $\mathbf{t}_A := \mathbf{u} + \mathbf{A}_1\tilde{\mathbf{s}}, \mathbf{t}_B := \mathbf{B}'\mathbf{u}, \mathbf{s} \stackrel{\$}{\leftarrow} \mathcal{R}_p^{m_1}, \tilde{\mathbf{s}} \leftarrow \text{RandomizedEncode}(\mathbf{s}, \sigma_1),$

3. $\mathbf{y}_{\text{rand}} \stackrel{\$}{\leftarrow} \mathcal{R}_p^{m_1}, \tilde{\mathbf{y}} \leftarrow \text{RandomizedEncode}(\mathbf{y}_{\text{rand}}, \mathbf{s}_1), \mathbf{w} = \mathbf{A}_2\mathbf{z} - c\mathbf{u} + \mathbf{A}_1\tilde{\mathbf{y}}, \tilde{\mathbf{z}} := c\tilde{\mathbf{s}} + \tilde{\mathbf{y}},$

4. Output $\mathcal{B}((\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}_1), (\mathbf{t}_A, \mathbf{t}_B, \mathbf{w}, \mathbf{c}, \tilde{\mathbf{z}}, \mathbf{z}))$.

Suppose $\mathbf{u} = [\mathbf{I}_n | \mathbf{A}]\mathbf{r}$ where $\mathbf{r} \leftarrow \mathcal{D}_{\mathcal{R}_p, \sigma_2}^{m_2}$. Then, $\mathbf{t}_A = \mathbf{u} + \mathbf{A}_1\tilde{\mathbf{s}} = \mathbf{A}_1\tilde{\mathbf{s}} + \mathbf{A}_2\mathbf{r}$, where $\mathbf{s}$ is known as in both distributions. Coming from the initial instance, the hint $\mathbf{z} = c\mathbf{r} + \mathbf{y}$ follows the same distributions in $\mathcal{H}_0$ and $\mathcal{H}_1$. The challenge $c$ is also unmodified. For $\mathbf{w}$, we have $\mathbf{w} = \mathbf{A}_2\mathbf{z} - c\mathbf{u} + \mathbf{A}_1\tilde{\mathbf{y}} = c\mathbf{A}_2\mathbf{r} + \mathbf{A}_2\mathbf{y} - c\mathbf{A}_2\mathbf{r} + \mathbf{A}_1\tilde{\mathbf{y}} = \mathbf{A}_1\tilde{\mathbf{y}} + \mathbf{A}_2\mathbf{y}$ with well-distributed $\tilde{\mathbf{y}}$ and $\mathbf{y}$. Also, $\mathbf{t}_B = \mathbf{B}'\mathbf{u} = \mathbf{Br}$. Therefore, this case explicitly generates an element of the distribution $\mathcal{H}_1((\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}), \mathbf{s})$.

Suppose $\mathbf{u}$ is uniformly sampled from $\mathcal{R}_p^n$: $\mathbf{t}_A, \mathbf{t}_B$ and $\mathbf{w}$ are also distributed uniformly over $\mathcal{R}_p$. As in the precedent case, $\mathbf{z}$ and the challenge $c$ remain the same and keep the same distribution. So, this case generates an element of $\mathcal{H}_2((\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}), \tilde{\mathbf{s}})$.

Our algorithm $\mathcal{A}$ outputting the same case as the one result by $\mathcal{B}$, we have that $\mathcal{A}$ has the same non-negligible advantage distinguishing Hint-MLWE samples.

Assuming parameters are chosen to harden Hint-MLWE$_{\mathcal{R},p,n,m_2,1,\sigma_2,s_2,C}$, $\mathcal{H}_1$ and $\mathcal{H}_2$ are computationally indistinguishable. $\square$

*Claim.* There is no polynomial distinguisher between samples from $\mathcal{H}_2$ or $\mathcal{H}_3$.

*Proof.* First, we remind that the encoding function is homomorphic. What we need to show here is that the distribution of $\mathbf{z}_1$ is the same in both case. Especially here, we will show that $\tilde{\mathbf{y}}_1$ in both distribution are statistically close. Without any loss of generality, we fix $c$. First, we remind the definition of the encoding function:

$\tilde{\mathbf{y}}_{1,1} \leftarrow \mathcal{D}_{\text{Encode}}(-c\mathbf{s}_1) + \mathbf{p}_{m_1} \mathcal{R}^{k m_1}, \mathbf{s}_1 P_{m_1}$ and $\tilde{\mathbf{y}}_{1,2} \leftarrow \mathcal{D}_{\text{Encode}}(\mathbf{y}_{\text{rand}}+c\mathbf{s}_1) + \mathbf{p}_{m_1} \mathcal{R}^{k m_1}, \mathbf{s}_1 P_{m_1}$.

By applying the Convolution Lemma 2.4 and the homomorphic property, $\tilde{\mathbf{y}}_1$ is at distance $8\varepsilon$ of $\mathcal{D}_{\text{Encode}}(\mathbf{y}_{\text{rand}})+\mathbf{p}_{m_1} \mathcal{R}^{k m_1}, \sqrt{2}\mathbf{s}_1 P_{m_1}$, requiring $\mathbf{s}_1 P_{m_1} \ge \eta_\varepsilon(\mathbf{p}_{m_1} \mathcal{R}^{k m_1})$, that is true by our conditions. This implies $\mathcal{H}_2$ and $\mathcal{H}_3$ are at distance $8\varepsilon$. $\square$

*Claim.* There is no polynomial distinguisher between samples from $\mathcal{H}_3$ or $\mathcal{H}_4$.
Proof. The focus will be on distinguishing $\tilde{z}_1$ generated with and without knowledge of $s_1$. Here we use Lemma 2.3. Without any loss of generality, we fix $c$, and define $C := \text{Rot}_{km_1d}(c)$. We take a look of $\mathcal{H}_3$. We view $s_1$ as a sample i.e. $\mathcal{D}_{\text{Encode}(s_1)+p_{m_1}\mathcal{R}^{km_1}, \sigma_1 p_{m_1}}$. We clearly see $\tilde{y}_{1,1}$ of as the masking part of the hint. By lemma 2.3, if the condition:

$$ \sqrt{(\sigma_1^{-2}(P_{m_1}^{\top} P_{m_1})^{-1} + \mathfrak{s}_1^{-2} C^{\top} (P_{m_1}^{\top} P_{m_1})^{-1} C)^{-1}} \geq \eta_{\varepsilon}(\mathfrak{p}_{m_1} \mathcal{R}^{km_1}) $$

is satisfied then the distributions $\{c\tilde{s}_1 + \tilde{y}_{1,1}\}$ of both $\mathcal{H}_3$ and $\mathcal{H}_4$ are without $2\varepsilon$-statistical distance. By lemma 2.1, we bound:

$$ \begin{aligned} \|\sigma_1^{-2}(P_{m_1}^{\top} P_{m_1})^{-1} + \mathfrak{s}_1^{-2} C^{\top} (P_{m_1}^{\top} P_{m_1})^{-1} C\|_2 &\leq (\sigma_1^{-2} + \mathfrak{s}_1^{-2} \|C\|_2^2) \|P_{m_1}^{-1}\|_2^2 \\ &\leq (\sigma_1^{-2} + \eta^2 \mathfrak{s}_1^{-2})(b-1)^{-2} \\ &= (\sqrt{2}\zeta_1)^{-2}(b-1)^{-2} \\ &\leq \eta_{\varepsilon}(\mathfrak{p}_{m_1} \mathcal{R}^{m_1})^{-2} \end{aligned} $$

if assuming that $\zeta_1 \geq \frac{1}{\sqrt{2(b-1)}}\eta_{\varepsilon}(\mathfrak{p}_{m_1} \mathcal{R}^{km_1})$ and by the fact that $\|P_{m_1}^{-1}\|_2 \leq \frac{1}{b-1}$. We also exploit the bound $\|C\|_2^2 \leq \eta^2$ in Appendix B.4.

As $\mathbf{y}_{\text{rand}}$ is a uniformly sampled from of $\mathcal{R}_p^n$, it follows that the distribution $\mathbf{y}_{\text{rand}} + c\mathbf{s}_1$ is uniform over the same set. Therefore $\tilde{y}_{1,2}$ follows the same distribution in both $\mathcal{H}_3$ and $\mathcal{H}_4$. Finally, this implies that both $\tilde{z}_1$ are also within a $2\varepsilon$ statistical distance. $\square$

Claim. There is no polynomial distinguisher between samples from $\mathcal{H}_4$ or $\mathcal{H}_5$.

Proof. The proof is the same as the one in the claim of the indistinguishability between $\mathcal{H}_2$ and $\mathcal{H}_3$. $\square$

Claim. There is no polynomial distinguisher between samples from $\mathcal{H}_5$ or $\mathcal{H}_6$ (defined as the output of the simulator $\mathcal{S}$ from Figure 3).

Proof. Between $\mathcal{H}_5$ and $\mathcal{H}_6$, as the elements constructing $\mathbf{w}$ are uniformly random, $\mathbf{w}$ from $\mathcal{H}_6$ follows the uniform distribution as in $\mathcal{H}_5$. $\square$

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

# 4 Proving more than just the knowledge

The aim of our construction is to give additional information about a committed secret message, such as proving linear or quadratic relations over the message.

The [LNP22] framework uses the fact that the message was not modified but only hidden in a commitment scheme. As we are not sending the message unmodified but its randomized encoding version, we can no longer use the original construction. We show in this section how to modify the relations in such a way that we can prove both linear and quadratic relations over the randomized encoding that imply original relations over the initial message. Our protocol
manages to extend the prove of knowledge of a committed element using the RF-ABDLOP commitment scheme, therefore, we no longer specify the rings and lengths. We refer to an instance of $R_{RF}$ in (3.1) in Section 3.1 for the public matrices $\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}$.

## 4.1 Transform the relations

**Relation over the secret to one over the encoding.** A main tool of the [LNP22] framework is the proof of both linear and quadratic relations over $\mathcal{R}_p$ of messages $\mathbf{s}_1$ and $\mathbf{m}$, which can be viewed as a matrix product over the coefficient of the matrices. We denote by $\mathcal{F}$ the full set of functions $f_i$ to be proven w.l.o.g. equal to 0, i.e. such that $\mathbf{s}$ is in $\text{Ker}\mathcal{F} := \bigcap_{f_i \in \mathcal{F}} \text{Ker}f_i$.

A quadratic relation over the committed element can be seen as proving the equation $f(\mathbf{s}) = \mathbf{s}^\top \mathbf{R}_2 \mathbf{s} + \mathbf{r}_1^\top \mathbf{s} + r_0 = 0$ for a committed message $\mathbf{s}^\top := (\mathbf{s}_1^\top, \mathbf{m}^\top)$, a matrix $\mathbf{R}_2 \in \mathcal{R}_p^{(m_1+\ell)\times(m_1+\ell)}$ and elements $\mathbf{r}_1 \in \mathcal{R}_p^{m_1+\ell}$ and $r_0 \in \mathcal{R}_p$. The linear function restricts $f$ to $\mathbf{R}_2$ being equal to $\mathbf{0}^{(m_1+\ell)\times(m_1+\ell)}$.

**Remark 4.1.** We can identify $\mathbf{R}_2$ as a triangular matrix (upper or lower depending on the transpose case in which we are) and, by abuse of notation, restrict the quadratic component to $\mathbf{s}^\top \mathbf{R}_2 \mathbf{s} = \mathbf{s}_1^\top \mathbf{R}_{1,1} \mathbf{s}_1 + \mathbf{s}_1^\top \mathbf{R}_{1,m} \mathbf{m} + \mathbf{m}^\top \mathbf{R}_{m,1} \mathbf{m}$ with only an upper triangular matrix $\mathbf{R}_2 := \begin{bmatrix} \mathbf{R}_{1,1} & \mathbf{R}_{1,m} \\ \mathbf{0}^{\ell \times m_1} & \mathbf{R}_{m,m} \end{bmatrix} \in \mathcal{R}_p^{(m_1+\ell)\times(m_1+\ell)}$. We extend the decomposition to the linear term $\mathbf{r}_1^\top = [\mathbf{r}_{1,1}^\top \quad \mathbf{r}_{1,m}^\top]$.

We define the set $R_{\mathcal{F}}$ of potentially committed elements satisfying the equations $f_i(\mathbf{s}) = 0$ for each $f_i \in \mathcal{F}$ for a publicly known set of functions $\mathcal{F}$.

$$ R_{\mathcal{F}} := \left\{ \begin{array}{c} \frac{(\mathbf{s}_1, \mathbf{m}, \mathbf{s}_2):}{(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B))} \quad \begin{array}{l} \mathbf{A}_1 \tilde{\mathbf{s}}_1 + \mathbf{A}_2 \mathbf{s}_2 = \mathbf{t}_A \\ \mathbf{B} \mathbf{s}_2 + \mathbf{m} = \mathbf{t}_B \\ \tilde{\mathbf{s}}_1 = \text{RandomizedEncode}(\mathbf{s}_1, \sigma_1) \\ (\mathbf{s}_1, \mathbf{m}) \in \bigcap_{f_i \in \mathcal{F}} \text{Ker}f_i \end{array} \end{array} \right\} $$

In our case, the RF-Ajtai part does not involve $\mathbf{s}_1$ but $\tilde{\mathbf{s}}_1$, therefore we can not execute the original construction in [LNP22]. Our new procedure consists of performing the decoding protocol during the execution of the function. For a function $f_i$ in $\mathcal{F}$, we construct a new $\tilde{f}_i$ and prove it holds for $\tilde{f}_i$ instead.

**Theorem 4.1.** Let $\mathcal{F}$ a set of linear and quadratic functions over $(\mathbf{s}_1, \mathbf{m})$. Then, for every function $f_i \in \mathcal{F}$, the associated $\tilde{f}_i := f_i \circ [\text{Decode}(\cdot), \text{id}(\cdot)]$ satisfies:

1. $\tilde{f}_i$ acts over $\tilde{\mathbf{s}} := (\tilde{\mathbf{s}}_1, \mathbf{m})$, is computable and preserves the $f_i$ structure,

2. if $(\tilde{\mathbf{s}}_1, \mathbf{m}) \in \text{Ker}\tilde{f}_i$ then $(\mathbf{s}_1, \mathbf{m}) \in \text{Ker}f_i$,

3. if $(\tilde{\mathbf{s}}_1, \mathbf{m}, \mathbf{s}_2) \in R_{RF-\mathcal{F}}$ then $(\mathbf{s}_1, \mathbf{m}, \mathbf{s}_2) \in R_{\mathcal{F}}$.

$$ R_{RF-\mathcal{F}} := \left\{ \begin{array}{c} \frac{(\tilde{\mathbf{s}}_1, \mathbf{m}, \mathbf{s}_2):}{(\mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B))} \quad \begin{array}{l} \mathbf{A}_1 \tilde{\mathbf{s}}_1 + \mathbf{A}_2 \mathbf{s}_2 = \mathbf{t}_A \\ \mathbf{B} \mathbf{s}_2 + \mathbf{m} = \mathbf{t}_B \\ (\tilde{\mathbf{s}}_1, \mathbf{m}) \in \bigcap_{f_i \in \mathcal{F}} \text{Ker}\tilde{f}_i \end{array} \end{array} \right\} $$
By "preserving the structure", we mean that the function $\tilde{f}$ is still linear resp. quadratic just like $f$.

The following lemma proves the stability of the structure of the quadratic component performing over a (possibly randomized) encoding.

**Lemma 4.1.** Let $m, n, u, b, k$ positive integers. Let $p := b^k + 1$. Let $\mathbf{A} \in \mathbb{Z}^{m \times n}$, $\mathbf{x}_1 \in \mathbb{Z}_p^m$ and $\mathbf{x}_2 \in \mathbb{Z}_p^n$. Then, we have for both $\bar{\mathbf{x}}_1 \in \{\hat{\mathbf{x}}_1, \tilde{\mathbf{x}}_1\}$ and $\bar{\mathbf{x}}_2 \in \{\hat{\mathbf{x}}_2, \tilde{\mathbf{x}}_2\}$:

$$ \begin{aligned} \mathbf{x}_1^\top \mathbf{A} \mathbf{x}_2 &= \bar{\mathbf{x}}_1^\top (\mathbf{A} \otimes \mathbf{g}_{b,k}) \mathbf{x}_2, \quad \mathbf{x}_1^\top \mathbf{A} \mathbf{x}_2 = \mathbf{x}_1^\top (\mathbf{A} \otimes \mathbf{g}_{b,k}^\top) \bar{\mathbf{x}}_2 \\ \text{and } \mathbf{x}_1^\top \mathbf{A} \mathbf{x}_2 &= \bar{\mathbf{x}}_1^\top (\mathbf{A} \otimes (\mathbf{g}_{b,k}^\top \otimes \mathbf{g}_{b,k})) \bar{\mathbf{x}}_2. \end{aligned} $$

*Proof.* First, we have $\mathbf{G}\hat{\mathbf{t}} = \mathbf{G}\tilde{\mathbf{t}}$ because $\tilde{\mathbf{t}} = \hat{\mathbf{t}} \bmod p$. The second equality comes from the linear transformation and the associativity of the matrix product. For the first one, the equality comes from $\mathbf{x}_1^\top \mathbf{A} \mathbf{x}_2 = (\mathbf{A}^\top \mathbf{x}_1)^\top \cdot \mathbf{x}_2 = ((\mathbf{A}^\top \otimes \mathbf{g}_{b,k}^\top) \cdot \bar{\mathbf{x}}_1)^\top \cdot \mathbf{x}_2 = \bar{\mathbf{x}}_1^\top \cdot (\mathbf{A} \otimes \mathbf{g}_{b,k}) \cdot \mathbf{x}_2$. The generalized equality is due to the two previous equalities and the associativity of the Kronecker product. $\square$

*Proof (of Theorem 4.1).* We have $\tilde{f}_i(\tilde{\mathbf{s}}_1, \mathbf{m}) = f_i(\mathbf{G}_{b,k,dm_1}\tilde{\mathbf{s}}_1, \mathbf{m}) = f_i(\mathbf{s}_1, \mathbf{m}) = 0$, implying the second point and the computability. The third point is clearly implied by the second point. For the initial point, we mean that if $f$ is linear (resp. quadratic), then $\tilde{f}$ is still linear (resp. quadratic). As identifying $f_i$ as a quadratic construction showed in remark 4.1, we construct $\tilde{f}(\tilde{\mathbf{s}}) = \tilde{\mathbf{s}}^\top \mathbf{R}_2' \tilde{\mathbf{s}} + \mathbf{r}_1'^\top \tilde{\mathbf{s}} + r_0$ with:

$$ \mathbf{r}_1'^\top = [\mathbf{r}_{1,1}^\top \otimes \mathbf{g}_{b,k}^\top \parallel \mathbf{r}_{1,m}^\top] \quad \text{and} \quad \mathbf{R}_2' := \begin{bmatrix} \mathbf{R}_{1,1} \otimes (\mathbf{g}_{b,k}^\top \otimes \mathbf{g}_{b,k}) & \mathbf{R}_{1,m} \otimes \mathbf{g}_{b,k} \\ \mathbf{0}^{\ell \times km_1} & \mathbf{R}_{m,m} \end{bmatrix}, $$

that maintains a quadratic structure over $\tilde{\mathbf{s}}$. For the linear structure, we study the quadratic component; if $\mathbf{R}_2 = \mathbf{0}^{(m_1+\ell) \times (m_1+\ell)}$, then by construction, we have $\mathbf{R}_2' = \mathbf{0}^{(km_1+\ell) \times (km_1+\ell)}$ that maintains the linear structure over $\tilde{\mathbf{s}}$. $\square$

## 4.2 Include the automorphism $\sigma$

Our final goal is to prove quadratic relations over the messages committed and their automorphism $\sigma: X \mapsto X^{-1}$ over $\mathcal{R}_p$. We define the full message involved as $\mathbf{s}^\top := (\mathbf{s}_1^\top, \sigma(\mathbf{s}_1)^\top, \mathbf{m}^\top, \sigma(\mathbf{m})^\top) \in \mathcal{R}_p^{2(m_1+\ell)}$. Therefore, together with the remark 4.1 and the explanation above, the relation can be seen as proving the equation $f(\mathbf{s}) = \mathbf{s}^\top \mathbf{R}_2 \mathbf{s} + \mathbf{s}^\top \mathbf{r}_1 + r_0 = 0$ with the (public) matrices:

$$ \mathbf{R}_2 = \begin{bmatrix} \mathbf{R}_{1,1} & \mathbf{R}_{1,\sigma(1)} & \mathbf{R}_{1,m} & \mathbf{R}_{1,\sigma(m)} \\ \mathbf{0}^{m_1 \times m_1} & \mathbf{R}_{\sigma(1),\sigma(1)} & \mathbf{R}_{\sigma(1),m} & \mathbf{R}_{\sigma(1),\sigma(m)} \\ \mathbf{0}^{\ell \times m_1} & \mathbf{0}^{\ell \times m_1} & \mathbf{R}_{m,m} & \mathbf{R}_{m,\sigma(m)} \\ \mathbf{0}^{\ell \times m_1} & \mathbf{0}^{\ell \times m_1} & \mathbf{0}^{\ell \times \ell} & \mathbf{R}_{\sigma(m),\sigma(m)} \end{bmatrix} \in \mathcal{R}_p^{2(m_1+\ell) \times 2(m_1+\ell)}, \quad (1) $$

$$ \mathbf{r}_1^\top = [\mathbf{r}_{1,1}^\top \ \mathbf{r}_{1,\sigma(1)}^\top \ \mathbf{r}_{1,m}^\top \ \mathbf{r}_{1,\sigma(m)}^\top] \in \mathcal{R}_p^{2(m_1+\ell)}. \quad (2) $$
**Remark 4.2** ([LNP22, Section 4]). A naive idea is to commit both the message and its automorphism. To be more efficient, the action of $\sigma$ can be computed from $(\mathbf{s}_1, \mathbf{m})$ and its commitment. It is an automorphism of $\mathcal{R}_p$, so when defining $\sigma$ over an element $\mathcal{R}_p^k$, we compute its coordinate-wise. We show that it is possible to compute the automorphism of an element based on its (randomized) encoding.

**Lemma 4.2.** Let $\sigma \in \text{Aut}(\mathcal{R}_p)$ and $\mathbf{x} \in \mathcal{R}_p^{m_1}$ a secret, and $\bar{\mathbf{x}} \in \{\hat{\mathbf{x}}, \tilde{\mathbf{x}}\}$ seen as an element of $\mathcal{R}_p^{km_1}$ its encoding (resp. randomized encoding) of $\mathbf{x}$. Then, we have for each $\bar{\mathbf{x}} \in \{\hat{\mathbf{x}}, \tilde{\mathbf{x}}\}: \overline{\sigma(\mathbf{x})} = \sigma(\bar{\mathbf{x}})$ decoded in a unique $\sigma(\mathbf{x})$.

The proof depends precisely on the choice of the Encode algorithm described in section 3 and is straightforward. The proof is done in Appendix B.1.

**Theorem 4.2.** Let $\mathcal{G}$ a set of linear and quadratic functions over $\mathbf{s}^\top$. Define the map $\psi: (\mathbf{x}_1, \mathbf{x}_2) \mapsto (\mathbf{x}_1, \sigma(\mathbf{x}_1), \mathbf{x}_2, \sigma(\mathbf{x}_2))$. Then, for every function $g_i \in \mathcal{G}$, the associated function $\tilde{g}_i := g_i \circ [\text{Decode}(\cdot), \text{Decode}(\cdot), \text{id}(\cdot), \text{id}(\cdot)]$ satisfies:

1. $\tilde{g}_i$ acts over $\tilde{\mathbf{s}} := \psi(\tilde{\mathbf{s}}_1, \mathbf{m})$, is computable and preserves the $g_i$ structure,

2. if $\psi(\tilde{\mathbf{s}}_1, \mathbf{m}) \in \text{Ker}\tilde{g}_i$ then $\psi(\mathbf{s}_1, \mathbf{m}) \in \text{Ker}g_i$,

3. if $(\tilde{\mathbf{s}}_1, \mathbf{m}, \mathbf{s}_2) \in \mathcal{R}_{\text{RF-AUT-G}}$ then $((\mathbf{s}_1^\top \| \sigma(\mathbf{s}_1)^\top), (\mathbf{m}^\top \| \sigma(\mathbf{m})^\top), \mathbf{s}_2^\top)^\top \in \mathcal{R}_G$.

$$ \mathcal{R}_{\text{RF-AUT-G}} := \left\{ \begin{array}{c} \overline{(\tilde{\mathbf{s}}_1, \mathbf{m}, \mathbf{s}_2)}: \\ \left( \mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B) \right) \middle| \begin{array}{l} \mathbf{A}_1 \tilde{\mathbf{s}}_1 + \mathbf{A}_2 \mathbf{s}_2 = \mathbf{t}_A \\ \mathbf{B} \mathbf{s}_2 + \mathbf{m} = \mathbf{t}_B \\ \psi(\tilde{\mathbf{s}}_1, \mathbf{m}) \in \cap_{g_i \in \mathcal{G}} \text{Ker}\tilde{g}_i \end{array} \end{array} \right\} $$

*Proof.* For 2 and 3, as $\tilde{g}_i(\psi(\tilde{\mathbf{s}}_1, \mathbf{m})) = g_i(\mathbf{G}_{b,k,dm_1}\tilde{\mathbf{s}}_1, \mathbf{G}_{b,k,dm_1}\sigma(\tilde{\mathbf{s}}_1), \mathbf{m}, \sigma(\mathbf{m}))$, we have $\tilde{g}_i(\psi(\tilde{\mathbf{s}}_1, \mathbf{m})) = g_i(\mathbf{s}_1, \sigma(\mathbf{s}_1), \mathbf{m}, \sigma(\mathbf{m})) = g_i(\psi(\mathbf{s}_1, \mathbf{m})) = 0$. We keep the same analysis done in Theorem 4.1 as the decoding and the identity are done coordinate-wise leading to a function with input $((\mathbf{s}_1^\top \| \sigma(\mathbf{s}_1)^\top), (\mathbf{m}^\top \| \sigma(\mathbf{m})^\top), \mathbf{s}_2^\top)^\top$. We can now see $\tilde{g}_i$ as $\tilde{g}_i(\tilde{\mathbf{s}}) = \tilde{\mathbf{s}}^\top \mathcal{R}_2' \tilde{\mathbf{s}} + \mathbf{r}_1^\top \tilde{\mathbf{s}} + r_0$ with $\mathcal{R}_2' \in \mathcal{R}_p^{2(km_1+\ell) \times 2(km_1+\ell)}$ such that:

$$ \mathcal{R}_2' := \left[ \begin{array}{c|c} \mathbf{R}_{1,1} \otimes (\mathbf{g}_{b,k}^\top \otimes \mathbf{g}_{b,k}) & \mathbf{R}_{1,\sigma(1)} \otimes (\mathbf{g}_{b,k}^\top \otimes \mathbf{g}_{b,k}) & \mathbf{R}_{1,m} \otimes \mathbf{g}_{b,k} & \mathbf{R}_{1,\sigma(m)} \otimes \mathbf{g}_{b,k} \\ \mathbf{0}^{km_1 \times km_1} & \mathbf{R}_{\sigma(1),\sigma(1)} \otimes (\mathbf{g}_{b,k}^\top \otimes \mathbf{g}_{b,k}) & \mathbf{R}_{\sigma(1),m} \otimes \mathbf{g}_{b,k} & \mathbf{R}_{\sigma(1),\sigma(m)} \otimes \mathbf{g}_{b,k} \\ \mathbf{0}^{\ell \times km_1} & \mathbf{0}^{\ell \times km_1} & \mathbf{R}_{m,m} & \mathbf{R}_{m,\sigma(m)} \\ \mathbf{0}^{\ell \times km_1} & \mathbf{0}^{\ell \times km_1} & \mathbf{0}^{\ell \times \ell} & \mathbf{R}_{\sigma(m),\sigma(m)} \end{array} \right], $$

$$ \text{and } \mathbf{r}_1^\top := \left[ \mathbf{r}_{1,1}^\top \otimes \mathbf{g}_{b,k}^\top \mathbf{r}_{1,\sigma(1)}^\top \otimes \mathbf{g}_{b,k}^\top \mathbf{r}_{1,m}^\top \mathbf{r}_{1,\sigma(m)}^\top \right] \in \mathcal{R}_p^{2(km_1+\ell)}. \quad (3) $$

Regarding the computability, it exploits Lemma 4.2: the (randomized) encoding, the (unique) decoding, and the automorphism $\sigma_{-1}$ are commutative. $\square$

In order to prove the security of the opening process, we define the associated opening relation. In particular, we choose parameters such that if $(\tilde{\mathbf{s}}_1, \tilde{\mathbf{s}}_2, \bar{\mathbf{c}}) \in \bar{\mathcal{R}}_{\text{RF-AUT-G}}$ then $(\tilde{\mathbf{s}}_1, \mathbf{t}_B - \mathbf{B}\tilde{\mathbf{s}}_2, \tilde{\mathbf{s}}_2) \in \mathcal{R}_{\text{RF-AUT-G}}$ with overwhelming probability for:

$$ \bar{\mathcal{R}}_{\text{RF-AUT-G}} := \left\{ \overline{(\tilde{\mathbf{s}}_1, \tilde{\mathbf{s}}_2, \bar{\mathbf{c}})}: \left( \mathbf{A}_1, \mathbf{A}_2, \mathbf{B}, (\mathbf{t}_A, \mathbf{t}_B) \right) \middle| \begin{array}{l} \mathbf{A}_1 \tilde{\mathbf{s}}_1 + \mathbf{A}_2 \tilde{\mathbf{s}}_2 = \mathbf{t}_A \\ \bar{\mathbf{m}} = \mathbf{t}_B - \mathbf{B}\tilde{\mathbf{s}}_2 \\ \psi(\tilde{\mathbf{s}}_1, \bar{\mathbf{m}}) \in \cap_{g_i \in \mathcal{G}} \text{Ker}\tilde{g}_i \end{array} \right\} $$
## 4.3 Proving the relations

**One relation holds.** We show in Theorem 4.2 that we manage to preserve the structure of the original relations $f$ when constructing $\tilde{f}$. Therefore, the idea behind the preservation was to keep using the same construction from [LNP22, Section 4.1]. Now that we can compute the automorphism over the encoding by Lemma 4.2, we define $\tilde{s} := \psi(\tilde{s}_1, \mathbf{m})$ and $\mathbf{y} := \psi(\tilde{y}_1, -\mathbf{By}_2)$ both in $\mathcal{R}_p^{2(km_1+l)}$. We also construct the response $\mathbf{z}_m$ (computable by the verifier) as in [LNP22] by defining $\mathbf{z}_m := c\mathbf{t}_B - \mathbf{Bz}_2 = c \cdot \mathbf{m} - \mathbf{By}_2$. We have:

$$ \mathbf{z} := \psi(\mathbf{z}_1, \mathbf{z}_m) = c \begin{bmatrix} \tilde{s}_1 \\ \sigma(\tilde{s}_1) \\ \mathbf{m} \\ \sigma(\mathbf{m}) \end{bmatrix} + \begin{bmatrix} \tilde{y}_1 \\ \sigma(\tilde{y}_1) \\ -\mathbf{By}_2 \\ \sigma(-\mathbf{By}_2) \end{bmatrix} = c \begin{bmatrix} \tilde{s}_1 \\ \overline{\sigma(\tilde{s}_1)} \\ \mathbf{m} \\ \sigma(\mathbf{m}) \end{bmatrix} + \begin{bmatrix} \tilde{y}_1 \\ \sigma(\tilde{y}_1) \\ -\mathbf{By}_2 \\ \sigma(-\mathbf{By}_2) \end{bmatrix} = c\tilde{s} + \mathbf{y}. $$

The idea of [LNP22, Section 4.1] is to prove the vanishment of a coefficient to reduce the problem to a linear relation. The quadratic relation $\tilde{f}$ is now modified in order to have $\mathbf{z}^\top \mathbf{R}_2' \mathbf{z} + c \mathbf{z}^\top \mathbf{r}'_1 + c^2 r_0 - c \cdot \mathbf{g}_1 - \mathbf{g}_0 = c^2 \tilde{f}(\mathbf{s})$, with two garbage polynomials $\mathbf{g}_0 := \mathbf{y}^\top \mathbf{R}_2' \mathbf{y} \in \mathcal{R}_p$ and $\mathbf{g}_1 := \tilde{s}^\top \mathbf{R}_2' \mathbf{y} + \mathbf{y}^\top \mathbf{R}_2' \tilde{s} + \mathbf{y}^\top \mathbf{r}'_1 \in \mathcal{R}_p$. The prover finally commits the element $\mathbf{g}_1$ by computing $t_1 = \mathbf{b}_1^\top \mathbf{s}_2 + \mathbf{g}_1$ (in the BDLOP part) and transmits directly $\mathbf{g}_0$ as it is not linked with any secret but only the randomness $\mathbf{s}_2$ freshly sampled in each execution of the protocol. The verifier checks if $\mathbf{z}^\top \mathbf{R}_2' \mathbf{z} + c \mathbf{z}^\top \mathbf{r}'_1 + c^2 r_0 \stackrel{?}{=} c \mathbf{t}_1 + \mathbf{g}_0 - \mathbf{b}_1^\top \mathbf{z}_2$ implying $\tilde{f}(\mathbf{s}) = 0$.

**Prove many relations.** We simply generalize to the proof of $N = |\mathcal{F}|$ relations using the exact same construction as in [LNP22, Section 4.2].

**Lemma 4.3 (Induced by [LNP22, Lemma 4.3]).** Consider a set of relations $\mathcal{F} = \{f_i\}_{i \in [N]}$. Define $f := \sum_{i \in [N]} \mu_i f_i$ with $\mu = (\mu_i)_{i \in [N]} \stackrel{\$}{\leftarrow} \mathcal{R}_p^N$. Then,

$$ \mathbb{P}[(\bar{s}_1, \bar{s}_2, \bar{c}) \notin \bar{\mathcal{R}}_{(\mathcal{R}F-AUT-\mathcal{F})} | (\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{\mathcal{R}}_{(\mathcal{R}F-AUT-\mathcal{F})} \{f\}] \le p^{-\frac{d}{2}}. $$

We give the protocol in Figure 2 with the following theorems ensuring security.

**Theorem 4.3 (Completeness).** The protocol instantiated in Figure 2 satisfies completeness if it satisfies conditions/constructions from Theorems 3.3 and 4.2.

*Proof.* The proof of completeness follows from the explanations in Section 4 as the elements transmitted allows the right construction in order to prove $f(\mathbf{s}) = 0$ for each function in $\mathcal{F}$. The last thing to check is that the commitment scheme used is relevant and ensure completeness: we simply launch parameters and conditions from Theorems 3.3 and 4.2. $\square$

**Theorem 4.4 (Knowledge Soundness).**

There exists an extractor of the protocol in Figure 2 that either produces an opening $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \bar{\mathcal{R}}_{\mathcal{R}F-AUT-\mathcal{F}}$ with non-negligible probability or solves an instance of a $\text{MSIS}_{\mathcal{R},p,n,km_1+m_2,8\eta\sqrt{\beta_{\text{open},1}^2+\beta_{\text{open},2}^2}}$.
*Proof.* Let's assume that the extractor finds two accepted transcripts for a same commitment $(t_A, t_B)$ with a rewind before the sampling of the challenge $(\mu, w, g_0, t_1, c, \tilde{z}_1, z_2)$ and $(\mu', w, g_0, t_1, c', \tilde{z}'_1, z'_2)$. Regarding the elements involved in the proof of opening knowledge, the proof has already been shown in Theorem 3.4. The final part involves proving that the process of proving relationships cannot be compromised. Consider $\mu$ not involved as we can reduce the multiple relation to a single one by launching Lemma 4.3 by setting $p^{\frac{d}{2}}$ being negligible. The proof follows essentially the one from [LNP22, Lemma 4.2] as it has the same structure, taking into account 3 rewinds in order to prove $(\bar{s}_1, \bar{s}_2, \bar{c}) \in \mathbb{R}_{\text{RF-AUT-}\{f\}}$. $\square$

**Theorem 4.5 (Simulatability).** For the simulatability of the Figure 2, we consider the parameters from Theorems 3.3,3.4 and 3.5 and the simulator in Figure 3 ensuring indistinguishability between an honest transcript $\pi$ generated from elements of $\mathbb{R}_{\text{RF-AUT-}\pi}$ and an output of the simulator $\mathbb{S}_{\text{REL-AUT-}\pi}$.

*Proof.* We immediately use Theorem 3.5 which defines the simulatability of RF-ABDLOP based on Hint-MLWE for the response $z_2$. The right construction of the additional $(\mu, g_0, t_1)$ follows from the correctness and the fact that $\bar{C} \subseteq \mathcal{R}_q^\times$. $\square$

# 5 Instantiations of the framework

We provide a library in C that uses and extends the actual LaZer library [LSS24], with a set of new rejection-free functions. We provide a concrete analysis of the running time of our code with the existing [LNP22] framework launched with the [LSS24] implementation. We obtain the results shown in Table 3 made with a compilation of our code on a laptop with Intel Core Ultra 7 165H, using gcc version 11.4.0 with the options `-O3 -march=native, -mtune=native` and `-pthread` to ensure optimality of the results. We recall the list of conditions our framework needs to follow to ensure security and compare the running time and the size of the transcript of our framework with the original ones of [LNP22].

## 5.1 Overview of all the conditions

First, the framework can be instantiated for a particular prime $p$ s.t. $p = 5$ mod 8 in order to use Lemma 2.5 but since $p = b^k + 1$, this can only be done for $k = 2$. Second, the false positive probability in Lemma 4.3 must be negligible. Third, we need to make sure that our standard deviations respect the initial conditions mentioned in the security Theorems. By taking $\varepsilon = 2^{-\lambda}$ with the security parameter $\lambda$ and as $\lambda_{kmd}(\mathcal{R}^m) = 1$ and $\lambda_{kmd}(\mathfrak{p}_m\mathcal{R}^m) = \sqrt{b^2 + 1} = \sqrt{p}$ for any $m$, we bound the smoothing parameters using [MR07, Lemma 3.3]. Overall, the parameters of the protocol depend on the size $m_1$, the degree $d$, the MSIS dimension $n$, and the size $m_2$ which is adjusted to achieve the MLWE security. As our security is based on MSIS and MLWE (through Hint-MLWE), we exploit the LWE-Estimator [APS15] to compute $m_2$ and $n$, ensuring the hardness of:
- $\text{MSIS}_{\mathcal{R},p,n,km_1+m_2,8\eta\sqrt{(\eta(b+1)\sigma_1+\sqrt{2s_1})^2(km_1d)+(\eta\sigma_2+s_2)^2(m_2d)}}$ (Know. Sound.),

- $\text{MSIS}_{\mathcal{R},p,n,km_1+m_2,2\sqrt{(b+1)^2\sigma_1^2m_1kd+\sigma_2^2m_2d}}$ (Binding),

- $\text{MLWE}_{\mathcal{R},p,n+\ell,m_2,\sigma_2}$ (Hiding) and $\text{MLWE}_{\mathcal{R},p,n+\ell,m_2,\zeta_2}$ (Simulatability).

## 5.2 Sizes and running time of the framework

**Size of an instance of our framework.** The optimisations are the same as in [LNP22]. We use the Dilithium-based compression from [LNP22, Appendix A.2], with variables $D$ and $\gamma$ cutting low-order bits for the transmitted elements $t_A$ and $w$. We use Huffman coding in order to optimise the size regarding the distribution of the responses $z_i$. As the set of relations is public and unaffecting the extractor, the challenge $\mu$ can be the output of the hash-function of the previous transmissions. Unlike the challenge $c$, that is transmitted and quantified with the bounds $\eta$ and $\kappa$ defining $\mathcal{C}$ in Section 2.3. The rest of the size depends on the $\nu$ BDLOP commits used dynamically. Finally, a transcript $\pi$ has length:

$$|\pi| := nd(\lceil \log p \rceil + 2.25 - D) + \nu d \cdot \lceil \log p \rceil + d \cdot \lceil \log(2\kappa + 1) \rceil + km_1 d \cdot (2.57 + \lceil \log(\eta(b+1)\sigma_1 + \sqrt{2s_1}) \rceil) + m_2 d \cdot (2.57 + \lceil \log(\eta\sigma_2 + s_2) \rceil).$$

**Complexity of the proving phase.** We study the complexity of the commitment. The prover needs to construct the elements $\tilde{s}_1$ by encoding it, samples an error $e$, and adds it. This is done in $O(n(km_1 + m_2))$ operations over $\mathcal{R}_p$ considering optimal methods of sampling from spherical discrete Gaussian from [HSS24, Section 3.2]. The proof is constructed with $O(n(km_1+m_2)+k^2m_1^2)$ operations over $\mathcal{R}_p$ because the computations are bounded by $w$ or $g_i$. If we consider that the multiplication in $O(d \log d)$ is the heavier operation in $\mathcal{R}$, then the prover complexity is $O(d \log d(n(km_1 + m_2) + k^2m_1^2))$ only enhancing the running time of a [LNP22] instance by a factor at most $k^2$. But, we are restricted to the case $k=2$. Then by denoting $T_{P,LNP}$ the initial time of a single instance of the proving phase (without rejection), we can bound the proving phase of our protocol: $T_{P,\text{new}} \le 4T_{P,LNP}$. Then, our framework executes in constant time and has a faster proving phase if the rejection rate is higher than 3.

**Complexity of the verifying phase.** With the same analysis, the verifier complexity is $O(d \log d(n(km_1 + m_2) + k^2m_1^2))$, majored by the checks regarding $w$ or $v$. We bound the running time of the prover by $T_{V,\text{new}} \le 4T_{V,LNP}$.

We manage to show a comparison of the size of the transcripts and the evolution of running time with [LNP22] in the Table 3 for 5 parameter sets defined in the Figure 2.

**Acknowledgments.** This work is supported by the PEPR quantique France 2030 program (ANR-22-PETQ-0008 PQ-TLS) and by the ASTRID program under the national project AMIRAL with reference ANR-21-ASTR-0016. Antoine Douteau is partially funded by the region of Normandy, France.
References

AAB<sup>22</sup>. C. Aguilar-Melchor, N. Aragon, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, E. Persichetti, G. Zémor, J. Bos, A. Dion, J. Lacan, J.-M. Robert, and P. Veron. HQC. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions.

ABB<sup>22</sup>. N. Aragon, P. Barreto, S. Bettaieb, L. Bidoux, O. Blazy, J.-C. Deneuville, P. Gaborit, S. Gueron, T. Guneysu, C. Aguilar-Melchor, R. Misoczki, E. Persichetti, N. Sendrier, J.-P. Tillich, G. Zémor, V. Vasseur, S. Ghosh, and J. Richter-Brokmann. BIKE. Technical report, National Institute of Standards and Technology, 2022. available at https://csrc.nist.gov/Projects/post-quantum-cryptography/round-4-submissions.

Ajt96. M. Ajtai. Generating hard instances of lattice problems (extended abstract). In *28th ACM STOC*, pages 99–108. ACM Press, May 1996.

Ajt98. M. Ajtai. The shortest vector problem in $L^2$ is NP-hard for randomized reductions (extended abstract). In *30th ACM STOC*, pages 10–19. ACM Press, May 1998.

AKSY22. S. Agrawal, E. Kirshanova, D. Stehlé, and A. Yadav. Practical, round-optimal lattice-based blind signatures. In *ACM CCS 2022*, pages 39–53. ACM Press, November 2022.

APS15. M. R. Albrecht, R. Player, and S. Scott. On the concrete hardness of learning with errors. In *Journal of Mathematical Cryptology*, pages 169–203, 10 2015.

BBD<sup>23</sup>. M. Barbosa, G. Barthe, C. Doczkal, J. Don, S. Fehr, B. Grégoire, Y.-H. Huang, A. Hülsing, Y. Lee, and X. Wu. Fixing and mechanizing the security proof of Fiat-Shamir with aborts and Dilithium. In *CRYPTO 2023, Part V*, LNCS 14085, pages 358–389. Springer, Cham, August 2023.

BBE<sup>18</sup>. G. Barthe, S. Belaïd, T. Espitau, P.-A. Fouque, B. Grégoire, M. Rossi, and M. Tibouchi. Masking the GLP lattice-based signature scheme at any order. In *EUROCRYPT 2018, Part II*, LNCS 10821, pages 354–384. Springer, Cham, April / May 2018.

BCM21. R. Behnia, Y. Chen, and D. Masny. On removing rejection conditions in practical lattice-based signatures. In *Post-Quantum Cryptography - 12th International Workshop, PQCrypto 2021*, pages 380–398. Springer, Cham, 2021.

BDK<sup>18</sup>. J. W. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J. M. Schanck, P. Schwabe, G. Seiler, and D. Stehlé. CRYSTALS - kyber: A CCA-secure module-lattice-based KEM. In *2018 IEEE European Symposium on Security and Privacy*, pages 353–367. IEEE Computer Society Press, April 2018.

BDK<sup>23</sup>. W. Beullens, S. Dobson, S. Katsumata, Y.-F. Lai, and F. Pintore. Group signatures and more from isogenies and lattices: generic, simple, and efficient. *DCC*, 91(6):2141–2200, 2023.

BDL<sup>18</sup>. C. Baum, I. Damgård, V. Lyubashevsky, S. Oechsner, and C. Peikert. More efficient commitments from structured lattice assumptions. In *SCN 18*, LNCS 11035, pages 368–385. Springer, Cham, September 2018.

BKP20. W. Beullens, S. Katsumata, and F. Pintore. Calamari and Falafi: Logarithmic (linkable) ring signatures from isogenies and lattices. In *ACI-ACRYPT 2020, Part II*, LNCS 12492, pages 464–492. Springer, Cham, December 2020.
BLNS23. J. Bootle, V. Lyubashevsky, N. K. Nguyen, and A. Sorniotti. A framework for practical anonymous credentials from lattices. In *CRYPTO 2023, Part II, LNCS* 14082, pages 384–417. Springer, Cham, August 2023.

CGL+24. J.-S. Coron, F. Gérard, T. Lepoint, M. Trannoy, and R. Zeitoun. Improved high-order masked generation of masking vector and rejection sampling in dilithium, 2024.

CLOS02. R. Canetti, Y. Lindell, R. Ostrovsky, and A. Sahai. Universally composable two-party and multi-party secure computation. In *34th ACM STOC*, pages 494–503. ACM Press, May 2002.

DDLL13. L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice signatures and bimodal Gaussians. In *CRYPTO 2013, Part I, LNCS* 8042, pages 40–56. Springer, Berlin, Heidelberg, August 2013.

DFPS22. J. Devevey, O. Fawzi, A. Passelègue, and D. Stehlé. On rejection sampling in Lyubashevsky’s signature scheme. In *ASIACRYPT 2022, Part IV, LNCS* 13794, pages 34–64. Springer, Cham, December 2022.

DFPS23. J. Devevey, P. Fallahpour, A. Passelègue, and D. Stehlé. A detailed analysis of Fiat-Shamir with aborts. In *CRYPTO 2023, Part V, LNCS* 14085, pages 327–357. Springer, Cham, August 2023.

DG19. L. De Feo and S. D. Galbraith. SeaSign: Compact isogeny signatures from class group actions. In *EUROCRYPT 2019, Part III, LNCS* 11478, pages 759–789. Springer, Cham, May 2019.

DKL+18. L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé. CRYSTALS-Dilithium: A lattice-based digital signature scheme. *IACR TCHES*, 2018(1):238–268, 2018.

DPS23. J. Devevey, A. Passelègue, and D. Stehlé. G+G: A fiat-shamir lattice signature based on convolved gaussians. In *ASIACRYPT 2023, Part VII, LNCS* 14444, pages 37–64. Springer, Singapore, December 2023.

EFGT17. T. Espitau, P.-A. Fouque, B. Gérard, and M. Tibouchi. Side-channel attacks on BLISS lattice-based signatures: Exploiting branch tracing against strongSwan and electromagnetic emanations in microcontrollers. In *ACM CCS 2017*, pages 1857–1874. ACM Press, October / November 2017.

ENP24. T. Espitau, G. Niot, and T. Prest. Flood and submerse: Distributed key generation and robust threshold signature from lattices. In *CRYPTO 2024, Part VII, LNCS* 14926, pages 425–458. Springer, Cham, August 2024.

FS87. A. Fiat and A. Shamir. How to prove yourself: Practical solutions to identification and signature problems. In *CRYPTO'86, LNCS* 263, pages 186–194. Springer, Berlin, Heidelberg, August 1987.

GHJ+22. Q. Guo, C. Hlauschek, T. Johansson, N. Lahr, A. Nilsson, and R. L. Schröder. Don’t reject this: Key-recovery timing attacks due to rejection-sampling in HQC and BIKE. *IACR TCHES*, 2022(3):223–263, 2022.

GMR85. S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof-systems (extended abstract). In *17th ACM STOC*, pages 291–304. ACM Press, May 1985.

GMSS99. O. Goldreich, D. Micciancio, S. Safra, and J.-P. Seifert. Approximating shortest lattice vectors is not harder than approximating closest lattice vectors. *Information Processing Letters*, 71(2):55–61, 1999.

GPV08. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for hard lattices and new cryptographic constructions. In *40th ACM STOC*, pages 197–206. ACM Press, May 2008.
HSS24. I. Hwang, J. Seo, and Y. Song. Concretely efficient lattice-based polynomial commitment from standard assumptions. In *CRYPTO 2024, Part X*, LNCS 14929, pages 414–448. Springer, Cham, August 2024.

ISW03. Y. Ishai, A. Sahai, and D. Wagner. Private circuits: Securing hardware against probing attacks. In *CRYPTO 2003, LNCS* 2729, pages 463–481. Springer, Berlin, Heidelberg, August 2003.

KLSS23. D. Kim, D. Lee, J. Seo, and Y. Song. Toward practical lattice-based proof of knowledge from hint-MLWE. In *CRYPTO 2023, Part V*, LNCS 14085, pages 549–580. Springer, Cham, August 2023.

LN22. V. Lyubashevsky and N. K. Nguyen. BLOOM: Bimodal lattice one-out-of-many proofs and applications. In *ASIACRYPT 2022, Part IV*, LNCS 13794, pages 95–125. Springer, Cham, December 2022.

LNP22. V. Lyubashevsky, N. K. Nguyen, and M. Plançon. Lattice-based zero-knowledge proofs and applications: Shorter, simpler, and more general. In *CRYPTO 2022, Part II*, LNCS 13508, pages 71–101. Springer, Cham, August 2022.

LNS21. V. Lyubashevsky, N. K. Nguyen, and G. Seiler. Shorter lattice-based zero-knowledge proofs via one-time commitments. In *PKC 2021, Part I*, LNCS 12710, pages 215–241. Springer, Cham, May 2021.

LS15. A. Langlois and D. Stehlé. Worst-case to average-case reductions for module lattices. *DCC*, 75(3):565–599, 2015.

LSS24. V. Lyubashevsky, G. Seiler, and P. Steuer. The LaZer library: Lattice-based zero knowledge and succinct proofs for quantum-safe privacy. In *ACM CCS 2024*, pages 3125–3137. ACM Press, October 2024.

Lyu09. V. Lyubashevsky. Fiat-Shamir with aborts: Applications to lattice and factoring-based signatures. In *ASIACRYPT 2009, LNCS* 5912, pages 598–616. Springer, Berlin, Heidelberg, December 2009.

Lyu12. V. Lyubashevsky. Lattice signatures without trapdoors. In *EUROCRYPT 2012, LNCS* 7237, pages 738–755. Springer, Berlin, Heidelberg, April 2012.

MGTF19. V. Migliore, B. Gérard, M. Tibouchi, and P.-A. Fouque. Masking Dilithium - efficient implementation and side-channel evaluation. In *ACNS 19International Conference on Applied Cryptography and Network Security*, LNCS 11464, pages 344–362. Springer, Cham, June 2019.

MP12. D. Micciancio and C. Peikert. Trapdoors for lattices: Simpler, tighter, faster, smaller. In *EUROCRYPT 2012, LNCS* 7237, pages 700–718. Springer, Berlin, Heidelberg, April 2012.

MR07. D. Micciancio and O. Regev. Worst-case to average-case reductions based on gaussian measures. *SIAM Journal on Computing*, 37(1):267–302, 2007.

NS24. N. K. Nguyen and G. Seiler. Greyhound: Fast polynomial commitments from lattices. In *CRYPTO 2024, Part X*, LNCS 14929, pages 243–275. Springer, Cham, August 2024.

Pei10. C. Peikert. An efficient and parallel Gaussian sampler for lattices. In *CRYPTO 2010, LNCS* 6223, pages 80–97. Springer, Berlin, Heidelberg, August 2010.

PR13. E. Prouff and M. Rivain. Masking against side-channel attacks: A formal security proof. In *EUROCRYPT 2013, LNCS* 7881, pages 142–159. Springer, Berlin, Heidelberg, May 2013.

Reg05. O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In *37th ACM STOC*, pages 84–93. ACM Press, May 2005.
# A Simulatability proof

# B Additional preliminaries

## B.1 Structured lattices

We consider a structured case of lattices defined over $\mathcal{R}$. It implies an isomorphism between $\mathcal{R}$ and $\mathbb{Z}^d$. We define the invertible operation Coeffs which transforms vectors of coefficients into polynomials. Then, the operations can be adapted to the specific case. The sum is intuitive, but the product needs to exploit the rotation matrix associated with the polynomial. For two elements $a = \sum_{0 \le i < d} a_i X^i \in \mathcal{R}$ and $b = \sum_{0 \le i < d} b_i X^i \in \mathcal{R}$ where $a_i, b_i \in \mathbb{Z}$, we have:

$$ \text{Coeffs}(a \cdot b) = \text{Rot}_d(a) \cdot \begin{bmatrix} b_0 \\ b_1 \\ \vdots \\ b_{d-1} \end{bmatrix} \quad \text{with} \quad \text{Rot}_d(a) := \begin{bmatrix} a_0 & -a_{d-1} & \cdots & -a_1 \\ a_1 & a_0 & \cdots & -a_2 \\ \vdots & \vdots & \ddots & \vdots \\ a_{d-1} & a_{d-2} & \cdots & a_0 \end{bmatrix} \in \mathbb{Z}^{d \times d}. $$

It can be generalized to a greater amount of such polynomials. Consider a matrix A with coefficients in $\mathcal{R}$; simply generate the block matrix composed with rotation matrices of each coefficient.

## B.2 Protocols

**Interactive proofs.** A prover $\mathcal{P}$ wants to prove knowledge to a third party, called Verifier $\mathcal{V}$, without revealing the private information. The idea originally revealed in [GMR85] is to involve $\mathcal{V}$ in the process and interact until they are convinced that $\mathcal{P}$ has the knowledge. The relation proven can be seen as a couple $(x,w)$, with $x$ being a public statement associated to a (private) witness $w$. We associate with such a proof different notions of security:

*Completeness.* A proof is complete if the verifier $\mathcal{V}$, with the knowledge of an accepting witness $w$, produces an accepting transcript (with overwhelming probability) of the protocol with an honest verifier $\mathcal{V}$.

*($\mathcal{Knowledge}$) Soundness.* Soundness means that a verifier $\mathcal{V}$ rejects false statements (with overwhelming probability). The case of Knowledge Soundness is a stronger notion and ensures that if a prover (not necessarily honest) convinces a verifier multiple times for the same statement $x$, then the prover must know (with overwhelming probability) a valid witness $w$. We defined as an extractor a PPT algorithm exploiting a convincing prover.

*Simulatability.* The simulator $\mathcal{S}$ is a PPT algorithm that produces a transcript $\pi$ associated with an interactive protocol $(\mathcal{P}, \mathcal{V})$ with the public statement $x$. We say that the protocol is simulatable if the output generated by $\mathcal{S}$ is indistinguishable from the transcript $\pi$ of a fully honest execution of the interactive protocol.

*Zero-Knowledge proofs.* As explained in [KLSS23, LNP22, LNS21], we prefer to define the notion of simulatability, which is a stronger notion than the zero-knowledge property. The zero-knowledge property means that the verifier does
not gain any information on the witness $w$ used and known by the prover $P$. The simulatability means that the verifier cannot distinguish between valid transcript (over public and private information) and simulated one (over only public information).

**Commitment Scheme.** In order to preserve the zero-knowledge property but also guarantee to $V$ that $P$ does not trick him, the notion of commitment scheme ensures a potentially well-constructed protocol. We recall the definition of a commitment scheme. A commitment scheme is a tuple of three PPT algorithms:

- **Setup**($1^{\lambda}$) → ck: Given a security parameter $\lambda$, it generates a key ck,

- **Commit** (ck, $m$) → (c, $\delta$): Given a message $m$ and the commitment key ck, it returns an associated commitment $c$ and an opening $\delta$,

- **Open** (ck, $c$, $m$, $\delta$) → {$\perp, \top$}: Given a commitment key ck, a commitment $c$, a message $m$, and an opening $\delta$, it outputs the validity of the opening.

A well-constructed commitment scheme needs to satisfy two properties to ensure its security. The first one is called *binding*, the hardness of opening a single commitment to two distinct initial messages. The second security notion is the *hiding* property. It is the "IND-CPA security" adapted to commitment schemes.

**Proof of Opening Knowledge.** A “proof of opening knowledge” is the interactive proof of knowledge regarding the process knowledge of the message committed using a commitment scheme.

### B.3 The Gaussianisation method from [HSS24]

The [HSS24] method is used to construct an encoding following a Gaussian distribution centered in the secret encoding. First, it computes an encoding version of an element $s \in \mathcal{R}_p^m$, exploiting the inverse $G^{-1}$ of the gadget matrix. In a second step, the encoding is randomized by sampling a non-influent error.

**Encoding protocol.** The encoding protocol treats a full polynomial as a large vector of its coefficients, encoding each coefficient by the signed decomposition in base $b$ (of length $k$) denoted by $G_{b,k,d}^{-1}$ and detailed in Algorithm 7.

- **Encode**($\mathbf{t}$) → $\hat{\mathbf{t}}$: For an element $\mathbf{t} \in \mathcal{R}_p^m$, we compute $\hat{\mathbf{t}} = G_{b,k,dm}^{-1} \mathbf{t} \in \mathcal{R}_p^{km}$. The output satisfies $\|\hat{\mathbf{t}}\|_{\infty} \le \frac{b+2}{2}$. The action of $G_{b,k,d}^{-1} \mathbf{t}$ is defined in the Algorithm 7. For any $m$, we proceed by defining: $G_{b,k,dm}^{-1} := I_m \otimes G_{b,k,d}^{-1}$.

- **Decode**($\hat{\mathbf{t}}$) → $\mathbf{t}$: Output the matrix product $\mathbf{t} = G_{b,k,dm} \hat{\mathbf{t}}$ over $\mathcal{R}_p$.

**Randomization step.** We recall the randomization process from [HSS24]. The key analysis is that encoded elements are equal modulo $p$ when considered as elements of $\hat{\mathcal{R}}$ i.e. if $\hat{a} = a' \bmod p$, then $\text{Decode}(\hat{a}) = \text{Decode}(a')$ over $\mathcal{R}_p$. This property is used to randomize a message over all the possibilities such that it satisfies the same decoding. However, it forces us to restrain the message space
as $\mathcal{R}_p$ with a valid $p$, but it is allowed by the fact that $\|\hat{\mathbf{t}}\|_{\infty} \le \frac{b+2}{2} < p$. We generalize to a length $m$ with $P_m := \text{Rot}_{kdm}(\mathfrak{p}_m) = \text{Rot}_{kd}(\mathfrak{p}) \otimes \mathbf{I}_m \in \mathbb{Z}_p^{kdm}$, where we have $\|P_m\| = \|\mathfrak{p}_m\| = b+1$.

- RandomizedEncode($\mathbf{t}, \sigma$) → $\tilde{\mathbf{t}}$: Compute $\hat{\mathbf{t}} \leftarrow \text{Encode}(\mathbf{t})$. Then, sample an error $\tilde{e} \leftarrow D_{\mathbb{Z}_{kdm}, \sigma}$. Return $\tilde{\mathbf{t}} = \hat{\mathbf{t}} + \text{Coeffs}^{-1}(P_m \tilde{e})$ as an element of $(\mathcal{R}_p^k)^m$,

- RandomizedDecode is the same as Decode.

During the rest of the paper, we distinguish the two notations related to the encoding of an element $\mathbf{t} \in \mathcal{R}_p^m$: the "classical" encoding is denoted by $\hat{\mathbf{t}}$ and the "randomized" encoding $\tilde{\mathbf{t}} = \hat{\mathbf{t}} + \mathfrak{p}_m \mathbf{e}$ that follows a Gaussian distribution. Both are elements of $\mathcal{R}_p^{km}$.

<caption>**Algorithm 7:** Encoding method from [HSS24].</caption>

**Input:** $\sum_{i=0}^{d-1} a_i X^i \in \mathcal{R}_p$
**Output:** $a \in \mathcal{R}^k$
**for** $0 \le i < d$ **do**
    if $a_i = -1 \bmod p$ **then**
        $\lfloor (a_{i,0}, \dots, a_{i,k-1}) \rfloor \leftarrow (0, \dots, 0, b)$
    else
        $\lfloor (a_{i,0}, \dots, a_{i,k-1}) \rfloor \leftarrow$ the $b$-representation of $a_i < b^k$
    **for** $0 \le i < d, 0 \le j < k$ **do**
        if $a_{i,j} > \frac{b}{2}$ **then**
            $\lfloor a_{i,j} \rfloor \leftarrow a_{i,j} - b$; $c_{i,j} \leftarrow 1$
        else
            $\lfloor c_{i,j} \rfloor \leftarrow 0$
    $\hat{a} \leftarrow \sum_{0 \le i < d} \sum_{0 \le j < k} a_{i,j} X^{d(j+i)} + c_{i,j} X^{d(j+1)+i} \in \hat{\mathcal{R}}$
    **Return** $a$ as an element of $\mathcal{R}^k$ with the same vector of coefficients of $\hat{a}$

## B.4 Bound of the norm of the challenge matrix

We recall the two definition of norm of matrices:

$$ \|C\|_1 := \|C\|_{1,1} = \max_{j \in [n]} \sum_{i \in [n]} |a_{i,j}| \quad \text{and} \quad \|C\|_{\infty} := \|C\|_{\infty,\infty} = \max_{i \in [n]} \sum_{j \in [n]} |a_{i,j}|. $$

Take a challenge $c \in \mathcal{C}$, and its associated rotated matrix $C := \text{Rot}_n(c)$. For the norm, we have $\|C\|^2 \le \|C\|_1 \cdot \|C\|_{\infty}$. We have by definition of the challenge space that $|c| \le \eta$. Exploiting the structure of the rotation matrix, shown above in Appendix B.1, we have $\|C\|_1 = \|C\|_{\infty} = \eta$, and therefore the bound $\|C\|_2^2 \le \eta^2$.

## B.5 Communativity between encoding and conjugate automorphism

**Lemma B.1 (Lemma 4.2).** Let $\sigma \in \text{Aut}(\mathcal{R}_p)$ and $\mathbf{x} \in \mathcal{R}_p^{m_1}$ a secret, and $\bar{\mathbf{x}} \in \{\hat{\mathbf{x}}, \tilde{\mathbf{x}}\}$ seen as an element of $\mathcal{R}_p^{km_1}$ its encoding (resp. randomized encoding) of $\mathbf{x}$. Then, we have for each $\bar{\mathbf{x}} \in \{\hat{\mathbf{x}}, \tilde{\mathbf{x}}\}: \overline{\sigma(\mathbf{x})} = \sigma(\bar{\mathbf{x}})$ decoded in a unique $\sigma(\mathbf{x})$.
Proof. We initiate the proof by seeing the action of an automorphism over the coefficients. Considering a polynomial $f \in \mathcal{R}$, we denote by $f^*$ its reciprocal polynomial. We have the equality $f^* = X^{d-1}\sigma(f)$ that implies $-X \cdot f^* = \sigma(f)$. Then, we consider the automorphism as a matrix product over the coefficients seen as Coeffs($\sigma(f)$) = Rot$_d(-X) \cdot \mathbf{J}_d \cdot Coeffs(f) = \begin{bmatrix} 1 & 0 \\ 0 & -\mathbf{J}_{d-1} \end{bmatrix} \cdot Coeffs(f)$.

In order to prove the Lemma, we first study the case of the $\hat{s}$ (the encoding without randomization). Suppose without loss of generality (via the concatenation process) that $m_1 = 1$ i.e. $\mathbf{s}$ is composed as a single message in $\mathcal{R}_p$. Then, we use the equality between the decomposition in base $b$ of an element $a$ and its inverse $-a$. Especially here, the decomposition used in the encoding protocol made our coefficients live in $[-\frac{b}{2}, \frac{b}{2}]$ with a carry $c$:

$$a := \sum_{0 \le j < k} a_j b^j + c_j b^{j+1} = (a_0 - c_{k-1}) + \sum_{0 \le j < k-1} (a_j + c_{j-1}) b^j,$$

so we have similarly the same decomposition for $-a$:

$$-a = -(a_0 - c_{k-1}) + \sum_{1 \le j < k} -(a_j + c_{j-1}) b^j.$$

We remind you from the remark at the beginning that we have for any element $t \in \mathcal{R}_p$, the equality $\vec{\sigma}(t) = \mathbf{A}\vec{t}$ by denoting $\mathbf{A} := \mathrm{Rot}_d(-X) \cdot \mathbf{J}_d$. For an element in $\mathcal{R}_p^k$ we involve the Kronecker product to apply the action of $\sigma$ over the $k$ polynomials such as $\vec{\sigma}(\mathbf{t}) = (\mathbf{I}_k \otimes \mathbf{A})\vec{t}$. Now, we expand the total formula of Encode($\sigma(t)$) by considering $t = \sum_{i=0}^{d-1} t_i X^i$ and the associated polynomial $\sigma(t) =: t' = \sum_{i=0}^{d-1} t'_i X^i$

$$\mathrm{Encode}(t') = \begin{pmatrix} (t'_{0,0} - c'_{0,k-1}, t'_{1,0} - c'_{1,k-1}, \dots, t'_{d-1,0} - c'_{d-1,k-1}) \\ (t'_{0,1} + c'_{0,0}, t'_{1,1} + c'_{1,0}, \dots, t'_{d-1,1} + c'_{d-1,0}) \\ \vdots \\ (t'_{0,k-1} + c'_{0,k-2}, t'_{1,k-1} + c'_{1,k-2}, \dots, t'_{d-1,k-1} + c'_{d-1,k-2}) \end{pmatrix},$$

where $\begin{cases} t'_0 = t_0, \\ t'_i = -t_{d-i} \end{cases}$ for $i \in [1, d-1]$.

that implies $\begin{cases} \forall j \in [0, k-1], t'_{0,j} = t_{0,j} \text{ and } c'_{0,j} = c_{0,j}, \\ \forall j \in [0, k-1], t'_{i,j} = -t_{d-i,j} \text{ and } c'_{i,j} = -c_{d-i,j}. \end{cases}$

$$\mathrm{Encode}(t') = \begin{pmatrix} (t_{0,0} - c_{0,k-1}, -(t'_{d-1,0} - c'_{d-1,k-1}), \dots, -(t'_{1,0} - c'_{1,k-1})) \\ (t_{0,1} + c_{0,0}, -(t'_{d-1,1} + c'_{d-1,0}), \dots, -(t'_{1,1} + c'_{1,0})) \\ \vdots \\ (t_{0,k-1} + c_{0,k-2}, -(t'_{d-1,k-1} + c'_{d-1,k-2}), \dots, -(t'_{1,k-1} + c'_{1,k-2})) \end{pmatrix}. \quad (8)$$

In a second step, we show the action of the $\sigma$ after the Encoding protocol.
$$ \text{Encode}(t) = \begin{pmatrix} (t_{0,0} - c_{0,k-1}, t_{1,0} - c_{1,k-1}, \dots, t_{d-1,0} - c_{d-1,k-1}) \\ (t_{0,1} + c_{0,0}, t_{1,1} + c_{1,0}, \dots, t_{d-1,1} + c_{d-1,0}) \\ \vdots \\ (t_{0,k-1} + c_{0,k-2}, t_{1,k-1} + c_{1,k-2}, \dots, a_{d-1,k-1} + c_{d-1,k-2}) \end{pmatrix}. $$

Now we apply the automorphism row per row by keeping fixed the constant coefficients and negarotating others.

$$ \sigma(\text{Encode}(t)) = \begin{pmatrix} (t_{0,0} - c_{0,k-1}, -(t'_{d-1,0} - c'_{d-1,k-1}), \dots, -(t'_{1,0} - c'_{1,k-1})) \\ (t_{0,1} + c_{0,0}, -(t_{d-1,1} + c_{d-1,0}), \dots, -(t_{1,1} + c_{1,0})) \\ \vdots \\ (t_{0,k-1} + c_{0,k-2}, -(t_{d-1,k-1} + c_{d-1,k-2}), \dots, -(t_{1,k-1} + c_{1,k-2})) \end{pmatrix}. \quad (10) $$

We now see the equality between the two structures (8) and (10) that implies the equality $G^{-1}A\tilde{t} = AG^{-1}\tilde{t}$. By considering $m_1$ elements $s \in \mathcal{R}_p^{m_1}$, we have the same property: $(I_{m_1} \otimes G^{-1}A)s = (I_{m_1} \otimes AG^{-1})s$.

Now, we show that the equality also works over randomized encoding. We remind that we have $\tilde{t} = \hat{t} + pt$ for $p := X^d - b$. We then view its vector of coefficients as $\text{Rot}_{kd}(X^d - b) \cdot \text{Coeffs}(e)$ with the aim of showing that we have the invariance over the polynomial $p$: $\sigma(\tilde{t}) = \sigma(\hat{t}) \mod X^d - b$. By using the homomorphic property of the automorphism $\sigma(\tilde{t}) = \sigma(\hat{t}) + \sigma(pe)$, we just need to prove that $\sigma(pe) = 0 \mod X^d - b$ i.e. a multiple of $X^d - b$. We remind the following Kronecker product property $AC \otimes BD = (A \otimes B) \cdot (C \otimes D)$ for well sized matrices. Expanding the matrix $\text{Rot}_{kd}(X^d - b)$, we can easily see that: $\text{Rot}_{kd}(X^d - b) = \text{Rot}_d(X^d - b) \otimes I_k = \text{Rot}_k(X - b) \otimes I_d$. By denoting $B = \text{Rot}_k(X - b)$ and using Kronecker product properties, we have:

$$ \begin{aligned} \text{Coeffs}(\sigma(pe)) &= (I_k \otimes A) \cdot (B \otimes I_d) \cdot \text{Coeffs}(e) \\ &= (B \otimes I_d) \cdot (I_k \otimes A) \cdot \text{Coeffs}(e) \\ &= \text{Rot}_{kd}(X^d - b) \cdot \text{Coeffs}(\sigma(e)) \\ &= \text{Coeffs}(p\sigma(e)) \end{aligned} $$

This ensures as well that $\sigma(e)$ using $p_m$. This proof is also valid for any message $s \in \mathcal{R}_p^{m_1}$ using the equality $\tilde{\sigma}(s) = (I_{m_1} \otimes A)\tilde{s}$. $\square$

# C Comparison with the original framework

## C.1 Details of the different sets of parameters

We chose to maintain the same ring degree $d = 64$ (rather than 128) because it does not significantly impact the overall comparison or ratio between our implementation and that of [LNP22], which relies on [LSS24]. Parameter sets 1 and 2 represent typical executions involving a low number of both bounded and
<table><caption>Table 2: Sets of parameters involved in the proof frameworks. The first section of parameters are manually set, others are either computed using /scripts of our code inspired by the LaZer Library or using LWE-Estimator [APS15].</caption><thead><tr><th colspan="6">Sets of parameters</th></tr><tr><th>Variable</th><th>Description</th><th>Set 1</th><th>Set 2</th><th>Set 3</th><th>Set 4</th><th>Set 5</th></tr></thead><tbody><tr><td>λ</td><td>Security parameter</td><td></td><td></td><td>128</td><td></td><td></td></tr><tr><td>d</td><td>Ring degree</td><td></td><td></td><td>64</td><td></td><td></td></tr><tr><td>log p</td><td>Log of the ring moduli</td><td>60</td><td>120</td><td>80</td><td>80</td><td>60</td></tr><tr><td>m<sub>1LNP</sub></td><td>Number of low-norm messages</td><td>10</td><td>10</td><td>100</td><td>0</td><td>100</td></tr><tr><td>ℓ<sub>LNP</sub></td><td>Number of unbounded messages</td><td>2</td><td>2</td><td>0</td><td>20</td><td>20</td></tr><tr><td>m<sub>1new</sub></td><td>Number of messages = m<sub>1LNP</sub> + ℓ<sub>LNP</sub></td><td>12</td><td>12</td><td>100</td><td>20</td><td>120</td></tr><tr><td>N</td><td>Number of quadratic equations to prove</td><td></td><td></td><td>3</td><td></td><td></td></tr><tr><td colspan="7">Security parameters</td></tr><tr><td>κ</td><td>||c||<sub>∞</sub> ≤ κ with c ∈ C</td><td></td><td></td><td>8</td><td></td><td></td></tr><tr><td>η</td><td>||cr|| ≤ η||r|| with c ∈ C and r a vector of R</td><td></td><td></td><td>140</td><td></td><td></td></tr><tr><td>n</td><td>Height of A<sub>1</sub> and A<sub>2</sub></td><td>32</td><td>38</td><td>35</td><td>34</td><td>34</td></tr><tr><td>m<sub>2</sub></td><td>Length of the randomness s<sub>2</sub></td><td>71</td><td>114</td><td>86</td><td>85</td><td>73</td></tr><tr><td colspan="7">Dilithium compression</td></tr><tr><td>γ</td><td>Largest parameter to cut low-order bits of w</td><td></td><td></td><td></td><td>See in implementation</td><td></td></tr><tr><td>D</td><td>Number of low-order bits cut from t<sub>A</sub></td><td>31</td><td>61</td><td>42</td><td>41</td><td>32</td></tr><tr><td colspan="7">Computed parameters</td></tr><tr><td>b</td><td>Base decomposition</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>p</td><td>Prime p := b<sup>2</sup> + 1 congruent to 5 modulo 8</td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>σ<sub>1</sub></td><td>SD of the randomized encoding of s<sub>1</sub></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>√2s<sub>1</sub></td><td>SD of the randomized encoding of the mask y<sub>rand</sub></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>σ<sub>2</sub></td><td>SD of the randomness s<sub>2</sub></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>s<sub>2</sub></td><td>SD of the mask of y<sub>2</sub></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>

unbounded messages, closely reflecting classical use cases of the framework, but with two different ring moduli. Parameter set 3 simulates an execution with a high number of bounded messages only, while set 4 focuses on a high number of unbounded messages only. Notably, the set 4 was not supported in the original construction without affecting the size of the transcript in log(p). Finally, parameter set 5 simulates a typical execution involving a high number of messages, reflecting use cases in more complex cryptographic applications such as aggregate signatures.

## C.2 Comparison table
<table><caption>Table 3: The first part of the Table explains the size of the transcripts in kilobytes for different parameter sets explained in Appendix C.1. In the second part, the results show our benchmarks for the mean running time of 100 executions of each phase for an execution of different instances of the protocol for the 5 different sets of parameters detailed in Table 2. The running time of the Prove part of [LNP22] using the [LSS24] implementation takes into account several executions due to rejection sampling.</caption><thead><tr><th colspan="7">Size of the transcripts (in kilobytes KB)</th></tr><tr><th>Protocol</th><th>Protocol/Phase</th><th>Param. 1</th><th>Param. 2</th><th>Param. 3</th><th>Param. 4</th><th>Param. 5</th></tr></thead><tbody><tr><td rowspan="3">[LNP22]</td><td rowspan="3">Opening proof<br/>+ 3 Quad.<br/>+ 3 Eval.</td><td>13.22</td><td>20.77</td><td>30.53</td><td>×</td><td>41.05</td></tr><tr><td>13.93</td><td>21.86</td><td>31.31</td><td>×</td><td>41.68</td></tr><tr><td>15.16</td><td>22.96</td><td>32.09</td><td>×</td><td>42.93</td></tr><tr><td rowspan="3">Ours</td><td rowspan="3">Opening proof<br/>+ 3 Quad.<br/>+ 3 Eval.</td><td>24.23</td><td>45.69</td><td>103.19</td><td>37.33</td><td>96.52</td></tr><tr><td>24.83</td><td>46.76</td><td>103.95</td><td>38.08</td><td>97.12</td></tr><tr><td>25.42</td><td>47.82</td><td>104.70</td><td>38.83</td><td>97.72</td></tr><tr><td colspan="7">Mean times (in million cycles)</td></tr><tr><td rowspan="5">[LNP22]</td><td rowspan="5">KeyGen<br/>Commit<br/>Prove<br/>Verify</td><td>7.63</td><td>10.32</td><td>19.32</td><td>×</td><td>39.35</td></tr><tr><td>7.29</td><td>20.89</td><td>31.33</td><td>×</td><td>39.42</td></tr><tr><td>324.22</td><td>352.22</td><td>4289.68</td><td>×</td><td>4462.29</td></tr><tr><td>18.54</td><td>39.17</td><td>1744.10</td><td>×</td><td>1629.12</td></tr><tr><td>19.01</td><td>47.04</td><td>66.30</td><td>29.55</td><td>62.01</td></tr><tr><td rowspan="4">Ours</td><td rowspan="4">KeyGen<br/>Commit<br/>Prove<br/>Verify</td><td>19.86</td><td>86.54</td><td>102.47</td><td>45.73</td><td>67.15</td></tr><tr><td>59.45</td><td>134.26</td><td>4248.67</td><td>220.98</td><td>3961.24</td></tr><tr><td>41.74</td><td>96.79</td><td>3897.43</td><td>180.31</td><td>3624.34</td></tr></tbody></table>