Boneh's and Venkatesan's "Hardness of computing the most significant bits of secret keys in Diffie-Hellman and related schemes" defines the Hidden Number Problem (HNP). The HNP shows that computing the most significant bits of a Diffie-Hellman shared secret is as hard as computing the entire secret.

The paper defines the function $MSB_{k}(x)$ which I originally interpreted to be the $k$ of $x$ most significant bits (e.g. $MSB_{2}(13)$ should be $11_{2}$). However, the paper uses the following definitions:

Given a prime $p$, we define $MSB_{k}(x)$ as the integer $t$ such that $\left(t - 1\right) \cdot \frac{p}{2^{k}} \leq x \lt t \cdot \frac{p}{2^k}$.

For convenience we will sometimes assume that $MSB_{k}(x)$ is an integer $z$ satisfying $|x - z| \lt \frac{p}{2^{k+1}}$.

I'm struggling with these definitions for a few reasons:

  • These inequalities can have a set of possible solutions but the $k$ most significant bits of $x$ should just be a single $k$ bit solution.
  • These definitions rely on a prime $p$ but $x$'s most significant bits are independent of $p$.

From my research it sounds like these definitions are a bit more "flexible" then the definition that I have in mind but I don't intuitively grasp how the flexible definitions relate to the definition have in mind.


Imagine you are working modulo the prime $p = 2^{255}+95$. Knowing the most significant bit, in the usual sense, of values modulo $p$ gives you almost no useful information—it's virtually always $0$. Knowing the $k$ most significant bits, in the usual sense, gives you roughly $k-1$ bits of information.

For the results to make sense over arbitrary prime fields, one thus needs a definition of most significant bits that is not affected by such quirks, and that's there the weirder definition of $\mathrm{MSB}_k$ comes in, which might be better understood as "suppose you know $k$ bits of information about $x$".

|improve this answer|||||

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.