Talk:Yao's Millionaires' problem

Cryptography: Computer science Low‑importance

	This article is within the scope of WikiProject Cryptography, a collaborative effort to improve the coverage of Cryptography on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.CryptographyWikipedia:WikiProject CryptographyTemplate:WikiProject CryptographyCryptography articles
Low	This article has been rated as Low-importance on the importance scale.
	This article is supported by WikiProject Computer science (assessed as Low-importance).

Sources

This value lacks sources, and it seems like the structure is slightly off as well. Tali.g (talk)

Easier to Explain?

OT can be expanded from 1 out of 2 to 1 out of n. Alice makes a list of salaries and the words 'higher' or 'lower', based on whether those salaries would be higher or lower than hers. Using OT, Bob requests the row associated with his salary level. Without Alice knowing which row Bob selected, he reveals whether the row replied that his salary was 'higher' or 'lower' than Alice's. Bob tells Alice the result. Maybe Alice includes a nonce with the options, like 'higher tiger' and 'lower moon', and Bob confirms by providing the correct nonce. (Of course, higher and lower could be represented by the final bit in a binary string, and the rest of the string could be the verifying nonce.)

The two have to pick a starting granularity, which trades precision for complexity. Low precision with multiple clarifying rounds might be a possibility to increase speed...

This may be considerably more complex than the protocol provided, I'm no good at complexity theory. —Preceding unsigned comment added by 204.87.16.4 (talk) 14:20, 12 May 2011 (UTC)[reply]

Inaccurate External Reference

The external reference talks about Alice and Bob's hourly wage. It says Bob sends 4 lock boxes to Alice, labeled $10/hr, $20, $30, and $40. He has the key only to the $20/hr box because that is the rate he earns. When Alice receives the boxes, she inserts slips of paper, "no," "no," "yes," and "no" into them, respectively, indicating that she makes $30/hr. When Bob receives the boxes back, he unlocks the $20/hr one, sees the "no" slip, and concludes Alice does not make the same money as he does.

In a true "millionaire's" implementation, both Alice and Bob learn the same answer at the same time, independent of one another. In this link, only Bob learns the answer, and Alice relies on him to tell her. This is not how the protocol is supposed to work.

There may be a way to fix this with Alice using pre-committed code numbers instead of simple "yes/no," but it would require an extra protocol step where Bob shares the code he received to Alice. Then again, if Alice has full knowledge of the codes, she would learn exactly how much Bob makes.

I don't mean to trash the author(s) of the external link, because this stuff is tricky to get right. (Additionally, they convey the correct idea of oblivious transfer.) I just want to caution others not to rely on it as an accurate and complete model. — Preceding unsigned comment added by 100.36.66.167 (talk) 13:03, 27 July 2018 (UTC)[reply]

More importantly, the external reference talks about the Socialist millionaire problem, not this problem. Macoroni (talk) 02:44, 12 December 2021 (UTC)[reply]

I'll just remove it, to avoid confusing anyone. Macoroni (talk) — Preceding undated comment added 02:46, 12 December 2021 (UTC)[reply]

Mandatory condition

Millionaires should solve their problem without using trusted third party otherwise solution is possible without using such complicated protocols. E.g third party is Eve. Alice and Bob generate some random value R together. Then Alice sends (a + R) to Eve, Bob sends (b + R) to Eve and then Eve compares numbers and announces result. This condition at least should be slightly mentioned in the article. Any objections? — Preceding unsigned comment added by 178.205.44.82 (talk) 18:22, 29 May 2023 (UTC)[reply]

Needs to be rewritten in an explanatory fashon.

The lede describes the problem, but the body does not describe the solution in a manner intelligible to a reader. Skepticalgiraffe (talk) 18:58, 7 October 2024 (UTC)[reply]

Agree. This article is crazy technical and incomprehensible to the average reader. I do competitive math but can't really understand this. Wildfireupdateman (talk) 17:34, 14 November 2024 (UTC)[reply]