3
$\begingroup$

Bob likes Apples and Oranges (virtual, not physical). Alice and Eve are fruit sellers (again, virtual, not physical). Bob wants to indicate his appetite to buy one Apple and one Orange without revealing who he is. Alice and Eve want to sell to Bob but they can't know Bob's identity. How does Bob communicate his preference to buy, and then take receipt, without Alice and Eve ever knowing who he is and without using a central authority?

$\endgroup$
7
  • 1
    $\begingroup$ "Bob shares what he likes with Alice" needs a definition. It's not even clear if that's information (as in Bob communicates to Alice the information that he likes 42) or something physical (as in Bob likes cake and shares a cake with Alice). Assuming the former, it's not clear how Bob knows about Alice in the first place; If he cares that Eve knows he likes 42; what kind of communication can occur between Bob and Alice; if Eve is able to replace 42 with 43.. For this and many other reasons that do not fit, the question is not precise enough. It must be improved, or will get closed. $\endgroup$
    – fgrieu
    May 27, 2021 at 16:25
  • 1
    $\begingroup$ Are you referring to the Soviet Spy Game, or something adjacent to it? Perhaps like a zero-knowledge proof-of-not-cheating for Go Fish? $\endgroup$ May 27, 2021 at 16:32
  • 1
    $\begingroup$ Sorry, I have edited the question. Is it now more clear? $\endgroup$ May 27, 2021 at 17:04
  • 1
    $\begingroup$ First and foremost, thank you very much JamesTheAwesomeDude for your answer. Can you possibly suggest additional reading material, or topic titles? I am keen to learn more. I don't really know how to search for answers to my problem. Does it fit within a particular sub-field of cryptography? $\endgroup$ May 28, 2021 at 7:20
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Alice_and_Bob $\endgroup$
    – kelalaka
    May 28, 2021 at 8:02

1 Answer 1

3
$\begingroup$

All Bob needs is to generate an Ephemeral key: just make (say) an RSA key, use it to initiate and proceed with communications with Alice, then delete it when he's done, taking care never to use it to process any personally-identifying information.

In fact, this is what web browsers do every time you connect to a website: by default, only the server has a certificate anchoring its identity; clients are anonymous until or unless they supply authentication. Your queries to, say, Searx are confidential, known only by the host and the anonymous client which started that TLS session.

(The bit about "no central authority certifying Alice" is a massive, separate question -- it is the puzzle which X.509, DANE, and an entire host of decentralized proto-solutions are still struggling to solve to this day; but I'll include a proto-solution to it as well.)

With any public-key cryptosystem, it's trivial to implement an ephemeral or "anonymous" key, by simply not attaching identity attestations to a freshly-generated public key and then throwing it away afterwards; if you're only concerned with the authenticity of one party (Alice is a recognized fruit seller or someone whom Bob otherwise knows the public key of; Bob is an anonymous client with no identity persisting beyond the scope of a single discussion session), it's quite easy -- For example (all messages listed are both signed by the sending key and encrypted by the receiving key):

Bob: (Acquires Alice's putative pk_A)
Bob: (Generates a keypair sk_B, pk_B)
Bob -> Alice (sk_B -> pk_A): "Buying oranges for 3 bitcoin, reply-to [pk_B]"
Alice -> Bob (sk_A -> pk_B): [initiate zero-knowledge proof of orange possession]
Bob -> Alice (sk_B -> pk_A): [challenge proof]
Alice -> Bob (sk_A -> pk_B): [complete proof]
Alice -> Bob (sk_A -> pk_B): "send 3 bitcoins to [btc_A] if you want them"
Bob -> Alice (sk_B -> pk_A): [transaction]
Alice -> Bob (sk_A -> pk_B): [oranges]
Bob: (deletes sk_B and all trace of pk_B off his computer)

In the real-world, something like this happens if you buy something from an online merchant using a burner e-mail (or no e-mail) and either General Delivery or inherently digital data served over the same TLS connection, though without a "proof" of the online merchant's legitimacy (which, again, is a whole separate scope from merely allowing bidirectional secure communications with an anonymous participant).


[Note that Bob and Alice are switched from their canonical roles in your question; I have written my answer to reflect that, but, in the future, you should use "Alice" to represent the initiator/sender of communications and Bob as the recipient or secondary participant. Additionally, "Eve" is used to denote the malicious party -- the hacker or "Eavesdropper" -- who may be just eavesdropping, or may be launching interactive or invasive MitM attacks; her abilities are generally assumed to comprise control of the network.]

$\endgroup$
4

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.