Simpler SpkGen option

[andrewwhitehead]

I'm curious what's wrong with this simpler SPK alternative which doesn't specifically use h_0 and s, treating them as a hidden message: https://hackmd.io/8t8o56mvTL6p-VZyayLnTA?view

One benefit here is that blind signatures become a true extension of the core spec, probably using a named generator, and signatures which don't involve this generator at all can be supported.

[BasileiosKal]

That is truly very interesting. How will you prove zero knowledge though?? Following the same logic from the paper doesn't seem possible, especially for Abar (the issuer will have to publish Gbar ^ (-e) for every signature, but the simulator will not know which one to use since they don't know the signature. Note that in the papers version the issuer publishes Gbar ^ x which is the same for all signatures)

[andrewwhitehead]

At first glance, I think you just take a random p and D, set A' = Gbar_1*p and Abar = Gbar_2*p - D? I need to go through it a bit more though.

[BasileiosKal]

Wright, that makes sense. In general, although I do agree that we may need to look more into it, this is a strong +1 from me. It simplifies spkGen so much that I think it is worth moving away from the papers. We will need to describe the simulator/ extractor in the spec though. IMO it's worth it.

Also, I think C2 in the prover should be

C2 = D*r3~ - sum_over_R(H_i * m~_i)

And then in the verifier it should be

C2 = (-P1 - sum_over_D(H_i * m_i)) * c + D * r3^ - sum_over_R(H_i * m^_i)

(we may want to invert all the + and - for efficiency. i,e., leave the equations the same and only change D*r3~ to D*(-r3~) in the prover and D*r3^ to D*(-r3^) to the verifier. I think that can also work)

[andrewwhitehead]

Thanks, yes I just negated r3 in C2 consistent with the current proof.

[mikelodder7]

@andrewwhitehead prove that this is secure. If you're going to deviate from the original paper spec then please provide a proof of security.

[andrewwhitehead]

It's actually trivial to convert from this proof output to the current proof output and still have it verify, which tells me it must be secure from the verifier's perspective. Is there more to the original proof than the Lemma 2 paragraph?

In any case, for a proof from this method (A', Abar, D, e^, r2^, m^_0, {m^_i}, c) one can just set Abar2 = Abar + D, r3^ = - r2^, s^ = m^_0 and output (A', Abar2, D, e^, r2^=0, r3^, s^, {m^_i}, c). A prover could do this now and save a few cycles (the r3^ negation is only because it's negated earlier here).

[BasileiosKal]

I do also agree with @mikelodder7 that we should supply a proof of security on the spec, i.e., describe an extractor and a simulator, rather than mapping to the original proof value (although that is good for having confidence in the security of the new method). Those do seem to be more or less constructed by @andrewwhitehead though and from my testings everything seems to work. Still more reviews are needed (and will likely come from the cfrg).

[andrewwhitehead]

Yes I agree it needs a formal proof, but I'm still curious why the original proof goes to the trouble it does with H_0, as it seems like an intentional choice.

[BasileiosKal]

It is curious. Τhe only thing that comes to mind is that they wanted to just use the proof of knowledge they had on Camenisch, Drijvers and Hajny, 2016 for weak Boneh-Boyen signatures, which they do reference as "inspiration" for the bbs+ proof. In that proof (for weak Boneh-Boyen signatures), if we map sigma to A, m to e and g1 to B we will get essentially the "standard" bbs+ proof I think.

[andrewwhitehead]

I've updated the document now to add an attempt at the proof.

[andrewwhitehead]

I think there's two ways this could be integrated in the current spec(s).

• Simply update SpkGen and SpkVerify to follow this method, but explicitly handling s as an unrevealed message. This would mean that the s generator would need to be defined in the core spec, whether it is chosen to be global or issuer-specific. Commitments, commitment proofs, blinded signature creation, and unblinding would still be defined in the separate specification.

• Sign, Verify, SpkGen, and SpkVerify can be updated to remove any mention of s. This would change the representation of the basic signature to have just A and e components. Since the blind signing extension spec already needs to define its own BlindSign method in order to include the commitment value, this does seem like a reasonable option to me. Note that blind signatures would still be compatible with the core methods, but s would be handled as an unrevealed message against a standard generator (defined in the extension spec).

[BasileiosKal]

I would go with option 1. IMO changing the signature would raise more questions and require more proofs (and unforgability proofs would be much harder constructed and described). This also facilitates the fact that s should be treated differently at least in spkGen i.e., as a secret message that is never revealed. That also requires s to be uniform random (not much use if the verifier is able to guess it) so it is easier to define it that way in sign.

The reason i think we should keep using s in spkGen is that if we don't then if A becomes known it can be used to reveal all the messages from the proof since it holds that e(A, D) = e(B, A'). The adversary could just keep trying hidden messages -which most likely will not be that many- and check the equality until they find B. Granted this "attack" is highly unlikely (maybe if the issuer's records get compromised, and only A is revealed?), but that will not even be possible if B contains a uniformly random element.

[andrewwhitehead]

It seems likely that if A becomes known then s would also be known, no?

In any case I did find this in section 5.2 of CL16:

Our protocol is quite similar to the most recent qSDH-based DAA schemes [Che09,BL10,CU15]. However, a few key changes were needed to achieve provable security and address the problems mentioned in Sect. 2. First, we use a BBS+ signature for the membership credential, instead of the simplified credential where the s-value is ommited as used in the recent schemes [Che09,BL10,CU15]. This credential is proven to be unforgeable, where the simplified version is not.

[BasileiosKal]

It seems likely that if A becomes known then s would also be known, no?

Yea which kinda raises an issue now that i think about it. If the signature is revealed at any point any subsequent proof presentations will be insecure (not zero knowledge).

Maybe a some slight modification of the original proposal is needed?? Just throwing an idea, maybe defining first D = B * r2 and then A' = A * (r1*r2) and Abar = A'*(-e) + D * (r1) = A'*x?? I have not test the modification at all formally for security, but from a very quick look it seems it may hold and i think it may also solve the above issue.

[BasileiosKal]

So here's the proposed modification and the security analysis; https://hackmd.io/@Vasileios/H190hWAg5

Essentially it's the same method as the original proposal from @andrewwhitehead but using an additional random number when blinding A in a way that doesn't raise complexity too much. This changes a little the specifics of the proof and makes spkGen to have 2 additional steps but it avoids the above problem, i.e., it no longer holds that e(A, D) = e(B, A'). Notice also that the simulator is essentially the same as the one in CDL16.

[andrewwhitehead]

Looks good to me, and the intent of the original seems clearer now. I slightly prefer setting r3 = -1/r2 so that the verifier doesn't need to negate anything, but if message responses need to be in the form m^i = m~i - c*m_i then that might change anyway.

[BasileiosKal]

Looks good to me, and the intent of the original seems clearer now. I slightly prefer setting r3 = -1/r2 so that the verifier doesn't need to negate anything, but if message responses need to be in the form m^i = m~i - c*m_i then that might change anyway.

Thanks! That's a good point. I negated the 1/r2 and left the messages as m^i = m~i + c*m_i. This seems to be the most efficient way.

I guess the next step is that we should decide if it is worth to update the spec and move away from the papers. As it is now, it seems that the spkGen will be more efficient and with 3-4 less steps + less point multiplications with scalars. So I don't see why to not update it since there is a more efficient version with a proof of security. Granted the security proof needs more reviews but those will likely come from the cfrg.

[mikelodder7]

I disagree that the reviews will come from the cfrg. If we’re that confident in the changes let’s write up a paper and submit it to be peer reviewed.

[BasileiosKal]

We can If @andrewwhitehead is interested. I was thinking maybe working on a paper that will give an overview of bbs+ as it forms in the spec with a little more detailed security analyses compared to the original paper (+binding +blinding maybe??). Maybe we can merge the 2. First though, I don't think that having something like that been reviewed by the academic community is necessary to move with the update. Secondly, simplifying the spkGen algorithm it may not be enough novelty to have a paper submitted to a good conference (not to mention a journal).

In the end the question kinda remains, publishing a paper will take at the very least a couple of months. In the mean time should we update the spec?? (IMO yes but i do also understand the counter point).

[andrewwhitehead]

I'm happy to help out where I can, but probably can't commit to following through with a paper or conference presentation right now.

Just to summarize the suggested update, ignoring sign changes (s, s~, s^ should be named explicitly as well)...

• A' is set to Ar1*r2 instead of Ar1
• D is set to Br2 instead of Br1 - H0r2
• Abar is set to A'(-e) + Br1*r2 instead of A'(-e) + Br1, still equal to A'x
• C1 shows that Abar = A'(-e) + Dr1 instead of Abar = A'(-e) + D + H0r2
• C2 remains essentially the same
• s^ uses the same formula as unrevealed messages, s~ + cs instead of s~ + c(s - r2 * r3) used to cancel out the extra H0r2 factor in D

Because we are not looking to support the revocation mechanism in the paper, including the SPK generation performed in cooperation by the host and the TPM (Sign Proceed), it makes sense that the SPK can be simplified a little.

[BasileiosKal]

Yes. We may also be able to adjust the Sign Proceed operation to work with the simplified version. I may have to look more into it but In the protocol I think s isn't communicated between the host and the TPM meaning that there is no reason to "randomize" it beforehand using s'. Treating it as any other hidden message may work.

[tplooker]

Interestingly a similar optimization has been documented in a new academic publication (cannot link yet as it isn't public) that formally proves the security of this construction, we will pause progressing this issue until that paper has been further reviewed.

[BasileiosKal]

Discussed on WG call on 20th of Mar. Closing for now and will revisit when reviewing the latest academic works!