0
$\begingroup$

Let $P$ and $Q$ are two points of NIST elliptic curve $E$ (defined over $F_{2^m}$ with prime $m$) and $k$ is a private key such that $k.P=Q$. Suppose $\ell$ be the number of bits in $k$, and let $k_i$ denote the $i$-th bit of $k$, so that $k=\sum\limits_{i=0}^\ell k_i \cdot 2^i$.

Given $\{(\sum\limits_{i=0}^{\ell-d+j} k_i \cdot 2^i) \cdot P | 0 \leq j\leq d\}$ , what is the minimum value of $d$ that with this set we can find $k$?

Improve this question
$\endgroup$
4
  • $\begingroup$ Isn't that the same as if we are simply given $\ell-d+j$ lowest bits of $k$, i.e., $k_0, k_1, \dots, k_{\ell-d+j}$ ? $\endgroup$
    – Max Alekseyev
    Commented Jan 16, 2016 at 5:47
  • $\begingroup$ @MaxAlekseyev, We have several $m'P$, so that $m'=\lfloor\frac{k}{2^t}\rfloor$. $\endgroup$
    – Meysam Ghahramani
    Commented Jan 19, 2016 at 12:57
  • $\begingroup$ This is confusing. I do not see any $m'$ in the original question. $\endgroup$
    – Max Alekseyev
    Commented Jan 20, 2016 at 3:13
  • $\begingroup$ @MaxAlekseyev, for fixed $j,d$ suppose $m'=(\sum\limits_{i=0}^{\ell-d+j} k_i \cdot 2^i)$. $\endgroup$
    – Meysam Ghahramani
    Commented Jan 20, 2016 at 11:22

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .