# Simple explanation of Miller's algorithm

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 ?

• Is this the algorithm you are talking about? Commented Sep 3, 2018 at 10:48
• what is the name of algorithm you ask? is it "Short Programs for functions on Curves"
– R1w
Commented Sep 4, 2018 at 10:07
• @HilderVitorLimaPereira Yes it's the one Commented Sep 5, 2018 at 12:45

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.