notes

Here are some notes that might help out someone someday. They are essentially small writings, mostly mathematical, that serve to exemplify a topic. They are not meant to be comprehensive, but rather to give a taste.

The Cokernel Pairing

We study a new pairing, beyond the Weil and Tate pairing. The Weil pairing is a non-degenerate pairing which operates on the kernel of the multiplication-by-m map. Similarly, when the m-th roots of unity are rational, the Tate pairing is a non-degenerate pairing which connects the kernel and the rational cokernel of the multiplication-by-m map. We define a pairing which operates directly on the rational cokernels of this map, filling the gap left by the Weil and Tate pairing. When the m-torsion is rational, this pairing is non-degenerate, and can be computed using three Tate pairings, and two discrete logarithms, given a basis for the m-torsion. When m = ell is a (small) prime, this pairing allows us to study the rational cokernel directly directly and simplifies the computation of a basis for the ell-power torsion, and more generally the Sylow ell-torsion. This finds many applications in isogeny-based cryptography when computing prime-power isogenies. note

Optimized Cubical Pairings of Degree 2 for Subgroup Membership Testing in Genus 2

In this short paper, we combine two new techniques in pairings to do subgroup membership testing for the Gaudry–Schost Kummer surface: showing that a point P is in the subgroup G of large prime order. First, we generalize Koshelev’s method for subgroup membership testing using Tate pairings to higher dimensions. Second, using Robert’s cubical arithmetic, we optimize degree-2 Tate pairings on Kummer surfaces. We verify P is in G using only 6 additions, 10 multiplications, and 4 Legendre symbols. note

The Advanced Use of the Tate Pairing

This short note explains how the Tate pairing can be used to efficiently sample torsion points with precise requirements, and other applications. These applications are most clearly explained on Montgomery curves, using the Tate pairing of degree 2, but hold more generally for any degree or abelian variety, or even generalized Tate pairings. This note is explanatory in nature; it does not contain new results, but aims to provide a clear and concise explanation of results in the literature that are somewhat hidden, yet are extremely useful in practical isogeny-based cryptography. note

Radical Isogenies on (Twisted) Edwards Curves

In this note, we try to find radical isogenies on twisted Edwards curves. We will do so by first looking at what radical isogenies are, and then look at how radical isogenies should work on twisted Edwards curves. Finally, by firing up a computer algebra system, we find the concrete radical isogeny formula for degree 3 on twisted Edwards curves. note

Number of Matrices of Given Rank over a Finite Field

It has long been known that one can count the number of matrices of given rank over a finite field using linear algebra. In this note, we try to give an argument based only on combinatorics instead. (todo)