10
$\begingroup$

Is there any research into digital cyphers that are easy for humans to decrypt, but hard for computers?

One example is Captchas, though those are being increasingly broken by computers. However, Captchas are not quite what I have in mind. Captchas depend on human domain expertise, which could theoretically be captured algorithmically and then cracked pretty easily with computers.

What I am looking for are cyphers that humans can easily decrypt, but are provably computationally hard or impossible. The encryption process has to also be performed algorithmically.

The scenario this encryption scheme would work in is the following:

  • The encrypted message is made available for offline processing.

  • Within a relatively short time the human can derive the message.

  • An algorithm will either find the message impossible to derive, or at least impossible in practice.

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ I don't think we need to worry about an AI only version of eve yet as the computers that break ciphers have human handlers. Also is your question about a digital cipher? Otherwise you could just put your message behind a closed door and it would be a hard problem for a computer to solve without human help: youtube.com/watch?v=HdtmmHEs9jg $\endgroup$ – daniel Jun 12 '17 at 16:02
  • 1
    $\begingroup$ Yes, digital cyphers. $\endgroup$ – yters Jun 12 '17 at 16:57
  • 1
    $\begingroup$ What is your input? The task you are looking for may be logically impossible if the input is an arbitrary bitstring, because computers are simply better at that than us. However, if the message can be a soft subtle concept subtly embedded in art, it may be impossible for a computer to detect. $\endgroup$ – Cort Ammon Jun 12 '17 at 22:29
  • 1
    $\begingroup$ @CortAmmon, it cannot be something as you suggest, since that could feasibly be algorithmically solved given enough context. I need problems that are inherently intractable for computers, but are trivial for humans. I've added an example to my question to give the general idea. $\endgroup$ – yters Jun 12 '17 at 23:24
  • 3
    $\begingroup$ I'd argue that finding something subtle added to a painting is enormously harder than the example in your question. The example in your question just calls for a little spatial awareness. A subtle nuance in a painting requires one to be deeply steeped in what it means to be human. When computers can appreciate the subtle nuances of Mona Lisa's smile, they can decrypt me =) $\endgroup$ – Cort Ammon Jun 12 '17 at 23:30
8
$\begingroup$

My opinion is that in order to design a cipher that is easier to decrypt by a human than by a competently programmed computer, the only working option is making the ciphertext or key unavailable to the computer due to some input limitation (like, the ciphertext or key is 3D-engraved in plexiglass, and the computer has no 3D vision); but that could be circumvented by an upgrade of the computer. With the relevant data available, no matter if we consider decryption with or without the key (the question is ambiguous about that), decryption is data processing, and properly programmed computers tend to vastly outperform humans at that.

Update: there are areas where the visual capabilities of the human brain (or possibly capabilities pertaining to other senses like audition) make humans somewhat competitive with computer programs; like finding a good move at the game of Go or Chess, an approximate solution to the Traveling Salesman Problem, or identifying some flaws in a pseudo random generator. I challenge that it allows constructing a cipher as asked, for two reasons:

  • For identification of flawed RNG, and arguably the TSP, there is evidence that humans perform significantly worse than computer programs primarily and competently designed for speed at the price of some error rate or non-optimality. Even for games, computer programs exist that beat the best humans with heavy hardware, and 99% of humans with a mere PC.
  • In tasks where humans are even mildly competitive with proper computer programs, humans tend to find only approximate solutions, and different humans will often find different solutions. It is hard to turn such capability into reliably deciphering a ciphertext, as necessary to answer the question.
Improve this answer
$\endgroup$
8
  • 1
    $\begingroup$ Is there any reason that you could not use misspelled words with a Caesar Cipher type of replacement? This would skew the distribution of letters. For example, "Elisabeth is the Queen of England" becomes "Elizabeth is qeen of yngland" The human brain can correct for amazing errors. $\endgroup$ – b degnan Jun 12 '17 at 10:04
  • 8
    $\begingroup$ @bdegnan So can computers. Search for qeen of yngland at Google and see what results you get. $\endgroup$ – r3mainer Jun 12 '17 at 10:46
  • 3
    $\begingroup$ @bdegnan It's nothing to do with the brain. It's an old algorithm called Soundex that's commonly used for misspellings. $\endgroup$ – Paul Uszak Jun 12 '17 at 12:25
  • 1
    $\begingroup$ @PaulUszak Make sense. I stand corrected. $\endgroup$ – b degnan Jun 12 '17 at 12:34
  • 1
    $\begingroup$ I think an example would be that if you encrypted your message into a magic eye picture, the computer might be fooled until it was updated to look for that, then it could use image processing to solve it faster than a human. $\endgroup$ – daniel Jun 12 '17 at 16:13
2
$\begingroup$

Depending on you assess the progress of AI capabilities moving forward, reaching the goal of "provably computationally hard or impossible" may not achievable. Specifically I'm thinking of future AI that equals or exceeds capabilities where humans are currently considered more proficient than computers.

Anyway, I'd suggest a condition of "practically computationally hard or achievable currently (or likely in the future)".

To that end a complex painting with various subtle clues, letters, or words as an integral part of the work, could communicate a message (or a key to a cipher) that could be relatively easy for most humans (possibly of a given culture) to interpret, but very hard for an automaton. The clues would be best if they were novel (not something from an existing knowledge base). In effect kind of a super-rebus or modern day hieroglyphics.

Similarly, some sort of performance art, where the message is communicated non-verbally, or figuratively. For example, a speech, where the words themselves are not the message, but the intonation, implication, what's not spoken, etc. are the sort of things that convey the message.

Certainly anything that relies on shared, private history between the participants would be hard for anything/anyone without the shared history to interpret.

Finally any kind of medium that heavily used artistic symbolism, again novel, could be used.

As with any encryption scheme, the threat model should be considered. If you want to use your company's network to send private messages and don't want them flagged by virtue of a simple keyword search, (and aren't worried about humans scanning the messages flowing through the company network) then a pretty simple scheme could be used, such as a cartoon like rebus. But if your adversary was more formidable, then a video with an actor miming the message may be more appropriate.

Improve this answer
$\endgroup$
2
$\begingroup$

Currently the best possible choices I can think of would be NP-hard problems. Most of these will be hard for humans as well though though we solve them a lot, but usually by using heuristics that don't ensure optimal solutions, in which case the computer is able to do the same.

One place I know where we do find ourselves still mostly doing better then Computers are mathematical proofs. The likes of Wiles's proof of Fermat's last theorem still seem to be miles beyond what computers can do. On the other hand it is also miles beyond what most people can do so it's not particularly useful. We are of course straying far from encryption and into humanity proving really. I wonder if anyone has really tried a Turing test with a modern smart elisa.

EDIT: apparently they have and the Elisa's are doing pretty damn good. See Turing Test.

Improve this answer
$\endgroup$
10
  • 1
    $\begingroup$ The only NP-hard problems I can think of where humans are even mildly competitive with computers are games (go..), but good computer programs beat the top 1% of humans; and such problems are hard to turn into a practical cipher. $\endgroup$ – fgrieu♦ Jun 12 '17 at 16:12
  • 1
    $\begingroup$ @yters That's a lot of calculating for a human, since small TS problems could be exhaustively solved by a computer. I mean you might be talking 2 hours work for a single puzzle solved (which might mean 1 bit deciphered). I don't even trust that a human can outperform a computer by some useful factor. $\endgroup$ – daniel Jun 12 '17 at 18:46
  • 1
    $\begingroup$ @yters do you have any links to studies on the TSP being solved faster by humans than computers? the only one I found where humans were used was for 20 points, which is small enough to be easily solved by a computer. $\endgroup$ – daniel Jun 12 '17 at 20:24
  • 3
    $\begingroup$ @yters as daniel points out I would be surprised if humans were actually better at TSP than computers. Mainly due to the fact that TSP of sizes big enough to challenge current computers will be quite big to challenge a human. $\endgroup$ – DRF Jun 12 '17 at 21:39
  • 2
    $\begingroup$ Here's the best paper I know of on the topic, graph sizes go up to 120 nodes: docs.lib.purdue.edu/cgi/… $\endgroup$ – yters Jun 12 '17 at 21:53
0
$\begingroup$

In spite this is not a direct answer, it shows that we humans have abilities to overcome computers in some areas.

Bo Allen showed in Pseudo-Random vs. True Random the visual comparison of the true random numbers generator and the pseudo-random one.

You may see 2 square pictures (created from randomly generated numbers) and you will immediately recognize the true randomness from the pseudo one.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Yes, this is good. Randomness, in general, is not computable. So, it is interesting that humans can distinguish true random from pseudorandom. $\endgroup$ – yters Jun 13 '17 at 2:23
  • 3
    $\begingroup$ 1) There is no evidence to suggest that Random.org is anything other that a pseudo random number generator. 2) Bo's comparison is childish and trite. I challenge you to visually compare Hotbits output with ISAAC and tell them apart. 3) The very definition of a CSPRNG is one that is computationally indistinguishable from truly random. So there. $\endgroup$ – Paul Uszak Jun 13 '17 at 2:39
  • $\begingroup$ @PaulUszak - Thanks for your valuable comment. May I ask you: Why RANDOM.ORG (atmospheric noise) is only a pseudo while HotBits (radioactive decay) is a true RNG? May you provide a link where I may visually compare HotBits output with ISAAC one? $\endgroup$ – MarianD Jun 13 '17 at 14:30
  • 1
    $\begingroup$ In the linked article, the author shows a "random" bitmap that was created via php's rand() function on windows, and compares it with a randomly generated one from random.org. This is a loaded comparison of apples v oranges that does not imply any kind of useful information: Yes, you can visually distinguish a bad RNG from a cryptographically secure one. You will not be able to do the same if you use two algorithms that are at least designed for the same purpose (i.e. Given only the output, you cannot distinguish sha-3 output from dev/urandom output ). This answer is simply wrong. -1. $\endgroup$ – Ella Rose Jun 13 '17 at 15:37
  • 2
    $\begingroup$ @MarianD See last para. of crypto.stackexchange.com/questions/42691/… re. problems with random.org. It's a con and I'm a cynic. There's no point visually comparing Hotbits vs. ISAAC as you'd just be looking at two identical grey squares. Trust me. $\endgroup$ – Paul Uszak Jun 13 '17 at 22:33

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.