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