Like many instances of innovation this one has personal roots. A few years back the innovator was involved in legal proceedings facing a court order to surrender his private diaries to his adversary, all part of a process called 'discovery'. For a moment the innovator regretted not having used some standard encryption, protecting his privacy, but he soon realized that it would make no difference since the judge would order him to use his key and unlock the ciphertext. Claiming loss of the key would be as helpful as claiming loss of a luggage key when facing a security inspection at an airport. To his chagrins the innovator quickly learned that no mainstay encryption method would offer deniability. In other words, the ciphertext commits to the plaintext that generated it. An innovation challenge was born: deniability cryptography, defined as follows. A private citizen writes a personal diary PD. To protect his privacy the citizen uses an encryption key, kPD, and encrypts PD to an encrypted file, EF. An enforcer comes forth, spots the encrypted file, EF, and orders the private citizen to decrypt EF into the unencrypted, plain version of his personal diary, PD. The citizen shrugs and pulls out a different key, kinstead, and uses it to decrypt EF into a lame text, LT, instead of his real personal diary. The lame text is forwarded to the enforcer, as if it were the true personal diary. Since the decryption process is the same, only the keys are different, it becomes impossible for the enforcer to realize that he has been fooled. In other words, using deniability encryption a writer could hide his true secret by substituting it with a secret-look-alike.

Since none of the mainstay encryption systems offered this attribute, it right away qualified as a bona fide innovation challenge. The challenge could not have been resolved in a direct manner. So the innovator tried the breakdown route. The following components were defined: (1) is a deniability cipher theoretically possible? (2) is there a practical version thereof? (3) if so, then what are its major attributes? And finally, (4) what would that cipher be? These four components were configured in a concentric mode. If the answer to (1) was in the negative, there would be no point to the other three. Attacking the first concentric component, it became readily clear that the answer is in the affirmative. Moreover, there is a well established ciphersystem, patented as early as 1917, which offers full deniability as defined above. It's called the Vernam cipher, or in its colloquial name: "One Time Pad". Moving into the 2nd concentric component, the answer became more iffy. It turns out that the key for the Vernam cipher must be as long as the unencrypted file. For a long diary, this would be a rather long key.

This limitation inspired the innovator to choose the abstraction route from this 'practical feasibility' challenge, redefining the challenge as: "is there any deniability-featuring ciphersystem that would be practical (comfortable) to use? -- that is, not necessarily the Vernam cipher. This abstracted challenge was subsequently divided into two concentric components: (1) what is the difference between the mainstay ciphersystems which don't offer deniability, and the Vernam cipher that does offer the same?, And (2) how to exploit the answer to [1] to come up with a non-Vernam ciphersystems which would be practical to employ? Attacking the first component the answer came forth directly. a simple statistical computation would show that if the key is much shorter than the encrypted message then there is no realistic chance for the existence of a second key that would qualify for deniability purposes. In other words, all the prevailing ciphersystems which employ short keys are powerless to offer deniability. Having resolved this challenge, the innovator turned his attention to the next component in the concentric sequence: how to exploit that difference? The latter challenge appeared too difficult to resolve directly, and it too underwent concentric breakdown. (1) what is the shortest key that would offer theoretical deniability? (2) What are the invisible assumptions that underlie the answer in [1]? (3) how to design a ciphersystem that would void the constricting assumptions in [2]? Some ready statistical calculations have shown that deniability vanishes very quickly as the key gets smaller than the message it encrypts. There is no hard and fast threshold, the probability simply decreases as the key gets shorter.

Armed with that resolution, the attention was turned into discerning the invisible assumptions that were underlying the latter statistical result. Direct attack yielded the following assumptions: (1) large keys are unwieldy and impractical, (2) Kerckhoff's law: the law that says that the adversary knows the exact length of the employed key, (3) that every bit of the contents of the plain message is of equal high secrecy, and (4) that the intended reader of the encrypted message has zero equivocation with respect to decrypting the ciphertext. Having resolved this 2nd challenge in the concentric set, the innovative attention was turned into the third one: building one or more ciphersystems on the basis of violating one or more of the underlying assumptions. This challenge was broken down into four parallel challenges, each for one of the four assumptions, followed by a concentric component -- a ciphersystem based on a combined solution to the previous challenge (where only one assumption is being violated). Modern technology offers a 1 gigabyte of key material to be written on a reasonably priced USB stick, allowing for 1 gigabyte of text to be encrypted using the Vernam cipher -- offering complete deniability. One would have to live a very long life to write a diary that exceeds one gigabyte of text. Alas, if one attempts to conceal pictures one gigabyte is not a very long key. Conclusion: what was totally impractical at the time of its invention, (1917) is quite practical today almost 90 years later. But it is not very elegant. The second assumption is more intriguing. Using Vernam it's clear that the size of the key corresponds to the size of the message. But is there a different ciphersystem where the size of the employed key would be part of the key secret? The answer to the latter question did not show up through a direct attempt, and thus the challenge was divided into two concentric parts: (1) identify the process difference between the mainstay short-key ciphersystems, and the Vernam cipher, (2) exploit the process difference found in [1] to suggest a ciphersystem where the key length would be part of the key secret. The first part is attacked and resolved directly.

It is found that the short-key mainstay ciphersystems are based on a process of high complexity between the bits of the short key, and the bits of the plaintext, while the Vernam cipher relies on the length of the key to provide the necessary complexity, and the bit operation itself is rather simple. Next, this process distinction is used to find a different solution where the key size would provide the complexity, while the operation itself would be simple. Such requirement turns out to be met with a simple, well known process of expressing a pathway on a graph by either listing the series of visited vertices, or by identifying the series of traversed edges. The path is the same, the means to describe it are different, and these two ways are connected through the existence of the graph. Hence one could regard the series of vertices as a plaintext version, and the series of edges as the ciphertext version of the same message. These two versions are easily translatable from one to the other using the graph itself, alas, without the graph, the translation may be impossible. It is further realized that this graph encryption would work on small as well as large graphs, and thus the challenge is met: the size of the graph is part of the key secret. For small graphs security is based on intractability alone, but when the graph increases in size, it reaches the point of deniability.

With this challenge resolved, the innovator turned into the third constricting assumption: content based security. Analyzing this challenge it became clear that in a typical secret text some terms, words, and phrases are more secret than others. This may lead to a code-book arrangement where the few highly secretive terms would be expressed via code names, which in turn would be encrypted through keys of comparable length, while the rest of the text would be encrypted with shorter keys. Thus a certain key size could be divided into a small portion that would be dedicated to the code-book, and a larger portion dedicated to the rest of the text. The combination would create a de-facto deniability, which is the objective of the original IC. Next, the innovator turned to the last constricting assumption, that the intended reader should be able to decrypt the message without any equivocation. On attacking that assumption it becomes clear that by allowing for some small as desired equivocation at the decryption end, that reader would be endowed with a high as desired degree of deniability. Thus the innovation path was able to achieve the original goal by circumventing each and every constricting assumption that prevented the same. Naturally, a combination of these three solutions is readily feasible, thus resolving the combination challenge.