Skip to content

Who Knew The Secret?

December 13, 2013

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.

The Problem

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” {p} 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 {p}, 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.

The Protocol

They supply an actual protocol:

Theorem: In the two-player problem, players can achieve success probability {1/3}.

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 {2/3} and speaks with probability {1/3}; otherwise, she passes with probability {1/3} and speaks with probability {2/3}.

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.

Open Problems

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?

10 Comments leave one →
  1. Alice permalink
    December 14, 2013 5:34 am

    This reminds me of Rivest’s “Three Vote” protocol. On a high level, he has a protocol in which Alice’s vote (secret) appears publicly on a bulletin board (so everyone can see it) but no one can prove that Alice voted this way, i.e. that this vote (secret) belongs to Alice.

    I guess the difference is that in the three vote protocol, there is an assumption that Eve is not watching Alice actually fill out her ballot?

    Also, what about the “blackballing” protocol. Suppose you vote whether someone should be a member of your club. Each voting member gets a white ball and a black ball. Each voter goes and puts one ball in the box. Again, the difference is that in this protocol, Eve can not see which color ball a person puts in the box? Or if there are all white balls, then we know how all voters voted?

    Is the new work of Winkler et al a protocol for blackballing when each person must announce information publicly rather than in assumed secrecy, i.e. secretly placing a ball in a box or a ballot in a box?

    • December 28, 2013 7:40 am

      You could view the cryptogenography protocol as a voting protocol, but its properties are very different from what you would usually want from a voting protocol:

      1) We assume that only one voter have an opinion and all the other voters do not care (but it is not know which of them who have an opinion)
      2) The voters can trust each other (everyone follows the protocol)
      3) With some probability, we might announce the wrong winner
      4) The protocol reveal some information about each voters preferences.

      In the paper we show that you do not need assumption 3. However, if we keep assumption 3, we could instead get rid of assumption 1 and get a voting protocol for the case where everyone have a preference: Everyone vote for their preference with probability 51% and against their preference with probability 49%. Now, a player’s vote does not tell much about her preference, and if there is a large number of voters we will find the correct winner with high probability. However, this protocol relies on assumption 2, that everyone can trust each other.

  2. December 14, 2013 5:34 am

    It is still being hotly debated whether Dick’s hidden message is correct or Ken’s, especially on this website.

  3. December 14, 2013 4:34 pm

    Is this one example where randomization in interactive communication is essential unlike in non-interactive case? I see no way of derandomization.

  4. Bobo permalink
    December 17, 2013 4:45 pm

    Isn’t it just oblivious transfer?

  5. December 19, 2013 3:51 am

    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.

  6. M. Musatov permalink
    December 20, 2013 7:19 am

    (5P – 4P) = NP
    (2, 2, 11, 1297) = 4P
    (424,866,199,037,051) = P
    This integer was arrived at by separating the p-values of the 22 P values beginning with 11 and ending with 101.
    This NP-Integer factors into 5 P-Values
    (2, 2, 11, 1297, 424,866,199,037,051)
    Two identical single digit values, one double-digit value consisting of the prior natural number repeated, no three-digit values, and only one four-digit number, wherein the first two digits satisfy the next countable number 12 as within 1297.
    From these 5-P factors we can obtain the average value of a P-value within NP
    (2 + 2 + 11 + 1297 + 424,866,199,037,051)=424,866,199,038,363
    424,866,199,038,363 / 5 = 84,973,239,807,672.6 (AVP) average P-value within NP
    From the factorization of NP we can also obtain an exact p-value from the fifth integer.
    The 5th P value of the actual NP factorization is 424,866,199,037,051.
    Divide integer by 5 to produce the exact p-value:
    The difference between the average and exact number is astonishingly close:
    The average NP value is P84,973,239,807,672.6
    The exact value the 5th P84,973,239,807,410.2
    A difference of 262.4
    It is also astonishing to note the total approximation from the average value of 5P (424,866,199,038,363) NP
    and the difference from the actual 5th P-value in the factorization of NP (424,866,199,037,051) equals 1,312 or 2^5+41.
    I am hoping this clarifies a few things and hope to hear your comments.

  7. M. Musatov permalink
    December 20, 2013 7:58 am

    2^5*41-41 closes out the set otherwise written correctly the first time as 2^5*41 without first writing 2^5+41 incorrectly.


  1. A Shameless Plug | Gödel's Lost Letter and P=NP

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s