5
$\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$
3
  • $\begingroup$ Is this the algorithm you are talking about? $\endgroup$ Commented Sep 3, 2018 at 10:48
  • $\begingroup$ what is the name of algorithm you ask? is it "Short Programs for functions on Curves" $\endgroup$
    – R1w
    Commented Sep 4, 2018 at 10:07
  • $\begingroup$ @HilderVitorLimaPereira Yes it's the one $\endgroup$ Commented Sep 5, 2018 at 12:45

1 Answer 1

5
+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 and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.