0
$\begingroup$

When I frist read about the famous dining cryptographers problem, in a book years ago I remember the author made a twist on it, demonstrating the generalization of the problem.

Basically the dining cryptographers wanted to know who has the best income. But since they all worked for secret agencies, they were not allowed to tell each other. So they had a system where they would write their income down in some order without giving away information to their sitting neighbors on what their income is. I'm unable to recall the way that system worked and I can't remember what book it was.

I was hoping somebody recalls this twist on the problem or the book.

$\endgroup$
  • 1
    $\begingroup$ Socialist millionaires? $\endgroup$ – Squeamish Ossifrage Apr 19 at 18:37
  • $\begingroup$ @SqueamishOssifrage that sounds very similar but it only outputs information if x=y but not what's the highest value in a scenario where the no. of actors is >2. But, if I remember correctly, that was true for the variant I'm looking for. basically the idea was to not know what the predecessor wrote down and, of course, it only works with more then two actors. $\endgroup$ – masi Apr 19 at 19:00
  • 2
    $\begingroup$ Correction: Mere millionaires problem, not socialist millionaires problem. MP was introduced by Yao in 1982, and various approaches are discussed in the Wikipedia article; SMP was a later variant for testing equality rather than ordering. $\endgroup$ – Squeamish Ossifrage Apr 19 at 21:35
  • $\begingroup$ Well, it's not that either. The 'millionaires problem" is limited to two parties, at least in that form shown. Also it's output is only a boolean value (greater then true/false, equal true/false, less then true/false) as far as I understood it, but it's not actually a value. I'm aware that, since we can pass a bit, we could repeat this an thus pass any information. But the approach I read about was more practical, resulting in a multi-digit ouput ("who has the biggest income and how big is it") with just a handfull of tasks performed by each (>2) participent at the table. $\endgroup$ – masi Apr 21 at 10:24
0
$\begingroup$

I believe I found the reference I was looking for. I believe it's from the book 'Einführung in die Kryptographie' from Albrecht Beutelspacher, Jörg Schwenk and Klaus-Dieter Wolfenstetter, published by Springer. I read it back in college.

In chapter 5.2 on 'Multiparity Computations' they talk about 'Wer verdient mehr' ('who earns most'). The idea is that in a multi-party with >2 participents one of them (Alice) starts by adding their income, i_1, to a random number r, writes it down on a note and passes that note around. Everybody else then adds their income i_n to the number. Once the note arrives back at Alice, Alice then can subtract the random number r and is able to compute the average income of the round, so they can compare if their income is above or below average without exposing any other information. Of course this only works if all participents answers are trustworthy.

A interesting approach. But I was wrong with my assumtion that it had anything to do with the 'dining cryptographers' problem.

$\endgroup$
  • 1
    $\begingroup$ Koblitz presents something similar in Algebraic Aspects of Cryptography (pp. 11-12); it is a common idea. $\endgroup$ – fkraiem Apr 21 at 11:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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