2
$\begingroup$

According to this, a $n$-bit key offers about $n/2$ bits of security. That got me wondering, can you compress the key in half?

At first blush, no, because the key is essentially a random number, and so can not be compressed.

But let's look at relative to the public key. From an information theory standpoint, the private key has zero entropy relative to the public key.

So, given a $n$-bit private key $x$, can you produce a $n/2$ secret $s$, such that using $s$ and the public key $X$, you can efficiently calculate the private key?

$\endgroup$
  • $\begingroup$ Can you confirm that in the question, the $n$ bit private key $x$ is fully random and a given generated before $s$ is? I ask because it is much easier to define a safe way to generate $x$ from $s$. $\endgroup$ – fgrieu Sep 16 '16 at 15:25
  • 1
    $\begingroup$ @fgrieu yes. I know what your talking about (letting x equal a hash of s), but I'm talking about random x. $\endgroup$ – PyRulez Sep 16 '16 at 15:26
  • 1
    $\begingroup$ It's pretty obvious how to create an $s$ which will allow you to recover $x$ in $O(2^{n/4})$ time; however that's hardly efficient... $\endgroup$ – poncho Sep 16 '16 at 15:49
  • $\begingroup$ What do you mean by "the private key has zero entropy relative to the public key"? Do you mean the conditional distribution? $\endgroup$ – pg1989 Sep 17 '16 at 3:24
  • $\begingroup$ Also, it seems unlikely that you could construct an efficient algorithm to do what you're asking that wouldn't also be a generic attack on the elliptic-curve discrete logarithm problem. $\endgroup$ – pg1989 Sep 17 '16 at 3:27
1
$\begingroup$

Fix a curve $E$ and a standard base point $G$ of order $\ell \approx 2^{256}$. Let $n \in \mathbb Z/\ell\mathbb Z$ be a uniform random secret scalar, and let $P = [n]G$ be the corresponding public key. If you store the 128-bit quantity $\tilde n = \lfloor n/2^{128}\rfloor$ alongside the 256-bit quantity $P$, you can recover $n$ by applying Pollard's kangaroo (paywall-free) to $P$ to find $n$ in the interval $[2^{128} \cdot \tilde n, 2^{129} \cdot \tilde n]$, at cost ${\sim}2^{64}$.

But now you have to store a 384-bit quantity $(\tilde n, P)$ and spend $2^{64}$ cycles on Pollard's kangaroo to decompress $n$, instead of storing a 256-bit quantity $n$ and spending ${\sim}2^{16}$ cycles on a scalar multiplication to decompress $P$ (if you need $P$ at all). So it is hard to imagine how this is an advantage.

$\endgroup$
1
$\begingroup$

This isn't the direction you were thinking of, however I believe that this is an answer to the question you meant to ask:

According to this, a $n$-bit key offers about $n/2$ bits of security. That got me wondering, can you compress the key in half?

One obvious approach would be to pick an $n/2$ bit secret $s$, and store that as your long term private key; then, when you're ready to start using it, you first compute $\text{SHAKE}(s, u)$ (where $u$ is some public identifier string [1]), and use the first $n$ bits of that as your private multiplier (which we'll call $t$, and so your public key is $tG$)

It would appear that the attacker has two possible approaches against this:

  • Brute force $s$; expected effort $O(2^{n/2})$

  • Use a discrete log algorithm to recover $t$ (which is just as good as $s$ to the attacker); expected effort $O(2^{n/2})$

It doesn't appear that there is a viable attack that combines these two; you can't tell if a potential multiplier is a possible value of $t$ without brute-forcing SHAKE; once you do that, you might as well stick with attack one.


[1]: We insert $u$ in the SHAKE call to try to avoid multi-key attacks (where an attacker is given a number of public keys, and tries to recover the private key for any one of them); it's analogous to the salt in password hashing.

$\endgroup$

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.