The currently most efficient, in terms of size and speed, quantum-safe basic primitives are based on the hardness of lattice problems with algebraic structure. Lattice-based constructions are therefore natural candidates for more advanced cryptographic tools like zero-knowledge proofs. Over the last few years, there has indeed been rapid progress in the field of lattice-based zero knowledge. There now exist fairly practical protocols for proving knowledge of pre-images of lattice-based 1-way functions, arithmetic sums and products of committed values, as well as various primitives such as ring signatures and group signatures. In virtually all of these cases, the lattice-based solutions result in the most efficient (potentially) quantum-safe option.

As far as a relatively complete quantum-safe transaction system, the recent work of Esgin et al, also based on the hardness of lattice problems, appears to be the most efficient solution. Their work adapts the RingCT protocol , which serves as the foundation of the digital currency Monero, and provides formal definitions upon which they construct their MatRiCT protocol. While certainly not as efficient as discrete logarithm based schemes, this work showed that a lattice-based confidential transaction system is something that may eventually be a very reasonable solution.

• Muhammed F. Esgin, Raymond K. Zhao, Ron Steinfeld, Joseph K. Liu, and Dongxi Liu. Matrict- Efficient, scalable and post-quantum blockchain confidential transactions protocol. In CCS, pages 567-584 . ACM, 2019 .

Part1Our Results

At the core of many privacy-based protocols is a set membership proof in which the prover shows, in zero-knowledge, that a commitment is to a value from a public set. This concept is very closely related to "one-out-of-many" proofs  and ring signatures. The main result of this work is a new set membership proof which is logarithmic in the size of the set and leads to a ring signature scheme with outputs noticeably smaller than the currently shortest schemes. We point out that "one-out-of many" proofs , in which the prover shows that one of the commitments in a set is a commitment to 0, are actually equivalent to the ring signatures that we construct. This is because lattice-based public keys can be thought of as commitments to 0. We then show how to use our ring signature scheme / "one-out-of-many" proof, together with a few other optimizations of prior work, to create a more efficient confidential transaction system based upon the MatRiCT definitions.

We now give a brief overview of where the efficiency advantage comes from. The shorter proofs in our scheme are partly a result of the fact that the modulus in our underlying polynomial ring stays the same for all practical set sizes. On the other hand, if the size of the set is , then the exponent of the modulus in the ring used in [EZS+19] increases linearly in The reason for this difference is that [EZS+19] use "Ajtai-type" commitments which compress the input, but only allow for commitments of "short" messages. In our construction, however, we use BDLOP commitments which allow commitments to arbitrary-size elements, at the expense of a slightly larger commitment size. But because the number of commitments we need is logarithmic in the size of the set, this does not pose a problem with the commitment size becoming too big.

• Carsten Baum, Ivan Damgård, Vadim Lyubashevsky, Sabine Oechsner, and Chris Peikert. More efficient commitments from structured lattice assumptions. In SCN, pages 368-385,2018.

An additional advantage of BDLOP commitments that we extensively use is that if one plans ahead by choosing a long-enough randomness vector in the beginning of the protocol, then one can adjoin a new commitment at any time and the size of the commitment only increases by the size of the committed message. In particular, the increase in size does not depend on the security parameter, which is what one would need if creating a new commitment. We use this property when combining our new techniques along with the framework for proving various relations committed to in BDLOP commitments. Thus our constructions essentially have just one BDLOP commitment for the entire protocol. We further reduce the transaction size by employing an amortization technique so that the proof contains just two elements whose size depends on the security parameter.

1The Polynomial Ring and BDLOP Commitments

Throughout this paper, we will be working over the polynomial ring where is set such that and are irreducible modulo . We will be exclusively using BDLOP commitments , where a commitment to a polynomial vector is of the form

where are uniform  public random matrices and is a random low-norm vector which serves as the commitment randomness. To open the commitment without revealing it, one would ideally want to give a zero-knowledge proof of a low-norm satisfying . Unfortunately, there is no particularly efficient zero-knowledge proof for this statement, and so a relaxed opening is defined which consists of a vector and a polynomial satisfying such that and are small (but is not necessarily small itself). The committed message is then implicitly

An efficient zero-knowledge proof for the above opening was given in [EZS+19] . That work also showed how to prove linear (over ) relations of without increasing the proof size. For this, it's in fact enough to just be able to prove that the commitment is to . The reason is that a commitment of can be easily converted to a commitment of by adding to . Similarly, for any matrix over , one can convert a commitment of to one of by multiplying the bottom part by to obtain . Thus proving that the message in satisfies , involves proving that the commitment with public key is a commitment to

Later works  showed how to prove more complicated relations between the committed messages in BDLOP commitments. These include proving multiplicative relations among the polynomials comprising and proving linear relations over (rather than ) of the integer coefficients comprising . An important feature of these aforementioned proofs is that the proof size does not grow with the number of relations that one needs to prove about one commitment. So the cost, in terms of proof size, of proving multiple relations about one commitment is the cost of proving the most expensive one.

2The New Set Membership Proof

In this work we extend the toolbox of what can be proved about in BDLOP commitments by showing how to do set membership proofs. Given a collection of polynomial vectors , and a commitment to one on them, we would like to prove that the committed is indeed one of the

More specifically, the public information consists of where , and a commitment The prover gives a zero knowledge proof that a commitment opens to where

Notice that by definition of the , their tensor product will be a vector of length consisting of all zeros and one 1 . If each vector will be committed as a polynomial in the BDLOP commitment , then it  can already be proved using the aforementioned techniques . Our main result in this work is an efficient proof  whose size is linear in , and thus logarithmic in the number of elements in . We also prove a more generic -dimensional version of this problem. In this version, there are public lists

and is a sum of elements, one taken from each set. The prover gives a zero knowledge proof that the commitment opens to

where

This proof is of size , so there is no amortization happening. But being able to prove the above will allow us to amortize away many of the other parts of the anonymous transaction protocol.

3From Set Membership to Ring Signatures

A ring signature scheme allows a signer to sign in a way that hides the public key that he is using. More specifically, the signer creates a set comprised of his public key and other public keys for which he may not know the secret key. He then creates a signature with the property that the verifier can check that the message was signed by an entity who knows the secret key to one of the public keys in the list. We now sketch how one can convert a "Schnorr-like" lattice-based signature scheme into a ring signature by using a set membership proof.

The basic signature scheme underlying the ring signature follows the usual "Fiat-Shamir with Aborts" approach for constructing lattice-based digital signatures . In particular, the secret key is a low-norm vector , while the public key consists of a random matrix and a vector . The signature is then a "relaxed" zero-knowledge proof of knowledge (made noninteractive using the Fiat-Shamir transform) of a vector and a polynomial , both with small norms, satisfying .

The ring signature public information consists of the matrix and vectors . A signer who knows an satisfying will want to give a zero-knowledge proof knowledge of , and satisfying . An interactive version of this proof is presented in Figure 1 and it is then made non-interactive using the Fiat-Shamir transform and inserting the message to be signed into the random oracle which is used to produce the challenge.

4Application to Confidential Transactions

We now show how to construct a confidential transaction system. The setup is the following: at any given moment, the state (which is managed by the blockchain, and is outside the scope of this work) consists of a set of accounts act , each of which contains a public key and a coin. The state also contains a set of serial numbers which implicitly correspond to the accounts that were already spent (to prevent double-spending). The secret account key associated to each account is ask , which consists of the secret key corresponding to and the commitment key , which is the randomness used to create the BDLOP commitment cn to the amount amt in the account.  We will assume that amt takes values between 0 and Since we are working over rings with 32 NTT slots, we will represent the values in base The basic operation has the sender choosing input accounts for which he knows the secret keys associated to , and then creating new output accounts with given public keys for which he does not need to know the associated secret keys. There are three correctness constraints. The first is that the spender knows the associated secret keys for the input accounts. The second is that the sum of the values of the input coins (i.e. the sum of the amt) equals to the sum of the values of the output coins. And the third is that none of the input accounts were used as inputs in any previous transaction.

In addition to correctness, there are also secrecy and anonymity requirements. The secrecy requirement states that nothing about the amounts amt is known except that the sum of the input and output coins is equal. The spender's anonymity is defined by hiding the spenders account among other accounts. In particular, rather than stating which accounts the spender is using, he will instead choose sets of accounts each, and then choose one account from each set in a way that hides which of the accounts has been chosen. How the spender chooses the other accounts is a policy issue that is outside the scope of this work.

The public information for the system consists of a polynomial matrix which forms the "top part" of the BDLOP commitment. The polynomial vectors (which will be used to commit to amt) and (which will be used to "commit" to zero, with the commitment being the serial number) form the "bottom part" of the commitments. In particular, sk is a low-norm vector where

And ck is another low-norm vector such that