A zero knowledge proof (ZKP) answers a question without revealing anything more than answer. For example, a digital signature proves your possession of a private key without revealing that key.
Here’s another example, one that’s more concrete than a digital signature. Suppose you have a deck of 52 cards, 13 of each of spades, hearts, diamonds, and clubs. If I draw a spade from the deck, I can prove that I drew a spade without showing which card I drew. If I show you that all the hearts, diamonds, and clubs are still in the deck, then you know that the missing card must be a spade.
Composite numbers
You can think of Fermat’s primality test as a zero knowledge proof. For example, I can convince you that the following number is composite without telling you what its factors are.
n = 244948974278317817239218684105179099697841253232749877148554952030873515325678914498692765804485233435199358326742674280590888061039570247306980857239550402418179621896817000856571932268313970451989041
Fermat’s little theorem says that if n is a prime and b is not a multiple of n, then
bn−1 = 1 (mod n).
A number b such that bn−1 ≠ 1 (mod n) is a proof that n is not prime, i.e. n is composite. So, for example, b = 2 is a proof that n above is composite. This can be verified very quickly using Python:
>>> pow(2, n-1, n)
10282 ... 4299
I tried the smallest possible base [1] and it worked. In general you may have to try a few bases. And for a few rare numbers (Carmichael numbers) you won’t be able to find a base. But if you do find a base b such that bn−1 is not congruent to 1 mod n, you know with certainty that b is composite.
Prime numbers
The converse of Fermat’s little theorem is false. It can be used to prove a number is not prime, but it cannot prove that a number is prime. But it can be used to show that a number is probably prime. (There’s some subtlety as to what it means for a number to probably be prime. See here.)
Fermat’s little theorem can give you a zero knowledge proof that a number is composite. Can it give you a zero knowledge proof that a number is prime? There are a couple oddities in this question.
First, what would it mean to have a zero knowledge proof that a number is prime? What knowledge are you keeping secret? When you prove that a number is composite, the prime factors are secret (or even unknown), but what’s the secret when you say a number is prime? Strictly speaking a ZKP doesn’t have to keep anything secret, but in practice it always does.
Second, what about the probability of error? Zero knowledge proofs do not have to be infallible. A ZKP can have some negligible probability of error, and usually do.
It’s not part of the definition, but n practice ZKPs are supposed to be easier to verify than the direct approach to what they prove. So you could have something like a primality certificate that takes far less computation to verify than the computation needed to determine from scratch that a number is prime.
Proving other things
You could think of non-constructive proofs as ZKPs. For example, you could think of the intermediate value theorem as a ZKP: it proves that a function has a zero in an interval without giving you any information about where that zero may be located.
What makes ZKPs interesting in application is that they can prove things of more general interest than mathematical statements [2]. For example, cryptocurrencies can provide ZKPs that accounting constraints hold without revealing the inputs or outputs of the transaction. You could prove that nobody tried to spend a negative amount and that the sum of the inputs equals the sum of the outputs.
Related posts
[1] You could try b = 1, but then bn−1 is always 1. This example shows that the existence of a base for which bn−1 = 1 (mod n) doesn’t prove anything.
[2] You might object that accounting rules are mathematical statements, and of course they are. But they’re of little interest to mathematicians and of great interest to the parties in a transaction.