2

I'm going through a Coursera cryptography class, and there appeared an interesting (and currently open) problem about extension of Diffie-Hellman protocol to multiple parties, while preserving the property of non-interactivity (i.e. no need for any exchange of information except the value $g^{a_{party}}$, which is a property of DH).

While I'm in no way a great mathematician, I decided I'd still try to think on this problem a bit. I have a feeling that the general construction is not secure, and try to build proof-by-contradiction for it.

Not going into details, I've broken down the problem to the following conditions:

We have some irreversible function $f(x)$ (i.e. for which a prototype $x$ can't be obtained from known $f(x)$) and a following function $F_f$:

\begin{align} \forall i,j \in [1,n], \; n \in \mathbf{N}, &\; n>2, \; a_i \in \mathbf{R}:\\ F_f(a_i,f(a_1),\ldots,f(a_{i-1}),f(a_{i+1}),\ldots,f(a_n)) &= F_f(a_j,f(a_1),\ldots,f(a_{j-1}),f(a_{j+1}),\ldots,f(a_n));\\ F_f(\ldots,f(a_i),f(a_j),\ldots) &= F_f(\ldots,f(a_j),f(a_i),\ldots) \end{align}

My question is: what can be inferred from such properties of function $F$? Can it be proven that given the $F_f$ we somehow can "break" the irreversibility of function $f$?

It's a completely open-ended question without a definite answer, I'm just looking for ideas.

DarkWanderer
  • 121
  • Your conditions look a bit abstract to me. Would you mind giving an example of what the $f$, $F_f$, $a_i$ would be in normal, two-party Diffie-Hellman? – TMM May 12 '13 at 12:25
  • In case of normal Diffie-Hellman, $f(x) = g^x\mod{p}$, and $F_f(a_1,f(a_2)) = f(a_2)^{a_1}\mod{p} = g^{a_1*a_2}\mod{p}$ (we assume that $g$ is "globally" fixed). So, regardless of order of passing $a_1,a_2$ to $F_f$ we get the same key for both parties. – DarkWanderer May 12 '13 at 12:32
  • Sorry for many edits, didn't quite got hold of TeX syntax :) – DarkWanderer May 12 '13 at 12:44
  • Alright, so $F_f(a_1, f(a_2)) = f(a_2)^{a_1} = f(a_1)^{a_2} = F_f(a_2, f(a_1))$. But how would you begin defining $F_f(a_1, f(a_2), f(a_3))$? And why do you think it holds that knowing $F_f$ allows us to break the irreversibility of $f$? (In the case of $n = 2$, we know what the function $F_f(a,b) = b^a$ is, yet we cannot compute $x$ from $g^x$.) – TMM May 12 '13 at 12:53
  • That's exactly what I'm trying to find out. I have an intuition that this mix-up property ($F(a_1,f(a_2),f(a_3)) = F(a_1,f(a_3),f(a_2))$, which obviously cannot be formulated for DH where $n = 2$) will allow to break the abstract protocol. So, basically, I'm trying to build a proof by contradiction for abstract protocol defined by $f$ and $F_f$. – DarkWanderer May 12 '13 at 13:03
  • Building the exact pair $f,F_f$ is also out of question, obviously. Forgot to add also that I'm looking for proof on non-interactive protocols only, i.e. where there can be no exchange between parties except "posting" some derived values $f(a_i)$ to public source (noninteractivity being the main property of DH). I'll edit the question. – DarkWanderer May 12 '13 at 13:08
  • m.se is for closed-ended questions with definite answers. – Gerry Myerson May 12 '13 at 13:12
  • 1
    This is already answered over on Crypto.se. – mikeazo May 13 '13 at 12:43
  • @mikeazo: Not this one exactly :) The protocol in the answer you linked is interactive (it can't be used e.g. by posting the exchange messages on Facebook, like DH allows). I'm looking strictly at non-interactive protocols, hence my formulation. – DarkWanderer May 15 '13 at 06:53
  • @GerryMyerson feel free to report it if you think so... – DarkWanderer May 15 '13 at 06:53
  • 1
    @DarkWanderer I stand corrected. Crypto.SE might be a better place for this question. I'll let you decide. As you say it is kind of open ended w/o a definitive answer. I can't predict how the community there will react to the question. – mikeazo May 15 '13 at 11:26
  • Yes, I just thought the math community is a better place for a question reduced to purely mathematical form. Thank you for the hint, regardless. Maybe I'll try. – DarkWanderer May 16 '13 at 14:52

0 Answers0