Re: [CFRG] RSA blind signatures

Jeff Burdges <> Wed, 24 February 2021 08:49 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id E93C13A0D69 for <>; Wed, 24 Feb 2021 00:49:53 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.897
X-Spam-Status: No, score=-1.897 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id 3ENt564t3O85 for <>; Wed, 24 Feb 2021 00:49:51 -0800 (PST)
Received: from ( []) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 957763A11C7 for <>; Wed, 24 Feb 2021 00:49:29 -0800 (PST)
Received: from [] ( [IPv6:2001:4ca0:2001:42:225:90ff:fe6b:d60]) by (Postfix) with ESMTP id E04601C00D2; Wed, 24 Feb 2021 09:50:37 +0100 (CET)
Content-Type: text/plain; charset="utf-8"
Mime-Version: 1.0 (Mac OS X Mail 13.4 \(3608.\))
From: Jeff Burdges <>
In-Reply-To: <>
Date: Wed, 24 Feb 2021 09:49:20 +0100
Cc: Taler <>
Content-Transfer-Encoding: quoted-printable
Message-Id: <>
References: <> <>
To: Michele Orrù <>, IRTF CFRG <>
X-Mailer: Apple Mail (2.3608.
Archived-At: <>
Subject: Re: [CFRG] RSA blind signatures
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 24 Feb 2021 08:49:54 -0000

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  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?


> On 24 Feb 2021, at 09:17, 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.
> 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.
> _______________________________________________
> CFRG mailing list