Kryptographisches Pairing: Verstehen der Multiplikation und Funktion

23.10.2017, 10:27

Shalec

Kryptographisches Pairing: Verstehen der Multiplikation und Funktion

[Vorbemerkung: Nachfolgend ist das Problem dargestellt und Stück für Stück weiter zurück geführt. Dabei habe ich versucht eine übersichtliche Unterteilung zu schaffen und alle notwendigen Informationen möglichst kurz darzustellen. ]

Hallo allerseits,

ich habe ein kleines Problem und bereits vor einer Weile (diesmal wirklich mehr als 24h her Big Laugh

) diese Frage auf Stackexchange [1] gepostet, und noch keine Antwort, trotz Bounty, erhalten. Es geht um das Optimal Ate Pairing. Genauer gesagt: Die Evaluierung der Produkte. Ich wiederhole mal die Stelle aus Stackexchange:

Zitat:

Consider the curve $\begin{align*} \newcommand{\F}{\mathbb F}E(\F_p):\ y^2=x^3+x \end{align*}$ and its quartic twist $\begin{align*} E'(\F_{p^4}):\ y^2= x^3+2^{1/4}x \end{align*}$ . For computing the optimal Ate pairing

$\begin{align*} e_{opt}:\ E(\F_p)[r]\times E'(\F_{p^4})[r]\cap Ker(\pi_p-p) \to \F_{p^{16}}\cap \mu_r,\quad (P,Q) \mapsto \left( (f_{u,Q}(P)\cdot l_{uQ,pQ}(P) )^{p^3} \cdot l_{Q,Q}(P) \right)^{\frac{p^{16}-1}{r}} \end{align*}$

where $\begin{align*} p \end{align*}$ is parameterized as a polynomial and evaluated at "u" as a prime. Furthermore, $\begin{align*} E[r] \end{align*}$ describes all points P on E, with $\begin{align*} rP=\mathcal O \end{align*}$ . $\begin{align*} Ker(\pi_p-p) \end{align*}$ is just a Eigenspace of $\begin{align*} \pi_p \end{align*}$ , the p-Frobenius.

Problem
Mein Problem ist vermutlich relativ grundlegender Natur: Ich verstehe nicht, über welchen Körper die Multiplikation definiert ist.

Die Potenzierung, d.h. der $\begin{align*} p^3 \end{align*}$ -Frobenius, ist über $\begin{align*} \F_{p^{16}} \end{align*}$ definiert. Demnach muss das Produkt $\begin{align*} f_{u,Q}(P)\cdot l_{uQ,pQ}(P) \in \F_{p^{16}} \end{align*}$ sein.

Beschreibung der Funktionen
$\begin{align*} f_{u,Q}(P) \end{align*}$ ist das Ergebnis der sog. Miller-loop [2, P.4 Table 2]. Hier ist z.B. nicht eindeutig klar, in welchem Körper $\begin{align*} f_1=1 \end{align*}$ gilt. Auch ist nicht ganz eindeutig klar, welchen Output die Funktion $\begin{align*} l_{A,B}(P) \end{align*}$ hat. Da der Output vermutlich ein $\begin{align*} \F_{p^{16}} \end{align*}$ Element sein wird, kann ich mir vorstellen, dass $\begin{align*} f_1 \end{align*}$ aus entsprechenden Körper kommt. Verbleibt also die Funktion $\begin{align*} l \end{align*}$

Beschreibung von $\begin{align*} l_{A,B}(P) \end{align*}$
Bei dieser Funktion handelt es sich um eine Gerade durch die Punkte $\begin{align*} A,B \in E' \end{align*}$ ausgewartet an $\begin{align*} P \end{align*}$ . Ausgabe ist eine Differenz von "y" und "x". (Vgl. meine ebenfalls unbeantwortete Frage [3] im Abschnitt "Question" Frage 1.) Da der Twist $\begin{align*} E' \end{align*}$ über $\begin{align*} F_{p^4} \end{align*}$ definiert ist, sind natürlich alle Koordinaten Elemente von $\begin{align*} \F_{p^4} \end{align*}$ .

Informationen zum Twist
Der Twist ist ein "quartic twist" von $\begin{align*} E(\F_{p^{16}}) \end{align*}$ . Entsprechend existiert ein Isomorphismus von $\begin{align*} \psi:\ E\to E' \end{align*}$ und sein Inverses.

Interpretation
Ich kann mir nun folgendes Vorstellen: Die Punkte von $\begin{align*} E(\F_{p^{16}}) \end{align*}$ werden über den Twist isomorph auf $\begin{align*} E'(\F_{p^4}) \end{align*}$ abgebildet, innerhalb dessen gerechnet und anschließend zurück abgebildet. Also wäre mein Vorgehen praktisch so: Ich berechne praktisch $\begin{align*} l_{\psi(A),\psi(B)}(P) \end{align*}$ allerdings sehe ich nicht, wie ich dadurch zurück auf $\begin{align*} E(\F_{p^{16}}) \end{align*}$ kommen soll, da ich $\begin{align*} \psi^{-1} \end{align*}$ nur auf die Punkte anwenden kann.

Ich bin für jeden Hinweis und jede Interpretation sehr dankbar. Auch wenn noch Informationen fehlen sollte, um diese Frage zu beantworten, werde ich mich bemühen alles notwendige zusammen zu tragen.

Quellen
[1] https://math.stackexchange.com/questions...ngs-optimal-ate

[2] https://eprint.iacr.org/2016/472.pdf

[3] https://math.stackexchange.com/questions...mal-ate-pairing

25.10.2017, 20:27

Shalec

Auf diesen Beitrag antworten »

Meine Theorie mit den Twists erhärtet sich. Ich werde in den kommenden 24h diesen Beitrag mit etwas Background editieren. Nochmal zur Verdeutlichung:
Frage: Ist $\begin{align*} l_{A,B}(P)\in \mathbb F_{p^{16}} \end{align*}$ ? Wenn ja, warum und wenn nein, warum nicht? Ich erwarte, dass es so ist, kann es aber nicht erklären unglücklich

27.10.2017, 10:18

Shalec

Auf diesen Beitrag antworten »

Ich habe praktisch die Frage gelöst. Es liegt an dem Twist. Ich weiß noch nicht so recht, an welcher Stelle ich den Twist anwenden muss. Ich hätte intuitiv die Produkte ausgerechnet, den Isomorphismus angewendet und dann addiert. Theoretisch kann ich aber auch noch vorher addieren und dann den Isomorphismus anwenden. Aber hier geht es wieder um die Feinheiten, die ich mir (noch) nicht erklären kann.

05.11.2017, 13:40

Shalec

Auf diesen Beitrag antworten »

Ein Twist ist ein Isomorphismus. Anhand dessen lassen sich alle Punkte von $\begin{align*} \newcommand\F[1]{\mathbb F_{p^{#1}}} E(\F{16}) \end{align*}$ auf $\begin{align*} E'(\F4) \end{align*}$ vereinfachen. Folglich ist klar, dass jede Operation zur Berechnung der Geraden zwischen A und B ausgewertet an P, eben Operationen über $\begin{align*} \F4 \end{align*}$ sind. Damit ist das Ergebnis $\begin{align*} l_{A,B}(P)\in\F4 \end{align*}$ .

Der Output der Miller-Loop $\begin{align*} f_{u,Q}(P)\in \F{16} \end{align*}$ . Wie also, definiere ich eine Multiplikation zwischen $\begin{align*} \F4 \end{align*}$ und $\begin{align*} \F{16} \end{align*}$ ? Über die natürliche Einbettung?

Weiteres Problem: Innerhalb der Miller-Loop (Ich wiederhole sie mal smile

Input: $\begin{align*} Q\in E'(\F4),\ P\in\F{} \end{align*}$ und ein bestimmtes $\begin{align*} u\in\mathbb N \end{align*}$ , von dem die Darstellung zur Basis 2 mit positiven und negativen Vorzeichen bekannt ist. Sei n die höchste Potenz dieser Darstellung: $\begin{align*} u=\sum_{k=0}^n u_k 2^k, u_i\in\{ -1,0,1\} \end{align*}$

Output: $\begin{align*} f_{u,Q}(P) \end{align*}$

Prozedur:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:

f\gets 1, R\gets Q
for k=n-1 down to 0 do
    f \gets f^2 \cdot l_{R,R}(P), R\gets 2R
    if ui == 1 then
        f\gets f\cdot l_{R,Q}(P), R\gets R+Q
    elif ui == -1 then
        f\gets f\cdot l_{R,-Q}(P), R\gets R-Q
endfor
return f

man sieht, dass hier (in keiner mir bekannten Ausführung dieses Algos) recht schwammig präzisiert wird. $\begin{align*} f\gets 1 \end{align*}$ stellt mich vor die Frage: welche 1? $\begin{align*} 1\in \F{16}? \end{align*}$ Das würde als einziges für mich Sinn machen.
Nun multipliziere ich dort aber auch mit einem $\begin{align*} \F4 \end{align*}$ Element, welches zur obigen Frage (erneut) führt: Wie definiere ich diese Multiplikation?

Den Rest habe ich für mich erschlossen. Hat jemand hierfür einen Vorschlag? Nutze ich einfach die natürliche Einbettung?

12.11.2017, 16:39

Shalec

Auf diesen Beitrag antworten »

Die Antwort ist unerwartet blöd.

Es ist $\begin{align*} \newcommand\F{\mathbb F}1\in\F_{p^{16}} \end{align*}$ und $\begin{align*} l_{A,B}(P)\in\F_{p^4}\hookrightarrow \F_{p^{16}} \end{align*}$ . Dadurch muss man sich eben eine "dünnbesetzte" Multiplikation zweier $\begin{align*} \F_{p^{16}} \end{align*}$ Elemente definieren. D.h. man nutzt den Twist nur in eine Richtung und bleibt dann dort einfach.

So eine Sparse-Multiplikation habe ich momentan eher blöd als schlau realisiert. Mein Vorgehen:

Sagen wir: $\begin{align*} A\in\F_{p^{16}}, B\in\F_{p^{4}} \end{align*}$ , dann:
Zerlege A in vier gleichgroße Blöcke (praktisch: low low, low high, high low und high high), wende auf jeden Block die Karazuba Multiplikation über $\begin{align*} \F_{p^4} \end{align*}$ an, jedoch ohne Reduktion. Wenn ich mir das als Arrays vorstelle: Jeder Array hat als Input 4 Einträge, Output sind dann 7 ( $\begin{align*} A_kB \end{align*}$ ). Danach werden die vier Return-Arrays jeweils zur Basis b^{4k}, k=0,1,2,3, addiert. Damit erhalte ich einen großen Array mit 19 Einträgen, welcher nun modulo dem definierenden Polynom von $\begin{align*} \F_{p^{16}}=\F_p[x]/(x^{16}-\alpha) \end{align*}$ reduziert wird.

Dabei prüfe ich an keiner Stelle, wie viele Multiplikationen für A überhaupt notwendig sind. (blöder Ansatz) Nun..ein Test ließe sich realisieren: Jeder 0-Block returnt einen 0-Block.

Neue Frage »

Antworten »

Kryptographisches Pairing: Verstehen der Multiplikation und Funktion

Verwandte Themen