Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Protocol: KVAC based #17

Closed
nothingmuch opened this issue Apr 22, 2020 · 15 comments
Closed

Protocol: KVAC based #17

nothingmuch opened this issue Apr 22, 2020 · 15 comments

Comments

@nothingmuch
Copy link
Contributor

nothingmuch commented Apr 22, 2020 •
edited by nopara73

I had a brain fart and for some reason I put down algebraic MACs in #13 as relying on bilinear groups, and consequentially we did not look at them in much detail. This is not the case. Again I have @jonasnick to thank for prompting me to look again at Keyed-Verification Anonymous Credentials (KVACs).

The gist of KVAC is that it is designed for when the issuer is also the verifier, like in our use case.

A newer scheme: The Signal Private Group System and Anonymous
Credentials Supporting Efficient Verifiable Encryption allows attributes to be group elements: for our use case the attributes can be Pederesen Commitments to amounts.

Since this scheme allows unlinkable multi-show, this reintroduces the double spending problem. However, this should be easily solvable by introducing serial numbers which are revealed as part of credential showing.

Note that by only using Pedersen commitments as group attributes we don't require the blind issuance protocol of either KVAC scheme, which relies on ElGamal encryption of the requested attributes, which has the nice benefit of perfect hiding of the sub-amounts and serial numbers, so the coordinator can't retrospectively de-anonymize users even if there is a crypto break.

Input Registration

The user submits a request for N credentials, with either 1 or 2 group attributes (not clear which is simpler yet):

  • Two separate Pedersen commitments, one for the sub-amount and one for the serial number.
  • A single Pedersen multi commitment for a requested sub-amount and serial number.

Along with a range proof for each amount commitment, and a proof that the sum of all the amount commitments matches the input amount.

The coordinator verifies the proofs, and responds with N MACs on the requested attributes, along with a proof of knowledge of the secret key.

Output Registration

The user executes the Show protocol for the combination of credentials they want to use, which produces as output randomized commitments to the attributes and a proof of the MAC verification.

The user also proves that the serial number commitments can be opened to their corresponding serial numbers. These serial numbers are revealed for double spending protection, but the commitment opening should be done in zero knowledge to avoid revealing the randomness of the original commitment in the input registration phase or the randomization added in the Show protocol.

The user also proves that the sum of the amount attributes matches the output amount, analogously to input registration (but there is no need for range proofs at this phase).

The user submits these proofs, the randomized attributes, and the serial numbers.

Note that the serial numbers should not be "revealed attributes" as I previously stated, since those would be trivially linkable to input registration.

Note that since all proofs are created with sigma protocol, the 2n+1 proofs should be composable into a proof of their conjunction. I believe this also holds if using bulletproofs for the range proofs at input registration.

Self Issuance

The (sub-)proof of MAC validity could be modified so that a credential is considered valid if it has a valid MAC OR the amount it certifies is exactly 0.

Since users could then generate such credentials without ever contacting the server, this makes it possible to require valid credentials to be shown at input registration, which would allow users merge an arbitrary number of inputs together into a single credential without requiring the output registration phase to accept as many credentials as there are inputs.

As few as 1 spent & newly requested credentials per input/output registration operation are needed if output registrations also produce newly signed credentials for the remaining amount, but ideally a larger number on the order of log(participants) should be used to allow users to make parallel requests for improved privacy.
@nothingmuch nothingmuch mentioned this issue Apr 22, 2020
Closed
@nothingmuch

This comment has been minimized.

Sign in to view
@nopara73

This comment has been minimized.

Sign in to view
@nopara73

This comment has been minimized.

Sign in to view
@nopara73

This comment has been minimized.

Sign in to view
@nothingmuch

This comment has been minimized.

Sign in to view
@nothingmuch
Copy link
Contributor Author

nothingmuch commented Apr 27, 2020 •
edited

  • reduced interactions during issuance -> we care, but how can the interactions be reduced while ACL already has the theoretically minimal interactions in the first place?

actually it doesn't, some of the proofs required for the 3 stages are interactive

  • this requires fewer group operations -> what does this mean? does this mean it reduces computational load, in which case we don't really care, or it means it makes the overall scheme simpler, in which case we care?

both senses, but we should mainly care about the simplicity of the protocol, especially in explaining how unlinkability is achieved (i think ACL's main downside is that this aspect is rather complex)

@seresistvanandras
Copy link
Contributor

  • reduced interactions during issuance -> we care, but how can the interactions be reduced while ACL already has the theoretically minimal interactions in the first place?

actually it doesn't, some of the proofs required for the 3 stages are interactive

Which proofs are interactive in the ACL-based scheme? I think all of them can be made non-interactive via the Fiat-Shamir heuristic! What am I missing?

@nothingmuch
Copy link
Contributor Author

nothingmuch commented Apr 27, 2020 •
edited

Which proofs are interactive in the ACL-based scheme? I think all of them can be made non-interactive via the Fiat-Shamir heuristic! What am I missing?

hmm, you're right about the first one.

Since the Fiat Shamir heuristic is already used in the signature scheme, I thought there was some reason why the proof in the registration phase must be interactive, but reviewing it now I can't find one:

During registration the User and the Signer carry out a standard interactive zero-knowledge proof of knowledge protocol where the User creates a proof π1 to convince the Signer that he knows an opening of the commitment C.

but the sigma protocol for producing the OR proof is still interactive, so even if combining the Preparation and Validation obtaining the signature requires 2 round trips (coordinator first gives rnd, a, a', then user responds with e, and then the coordinator responds with c, r, c', r').

I don't think this is a serious issue since this is per client

@nothingmuch
Copy link
Contributor Author

Note that there is a third KVAC scheme I was not aware of, which natively supports pseudonymous showing, which removes the requirement for a serial number, but it also supports anonymity revocation using a trusted party, which is undesirable for this use case even if the trusted party's keys are set up with hash-to-curve.

This scheme also supports non interactive ZK proofs without the Fiat-Shamir heuristic, but I don't think this changes anything for our use case since Bitcoin already relies on that in its digital signature scheme, and lacks security proofs for other aspects of its security even in the random oracle model.

@nothingmuch
Copy link
Contributor Author

i updated the top post to remove the more complicated approach, which has no real advantages (even the ones i speculated about seem invalid).

@nopara73

This comment has been minimized.

Sign in to view
@nothingmuch

This comment has been minimized.

Sign in to view
@seresistvanandras
Copy link
Contributor

A bit more formal presentation of the proposed coin splitting and merging is presented below in the context of the KVAC-scheme.

Each registered UTXO has two attributes: a value and a serial number. They are both committed in Pedersen commitments, i.e. $M_v=\mathit{Com}(v,r_v),M_s=\mathit{Com}(s,r_s)$.

  1. Input UTXO splitting
    Since input UTXO values are still committed in Pedersen commitments, hence input UTXO splitting works just like in all the previous schemes.

  2. UTXO merging
    Suppose user wants to merge two UTXOs at output registration with secret values $v,v'$ to a UTXO with public value $v_{\mathit{out}}$. User needs to convince the coordinator that $v_{\mathit{out}}=v+v'$.

User has two Pedersen multi-commitments to the input UTXO values she would like to merge: $C_{y_{v}},C^{'}{y{v}}$. Each commitment has the following structure: $C_{y_{v}}=G^{z}{y_v}M_v=G^{z}{y_{v}}h^{v}g^{r}$. Therefore multiplying the two commitments we'll have $C_{y_{v}}\cdot C^{'}{y{v}}=G^{z}{y_v}M{v}\cdot G^{z'}{y_v}M{v^'}=G^{z+z'}{y{v}}h^{v+v'}g^{r+r'}$. The proof contains of $\pi=(z+z',r+r')$, i.e. coordinator learns $h^{v+v'}$ and checks whether $h^{v+v'}=h^{v_{\mathit{out}}}$.

  • Soundness is achieved as user does not know the discrete logarithms between generator points used in the commitment scheme.

  • Zero-knowledge is ensured as the revealed sums do not leak anything about individual $r,r',z,z'\mod q$.

@nothingmuch
Copy link
Contributor Author

nothingmuch commented Apr 28, 2020 •
edited

Hmm, this is exactly equivalent to what we discussed in the call, where we end up with a commitment to 0 and open that as $(z+z'-z'',r+r'-r'')$, right?

Is it worth rewriting these for n credentials instead of 2? there's no loss of generality in assuming n=2, as we did on the board, but I think it would be clearer, and we did free up numerical subscripts by indexing the different attributes as v and s.

Secondly, for each credential M_s commitment is, the user submits $(s, \frac{C_{y_s}}{h^s}) = (s, G_{y_s}^z g^{r_s})$, which the coordinator can then verify without linking to a specific M_s. (edit: also need to prove in zero knowledge DLOGs of these products WRT g and G_{y_s})

Note that after the coordinator has learned s, the original M_s commitments are no longer prefectly hiding, since there is exactly one r_s \in \mathbb{Z}_q where h^s g^{r_s} = M_s.

This is admittedly a contrivance, but I think it's still desirable to preserve unconditional hiding, so that we can be sure that the coordinator can't ever de-anonymize users retrospectively even in case of a crypto break. If I'm not mistaken, I think all we would need is to add another randomness term to the serial number commitment with a 3rd generator, so that $M_s = h^s g_1^{r_{s1}} g_2^{r_{s2}}$.

nothingmuch added a commit that referenced this issue May 3, 2020
@nothingmuch @seresistvanandras
First version attempt at converting #17 to latex
806be97 
This commit includes some of the formulae from the github comments.

Note that there are a few mistakes, and there is no coherent structure
to the document, this just gathers the information that was spread out
in the github issue into one file.

Co-authored-by: Seres István András <seresistvanandras@gmail.com>
@nothingmuch nothingmuch mentioned this issue May 3, 2020
Merged
@nothingmuch nothingmuch mentioned this issue May 16, 2020
Closed
@nopara73
Copy link
Contributor

#30

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
3 participants
@nothingmuch @nopara73 @seresistvanandras