Abstract Lattice-based commitment schemes and their associated zero-knowledge proofs are essential building blocks for advanced lattice-based cryptographic protocols. In particular, proofs of algebraic relations among committed messages are widely used in privacy-preserving protocols such as range proofs. At CRYPTO 2020, Attema et al. proposed practical proofs for valid openings and multiplicative relations among committed values using the BDLOP commitment scheme. In their work, all commitments are generated using the same short randomness. In this paper, we consider a batch setting where commitments are generated using $$\ell$$ ℓ independent random vectors and present a batch valid opening proof. Our construction generalizes the approach of Baum et al. by supporting a larger challenge set and removing the requirement for invertible challenge differences. As a result, the proof size scales logarithmically with $$\ell$$ ℓ , rather than linearly. Furthermore, we introduce a product proof for committed messages with shared randomness across these $$\ell$$ ℓ commitment groups. Compared to the naive approach of applying Attema’s product proof once and repeating the opening proof $$\ell -1$$ ℓ - 1 times, our method achieves significantly better communication efficiency.

Abstract Verifiable encryption enables the decryption to be taken on properly generated ciphertexts, by making the encryptor provide a zero-knowledge proof. To meet the quantum-safe application requirements, such as key escrow, Lyubashevsky et al. proposed a one-shot verifiable encryption (LN17 scheme) based on the hardness of lattice problems. In their scheme, the FSwA-type zero-knowledge proof was obtained using rejection sampling on a discrete Gaussian distribution. In this paper, we present a construction of verifiable encryption that utilizes rejection sampling on bimodal Gaussian to get the associated zero-knowledge proof. Our new construction, while exhibiting a weaker soundness property than LN17 scheme, benefits from a smaller proof size, leading to a reduced size of the verifiable ciphertext. As for the weaker soundness property, it supports some applications such as key escrow where honestly generated verifiable ciphertexts are more useful to be decrypted out in the hope of doing some further computation tasks. We provide the efficiency comparison of the new construction by instantiating it with several sets of concrete parameters.

The BDLOP commitment of Baum et al. (SCN 2018) is the currently most efficient commitment scheme. Based on BDLOP commitment, Attema et al. in CRYPTO 2020 presented an efficient product proof in the ring Rq = ℤq[X]/(Xd + 1) where Xd + 1 splits into low-degree factors (ALS scheme). Their proof has only one garbage commitment besides the necessary opening proof and works in the case that all the messages are committed simultaneously using the same randomness r⃗. In this paper, we deal with the case where the messages involved in the multiplicative relation are committed using different randomnesses, and construct a parallel product proof and two sequential product proofs. Both of which still require need one additional garbage commitment.

Abstract Bootle et al. in CRYPTO 2019 proposed a zero knowledge proof for an $\mathrm{ISIS}_{m,n,q,\beta }$ instance $A\vec{s} = \vec{u} \bmod q$ with $\|\vec{s}\|_{\infty }\leq \beta $ (BLS scheme). It was implemented by transforming the instance into the form $A^{\prime }\vec{s}^{\prime } =\vec{u}\bmod q$, where the coefficients of $\vec{s}^{\prime}$ are in $\{0,1,2\}$, and proved the latter in an exact way. With the concrete parameters $m=1024,n=2048,\beta =1,q\approx 2^{32}$, their proof is of length 384.03KB. In this paper, we decrease the proof size of BLS scheme by two techniques. The first one takes effect on some special parameters. For these parameters, using the binary basic set instead of the ternary one results in a shorter proof. The second one deals with the repetition of the lower half in BLS scheme. Observing that what the lower half proves is of form $\mathbf{B}\vec{\mathbf{r}}=\vec{\mathbf{t}}$ with a short vector $\vec{\mathbf{r}}$ of polynomials, a variant of parallel repetition can be used to shorten the proof size. Combining these two techniques together, the proof size of the above-mentioned instance can be reduced to 220.01KB, only 57.3$\%$ of BLS scheme.

Zero-knowledge proof for any relation amongst committed values is crucial and widely applicable in the design of high level cryptographic schemes, especially in privacy-preserving protocols. Besides quantum resistance, efficiency is what we are most concerned about, including asymptotic efficiency and concrete efficiency. Jain et al. proposed a simple string commitment scheme based on the Learning Parity with Noise (LPN) problem (JKPT12), and then designed zero-knowledge proofs for valid opening, linear relation and multiplicative relation of committed values. As a result, they got an efficient zero-knowledge proof for any circuit C, with communication complexity $\mathcal{O}(t|C|\ell \log \ell )$, where t is a security parameter measuring soundness and ℓ is the secret length of the LPN problem. In this work, we improve the concrete communication complexity by combining some commitments in JKPT12 together. The proofs of linear relation and multiplicative relation are shortened by (6α + 4)ℓ and (42α+28)ℓ respectively, where ℓ is the size of LPN secret. As a result, the communication cost of the protocol proving arbitrary relation is reduced by a constant level.