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

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2015-07-03T17:19:55.413Z
In layman's terms what is information theoretic security?
Turbo
CC BY-SA 3.0
2015-07-03T19:23:22.210Z
@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.
CC BY-SA 3.0
2015-07-03T20:01:13.807Z
Sorry could you give an actual modern concrete example for this other than one time pad?
Turbo
CC BY-SA 3.0
2015-07-04T08:04:19.540Z
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
CC BY-SA 3.0
2015-07-02T23:10:12.983Z
2015-07-02T23:10:12.983Z
D.W.
<p>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.</p>

<p>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.</p>

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

<ul>
<li>In a fine way using an upper-bound and lower-bound oracle.</li>
<li>In one coarse form by using an upper-bound oracle.</li>
<li>In another coarse form by using a lower-bound oracle.</li>
</ul>

<p>Is there any literature on this?</p>

<p>Cheers</p>

<cc.complexity-theory><computability><cr.crypto-security><it.information-theory>
Information-theoretic Diffie-Hellman
wlad
# Information-theoretic Diffie-Hellman

(Asked by: username_0 on 2015-07-02)

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

**Tags:** cc.complexity-theory, computability, cr.crypto-security, it.information-theory

---

## 1 answers

### Answer by username_1 on 2015-07-02. Score: 5

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.

> **Comments:**
> **username_2**: In layman's terms what is information theoretic security?  
> **username_1**: @Turbo, it means security against a computationally-unbounded adversary (no limits on the amount of computation power that the adversary can bring to bear).  
> **username_2**: Sorry could you give an actual modern concrete example for this other than one time pad?  
> **username_2**: 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?  

---

