A public key cryptographic technique usable without aid of computer 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?
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.