<p>Secure cryptographic protocols that can be executed by humans are considered in this paper: <a href="http://link.springer.com/chapter/10.1007%2F3-540-45682-1_4">http://link.springer.com/chapter/10.1007%2F3-540-45682-1_4</a> (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. </p>

CC BY-SA 3.0
2013-06-11T13:06:12.183Z
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?
Magnus
CC BY-SA 3.0
2013-06-10T20:17:38.927Z
2013-06-10T20:17:38.927Z
Aaron Roth
<p>The Cæsar and Vigenère cipher are <em>breakable</em>. 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.</p>

CC BY-SA 3.0
2013-06-10T03:51:01.080Z
2013-06-10T03:51:01.080Z
Yuval Filmus
<p>If we look at a related topic, namely interactive identification protocols, we get a problem that has been well-studied.</p>

<p>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.</p>

<p>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".</p>

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

<ul>
<li><a href="http://www.internetsociety.org/sites/default/files/06_2.pdf" rel="nofollow">On Limitations of Designing Leakage-Resilient Password Systems: Attacks, Principals and Usability</a>.  Qiang Yan, Jin Han, Yingjiu Li and Robert H. Deng.  NDSS 2012.</li>
</ul>

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

<ul>
<li><a href="http://www-users.cs.umn.edu/~hopper/secure_human_identification_protocols.pdf" rel="nofollow">Secure Human Identification Protocols</a>.  Nicholas J. Hopper, Manuel Blum.  ASIACRYPT 2001.</li>
</ul>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2013-06-14T06:50:38.720Z
2013-06-14T06:58:44.250Z
2013-06-14T06:58:44.250Z
D.W.
<p>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?</p>

<p>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?</p>

CC BY-SA 3.0
2013-06-09T23:05:43.263Z
Do you mean boxes, padlocks, seals, physical keys, etc?
Mahdi Cheraghchi
CC BY-SA 3.0
2013-06-09T23:29:05.580Z
No I mean an algorithm like Caesar or Vigenere encryption.
Magnus
CC BY-SA 3.0
2013-06-10T08:46:47.813Z
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.
András Salamon
CC BY-SA 3.0
2013-06-10T08:54:01.613Z
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.
András Salamon
CC BY-SA 3.0
2013-06-11T02:31:50.470Z
See Bruce Schneier's [Solitaire](http://en.wikipedia.org/wiki/Solitaire_(cipher)).
Jeffε
CC BY-SA 3.0
2013-06-11T02:54:09.550Z
Very interesting, thanks!  It looks like this is however an ordinary cipher which would require a pre-arranged shared key?  I'd be very interested to know about a public/private key mechanism using a deck of cards.
Magnus
<cr.crypto-security><key-exchange>
A public key cryptographic technique usable without aid of computer
Magnus
# A public key cryptographic technique usable without aid of computer

(Asked by: username_0 on 2013-06-09)

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?

**Tags:** cr.crypto-security, key-exchange

> **Comments:**
> **username_1**: Do you mean boxes, padlocks, seals, physical keys, etc?  
> **username_0**: No I mean an algorithm like Caesar or Vigenere encryption.  
> **username_2**: 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.  
> **username_2**: 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.  
> **username_3**: See Bruce Schneier's [Solitaire](http://en.wikipedia.org/wiki/Solitaire_(cipher)).  
> **username_0**: Very interesting, thanks!  It looks like this is however an ordinary cipher which would require a pre-arranged shared key?  I'd be very interested to know about a public/private key mechanism using a deck of cards.  

---

## 3 answers

### Answer by username_4 on 2013-06-10. Score: 6

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.

> **Comments:**
> **username_0**: 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?  

---

### Answer by username_5 on 2013-06-10. Score: 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 by username_6 on 2013-06-14. Score: 1

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](http://www.internetsociety.org/sites/default/files/06_2.pdf). 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](http://www-users.cs.umn.edu/~hopper/secure_human_identification_protocols.pdf). 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.


---

