A public key cryptographic technique usable without aid of computer

Question

I wondered if there is any known algorithm for secure messaging without pre-shared keys (i.e. public key cryptography) that is practical to use without the aid of a computer?

Obviously I would not expect it to be as secure as modern 256-bit encryption, but I wondered whether it was theoretically possible that older civilizations ever could have used something akin to public key cryptography, perhaps something with a computational complexity on the order of the Vigenere technique but without the need for a pre-arranged shared key?

Answer 1

Secure cryptographic protocols that can be executed by humans are considered in this paper: http://link.springer.com/chapter/10.1007%2F3-540-45682-1_4 (Hopper and Blum, "Secure Human Identification Protocols"). Reading the abstract, it sounds like they don't fully solve the problem. I suspect a satisfying solution is not known, but if you want to look into it I would start by looking at papers citing this one.

Answer 2

The Cæsar and Vigenère cipher are breakable. While some private key ciphers such as RC4, SNOW and SNOW2 (which are quite safe if used properly) can in principle be used by hand (albeit very slowly), public key ciphers usually require modular exponentiation of (very) large integers, which seems out of reach even for a determined individual. (Rabin's cipher may be somewhat practical to encrypt but not to decrypt.) Elliptic curve-based methods are even worse. Lattice-based public key encryption requires generating randomness on the encryptor's side, and some non-trivial algorithics on the decryptor's, so also seem to be too difficult to implement by hand.

Answer 3

If we look at a related topic, namely interactive identification protocols, we get a problem that has been well-studied.

Unfortunately there are no known protocols that are both secure (against attacks by computers) yet where ordinary humans can reasonably execute the protocol mentally without the aid of the computer. There have been lots of proposals, but all of them have either been broken or have proven too complicated for ordinary people to follow without making mistakes.

I think many researchers in the security and cryptography community expect that the problem is very hard and that, in all likelihood, no such secure and usable identification protocol exists. Of course, there is no proof of this -- it is not even clear how you could prove it, since it is not clear how you would formalize "can reasonably be executed by an ordinary human, in everyday life, without aid of a computer".

For a good entrance into the broad literature on interactive identification protocols, the following paper is excellent:

• On Limitations of Designing Leakage-Resilient Password Systems: Attacks, Principals and Usability. Qiang Yan, Jin Han, Yingjiu Li and Robert H. Deng. NDSS 2012.

There's also the seminal paper by Hopper and Blum that motivated a lot of the work in this area:

• Secure Human Identification Protocols. Nicholas J. Hopper, Manuel Blum. ASIACRYPT 2001.

Reading these two papers will give you a good sense of the directions, and a lot of relevant techniques and ideas. It will also help you understand why the interactive identification problem is so incredibly hard to do securely, without a computer.

Public-key cryptography is a strictly harder problem than interactive identification. If you could do public-key cryptography, you could also do interactive identification securely. For instance, I could prove my identity by demonstrating the ability to sign a random challenge chosen by the verifier; or by demonstrating the ability to decrypt a ciphertext chosen by the verifier. Therefore, my expectation is that there is no way to implement public-key cryptography securely without a computer, either.