# Information-theoretic Diffie-Hellman

The following non-standard description of Diffie-Hellman is entirely my own, by which I mean that I came up with it having not read about it anywhere else beforehand.

In Diffie-Hellman Alice and Bob choose numbers $x$ and $y$ in a fine representation and publish $x$ and $y$ in a coarser form from which they can both determine $xy$ in coarse form. A form is considered coarse if the product of two numbers in the coarse form is (practically) uncomputable, but the product of a number in the coarse form and another number in the fine form is computable.

So is there an information-theoretic analogue? My thoughts are that a number $x \in [0,1] \subset \Bbb R$ can be represented:

• In a fine way using an upper-bound and lower-bound oracle.
• In one coarse form by using an upper-bound oracle.
• In another coarse form by using a lower-bound oracle.

Is there any literature on this?

Cheers

No, there is no information-theoretic analog that is secure against computationally-unbounded adversaries.

To form an analog, we'd need an injection $\varphi$ that maps $x$ in fine representation to $x$ in coarse representation. But then Diffie-Hellman involves Alice sending $\varphi(x)$ publicly, and Bob sending $\varphi(y)$ publicly. An eavesdropper can see $\varphi(x),\varphi(y)$. Since $\varphi$ is an injection, information-theoretically this reveals $x,y$, which is enough to reveal the negotiated key.

What if we consider a function $\varphi$ that is non-injective? This doesn't help. Consider the equivalence relation $\sim$ where $x \sim x'$ if $\varphi(x)=\varphi(x')$, and let $[x]$ be the equivalence class of $x$. Then for the scheme to work, the negotiated secret has to depend only on $\varphi(x),y$, i.e., only on $[x],y$ (since Bob has to be able to compute it). Similarly, the negotiated secret has to depend only on $x,[y]$. It follows that the negotiated secret depends only on $[x],[y]$. Why? Let $f(x,y)$ denote the secret negotiated if Alice uses fine value $x$ and Bob uses fine value $y$. Suppose $x \sim x'$ and $y \sim y'$. Then since $[x]=[x']$, it follows that $f(x,y)=f(x',y)$ (since $f(x,y)$ depends only on $[x],y$). Also since $[y]=[y']$, it follows that $f(x',y)=f(x',y')$ (since $f(x,y)$ depends only on $x,[y]$). Therefore $f(x,y)=f(x',y')$ whenever $x=x'$ and $y=y'$. In other words, the final negotiated secret depends only on $[x],[y]$. However, the eavesdropper can observe $\varphi(x),\varphi(y)$, from which $[x],[y]$ are uniquely determined and thus the negotiated secret is uniquely determined and thus information-theoretically cannot be hidden from the eavesdropper.

Public-key exchange can only be secure computationally -- you can't achieve information-theoretically secure public-key exchange.

• In layman's terms what is information theoretic security? – Turbo Jul 3 '15 at 17:19
• @Turbo, it means security against a computationally-unbounded adversary (no limits on the amount of computation power that the adversary can bring to bear). – D.W. Jul 3 '15 at 19:23
• Sorry could you give an actual modern concrete example for this other than one time pad? – Turbo Jul 3 '15 at 20:01
• @Turbo : $\:$ en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing $\;\;\;\;$ – user6973 Jul 3 '15 at 23:17
• So you have two extremes. Unbounded capability and polynomial capability of adversaries. In the latter you have a PKC system. How about if adversary has intermediate capability? – Turbo Jul 4 '15 at 8:04

(This is a response to Turbo that wouldn't fit in a comment.)

An NP oracle is enough to break essentially all complexity-based cryptography, so if public-key cryptography (PKC) can be secure against polynomially-capable adversaries then $\mathrm{RP} \neq \mathrm{NP}$ (see definition of $\mathrm{RP}$). In particular, secure PKC is not known to be possible, even just against polynomially capable adversaries.

On the other hand, I think most cryptographers would expect, if they thought about it, that there is a PKE scheme such that

1. completeness holds with certainty, and
2. public keys for the same security parameter $k$ will certainty have the same length, and
3. ciphertexts for the same security parameter $k$ will with certainty give the same value to $\mathrm{length}(\mathrm{ciphertext}) - \mathrm{length}(\mathrm{plaintext})$, and
4. there is a positive real number $\epsilon$ such that even quantum adversaries with $2^{\lceil k^\epsilon\rceil}$ time and $2^{\lceil k^\epsilon\rceil}$ qubits of advice cannot distinguish public keys from random strings by more than $2^{-k^\epsilon}$, and
5. there is a positive real number $\epsilon$ such that even quantum adversaries which:

• have the public key and $2^{\lceil k^\epsilon\rceil}$ time, and
• $2^{\lceil k^\epsilon \rceil}$ qubits of advice, and
• can submit $2^{\lceil k^\epsilon\rceil}$ strings to the decryption oracle (which functions just like the in the IND-CCA2 experiment), and
• can use its responses to choose the plaintext

cannot distinguish ciphertexts from random strings by more than $2^{-k^\epsilon}$.