The Approximate GCD Problem

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.