4
$\begingroup$

Could someone explain to me in few lines (even one sentence) what Miller's algorithm computes?

Without talking about divisors and all the other concepts, I would like to be able to explain it to someone who doesn't necessarily know elliptic curve cryptography in details but understands the basics because it's a really abstract concept.

Like what is the value returned by the Miller's function and why use this function ?

$\endgroup$
  • $\begingroup$ Is this the algorithm you are talking about? $\endgroup$ – Hilder Vítor Lima Pereira Sep 3 '18 at 10:48
  • $\begingroup$ what is the name of algorithm you ask? is it "Short Programs for functions on Curves" $\endgroup$ – R1w Sep 4 '18 at 10:07
  • $\begingroup$ @HilderVitorLimaPereira Yes it's the one $\endgroup$ – user1990088 Sep 5 '18 at 12:45
3
+50
$\begingroup$

Miller's algorithm maps two points in a elliptic curve into a element of a finite field. So, if you have a point $P$ and a point $Q$, then Miller's algorithm (which we'll denote $e$) will compute some value $r \leftarrow e(P, Q)$, where $r$ is a finite field element.

Recall that points can be added (e.g. $T \leftarrow P + Q$) and multiplied by a integer (e.g. $T \leftarrow kP$, which is just repeated addition), while finite field elements can be multiplied (e.g. $t \leftarrow pq$) and raised to the power of an integer (e.g. $t \leftarrow p^k$, which is just repeated multiplication).

The crucial property of Miller's algorithm is bilinearity. Assume that you have points $P$ and $Q$ and integers $a$ and $b$, and compute the points $R \leftarrow aP$ and $S \leftarrow bQ$. Then, if you compute Miller's algorithm for $P$ and $Q$:

$x \leftarrow e(P, Q)$

and for $R$ and $S$:

$y \leftarrow e(R, S) = e(aP, bQ)$,

then these values will be related with:

$y = x^{ab}$.

In other words, bilinearity means that:

$e(aP, bQ) = e(P,Q)^{ab}$.

The bilinearity property allows the construction of cryptographic protocols which were not possible before or too complicated: identity-based cryptography, short signatures, non-interactive key agreement, and so on.

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