[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 withm_b
andm_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