Connecting Legendre with Kummer and Edwards

Sabyasachi Karati; Palash Sarkar

doi:10.3934/amc.2019003

Article Contents

2019, Volume 13, Issue 1: 41-66. Doi: 10.3934/amc.2019003

This issue Previous Article The secrecy capacity of the arbitrarily varying wiretap channel under list decoding Next Article Wave-shaped round functions and primitive groups

Connecting Legendre with Kummer and Edwards

Sabyasachi Karati^1, , and
Palash Sarkar^2,

1.
iCIS Lab, Department of Computer Science, University of Calgary, Canada
2.
Applied Statistics Unit, Indian Statistical Institute, 203, B.T. Road, Kolkata, India

* Corresponding author
* Corresponding author

Received: January 2018

Revised: August 2018

Published: December 2018

Abstract Full Text(HTML) Figure(0) / Table(9) Related Papers Cited by

Abstract

Scalar multiplication on suitable Legendre form elliptic curves can be speeded up in two ways. One can perform the bulk of the computation either on the associated Kummer line or on an appropriate twisted Edwards form elliptic curve. This paper provides details of moving to and from between Legendre form elliptic curves and associated Kummer line and moving to and from between Legendre form elliptic curves and related twisted Edwards form elliptic curves. Further, concrete twisted Edwards form elliptic curves are identified which correspond to known Kummer lines at the 128-bit security level which provide very fast scalar multiplication on modern architectures supporting SIMD operations.

Keywords:

Mathematics Subject Classification: Primary: 58F15, 58F17; Secondary: 53C35.

Citation:

Full Text(HTML)

Table 1. Double and differential addition in the square-only setting

$\mathsf{dbl}(\mathsf{x}^2,\mathsf{z}^2)$	$\mathsf{diffAdd}(\mathsf{x}_1^2,\mathsf{z}_1^2,\mathsf{x}_2^2,\mathsf{z}_2^2,\mathsf{x}^2,\mathsf{z}^2)$
$\mathsf{s}_0 = \mathsf{B}^2(\mathsf{x}^2+\mathsf{z}^2)^2$;	$\mathsf{s}_0 = \mathsf{B}^2(\mathsf{x}_1^2+\mathsf{z}_1^2)(\mathsf{x}_2^2+\mathsf{z}_2^2)$;
$\mathsf{t}_0 = \mathsf{A}^2(\mathsf{x}^2-\mathsf{z}^2)^2$;	$\mathsf{t}_0 = \mathsf{A}^2(\mathsf{x}_1^2-\mathsf{z}_1^2)(\mathsf{x}_2^2-\mathsf{z}_2^2)$;
$\mathsf{x}_3^2 = \mathsf{b}^2(\mathsf{s}_0+\mathsf{t}_0)^2$;	$\mathsf{x}_3^2 = \mathsf{z}^2(\mathsf{s}_0+\mathsf{t}_0)^2$;
$\mathsf{z}_3^2 = \mathsf{a}^2(\mathsf{s}_0-\mathsf{t}_0)^2$;	$\mathsf{z}_3^2 = \mathsf{x}^2(\mathsf{s}_0-\mathsf{t}_0)^2$;
return $(\mathsf{x}_3^2,\mathsf{z}_3^2)$.	return $(\mathsf{x}_3^2,\mathsf{z}_3^2)$.

| Show Table

DownLoad: CSV

Table 2. Scalar multiplication on Kummer line using a ladder

$\mathsf{scalarMult}(\mathsf{P},n)$	$\mathsf{ladder}(\mathsf{R},\mathsf{S},\mathfrak{b})$
input: $\mathsf{P}\in{\mathcal K}_{\mathsf{a}^2,\mathsf{b}^2}$;	if ($\mathfrak{b}=0$)
$\ell$-bit scalar $n=(1,n_{\ell-2},\ldots,n_0)$;	$\mathsf{S}=\mathsf{diffAdd}(\mathsf{R},\mathsf{S},\mathsf{P})$;
output: $n\mathsf{P}$;	$\mathsf{R}=\mathsf{dbl}(\mathsf{R})$;
set $\mathsf{R}=\mathsf{P}$ and $\mathsf{S}=\mathsf{dbl}(\mathsf{P})$;	else
for $i=\ell-2,\ell-3,\ldots,0$ do	$\mathsf{R}=\mathsf{diffAdd}(\mathsf{R},\mathsf{S},\mathsf{P})$;
$(\mathsf{R},\mathsf{S})=\mathsf{ladder}(\mathsf{R},\mathsf{S},n_i)$;	$\mathsf{S}=\mathsf{dbl}(\mathsf{S})$;
return $(\mathsf{R},\mathsf{S})$.	return $(\mathsf{R},\mathsf{S})$.

| Show Table

DownLoad: CSV

Table 3. Some properties of the group of $\mathbb{F}_p$-rational points of the Legendre form elliptic curves $E_{1a}$, $E_{1b}$, $E_2$ and $E_3$

	$E_{1a}$	$E_{1b}$	$E_2$	$E_3$
$p$	$2^{251}-9$	$2^{251}-9$	$2^{255}-19$	$2^{266}-3$
$(\lg\ell,\lg\ell_T)$	$(248,248)$	$(248,248)$	$(251.4,252)$	$(262.4,263)$
$(h,h_T)$	$(8,8)$	$(8,8)$	$(12,8)$	$(12,8)$
$(k,k_T)$	$\left(\ell-1,\frac{\ell_T-1}{7}\right)$	$\left(\ell-1,\ell_T-1\right)$	$\left(\ell-1,\ell_T-1\right)$	$\left(\frac{\ell-1}{2},\ell_T-1\right)$
$\lg (-D)$	$246.3$	$249.8$	$255$	$266$
$\mathsf{KL}$ base pt	$[64:1]$	$[19:1]$	$[31:1]$	$[2:1]$

| Show Table

DownLoad: CSV

Table 4. Conversions from Kummer line to Legendre form elliptic curves and vice versa. Here $\alpha_0 = \mathsf{a}^2$ and $\alpha_1 = \mathsf{b}^2$ are precomputed quantities

KL to Legendre	Legendre to KL
$\widehat{\psi}([\mathsf{x}^2:\mathsf{z}^2])$	$\widehat{\psi}^{-1}(X:\cdot:Z)$
$X=\alpha_0\mathsf{z}^2$;	$\mathsf{x}^2=\alpha_0(X-Z)$;
$t_1=\alpha_1\mathsf{x}^2$;	$\mathsf{z}^2=\alpha_1X$;
$Z=X-t_1$;	return $[\mathsf{x}^2:\mathsf{z}^2]$.
return $(X:\cdot:Z)$.	return $[\mathsf{x}^2:\mathsf{z}^2]$.

| Show Table

DownLoad: CSV

Table 5. Base points for $E_{1a}$, $E_{1b}$, $E_2$ and $E_3$ corresponding to $\mathsf{KL}_{1a}$, $\mathsf{KL}_{1b}$, $\mathsf{KL}_{2}$ and $\mathsf{KL}_{3}$

$p$	$\mathsf{a}^2$	$\mathsf{b}^2$	$[\mathsf{x}^2:\mathsf{z}^2]$	$(x,y)$
$2^{251}-9$	$81$	$20$	$[64:1]$	$(-81/1199,\mathfrak{y}_1)$
$2^{251}-9$	$186$	$175$	$[19:1]$	$(-186/3139,\mathfrak{y}_2)$
$2^{255}-19$	$82$	$77$	$[31:1]$	$(-82/2305,\mathfrak{y}_3)$
$2^{266}-3$	$260$	$139$	$[2:1]$	$(-260/18,\mathfrak{y}_4)$

| Show Table

DownLoad: CSV

Table 6. Values of $x_1,y_1$ and $x_2$ which are solutions to (24)

$x_2=0$	$x_1 = \sqrt{\mu}$	$y_1 = \pm\sqrt{-\mu^2 + 2\mu^{3/2} - \mu}$
$x_2=0$	$x_1 = -\sqrt{\mu}$	$y_1 = \pm\sqrt{-\mu^2 - 2\mu^{3/2} - \mu}$
$x_2=1$	$x_1 = 1 + \sqrt{1-\mu}$	$y_1 = \pm (-1+\mu-\sqrt{1-\mu})$
$x_2=1$	$x_1 = 1 - \sqrt{1-\mu}$	$y_1 = \pm (-1+\mu+\sqrt{1-\mu})$
$x_2=\mu$	$x_1 = \mu + \sqrt{\mu^2-\mu}$	$y_1 = \pm \left(2\mu^3 + 2\mu^2\sqrt{\mu^2-\mu}-3\mu^2-2\mu\sqrt{\mu^2-\mu}+\mu\right)^{1/2}$
$x_2=\mu$	$x_1 = \mu - \sqrt{\mu^2-\mu}$	$y_1 = \pm \left(2\mu^3 - 2\mu^2\sqrt{\mu^2-\mu}-3\mu^2+2\mu\sqrt{\mu^2-\mu}+\mu\right)^{1/2}$

| Show Table

DownLoad: CSV

Table 7. Summary of the different twisted Edwards form curve. Here b.r. denotes birational equivalence and 2-iso denotes 2-isogeny

Kummer	Legendre	twisted Edwards	Legendre to twisted Edwards
$\mathsf{KL2519}(81,20)$	$E_{1a}$	$\mathsf{Ed}_{1a,1}$	b.r. (Thm 4.4)
$\mathsf{KL2519}(81,20)$	$E_{1a}$	$\mathsf{Ed}_{1a,2}$	b.r. (Thm 4.4)
$\mathsf{KL2519}(186,175)$	$E_{1b}$	$\mathsf{Ed}_{1b,1}$	b.r. (Thm 4.4)
		$\mathsf{Ed}_{1b,2}$	b.r. (Thm 4.4)
		$\mathsf{Ed}_{1b,3}$	2-iso (Thm 4.5)
$\mathsf{KL25519}(82,77)$	$E_{2}$	$\mathsf{Ed}_{2}$	2-iso (Thm 4.5)
$\mathsf{KL2663}(260,139)$	$E_{3}$	$\mathsf{Ed}_{3}$	2-iso (Thm 4.5)

| Show Table

DownLoad: CSV

Table 8. General $d$

$A \leftarrow (V_1 - U_1 ) \cdot (V_2 - U_2 )$,
$B \leftarrow (V_1 + U_1 ) \cdot (V_2 + U_2 )$,
$C \leftarrow (2d) T_1 \cdot T_2$,
$D \leftarrow 2W_1 \cdot W_2$,
$E \leftarrow B - A$,
$F \leftarrow D - C$,
$G \leftarrow D + C$,
$H \leftarrow B + A$,
$U_3 \leftarrow E \cdot F$,
$V_3 \leftarrow G \cdot H$,
$T_3 \leftarrow E \cdot H$,
$W_3 \leftarrow F \cdot G$.

| Show Table

DownLoad: CSV

Table 9. $d = d_1/d_2$ with $d_1,d_2$ small

$A \leftarrow (V_1 - U_1 ) \cdot (V_2 - U_2 )$,
$B \leftarrow (V_1 + U_1 ) \cdot (V_2 + U_2 )$,
$C \leftarrow (2d_1) T_1 \cdot T_2$,
$D \leftarrow (2d_2) W_1 \cdot W_2$,
$E \leftarrow d_2(B - A)$,
$F \leftarrow D - C$,
$G \leftarrow D + C$,
$H \leftarrow d_2(B + A)$,
$U_3 \leftarrow E \cdot F$,
$V_3 \leftarrow G \cdot H$,
$T_3 \leftarrow E \cdot H$,
$W_3 \leftarrow F \cdot G$.

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	J. Barwise and P. Eklof, Lefschetz's principle, Journal of Algebra, 13 (1969), 554-570. doi: 10.1016/0021-8693(69)90117-3.
[2]	D. J. Bernstein, Curve25519: New Diffie-Hellman speed records, Public Key Cryptography - PKC, 3958 (2006), 207-228. doi: 10.1007/11745853_14.
[3]	D. J. Bernstein and T. Lange, Explicit-Formulas Database, 2007. Available from: http://www.hyperelliptic.org/EFD/index.html.
[4]	D. J. Bernstein and T. Lange, Faster Addition and Doubling on Elliptic Curves, Advances in Cryptology - ASIACRYPT, 4833 (2007), 29-50. doi: 10.1007/978-3-540-76900-2_3.
[5]	D. J. Bernstein, P. Birkner, M. Joye, T. Lange and C. Peters, Twisted Edwards curves, Progress in Cryptology - AFRICACRYPT, 5023 (2008), 389-405. doi: 10.1007/978-3-540-68164-9_26.
[6]	D. J. Bernstein, N. Duif, T. Lange, P. Schwabe and B.-Y. Yang, High-speed high-security signatures, J. Cryptographic Engineering, 2 (2012), 77-89.
[7]	E. Brier and M. Joye, Fast point multiplication on elliptic curves through isogenies, Applied Algebra, Algebraic Algorithms and Error-Correcting Codes - AAECC, 2643 (2003), 43-50. doi: 10.1007/3-540-44828-4_6.
[8]	M. P. L. Das and P. Sarkar, Pairing computation on twisted Edwards form elliptic curves, Pairing-Based Cryptography - Pairing, 5209 (2008), 192-210. doi: 10.1007/978-3-540-85538-5_14.
[9]	H. M. Edwards, A normal form for elliptic curves, Bulletin of the American Mathematical Society, 44 (2007), 393-422. doi: 10.1090/S0273-0979-07-01153-6.
[10]	G. Frey and H.-G. Rück, The strong Lefschetz principle in algebraic geometry, Manuscripta Mathematica, 55 (1986), 385-401. doi: 10.1007/BF01186653.
[11]	P. Gaudry, Fast genus 2 arithmetic based on Theta functions, J. Mathematical Cryptology, 1 (2007), 243-265. doi: 10.1515/JMC.2007.012.
[12]	P. Gaudry and D. Lubicz, The arithmetic of characteristic 2 Kummer surfaces and of elliptic Kummer lines, Finite Fields and Their Applications, 15 (2009), 246-260. doi: 10.1016/j.ffa.2008.12.006.
[13]	H. Hisil and C. Costello, Jacobian coordinates on genus 2 curves, J. Cryptology, 30 (2017), 572-600. doi: 10.1007/s00145-016-9227-7.
[14]	H. Hisil, K. K.-H. Wong, G. Carter and E. Dawson, Twisted edwards curves revisited, Advances in Cryptology - ASIACRYPT, 5350 (2008), 326-343. doi: 10.1007/978-3-540-89255-7_20.
[15]	J.-I. Igusa, Theta Functions, Springer, 1972.
[16]	S. Karati and P. Sarkar, 2007. Available from: https://github.com/skarati/Connecting-Legendre-with-Kummer-and-Edwards.
[17]	S. Karati and P. Sarkar, Kummer for Genus One over Prime Order Fields, Advances in Cryptology - ASIACRYPT, 10625 (2017), 3-32.
[18]	N. Koblitz, Elliptic curve cryptosystems, Mathematics of Computation, 48 (1987), 203-209. doi: 10.1090/S0025-5718-1987-0866109-5.
[19]	V. S. Miller, Use of elliptic curves in cryptography, Advances in Cryptology - CRYPTO, 218 (1985), 417-426. doi: 10.1007/3-540-39799-X_31.
[20]	P. L. Montgomery, Speeding the Pollard and elliptic curve methods of factorization, Mathematics of Computation, 48 (1987), 243-264. doi: 10.1090/S0025-5718-1987-0866113-7.
[21]	D. Mumford, Tata Lectures on Theta I, Progress in Mathematics 28. Birkh äuser, 1983. doi: 10.1007/978-1-4899-2843-6.
[22]	K. Okeya, H. Kurumatani and K. Sakurai, Elliptic curves with the Montgomery-form and their cryptographic applications, Public Key Cryptography - PKC, 1751 (2000), 238-257. doi: 10.1007/978-3-540-46588-1_17.
[23]	K. Okeya and K. Sakurai, Efficient elliptic curve cryptosystems from a scalar multiplication algorithm with recovery of the y-coordinate on a Montgomery-form elliptic curve, Cryptographic Hardware and Embedded Systems - CHES, 2162 (2001), 126-141. doi: 10.1007/3-540-44709-1_12.
[24]	J. H. Silverman, The Arithmetic of Elliptic Curves, Springer, 2009. doi: 10.1007/978-0-387-09494-6.