Proving multiplicative relations for different lattice commitments

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.