3
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ Do you mean boxes, padlocks, seals, physical keys, etc? $\endgroup$ – Mahdi Cheraghchi Jun 9 '13 at 23:05
  • $\begingroup$ No I mean an algorithm like Caesar or Vigenere encryption. $\endgroup$ – Magnus Jun 9 '13 at 23:29
  • $\begingroup$ Given 1. that public-key cryptography was only published outside the intelligence community less than 40 years ago, and 2. that the essential insight of PKC is that in the digital realm a lock-and-key system can be inverted to keep the key while giving away many copies of the lock, it seems unlikely to me that there are historical analogues. $\endgroup$ – András Salamon Jun 10 '13 at 8:46
  • 1
    $\begingroup$ However, the Cinderella story about the glass slipper is a kind of analogue of PKC -- the message (the identity of the wearer) is locked until the right private key (in this case, a biometric: the correct foot) is united with the public key (the slipper). But this is a bit of a stretch. $\endgroup$ – András Salamon Jun 10 '13 at 8:54
  • $\begingroup$ See Bruce Schneier's Solitaire. $\endgroup$ – Jeffε Jun 11 '13 at 2:31
6
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you for this fascinating link! Incidentally it's not protected, I was able to read the whole thing. However I unfortunately was not able to follow much of it... Any chance you might be able to translate the essence of their algorithm into plain English? $\endgroup$ – Magnus Jun 11 '13 at 13:06
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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:

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

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.

$\endgroup$
2
  • $\begingroup$ Here's a basic idea for formalizing that: can be executed by a log-space machine with a polylogarithmic length read-only private key. $\:$ I'm not sure whether one would require that the algorithm be deterministic or allow the algorithm to be randomized; in the latter case one would $\;\;$ also require that it be polynomial time (which would be redundant in the first case). $\:$ [continued ...] $\endgroup$ – user6973 Jun 14 '13 at 8:59
  • $\begingroup$ [... continued] $\:$ I'm also not sure whether one would make the input tape one-way or two-way and whether one would erase the input tape between rounds or not (these would correspond to how $\;\;$ well the human can notice a change in what is being displayed while also running the algorithm). $\endgroup$ – user6973 Jun 14 '13 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.