Steven Galbraith once told me that he expects mathematicians to teach RSA long after the world has migrated to post-quantum algorithms; because it is so easy to explain. Arguably, LWE is easier to explain than RSA but the Approximate Greatest Common Divisors problem (AGCD) is even easier than that and requires only scalars. Thus, it is a nice post-quantum alternative for an undergraduate mathematics module. Someone should perhaps write an undergraduate mathematics textbook introducing cryptography using Approximate Common Divisors.
RSA
To set a baseline, let’s start with recalling naive RSA.
- KeyGen. The public key is
and the private key is
, with
where
and
prime,
coprime to
and
such that
.
- Enc.
- Dec.
This naive version of RSA only achieves a basic form of security — OW-CPA — even against classical adversaries: it is hard to recover random messages when eavesdropping. Kids, always implement RSA-OAEP. It is easy to see that an adversary that can factor large integers can break RSA: knowing and
permits to compute
which permits to compute
. (It should be noted, though, that this does not mean an adversary has to factor to solve RSA.) The best known classical algorithm for factoring is the Number Field Sieve (NFS). It has a super-polynomial but sub-exponential complexity of
operations. On the other hand, and this is the reason why we care about post-quantum cryptography, an adversary with access to a quantum computer with
gates can factor using Shor’s algorithm.
Greatest Common Divisors
Now, to pivot to GCDs, what if two or more users generate moduli and
, i.e. moduli with shared factors? We assume that factoring each of
or
is hard, but computing
, i.e. the largest integer dividing both
and
, reveals
(or a small multiple). We can compute greatest common divisors using the Euclidean algorithm:
def gcd(a, b): if b == 0: return a else: return gcd(b, a % b)
This algorithm runs in time but the best known algorithm runs in time
. For comparison, integer multiplication costs
using the Harvey and van der Hoeven algorithm. So computing GCDs is pretty fast.
Approximate Greatest Common Divisors
Thus, computing GCDs can break RSA with poor randomness. On the other hand, adding a bit of noise to the problem – going from Greatest Common Divisors to Approximate Greatest Common Divisors – makes the problem (for all we know) hard, even on a quantum computer.
The Approximate GCD problem is the problem of distinguishing
from uniform with
(
,
and
are secret). For the problem to be hard, we require
,
and
.
We can build public-key encryption from the AGCD problem as follows:
- KeyGen. The public key is a bunch of AGCD samples where the errors are multiples of 2, i.e.
and the private key is
. It can be shown that all errors being multiples of two does not weaken security.
- Enc. For
output
with
, i.e. do a random zero-one combination of the samples in the public key and add
. This effectively samples a new AGCD sample and adds
.
- Dec.
, i.e. take the ciphertext mod
which produces
and the take that mod 2 to recover
.
If the AGCD problem is hard then this encryption scheme is IND-CPA secure. That’s better than merely OW-CPA but to achieve security against active attacks we would need to apply a generic transform.
Solving AGCD
How would we attempt to solve the AGCD problem? Following the mantra I first heard from Alexander May – first you try exhaustive search, then you try a time-memory trade-off, then you think – let’s start with exhaustive search.
Given and
we know that
and we can simply guess and
which costs
GCD computations.
Thus, under this attack would get way with smaller but there is time-memory trade-off. The basic idea is the realisation that we can replace GCDs by multiplications, if
or
then we have
and
. That is, we can compute
for all guesses with
. The cost of this is
GCD computations (yay!),
multiplications (boo!), so it does not give us much of a saving. Yet, this can be extended to a time-memory trade-off which recovers
with overwhelming probability in time
. This is why we require
.
Finally, a lattice attack. Given and
, consider
and note that . So there is a linear combination of
and
that produces something small. This is all nice and well, but we don’t know which
to pick! Still, let’s generalise this observation and write it down in matrix form.
As before, multiplying on the left by the vector gives
which is a vector with small coefficients compared to the .
The set of all integer-linear combinations of the rows of matrix is called the lattice spanned by (the rows of) that matrix. Finding short vectors in lattices is assumed to be hard, even on a quantum computer.
While the above only sketches that we can break AGCD if we can find short vectors (similar to RSA and factoring), it is also possible to show that if you can solve the AGCD problem then we can also find short vectors in lattices (in contrast to RSA and factoring!). That is, if there is an algorithm efficiently solving the AGCD problem then there exists an algorithm which solves the Learning with Errors problem with essentially the same performance. Then, second step, if there is an algorithm efficiently solving the LWE problem then there exists a quantum algorithm which solves worst-case SIVP instances, i.e. finds short vectors in arbitrary lattices.
PS: Homomorphic encryption
Given with
, we can compute
to get and
. We can also compute
to get . That is, we can compute
AND
and XOR
which suffice to build any gate. Thus, we can compute on encrypted data.
Hi Martin. What is ρ in the time-memory tradeoff complexity?
sorry, that’s $\lambda$. Fixed.