Who Knew The Secret?
Controlled release of secret information
Peter Winkler is a world famous mathematician who works mostly on combinatorial problems. He is famous for many things, but his series of puzzle book are terrific—see here. Also he is “notorious” for his discovery that cryptography could be used in contract bridge. Amazing.
Today Ken and I want to talk about his paper on “Cryptogenography” to be presented at the ITCS Conference this coming January. It is joint with Joshua Brody, Sune Jakobsen, and Dominik Scheder. They have made up the word from cryptography and steganography.
Previously the whole area was just known as steganography, but they have a slightly different take on it, hence the new name. Even those who use strong cryptography can be attacked and have their secrets discovered. Quite a danger is presented to those with real secrets, and this raises the need for hiding the message itself. Unlike cryptography, if you do not even see the message it is hard—impossible?—to break it. Attacks on those using hidden messages are quite difficult and often yield more security than conventional methods. Little theory has yet been developed, however, and that is the main goal of this paper. Steganography, or cryptogenography as they call it, can use a robust theory. Not that their results aren’t interesting, but the main contribution is the theory. Perhaps this will be the first of many papers in this new area?
This last paragraph is a weak attempt at Steganography—see the end for the answer—unless you have figured it out already. An example of the real thing is:
Steganography is used by some modern printers, including HP and Xerox brand color laser printers. Tiny yellow dots are added to each page. The dots are barely visible and contain encoded printer serial numbers, as well as date and time stamps.
Let’s turn to Peter and his co-authors’ results.
It’s Alice and Bob again, against Eve. The paper treats the general case of many people, but we will limit our discussion to just Alice and Bob. A secret bit is held by one of Alice or Bob—they both know who has the secret bit initially, but they do not both know the bit. After they perform a protocol, the secret bit is revealed to all, but they want to hide who was the initial bit-holder, even from Eve—who hears everything and is not computationally limited.
A protocol’s success is measured by the “success probability” that the secret is correctly revealed and the eavesdropper mis-guesses the identity of the secret-owner. The goal of Alice and Bob is to maximize , and Eve’s goal is to minimize it: this is the “game” they call cryptogenography. See their paper for the technical definition and also the extension to multiple players.
The novelty is, of course, that the secret is revealed to all, but who initially held the secret is protected. This seems quite innovative—perhaps that is why it is a paper at ITCS.
They supply an actual protocol:
Theorem: In the two-player problem, players can achieve success probability .
See their paper for the full details, but here is their protocol as they describe it:
This protocol proceeds in two rounds. In the first round of communication, Alice decides whether to “pass”or “speak.” If she passes, then Bob speaks in the second round; otherwise she speaks. In the second round of communication, whoever speaks will (i) send the secret if they own it and (ii) send a random bit otherwise. Both players output the second bit of communication as their guess for the secret. All that remains is to complete the protocol is to specify how Alice chooses to pass or speak in the first round. If Alice owns the secret, she passes with probability and speaks with probability ; otherwise, she passes with probability and speaks with probability .
Note that Alice is more likely to speak in round 2 when she doesn’t own the secret. This is perhaps counterintuitive—the players output the second bit of communication, so intuitively Alice should speak more often when she actually owns the bit. Is there an a priori reason why Alice shouldn’t just announce the secret if she owns it and pass otherwise? Unfortunately in this case, Eve will learn with certainty who owns the bit. Alice’s probability of passing are chosen to give Eve no information about the secret-owner conditioned on players successfully outputting the secret.
Answer to the initial hidden message: paragraph’s \capitals, never exactly quite noticeable perfectly.
Dick used a pretty simple encoding, but you get the idea. Ken hid another message just above. Which of Dick’s and Ken’s hidden messages is correct?