On Kummer Lines with Full Rational 2-torsion and Their Usage in Cryptography

Abstract

A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus 1 by observing that their SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this article we extend this work and significantly simplify the treatment of Karati and Sarkar. We show that their Kummer line is the x-line of a Montgomery curve translated by a point of order two and exhibit a natural isomorphism to the y-line of a twisted Edwards curve. Moreover we show that the Kummer line presented by Gaudry and Lubicz can be obtained via the action of a point of order two on the y-line of an Edwards curve. The maps connecting these curves and lines are all very simple. As a result a cryptographic implementation can use the arithmetic that is optimal for its instruction set at negligible cost.