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?



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.

  • $\begingroup$ In layman's terms what is information theoretic security? $\endgroup$
    – Turbo
    Jul 3 '15 at 17:19
  • $\begingroup$ @Turbo, it means security against a computationally-unbounded adversary (no limits on the amount of computation power that the adversary can bring to bear). $\endgroup$
    – D.W.
    Jul 3 '15 at 19:23
  • $\begingroup$ Sorry could you give an actual modern concrete example for this other than one time pad? $\endgroup$
    – Turbo
    Jul 3 '15 at 20:01
  • 1
    $\begingroup$ @Turbo : $\:$ en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing $\;\;\;\;$ $\endgroup$
    – user6973
    Jul 3 '15 at 23:17
  • $\begingroup$ 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? $\endgroup$
    – 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}$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.