1
$\begingroup$

While reading up for a question on Cryptography.SE I stumbled across quite a complex equation approximating the bias of a "down-sampling" function. The original paper is "The Security of DSA and ECDSA Bypassing the Standard Elliptic Curve Certification Scheme" by Vaudenay (PS).

The question on Crypto.SE has a full quote of the relevant section, but I will re-state things here.

Suppose we have a prime $q\in\mathbb P$ from the interval $[2^{N-1},2^{N})$. Suppose further we have an integer $k\in\mathbb N$, that is uniformly, randomly sampled from the range $[0,2^N)$. Now suppose we construct $\mathbb N\ni k'=k\bmod q$, obviously "all the numbers larger than $q$ get wrapped around" which means that the probability that $k'\in[0,N-q]$ is double as high as for the rest of the interval $[0,q)$.

Now the paper states that this leads to the bias $$E\left(e^{\frac{2i\pi k}q}\right)\approx \frac{q e^{i\pi\frac{N-1}q}}{\pi N} \times \sin\left(\frac{\pi N}q\right)$$

My question is "simple":
From the above definitions, how do we arrive at this approximation?

$\endgroup$
2
$\begingroup$

(Sorry for the late answer. I stumbled across this question while searching for a different paper)

This is a straightforward application of the sum of complex exponentials. E.g. here

Suppose $N > q$ and $k$ is uniformly distributed on $[0, N)$, i.e. $P(k=j) = \frac{1}{N} \forall j \in [0,N)$. Then the bias term \begin{align} E\left(e^{\frac{i2\pi k}{q}}\right) & = \sum_{j=0}^{N-1}P(k) e^{\frac{i2\pi k}{q}} \\ & = \frac{1}{N}\sum_{j=0}^{N-1}e^{\frac{i2\pi k}{q}} \\ & = \frac{1}{N} \frac{1-e^{\frac{i2\pi N}{q}}}{1-e^{\frac{i2\pi}{q}}} \\ & = \frac{1}{N} \frac{ e^{\frac{i\pi N}{q}}(e^{-\frac{i\pi N}{q}}-e^{\frac{i\pi N}{q}})}{e^{\frac{i\pi}{q}}(e^{-\frac{i\pi}{q}}-e^{\frac{i\pi}{q}})} \\ & = \frac{1}{N} \times e^{ i\pi \frac{N-1}{q}} \times \frac{\sin(\frac{\pi N}{q})}{\sin(\frac{\pi}{q})}\\ & \approx \frac{q e^{i\pi\frac{N-1}q}}{\pi N} \times \sin\left(\frac{\pi N}q\right) \end{align} where the last approximation uses $\sin x \approx x$ for $x \rightarrow 0$. This will be the case if $q$ is large, as is typical for most cryptosystems.

Note that the wraparound is implicitly handled in the summation from $0$ to $N-1$, since for $j \geq q$, the complex exponential term wraps around as well.

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