Assume you have some source of $\mathsf{Bern}(1/2)$'s (probably some CSPRNG in practice). What is generally done to sample from $\mathsf{Unif}([d])$ in a side-channel resistant way (assuming $d$ isn't a power of 2)?

For the power of 2 case, it seems clear that you can generate $t = \log_2(d)$ random bits and interpret them as an integer. While I'm sure the implementation must be more careful than this, this seems algorithmicly rather straighforward.

For the non-power of 2 case, you could simply set $t = \lceil \log_2(d)\rceil$, then rejection-sample from $\mathsf{Unif}([2^t])$. This seems like it should be side-channel resistant as well (when you reject you leak information, but you also throw away the randomness the adversary knows information about). The downside of this is that (in expectation) it requires (up to) twice as many random bits used, if $d = 2^t + 1$ for some $t$. This will still be $O(\log_2(d))$ random bits, so asymptotically it's optimal, but it definitely feels like it could be improved.

So my question is essentially if anything better is known/used (either in the literature, or in practice).

  • $\begingroup$ This answer looks like it's relevant, although I'd like to avoid the additive increase in entropy usage of $64$. $\endgroup$
    – Mark
    Aug 2 '19 at 0:14

Off the top of my head, here's a somewhat more efficient rejection sampling algorithm. It involves maintaining a (possibly non-secret) bit counter $k$ and a secret $k$-bit value $0 ≤ s < 2^k$.

  • Initially, let $k = 0$ and $s = 0$.
  • To sample a uniform integer $x$ from $\{0, \dots, d-1\}$ for a given upper bound $d$:

    1. Let $t = \lceil \log_2 d \rceil$ and $g = 2^t - d$.
    2. If $t > k$, generate a uniformly distributed random $t - k$ bit number $z$ and let $r = s + 2^kz$; else let $r = s \bmod 2^t$. (That is, we take $r$ to be the lowest $t$ bits of $s$, adding extra random bits at the top if needed.) Now $r$ is uniformly distributed on $\{0, \dots, 2^t-1\}$.
    3. If $r ≥ g$, update $k \leftarrow \max(0, k - t)$ and $s \leftarrow \lfloor s \mathbin/ 2^t \rfloor$ and return $x = r - g$.
    4. Else let $h = \lfloor \log_2 g \rfloor$. If $r ≥ 2^h$, subtract $2^h$ from both $r$ and $g$ and repeat this step. (In other words, while $g$ and $r$ have the same highest set bit, clear that bit and repeat. This process will eventually stop, since we know that $0 \le r < g$; it's not hard to show that clearing the highest bit preserved this invariant, and that $r$ is always uniformly distributed on $\{0, \dots, g-1\}$.)
    5. (Now $r$ is uniformly distributed on $\{0, \dots, 2^h-1\}$.) Update $k \leftarrow h + \max(0, k-t)$ and $s \leftarrow r + 2^h \lfloor s \mathbin/ 2^t \rfloor$ and repeat from step 1.

Note that I'm assuming that we can do comparisons and basic arithmetic (i.e. addition, subtraction and bit shifts) on secret values without leaking any information about them (other than the result of the comparison).

Basically, the idea is to split the interval $\{0, \dots, g\}$ of rejected values into a sum of intervals of power-of-two sizes (which can be conveniently obtained from the binary expansion of $g$), find out into which of these intervals the rejected sample belongs to, and add that many bits of randomness from the rejected sample back into the entropy pool $s$.

(In particular, note that the number of bits in the entropy pool $s$ is always strictly less than the length of the longest requested value. In particular, if $d$ is constrained to be at most $2^n$, then an $n$-bit integer variable can be safely used to store $s$.)

  • $\begingroup$ Do you have a reference for this type of side-channel attack or protection? This is one of the few times that I have read a question and answer and really had no idea what was going on. :/ $\endgroup$
    – b degnan
    Aug 2 '19 at 2:01
  • $\begingroup$ @bdegnan The question can be restated as "How can you sample from $\mathsf{Unif}([d])$ in the FaCT Programming Language", so reading the introduction + abstract of that should be useful for the protection (here against timing and cache attacks) side of things. $\endgroup$
    – Mark
    Aug 2 '19 at 2:10
  • $\begingroup$ @Mark Thanks for the reference. $\endgroup$
    – b degnan
    Aug 2 '19 at 14:07

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.