Talk:Dining cryptographers problem

XOR or OR problem?

On 13:52, 24 January 2022‎, 80.112.158.130 changed the DC problem as one that requires computing XOR rather than OR with a note "The DC problem discusses how to perform an XOR operation rather than an OR operation". However, I don't think this change is correct. The context of the DC problem described in Chaum's original paper should make it clear that what three cryptographers "intend" to compute is actually OR, not XOR. DC-net tries to solve this problem by doing the XOR operations among the shared bits, but that leads to likely collisions (in case of a collision, the outcome is not considered correct and the suggestion in the original paper to resolve the collision problem is to re-run the protocol). Therefore, it should be clear that what the DC problem really concerns is actually the computation of OR. Fh240 (talk) 19:27, 27 January 2022 (UTC)

Merge with Dining cryptographers protocol

It has been suggested that this page and Dining cryptographers protocol are too closely related and should be merged. There was some progress made in rewriting the article, Dining_cryptographers_protocol/Rewrite, but it hasn't seen any content updates since March 2008. Thoughts? -- Autopilot (talk) 14:59, 7 March 2009 (UTC)

I've gone ahead and done the merge from Dining cryptographers protocol to Dining_cryptographers_problem. I'll get around to merging in the new content from Dining_cryptographers_protocol/Rewrite in the next few days, unless someone else wants to go for it first. I didn't see any recent discussion on this matter, but I felt that the articles were at least 95% similar and that Dining cryptographers protocol contained almost nothing that this article did not. WP:BOLD and all. If anyone objects to this, please let me know so we can work something out. Burningstarfour (talk) 19:09, 4 May 2011 (UTC)

There are actually 3 pages about the same topic:

• Dining cryptographers protocol,
• Dining_cryptographers_protocol/Rewrite,
• Dining_cryptographers_problem.

The one that contains the least inaccurate stuff is the last one. The other two pages are very inaccurate.

Some remarks:

• The generalisation of the protocol IS NOT A RING structure. The idea is that each participant should ideally establish a shared secret with every other participant (fully connected graph). In the story, there are only 3 cryptographers, and in this very situation (fully connected graph with 3 nodes), this looks like a ring. It is however not supposed to be a ring in the general case.
• There are NO ENCRYPTED LINKS. Particiants use a secure channel (which is a theoretical concept) and not an encrypted link (which has to do with cryptography). This especially wrong because the protocol guarantees unconditional (information theoretical) untraceability, and therefore cannot use cryptography (which is based on the assumption that some problems that are hard to compute).
• All the other stuff (aging cryptographers, and so on), is absolutely unrelated. I have never heard of this, and I wonder who invented all that stuff. (The dining philosophers problem actually exists, but it is completely unrelated.) There is only the dining cryptographers protocol. All these strange derivations do not exist and do not belong here.
• An external site that is sometimes referenced contains the same inaccurate information, and should be avoided.
• The last page has the following problems: It is not about computing a multiparty OR ; Chaum does suggest a reservation technique to avoid collisions (using a reservation vector); and he does suggest a technique to detect disruptors.

That's interesting. If it's not about multiparty OR, what do you think it is computing? Using a trap to capture disruptors is a theoretical concept in Chaum'a paper. Does the paper explain how to do it exactly? Some other papers followed up the trap concept. They assumed the DC-net as a ring and proposed more concrete measures to implement the "trap", but DC-net is not a ring. Fh240 (talk) 13:35, 10 April 2009 (UTC)

Hm, in original paper Chaum considers various configurations of graph. He concludes that connected components form indistinguishable groups for an observer and biconnected components make indistinguishable groups for participants too. So where from comes idea that graph should be ideally fully connected? This idea is not obvious and not explained well. Fedoresko (talk) 17:59, 22 October 2022 (UTC)

Things one could mention:

• Sender untraceability is achieved through a technique called superposed sending.

(Not sure what that means. It seems only to confuse people. Fh240 (talk) 13:35, 10 April 2009 (UTC))

• Receiver untraceability is based on the reliable broadcast assumption.

(That's illogical. In DC-net, the receiver is untraceable because everyone (including the attacker) is the receiver. Fh240 (talk) 13:35, 10 April 2009 (UTC))

• Most relevant work on the topic has been done by Chaum, Pfitzmann, Waidner, Golle and Juels.

(It's necessary to explain what the paper are about before adding the references, so that readers can decide how relevant (or irrelevant) they are. Otherwise, it only confuses people. Fh240 (talk) 13:35, 10 April 2009 (UTC))

—Preceding unsigned comment added by 85.93.206.248 (talk) 16:00, 7 March 2009 (UTC)

---

I am the author of the initial remarks, and I believe they are perfectly valid. Here is the list of papers with the paper that are in my opinion the most relevant about the Dining cryptographers protocol. You will find the detail about everything in these papers (Especially the early papers explain the details of the protocol.) :

• D. Chaum. The dining cryptographers problem: Unconditional sender and recipient untraceability. Journal of Cryptology, 1(1):65–75, 1988.
• M. Waidner and B. Pfitzmann. The Dining Cryptographers in the Disco: Unconditional Sender and Recipient Untraceability with Computationally Secure Serviceability. Advances in Cryptology - EUROCRYPT, 89:10–13, 1989.
• M. Waidner. Unconditional Sender and Recipient Untraceability in spite of Active Attacks. Lecture Notes in Computer Science, 434:302, 1990.
• M Waidner, B Pfitzmann Unconditional Sender and Recipient Untraceability in Spite of Active Attacks: Some Remarks
• P. Golle and A. Juels. Dining Cryptographers Revisited. Advances in cryptology - EUROCRYPT 2004: International Conference on the Theory and Applications of Cryptographic Techniques, Interlaken, Switzerland, May 2-6, 2004: Proceedings, 2004.

158.64.77.254 (talk) 12:16, 12 June 2009 (UTC)

• Support merge. I'm not an expert here - I don't know much about cryptography - but it looks to me like we have here three articles covering substantially the same subject. Even if there are differences between them, they could all be covered sa part of one article. Robofish (talk) 00:49, 26 November 2009 (UTC)

Yao's Millionaires' Problem

It seems to me that any solution to Yao's Millionaires' Problem could also be used to solve the "Aging Cryptographers" problem, and vice versa. ("Aging Cryptographers" apparently was mentioned -- but alas, no solution given -- on an old version of the dining cryptographers problem, and currently lingers on at Wikipedia:WikiProject Computing/Dining cryptographers protocol/Rewrite).

I see that one editor claims that the "Aging Cryptographers" problem "does not exist". My internet searches support that claim -- I failed to turn up anything more on this problem. I still wonder if perhaps it is one of the many notable pieces of human knowledge that have not yet been published ("mathematical folklore"), or perhaps have been published but are not yet available online (WP:SOURCEACCESS).

Should this article on dining cryptographers mention and link to the Yao's Millionaires' Problem, or are they "not similar enough"? --DavidCary (talk) 18:03, 25 July 2012 (UTC)