Subject: [CFRG] RSA blind signatures

From: "Christopher Wood" <[email-masked]>
Date: Tue, 23 Feb 2021 09:37:07 -0800

There are a growing number of use cases where we need something like VOPRFs but with public verifiability [1,2]. Given the results in 2020/945 [3], it seems prudent to try and fill the gap with something we know is reasonably safe. To that end, here's a draft describing RSA-based blind signatures:

   https://chris-wood.github.io/draft-wood-cfrg-blind-signatures/draft-wood-cfrg-rsa-blind-signatures.html

(I missed the deadline yesterday, so apologies for not having an actual datatracker draft to point at.)

Obviously, something better than RSA (in terms of bandwidth and overall messages) would be great. But it's not clear what that is right now.

Time permitting, I'd like to request some time on the agenda to present this to the group at IETF 110.

Thanks,
Chris

[1] https://github.com/ietf-wg-privacypass/base-drafts/issues/40
[2] https://github.com/privacycg/private-click-measurement/issues/27
[3] https://eprint.iacr.org/2020/945.pdf

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 24 Feb 2021 09:03:32 +0100

Hello Chris,

It’s critically important the blinding factor r be a uniformly random integer mod n, which I think deserves more emphasis than you give.  There is an easy deanonymization attack if r were say generated a random integer mod 2^{floor(log2 n)}.  You hould emphasize that random_integer should be instantiated with a CSPRNG and rejection sampling, maybe even specify the rejection sampling algorithm starting with shake or chacha.  

If I recall, RSA-PSS depends upon signer randomness for its security arguments.  As such, one should ideally not base an RSA blind signature off PSS but instead specify a full domain hash (FDH).  

At this point, one could specify the blinding factor be produced by applying the FDH to system randomness.  This is what I did for Taler’s blind RSA signatures: https://taler.net/en/

Initially I wanted to point you to the RSA-FDH-VRF in https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/ except..  Actually the RSA-FDH-VRF draft does not properly specify the FDH either, but only points to https://tools.ietf.org/html/rfc8017 which does not specify the FDH.

An FDH is a pretty easy notion but people get this wrong.  Also, there might be interoperability advantages in specifying it more fully. 

Best,
Jeff

p.s.  I think one should not deploy RSA-FDH-VRF but instead work through all the tricks to make Rabin-Williams deterministic.  It’s not too hard but not as easy as RSA-FDH-VRF.  I’ve no looked at wether Rabin-Williams could be adopted to blind signatures, but I think some issues arose beyond what one alters for a Rabin-Williams VRF. 

> On 23 Feb 2021, at 18:37, Christopher Wood <[email-masked]> wrote:
> 
> _______________________________________________
> CFRG mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg

---

From: Michele Orrù <[email-masked]>
Date: Wed, 24 Feb 2021 09:17:24 +0100

For those cases needing Privacy Pass but with public verifiability, I would
kindly ask CFRG to also take a second to evaluate blind BLS signatures.

It is true that verification would be much slower than RSA;  however, they
have efficient batching algorithms (for which the amortized cost is ~2
scalar multiplications) and the issuance protocol is literally the same as
a Privacy Pass.
Additionally, they have the same number of rounds and same number of
messages.

This would avoid perhaps creating an entire new standard and having just a
new section on the privacy pass draft?
Hoping to help,
--
Michele.

---

From: Jeff Burdges <[email-masked]>
Date: Wed, 24 Feb 2021 09:49:20 +0100

As a rule, there are relatively few keys in an RSA blind signature deployment, so you could batch verify all messages with the same public key.  I suppose someone who knows the secret p and q might construct FDH with interesting summations, ala https://eprint.iacr.org/2020/945  I’d expect some common RSA assumption forbids this for anyone who does not know the secret key though, so RSA batch verification should turn out secure.

I think RSA batch verification does not improve performance for one spend operation *if* your public keys represent denominations in powers of two, but batch verification does help RSA if you’ve less dense denominations.  In this setting, an RSA blind signature would likely be checked twice, first at a merchant, and second at the exchange/bank/mint.  I suppose exchanges could quickly return “no double spend” to merchants, and then aggregate RSA verification across thousands of spends.  

You'll never benefit from common message aggregation for BLS blind signatures, so every denomination requires another 1500 microsecond Miller loop, which  sounds slower than RSA, no?

Jeff

> On 24 Feb 2021, at 09:17, Michele Orrù <[email-masked]> wrote:
> 
> For those cases needing Privacy Pass but with public verifiability, I would kindly ask CFRG to also take a second to evaluate blind BLS signatures.
> 
> It is true that verification would be much slower than RSA;  however, they have efficient batching algorithms (for which the amortized cost is ~2 scalar multiplications) and the issuance protocol is literally the same as a Privacy Pass.
> Additionally, they have the same number of rounds and same number of messages.  
> 
> This would avoid perhaps creating an entire new standard and having just a new section on the privacy pass draft?
> Hoping to help,
> --
> Michele.

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 24 Feb 2021 15:25:18 -0800

Hi Jeff,

Thanks for the feedback! Please see inline below.

On Wed, Feb 24, 2021, at 12:03 AM, Jeff Burdges wrote:
> 
> It’s critically important the blinding factor r be a uniformly random 
> integer mod n, which I think deserves more emphasis than you give.  
> There is an easy deanonymization attack if r were say generated a 
> random integer mod 2^{floor(log2 n)}.  You hould emphasize that 
> random_integer should be instantiated with a CSPRNG and rejection 
> sampling, maybe even specify the rejection sampling algorithm starting 
> with shake or chacha.  

Indeed -- we can definitely sharpen the language here to emphasize the importance of this point:

   https://github.com/chris-wood/draft-wood-cfrg-blind-signatures/issues/55

> If I recall, RSA-PSS depends upon signer randomness for its security 
> arguments.  As such, one should ideally not base an RSA blind signature 
> off PSS but instead specify a full domain hash (FDH).  

Is this a useful distinction? Blind RSA in general requires randomness for it to be useful (as you carefully point out above). 

In any case, the rationale for PSS was two-fold:

1) It's widely supported in libraries. (To my knowledge FDH is not widely supported... yet.)
2) One can basically replicate FDH with a zero-length salt, even though some APIs make it difficult to do so.

> At this point, one could specify the blinding factor be produced by 
> applying the FDH to system randomness.  This is what I did for Taler’s 
> blind RSA signatures: https://taler.net/en/
> 
> Initially I wanted to point you to the RSA-FDH-VRF in 
> https://datatracker.ietf.org/doc/draft-irtf-cfrg-vrf/ except..  
> Actually the RSA-FDH-VRF draft does not properly specify the FDH 
> either, but only points to https://tools.ietf.org/html/rfc8017 which 
> does not specify the FDH.
> 
> An FDH is a pretty easy notion but people get this wrong.  Also, there 
> might be interoperability advantages in specifying it more fully. 

Quite true! Perhaps a more clean specification of FDH would address (1) above?

Best,
Chris

> p.s.  I think one should not deploy RSA-FDH-VRF but instead work 
> through all the tricks to make Rabin-Williams deterministic.  It’s not 
> too hard but not as easy as RSA-FDH-VRF.  I’ve no looked at wether 
> Rabin-Williams could be adopted to blind signatures, but I think some 
> issues arose beyond what one alters for a Rabin-Williams VRF. 
> 
> 
> 
> 
>

---

From: "Christopher Wood" <[email-masked]>
Date: Wed, 24 Feb 2021 15:26:42 -0800

On Wed, Feb 24, 2021, at 12:17 AM, Michele Orrù wrote:
> For those cases needing Privacy Pass but with public verifiability, I 
> would kindly ask CFRG to also take a second to evaluate blind BLS 
> signatures.

+1 -- it would be great to know if there's general interest in implementers for blind BLS.

Best,
Chris

> It is true that verification would be much slower than RSA;  however, 
> they have efficient batching algorithms (for which the amortized cost 
> is ~2 scalar multiplications) and the issuance protocol is literally 
> the same as a Privacy Pass.
> This would avoid perhaps creating an entire new standard and having 
> just a new section on the privacy pass draft?
> Hoping to help,
> --
> Michele.

---

From: John Mattsson <[email-masked]>
Date: Wed, 24 Feb 2021 23:36:29 +0000

+1 for CFRG looking into blind signatures of some kind.

---

From: Jeff Burdges <[email-masked]>
Date: Thu, 25 Feb 2021 07:44:54 +0100

> On 25 Feb 2021, at 00:25, Christopher Wood <[email-masked]> wrote:

That’s randomness by the token holder.  I’m taking about randomness held by the issuer.

Bellare and Rogaway suggested PSS over FDH because PSS provides a tighter security argument than FDH, due to the signer providing randomness, i.e. purely a provable security reason.
https://web.cs.ucdavis.edu/~rogaway/papers/exact.pdf

> 1) It's widely supported in libraries. (To my knowledge FDH is not widely supported... yet.)

We verify RSA blind signatures roughly three times in a typical token deployment, once by the user after token issuance as part of the signing algorithm, once by the merchant upon tokens being spent, and once by the exchange upon tokens finally being redeemed.  As the signer code must change, only the merchant code justifies a gymnastics for support of existing libraries.

> 2) One can basically replicate FDH with a zero-length salt, even though some APIs make it difficult to do so.

Is a zero length salt secure?  It’s likely "less" secure than an FDH’s rejection sampling, but do we know if a security proof exists or if it de facto becomes roughly PKCS#1 v1.5 like? 

We cannot abuse the salt to perform rejection sampling since presumably the three components in PSS’ output, maskedDB, H, and bc all avoid the high bit, which gets set like 1/3rd of the time.

Jeff

p.s.  An FDH consumes the input message using hash function with extensible output, like shake, blake2x, ad hoc hash plus stream cipher constructions, or strobe https://strobe.sourceforge.io and then produces first the low order log_2 n + 1 - k output bits L where k = 128 or 256, and then it produces the high k output bits H using rejection sampling, i.e. loop until (H || L) < n.  It’s probably fine if the whole output were rejection sampled all at once, slightly slower but the performance loss sounds minor given the arithmetic.

---

From: "Christopher Wood" <[email-masked]>
Date: Thu, 25 Feb 2021 04:32:14 -0800

> That’s randomness by the token holder.  I’m taking about randomness 

Perhaps I'm missing something, but my point was the following: Clients, who actually encode messages -- either via FDH or PSS -- require randomness to blind their message sent to the server. Servers (issuers), in contrast, deterministically sign the blinded message sent to them. (They hopefully also include some variant of blinding to mitigate obvious side channels, but that's an implementation detail.)
 
> Bellare and Rogaway suggested PSS over FDH because PSS provides a 
> tighter security argument than FDH, due to the signer providing 
> randomness, i.e. purely a provable security reason.

Indeed. This, along with availability, is primarily what led to PSS in this case. 

> We verify RSA blind signatures roughly three times in a typical token 
> deployment, once by the user after token issuance as part of the 
> signing algorithm, once by the merchant upon tokens being spent, and 
> once by the exchange upon tokens finally being redeemed.  As the signer 
> code must change, only the merchant code justifies a gymnastics for 
> support of existing libraries.
> 
> Is a zero length salt secure?  It’s likely "less" secure than an FDH’s 
> rejection sampling, but do we know if a security proof exists or if it 
> de facto becomes roughly PKCS#1 v1.5 like? 

I'm not an expert, and I'm certainly not advocating for it, but 2019/1268 [1] seems to suggest it's safe.

Best,
Chris

[1] https://eprint.iacr.org/2019/1268.pdf

> We cannot abuse the salt to perform rejection sampling since presumably 
> the three components in PSS’ output, maskedDB, H, and bc all avoid the 
> high bit, which gets set like 1/3rd of the time.
> 
> Jeff
> 
> p.s.  An FDH consumes the input message using hash function with 
> extensible output, like shake, blake2x, ad hoc hash plus stream cipher 
> constructions, or strobe https://strobe.sourceforge.io and then 
> produces first the low order log_2 n + 1 - k output bits L where k = 
> 128 or 256, and then it produces the high k output bits H using 
> rejection sampling, i.e. loop until (H || L) < n.  It’s probably fine 
> if the whole output were rejection sampled all at once, slightly slower 
> but the performance loss sounds minor given the arithmetic.  
> 
> 
> 
>

---

From: Jeff Burdges <[email-masked]>
Date: Thu, 25 Feb 2021 14:35:59 +0100

> On 25 Feb 2021, at 13:32, Christopher Wood <[email-masked]> wrote:

There is no randomness inside FDH but the salt in PSS is randomness, which the security arguments for PSS require comes from the signer, and cannot come from the singer in a blind signature.  

This does not say PSS becomes insecure when this randomness comes from the user, but one cannot cite existing arguments about PSS being secure.  Instead, one should acknowledge that PSS with user controlled salt acts like a hash with domain [0..2^(k-8)] with k maximal such that 2^k < n, and then find some arguments that this suffices.

> [1] https://eprint.iacr.org/2019/1268.pdf

Oh cool?  Where?  I missed anything about empty or fixed salts.  That’s what you want if you want to use PSS.

Jeff

---

From: Mihir Bellare <[email-masked]>
Date: Thu, 25 Feb 2021 08:38:10 -0800

On Wed, Feb 24, 2021 at 10:45 PM Jeff Burdges <[email-masked]> wrote:

> Bellare and Rogaway suggested PSS over FDH because PSS provides a tighter
> security argument than FDH, due to the signer providing randomness, i.e.
> purely a provable security reason.

The proofs for RSA-FDH and RSA-PSS as normal signatures are from the
one-wayness assumption on RSA. As you say, the reduction for RSA-PSS is
tight, and that for RSA-FDH is not. The proof for Blind-RSA-FDH is from the
One-More Discrete Log (OMDL) problem, and this would also be the case for
Blind-RSA-PSS. I have not done the latter proof in detail, so this is just
a guess, but I don't see a difference in tightness between the two. So from
the point of view of tightness of security arguments, my guess is that
Blind-RSA-FDH and Blind-RSA-PSS are about the same. I understand of course
that there may be many other factors and reasons to prefer one over the
other.

PSS, when used as a normal signature, can be de-randomized in the usual way
of deriving the randomness by hashing the secret signing key and the
message, but this does not seem to apply in the blind case.

Mihir

---

From: Jeff Burdges <[email-masked]>
Date: Thu, 25 Feb 2021 19:58:41 +0100

> On 25 Feb 2021, at 17:38, Mihir Bellare <[email-masked]> wrote:
> The proofs for RSA-FDH and RSA-PSS as normal signatures are from the one-wayness assumption on RSA. As you say, the reduction for RSA-PSS is tight, and that for RSA-FDH is not. The proof for Blind-RSA-FDH is from the One-More Discrete Log (OMDL) problem, and this would also be the case for Blind-RSA-PSS. I have not done the latter proof in detail, so this is just a guess, but I don't see a difference in tightness between the two. So from the point of view of tightness of security arguments, my guess is that Blind-RSA-FDH and Blind-RSA-PSS are about the same.

Cool, good enough.  :)

In this case, Chris' draft could just say PSS gets used only as a “large domain hash” or some similar phrasing, and maybe mention security arguments rest on OMDL as opposed to the usual PSS arguments.  I suppose the VRF draft could use PSS with an empty salt for the same reason this draft does.

> I understand of course that there may be many other factors and reasons to prefer one over the other.

I think both RSA VRFs and blind RSA require enough extra code to avoid footguns that folks could implement an FDH too, but if PSS suffices then reusing it avoids some mistakes.  

Jeff

p.s.  It’s also worth mentioning that blind Schnorr signatures now make sense using https://eprint.iacr.org/2019/877.pdf although the two round trips make them painful.