We have seen that both of the following problems are conjectured not to be solvable in polynomial time.
Both of those problems are equivalent in difficulty to problems that are in NP ∩ CoNP, so the conjecture that they are difficult relies on the conjecture that P ⊂ NP ∩ CoNP.
The problem of telling whether a number is prime is much easier than factoring. It is solvable in polynomial time.
Complexity allows the definition of public-key ciphers.
Where classical cipher systems rely on an eavesdropper not having enough information to decrypt a messages, a public-key cipher's strength is based on an eavesdropper not having enough time to decipher messages.
One simple encryption scheme is to choose two large prime numbers p and q, to define m = pq, and to use function
Decrypting with knowing p and q is conjectured to be difficult. But there is a polynomial-time algorithm to compute all discrete square roots of a quadratic residue, provided you know the prime factorization of the modulus.
An issue with this scheme is that there are 4 square roots of x (if gcd(x, m) = 1, which is true with overwhelmingly high probability). Redundancy needs to be used to decide which is the correct one.
The RSA system is as follows.
Select two different large prime numbers p and q independently at random.
Let n = pq and compute φ = (p − 1)(q − 1).
Select a small number e > 2 that is relatively prime to φ.
Let d by the inverse of e (mod φ) (found using the extended Euclid algorithm).
The encipher and decipher functions are:
| E(x) | = | xe mod n |
| D(x) | = | xd mod n |
RSA has the advantage that D(x) is the functional inverse of E(x).
It has the disadvantage that it is not known whether decrypting RSA is as difficult as factoring n.
Public-key ciphers can be used for digital signatures. The signer publishes pair (x, D(x)), where x is the document to be signed and D is the decipher function.
To check that the signature is valid, you use E to compute E(D(x)) and check that it is the same as x.
An interactive proof is a system to allows a prover to demonstrate a fact to a verifier by carrying out a conversation.
The prover is assumed to have high computational power, but the verifier is assumed only to be able to use polynomial-time algorithms.
A zero-knowledge proof is an interactive proof where the prover does not tell the verifier any information that the verifier could not get without the prover's help.