# Understanding the Definition of Most Significant Bits in the Hidden Number Problem

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$$".