taler
[Top][All Lists]

## Re: [Taler] question about "how to issue": quantum computer attacks

 From: Jeff Burdges Subject: Re: [Taler] question about "how to issue": quantum computer attacks Date: Mon, 24 Oct 2022 00:11:08 +0200

```Oops I used elliptic curve additive notation there, as BLS looks
similar, but this becomes confusing since RSA really is multiplicative,
except RSA uses a multiplicative blinding anyways!  lol

We assume the attackers controls the bank, so they already know the
banks's secret key sk anyways.

All tokens have different x = FDH(token_pk) so if we use RSA like Taler
then an attacker learns b_i^pk x_i = b_i x_i^sk on withdrawal and
x_{pi(i)} on deposit, for some unknown permutation pi.

A non-quantum attacker can compute b_i x_i^sk / x_{pi(j)}^sk for all i,j
which then equals b_i when i=pi(j), and is pretty uselessly random
otherwise. An attacker wants to learn some of pi by finding the cases
where i=pi(j).

As the attacker knows sk, we need b_i to be uniformly random mod N in
RSA, so that these b_i x_i^sk / x_{pi(j)}^sk reveal nothing, but even a
small bias harms the anonymity!  This means you must compute b_i using
rejection sampling or some other uniform sampling scheme.

There is no gain for a quantum computer though because if b_i do not
stick out then they learn nothing about pi.

In BLS blind signatures, we do not require blinding factors to be
sampled uniformly mod the group order, except an adversary with a
quantum computer can compute these x_i^{b_i) / x_j.  In other words, a
qunatum attacker against of BLS blind signatures has exactly the same
deanonymization powers as a classical attacker against RSA.  And Schnorr
blind signatures should be similar.

> So what an attacker (who does not know b) with a quantum computer (qc)
> could try
> is to calculate sk⁽⁻¹⁾ ("morally") which gives bx.  But for all
> messages x'
> there is a b' ∈ B from the set B of blinding factors (like b) such
> that b'x' = bx.
> That means from the attackers perspective x could have been any
> message. He just
> needs to choose an appropriate b' ∈ B to get bx.
>

```