Public key encryption based on squares and non squares
The RSA encryption algorithm depends indirectly on the assumption that factoring the product of large primes is hard. The algorithm presented here, invented by Shafi Goldwasser and Silvio Micali, depends on the same assumption but in a different way. The Goldwasser-Micali algorithm is more direct than RSA, thought it is also less efficient.
One thing that makes GM interesting is that allows a form of computing on encrypted data that we'll describe below.
GM in a nutshellTo create a public key, find two large primes p and q and publish N = pq. (There's one more piece we'll get to shortly.) You keep p and q private, but publish N, much like with RSA.
Someone can send you a message, one bit at a time, by sending you numbers that either do or do not have a square root mod N.
Sending a 0If someone wants to send you a 0, they send you a number that has a square root mod N. This is easy to do: they select a number between 1 and N at random, square it mod N, and send you the result.
Determining whether a random number is a square mod N is easy if and only if you know how to factor N. [1]
When you receive the number, you can quickly tell that it is a square because you know how to factor N. The sender knows that it's a square because he got it by squaring something. You can produce a square without knowing how to factor N, but it's computationally infeasible to start with a given number and tell whether it's a square mod N, unless you know the factorization of N.
Sending a 1Sending a 1 bit is a little more involved. How can someone who cannot factor N produce a number that's not a square? That's actually not feasible without some extra information. The public key is not just N. It's also a number z that is not a square mod N. So the full public key is two numbers, N and z.
To generate a non-square, you first generate a square then multiply it by z.
ExampleSuppose you choose p = 314159 and q = 2718281. (Yes, p is a prime. See the post on pi primes. And q comes from the first few digits of e.) In practice you'd choose p and q to be very large, hundreds of digits, and you wouldn't pick them to have a cute pattern like we did here. You publish N = pq = 853972440679 and imagine it's too large for anyone to factor (which may be true for someone armed with only pencil and paper).
Next you need to find a number z that is not a square mod N. You do that by trying numbers at random until you find one that is not a square mod p and not a square mod q. You can do that by using Legendre symbols, It turns out z = 400005 will work.
So you tell the world your public key is (853972440679, 400005).
Someone wanting to send you a 0 bit chooses a number between 1 and N = 853972440679, say 731976377724. Then they square it and take the remainder by N to get 592552305778, and so they send you 592552305778. You can tell, using Legendre symbols, that this is a square mod p and mod q, so it's a square mod N.
If they had wanted to send you a 1, they could have sent us 592552305778 * 400005 mod N = 41827250972, which you could tell isn't a square mod N.
Homomorphic encryptionHomomorphic encryption lets you compute things on encrypted data without having to first decrypt it. The GM encryption algorithm is homomorphic in the sense that you can compute an encrypted form of the XOR of two bits from an encrypted form of each bit. Specifically, if c1 and c2 are encrypted forms of bits b1 and b2, then c1c2 is an encrypted form of b1 a b2. Let's see why this is, and where there's a small wrinkle.
Suppose our two bits are both 0s. Then c1 and c2 are squares mod N, and c1c2 is a square mod N.
Now suppose one bit is a 0 and the other is a 1. Then either c1 is a square mod N and c2 isn't or vice versa, but in either case their product is not a square mod N.
Finally suppose both our bits are 1s. Since 1a1 = 0, we'd like to say that c1c2 is a square mod N. Is it?
The product of two non-squares is not necessarily a non-square. For example, 2 and 3 are not squares mod 35, and neither is their product 6 [2]. But if we followed the recipe above, and calculated c1 and c2 both by multiplying a square by the z in the public key, then we're OK. That is, if c1 = x^2z and c2 = y^2z, then c1c2 = x^2y^2z^2, which is a square. So if you return non-squares that you find as expected, you get the homomorphic property. If you somehow find your own non-squares, they might not work.
Related posts[1] As far as we know. There may be an efficient way to tell whether x is a square mod N without factoring N, but no such method has been published. The problem of actually finding modular square roots is equivalent to factoring, but simply telling whether modular square roots exist, without having to produce the roots, may be easier.
If quantum computing becomes practical, then factoring will be efficient and so telling whether numbers are squares modulo a composite number will be efficient.
[2] You could find all the squares mod 35 by hand, or you could let Python do it for you:
>>> set([x*x % 35 for x in range(35)]){0, 1, 4, 9, 11, 14, 15, 16, 21, 25, 29, 30}