[Question edited at the request of Mods]

I recently became fascinated with the elegant and simple solution that Chaum proposed for the Dining Cryptographers problem. If you are unfamiliar, please checkout Wikipedia for a summary and solution.

What is interesting is that DC-Nets allow for participants in a group to share messages to the rest of the group anonymously. Wow! But there is a clear issue - two participants in a DC-Net cannot publish messages at the same time (what we call a collision).

So now I am trying to figure out a protocol that alleges to solve this problem by doing the following alterations to the original DC-net:

  • Let Alice, Bob and Carol be three participants in this DC-net A,B,C
  • Suppose that each participant has a shared secret to the right and to the left, such that |shared secret| = |message|
  • Alice hides her message by XORing with her two shared secrets. Call this encrypted message m_a. Bob and Carol do this same with m_b and m_c
  • All participants publish their respective messages in three slots. In the first slot they publish m, in the second $m^2$, and so forth (in the third $m^3$). These messages are interpreted as elements in a finite field and thus multiplication is done in this field.
  • These (encrypted) messages are then interpreted as finite field elements (not an extension field, but a prime field, to be specific) and they are added together according to the arithmetic operators defined by the finite field.
  • Once the three rounds are done, we are left with three power sums $S_1,S_2,S_3$. ($\sum_{i\in{1,2,3}}{m_i} = S_1, \sum_{i\in{1,2,3}}{m_i^2}= S_2, \sum_{i\in{1,2,3}}{m^3_i}= S_3, in \space \mathbb{F}$)

Here is where I get completely lost - the author claims that given these power sums and newtons identities, we can construct a polynomial and we are able to extract the un-encrypted messages! This is really baffling and would be incredible if true.

We construct a polynomial of the form: $a_3x^3+a_2x^2+a_1x^1+a_0$

$a_3 = 1 $

$a_2 = S_1$

$a_1 = \frac{(a_2S_1 - S_2)}{2}$

$a_0 = \frac{(a_1S_1 - a_2S_2 +S_3)}{2}$

Is anyone able to shed light on how powersum of encrypted messages over a finite field can be decrypted using polynomials and newtons identities, I am all ears. If this is too broad of a question, it can be closed.

(Solution is described on page 4) Paper

  • $\begingroup$ The question is too broad and can be closed. Please be more focused and describe what exactly is not clear. $\endgroup$
    – mentallurg
    Feb 16 '20 at 0:48
  • $\begingroup$ @mentallurg No, that's not the right way to go about it. You explain to the poster that the question is unclear and that it should be amended. Then you vote to close if you think it cannot be answered if left at this state. $\endgroup$
    – Maarten Bodewes
    Feb 17 '20 at 1:07
  • $\begingroup$ Maarten, thank you for letting me know. I will amend the question tomorrow morning and I will do my best to be more specific. $\endgroup$
    – A M
    Feb 17 '20 at 6:47

Your Answer

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

Browse other questions tagged or ask your own question.