134 results sorted by ID
Possible spell-corrected query: twist
On the cryptosystems based on two Eulerian transfor-mations defined over the commutative rings $Z_{2^s}, s>1$.
Vasyl Ustimenko
Cryptographic protocols
We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations.
The cipher is...
A Survey of Polynomial Multiplications for Lattice-Based Cryptosystems
Vincent Hwang
Implementation
We survey various mathematical tools used in software works multiplying polynomials in
\[
\frac{\mathbb{Z}_q[x]}{\left\langle {x^n - \alpha x - \beta} \right\rangle}.
\]
In particular, we survey implementation works targeting polynomial multiplications in lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber with instruction set architectures/extensions Armv7-M, Armv7E-M, Armv8-A, and AVX2.
There are three emphases in this paper: (i) modular arithmetic, (ii)...
ASOZ: a decentralized payment system with privacy preserving and auditing on public blockchain
Tianjian Liu, Dawei Zhang, Wei Wang, Chang Chen
Public-key cryptography
Decentralized payment systems have gradually received more attention in recent years. By removing the trusted intermediary used for accounting ledgers, those payment systems fundamentally empower users to control their assets. As privacy concerns grow, some cryptocurrencies are proposed to preserve the privacy of users. However, those cryptocurrencies also inadvertently facilitate illicit activities such as money laundering, fraudulent trading, etc. So it is necessary to design an auditing...
CSI-Otter: Isogeny-based (Partially) Blind Signatures from the Class Group Action with a Twist
Shuichi Katsumata, Yi-Fu Lai, Jason T. LeGrow, Ling Qin
Public-key cryptography
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme.
While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure.
Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct...
An extension of Overbeck's attack with an application to cryptanalysis of Twisted Gabidulin-based schemes.
Alain Couvreur, Ilaria Zappatore
Attacks and cryptanalysis
In this article, we discuss the decoding of Gabidulin and related codes from a cryptographic point of view, and we observe that these codes can be decoded solely from the knowledge of a generator matrix. We then extend and revisit Gibson and Overbeck attacks on the generalized GPT encryption scheme (instantiated with the Gabidulin code) for different ranks of the distortion matrix. We apply our attack to the case of an instantiation with twisted Gabidulin codes.
SDitH in the QROM
Carlos Aguilar-Melchor, Andreas Hülsing, David Joseph, Christian Majenz, Eyal Ronen, Dongze Yue
Public-key cryptography
The MPC in the Head (MPCitH) paradigm has recently led to significant improvements for signatures in the code-based setting. In this paper we consider some modifications to a recent twist of MPCitH, called Hypercube-MPCitH, that in the code-based setting provides the currently best known signature sizes. By compressing the Hypercube-MPCitH five-round code-based identification scheme into three-rounds we obtain two main benefits. On the one hand, it allows us to further develop recent...
Generic Models for Group Actions
Julien Duman, Dominik Hartmann, Eike Kiltz, Sabrina Kunzweiler, Jonas Lehmann, Doreen Riepel
Foundations
We define the Generic Group Action Model (GGAM), an adaptation of the Generic Group Model to the setting of group actions (such as CSIDH). Compared to a previously proposed definition by Montgomery and Zhandry (ASIACRYPT'22), our GGAM more accurately abstracts the security properties of group actions.
We are able to prove information-theoretic lower bounds in the GGAM for the discrete logarithm assumption, as well as for non-standard assumptions recently introduced in the setting of...
CAPYBARA and TSUBAKI: Verifiable Random Functions from Group Actions and Isogenies
Yi-Fu Lai
Public-key cryptography
In this work, we propose two post-quantum verifiable random functions (VRFs) constructions based on group actions and isogenies, one of which is based on the standard DDH assumption. VRF is a cryptographic tool that enables a user to generate a pseudorandom output along with a publicly verifiable proof. The residual pseudorandomness of VRF ensures the pseudorandomness of unrevealed inputs, even if an arbitrary number of outputs and proofs are revealed.
Furthermore, it is infeasible to...
Non-Interactive Secure Computation of Inner-Product from LPN and LWE
Geoffroy Couteau, Maryam Zarezadeh
Cryptographic protocols
We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors.
We give constructions of this primitive from a common template, which can be...
Enhancing Ring-LWE Hardness using Dedekind Index Theorem
Charanjit S Jutla, Chengyu Lin
Foundations
In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the...
EdMSM: Multi-Scalar-Multiplication for SNARKs and Faster Montgomery multiplication
Youssef El Housni, Gautam Botrel
Implementation
The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. We prove that this is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Our contribution is twofold: first, we optimize...
FPGA Acceleration of Multi-Scalar Multiplication: CycloneMSM
Kaveh Aasaraai, Don Beaver, Emanuele Cesena, Rahul Maganti, Nicolas Stalder, Javier Varela
Implementation
Multi-Scalar Multiplication (MSM) on elliptic curves is one of the primitives and bottlenecks at the core of many zero-knowledge proof systems. Speeding up MSM typically results in faster proof generation, which in turn makes ZK-based applications practical.
We focus on accelerating large MSM on FPGA, and we present speed records for $\texttt{BLS12-377}$ on FPGA: 5.66s for $N=2^{26}$, sub-second for $N=2^{22}$.
We developed a fully-pipelined curve adder in extended Twisted Edwards...
Point-Halving and Subgroup Membership in Twisted Edwards Curves
Thomas Pornin
Public-key cryptography
In this short note, we describe a process for halving a point on a
twisted Edwards curve. This can be used to test whether a given point
is in the subgroup of prime order $\ell$, which is used by some
cryptographic protocols. On Curve25519, this new test is about twice
faster than the classic method consisting of multiplying the source
point by $\ell$.
Fast Hashing to $\mathbb{G}_2$ on Pairing-friendly Curves with the Lack of Twists
Yu Dai, Fangguo Zhang, Chang-An Zhao
Public-key cryptography
Pairing-friendly curves with the lack of twists, such as BW13-P310 and BW19-P286, have been receiving attention in pairing-based cryptographic protocols as they provide fast operation in the first pairing subgroup $\mathbb{G}_1$ at the 128-bit security level. However, they also incur a performance penalty for hashing to $\mathbb{G}_2$ simultaneously since $\mathbb{G}_2$ is totally defined over a full extension field. Furthermore, the previous methods for hashing to $\mathbb{G}_2$ focus on...
Supersingular Isogeny Diffie-Hellman with Legendre Form
Jesse Elliott, Aaron Hutchinson
Public-key cryptography
SIDH is a key exchange algorithm proposed by Jao and De Feo that is conjectured to be post-quantum secure. The majority of work based on an SIDH framework uses elliptic curves in Montgomery form; this includes the original work by Jao, De Feo and Plût and the sate of the art implementation of SIKE. Elliptic curves in twisted Edwards form have also been used due to their efficient elliptic curve arithmetic, and complete Edwards curves have been used for their benefit of providing added...
A note on key control in CSIDH
Antonio Sanso
Public-key cryptography
In this short note we explore a particular behaviour of the CSIDH key exchange that leads to a very special form of (shared) key control via the use of the quadratic twists. This peculiarity contained in CSIDH with regard to quadratic twists was already noted in the original CSDIH work and used in several subsequent papers but we believe spelling out this in the form of an attack might be useful to the wider community.
Password-Authenticated Key Exchange from Group Actions
Michel Abdalla, Thorsten Eisenhofer, Eike Kiltz, Sabrina Kunzweiler, Doreen Riepel
Cryptographic protocols
We present two provably secure password-authenticated key exchange (PAKE) protocols based on a commutative group action. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model the properties more accurately, we extend the framework of cryptographic group actions (Alamati et al., ASIACRYPT 2020) by the ability of computing the quadratic twist of an elliptic curve. This property is always present in the CSIDH setting and turns out to be crucial in...
The Generalized Montgomery Coordinate: A New Computational Tool for Isogeny-based Cryptography
Tomoki Moriya, Hiroshi Onuki, Yusuke Aikawa, Tsuyoshi Takagi
Public-key cryptography
Recently, some studies have constructed one-coordinate arithmetics on elliptic curves. For example, formulas of the $x$-coordinate of Montgomery curves, $x$-coordinate of Montgomery$^-$ curves, $w$-coordinate of Edwards curves, $w$-coordinate of Huff's curves, $\omega$-coordinates of twisted Jacobi intersections have been proposed. These formulas are useful for isogeny-based cryptography because of their compactness and efficiency.
In this paper, we define a novel function on elliptic...
Log-$\mathcal{S}$-unit lattices using Explicit Stickelberger Generators to solve Approx Ideal-SVP
Olivier Bernard, Andrea Lesavourey, Tuong-Huy Nguyen, Adeline Roux-Langlois
Public-key cryptography
In 2020, Bernard and Roux-Langlois introduced the Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé. They performed experiments for prime conductors cyclotomic fields of degrees at most 70, one of the main bottlenecks being the computation of a log-$\mathcal{S}$-unit lattice which requires subexponential time.
Our main contribution is to extend these experiments to cyclotomic fields of degree up...
Isogeny-based Group Signatures and Accountable Ring Signatures in QROM
Kai-Min Chung, Yao-Ching Hsieh, Mi-Ying Huang, Yu-Hsuan Huang, Tanja Lange, Bo-Yin Yang
Public-key cryptography
We provide the first isogeny-based group signature (GS) and accountable ring signature (ARS) that are provably secure in the quantum random oracle model (QROM). We do so by building an intermediate primitive called openable sigma protocol and show that every such protocol gives rise to a secure ARS and GS. Additionally, the QROM security is guaranteed if the perfect unique-response property is satisfied. Our design, with the underlying protocol satisfying this essential unique-response...
Efficient Leakage-Resilient MACs without Idealized Assumptions
Francesco Berti, Chun Guo, Thomas Peters, François-Xavier Standaert
Secret-key cryptography
The security proofs of leakage-resilient MACs based on symmetric
building blocks currently rely on idealized assumptions that hardly translate into
interpretable guidelines for the cryptographic engineers implementing these schemes.
In this paper, we first present a leakage-resilient MAC that is both efficient
and secure under standard and easily interpretable black box and physical assumptions.
It only requires a collision resistant hash function and a single call per message...
2021/1142
Last updated: 2021-09-13
The Elliptic Net Algorithm Revisited
Shiping Cai, Zhi Hu, Zheng-An Yao, Chang-An Zhao
Implementation
Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller’s algorithm. We use several methods to...
Some remarks on how to hash faster onto elliptic curves
Dmitrii Koshelev
Implementation
This article proposes four optimizations of indifferentiable hashing onto (prime-order subgroups of) ordinary elliptic curves over finite fields $\mathbb{F}_{\!q}$. One of them is dedicated to elliptic curves $E$ without non-trivial automorphisms provided that $q \equiv 2 \ (\mathrm{mod} \ 3)$. The second deals with $q \equiv 2, 4 \ (\mathrm{mod} \ 7)$ and an elliptic curve $E_7$ of $j$-invariant $-3^3 5^3$. The corresponding section plays a rather theoretical role, because (the quadratic...
Edwards curves and FFT-based multiplication
Pavel Atnashev, George Woltman
This paper introduces fast algorithms for performing group operations on Edwards curves using FFT-based multiplication. Previously known algorithms can use such multiplication too, but better results can be achieved if particular properties of FFT-based arithmetic are accounted for. The introduced algorithms perform operations in extended Edwards coordinates and in Montgomery single coordinate.
GLV+HWCD for 2y^2=x^3+x/GF(8^91+5)
Daniel R. L. Brown
Implementation
This report considers combining three well-known optimization methods for elliptic curve scalar multiplication: Gallant--Lambert--Vanstone (GLV) for complex multiplication endomorphisms $[i]$ and $[i+1]$; 3-bit fixed windows (signed base 8); and Hisil--Wong--Carter--Dawson (HWCD) curve arithmetic for twisted Edwards curves.
An $x$-only Diffie--Hellman scalar multiplication for curve $2y^2=x^3+x$ over field size $8^{91}+5$ has arithmetic cost $947\textbf{M} + 1086\textbf{S}$, where...
Ready-Made Short Basis for GLV+GLS on High Degree Twisted Curves
Bei Wang, Songsong Li, Yi Ouyang, Honggang Hu
Public-key cryptography
The crucial step in elliptic curve scalar multiplication based on scalar decompositions using efficient endomorphisms—such as GLV, GLS or GLV+GLS—is to produce a short basis of a lattice involving the eigenvalues of the endomorphisms, which usually is obtained by lattice basis reduction algorithms or even more specialized algorithms. Recently, lattice basis reduction is found to be unnecessary. Benjamin Smith (AMS 2015) was able to immediately write down a short basis of the lattice for the...
Double-Odd Elliptic Curves
Thomas Pornin
Public-key cryptography
This article explores the use of elliptic curves with order 2r = 2 mod 4, which we call double-odd elliptic curves. This is a very large class, comprising about 1/4th of all curves over a given field. On such curves, we manage to define a prime order group with appropriate characteristics for building cryptographic protocols:
- Element encoding is canonical, and verified upon decoding. For a 2n-bit group (with n-bit security), encoding size is 2n + 1 bits, i.e. as good as compressed points...
Twisted-PHS: Using the Product Formula to Solve Approx-SVP in Ideal Lattices
Olivier Bernard, Adeline Roux-Langlois
Public-key cryptography
Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal...
Efficient indifferentiable hashing to elliptic curves $y^2 = x^3 + b$ provided that $b$ is a quadratic residue
Dmitrii Koshelev
Implementation
Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary elliptic $\mathbb{F}_{\!q}$-curve of $j$-invariant $0$ such that $\sqrt{b} \in \mathbb{F}_{\!q}$. In particular, this condition is fulfilled for the curve BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases $b=4$). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time encoding $h\!: \mathbb{F}_{\!q} \to E_b(\mathbb{F}_{\!q})$ of an...
A Note on Authenticated Group Key Agreement Protocol Based on Twist Conjugacy Problem in Near – Rings
Atul Chaturvedi, Varun Shukla, Manoj K. Misra
Foundations
ABSTRACT
In 2017, D. Ezhilmaran & V. Muthukumaran (E&M [1]) have proposed key agreement protocols based on twisted conjugacy search problem in Near – ring and they have claimed that one can extend 3 party key agreement protocol (3PKAP) to any number of parties. Unfortunately their protocol is not an extension of 3PKAP and we present this weakness in this paper. We also show that their proposed 3PKAP is practically infeasible. Their protocol is not extendable to large number of parties like...
WAGE: An Authenticated Encryption with a Twist
Riham AlTawy, Guang Gong, Kalikinkar Mandal, Raghvendra Rohit
Secret-key cryptography
This paper presents WAGE, a new lightweight sponge-based authenticated cipher whose underlying permutation is based on a 37-stage Galois NLFSR over $\mathbb{F}_{2^7}$. At its core, the round function of the permutation consists of the well-analyzed Welch-Gong permutation (WGP), primitive feedback polynomial, a newly designed 7-bit SB sbox and partial word-wise XORs. The construction of the permutation is carried out such that the design of individual components is highly coupled with...
Efficient ECM factorization in parallel with the Lyness map
Andrew Hone
Foundations
The Lyness map is a birational map in the plane which provides one of the simplest discrete analogues of a Hamiltonian system with one degree of freedom, having a conserved quantity and an invariant symplectic form. As an example of a symmetric Quispel-Roberts-Thompson (QRT) map, each generic orbit of the Lyness map lies on a curve of genus one, and corresponds to a sequence of points on an elliptic curve which is one of the fibres in a pencil of biquadratic curves in the plane.
We...
Elliptic Curves of Nearly Prime Order
Manoj Gyawali, Daniele Di Tullio
Public-key cryptography
Constructing an elliptic curve of prime order has a significant role in
elliptic curve cryptography. For security purposes, we need an elliptic curve of
almost prime order. In this paper, we propose an efficient technique to generate
an elliptic curve of nearly prime order. In practice, this algorithm produces an
elliptic curve of order 2 times a prime number. Therefore, these elliptic curves are
appropriate for practical uses. Presently, the most known working algorithms for
generating...
Analogue of Vélu's Formulas for Computing Isogenies over Hessian Model of Elliptic Curves
Fouazou Lontouo Perez Broon, Emmanuel Fouotsa
Public-key cryptography
Vélu's formulas for computing isogenies over Weierstrass model of elliptic curves has been extended to other models of elliptic curves such as the Huff model, the Edwards model and the Jacobi model of elliptic curves. This work continues this line of research by providing efficient formulas for computing isogenies over elliptic curves of Hessian form. We provide explicit formulas for computing isogenies of degree 3 and isogenies of degree l not divisible by 3. The theoretical cost of...
Hashing to elliptic curves of $j$-invariant $1728$
Dmitrii Koshelev
Implementation
This article generalizes the simplified Shallue--van de Woestijne--Ulas (SWU) method of a deterministic finite field mapping $h\!: \mathbb{F}_{\!q} \to E_a(\mathbb{F}_{\!q})$ to the case of any elliptic $\mathbb{F}_{\!q}$-curve $E_a\!: y^2 = x^3 - ax$ of $j$-invariant $1728$. In comparison with the (classical) SWU method the simplified SWU method allows to avoid one quadratic residuosity test in the field $\mathbb{F}_{\!q}$, which is a quite painful operation in cryptography with regard to...
Security and Efficiency Trade-offs for Elliptic Curve Diffie-Hellman at the 128-bit and 224-bit Security Levels
Kaushik Nath, Palash Sarkar
Implementation
Within the Transport Layer Security (TLS) Protocol Version 1.3, RFC 7748 specifies elliptic curves targeted at the 128-bit and the 224-bit security levels. For the 128-bit security level, the Montgomery curve Curve25519 and its birationally equivalent twisted Edwards curve Ed25519 are specified; for the 224-bit security level, the Montgomery curve Curve448, the Edwards curve Edwards448 (which is isogenous to Curve448) and another Edwards curve which is birationally equivalent to Curve448...
The complete cost of cofactor h=1
Peter Schwabe, Amber Sprenkels
Implementation
This paper presents optimized software for constant-time variable-base scalar multiplication on prime-order Weierstraß curves using the complete addition and doubling formulas presented by Renes, Costello, and Batina in 2016. Our software targets three different microarchitectures: Intel Sandy Bridge, Intel Haswell, and ARM Cortex-M4. We use a 255-bit elliptic curve over $\mathbb{F}_{2^{255}-19}$ that was proposed by Barreto in 2017. The reason for choosing this curve in our software is that...
B-SIDH: supersingular isogeny Diffie-Hellman using twisted torsion
Craig Costello
Public-key cryptography
This paper explores a new way of instantiating isogeny-based cryptography in which parties can work in both the (p+1)-torsion of a set of supersingular curves and in the (p-1)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over GF(p^2) in general, restricting operations to the x-lines of both sets of twists allows all arithmetic to be carried out over GF(p^2) as usual....
A New Public Key Cryptosystem Based on Edwards Curves
Maher Boudabra, Abderrahmane Nitaj
Public-key cryptography
The elliptic curve cryptography plays a central role in various cryptographic schemes and protocols. For efficiency reasons, Edwards curves and twisted Edwards curves have been introduced. In this paper, we study the properties of twisted Edwards curves on the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=p^rq^s$ is a prime power RSA modulus and propose a new scheme and study its efficiency and security.
Twisted Hessian Isogenies
Thinh Dang, Dustin Moody
Implementation
Elliptic curves are typically defined by Weierstrass equations. Given a kernel, the well-known Velu’s formula shows how to explicitly write down an isogeny between Weierstrass curves. However, it is not clear how to do the same on other forms of elliptic curves without isomorphisms mapping to and from the Weierstrass form. Previous papers have shown some isogeny formulas for (twisted) Edwards, Huff, and Montgomery forms of elliptic curves. Continuing this line of work, this paper derives an...
Optimal TNFS-secure pairings on elliptic curves with composite embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
CSI-FiSh: Efficient Isogeny based Signatures through Class Group Computations
Ward Beullens, Thorsten Kleinjung, Frederik Vercauteren
Public-key cryptography
In this paper we report on a new record class group computation of an imaginary quadratic field having 154-digit discriminant, surpassing the previous record of 130 digits. This class group is central to the CSIDH-512 isogeny based cryptosystem, and knowing the class group structure and relation lattice implies efficient uniform sampling and a canonical representation of its elements. Both operations were impossible before and allow us to instantiate an isogeny based signature scheme first...
A taxonomy of pairings, their security, their complexity
Razvan Barbulescu, Nadia El Mrabet, Loubna Ghammam
Public-key cryptography
The Kim-Barbulescu attack against pairings made it necessary to increase the key sizes of the most popular families of pairings : BN, BLS-12, KSS-16, KSS-18 and BLS-24. The computation of new key sizes was a slow process because it was done in two waves : first a series of theoretical estimations, then a wave of precise estimations based on practical models. In this paper, we propose an up-to-date security evaluation for more then hundred pairing friendly elliptic curves. We evaluate the...
Cryptanalysis of a System Based on Twisted Reed-Solomon Codes
Julien Lavauzelle, Julian Renner
Public-key cryptography
Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed--Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic...
PGC: Pretty Good Decentralized Confidential Payment System with Auditability
Yu Chen, Xuecheng Ma, Cong Tang, Man Ho Au
Applications
Modern cryptocurrencies such as Bitcoin and Ethereum achieve decentralization by replacing a trusted center with
a distributed and append-only ledger (known as blockchain). However, removing this trusted center comes at significant cost of privacy due to the public nature of blockchain. Many existing cryptocurrencies fail to provide transaction anonymity and confidentiality, meaning that addresses of sender, receiver and transfer amount are publicly accessible. As the privacy concerns...
On Quantum Slide Attacks
Xavier Bonnetain, María Naya-Plasencia, André Schrottenloher
Secret-key cryptography
At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical
symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon's algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with O(n) quantum time and queries.
In this paper we propose many other types of quantum slide attacks. First, we are able to quantize classical advanced slide attacks on Feistel...
Pairing-Friendly Twisted Hessian Curves
Chitchanok Chuengsatiansup, Chloe Martindale
Public-key cryptography
This paper presents efficient formulas to compute Miller doubling and Miller addition utilizing degree-3 twists on curves with j-invariant 0 written in Hessian form. We give the formulas for both odd and even embedding degrees and for pairings on both $\mathbb{G}_1\times\mathbb{G}_2$ and $\mathbb{G}_2\times\mathbb{G}_1$. We propose the use of embedding degrees 15 and 21 for 128-bit and 192-bit security respectively in light of the NFS attacks and their variants. We give a comprehensive...
Optimal TNFS-secure pairings on elliptic curves with even embedding degree
Georgios Fotiadis, Chloe Martindale
Public-key cryptography
In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible...
Fast Scalar Multiplication for Elliptic Curves over Prime Fields by Efficiently Computable Formulas
Saud Al Musa, Guangwu Xu
Public-key cryptography
This paper addresses fast scalar multiplication for elliptic curves over finite fields. In the first part of the paper, we obtain several efficiently computable formulas for basic elliptic curves arithmetic in the family of twisted Edwards curves over prime fields. Our $2Q+P$ formula saves about $2.8$ field multiplications, and our $5P$ formula saves about $4.2$ field multiplications in standard projective coordinate systems, compared to the latest existing results. In the second part of the...
On Kummer Lines With Full Rational 2-torsion and Their Usage in Cryptography
Huseyin Hisil, Joost Renes
Public-key cryptography
A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus one, by observing that its SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this paper we extend this work and significantly simplify their treatment. 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 a twisted...
A faster way to the CSIDH
Michael Meyer, Steffen Reith
Implementation
Recently Castryck, Lange, Martindale, Panny, and Renes published CSIDH, a new key exchange scheme using supersingular elliptic curve isogenies. Due to its small key sizes, and the possibility of a non-interactive and a static-static key exchange, CSIDH seems very interesting for practical applications. However, the performance is rather slow. Therefore, we employ some techniques to speed up the algorithms, mainly by restructuring the elliptic curve point multiplications and by using twisted...
On CCZ-Equivalence, Extended-Affine Equivalence, and Function Twisting
Anne Canteaut, Léo Perrin
Secret-key cryptography
Two vectorial Boolean functions are ``CCZ-equivalent'' if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a...
Faster cofactorization with ECM using mixed representations
Cyril Bouvier, Laurent Imbert
Public-key cryptography
This paper introduces a novel implementation of the elliptic curve factoring method specifically designed for medium-size integers such as those arising by billions in the cofactorization step of the number field sieve. In this context, our algorithm requires fewer modular multiplications than any other publicly available implementation. The main ingredients are: the use of batches of primes, fast point tripling, optimal double-base decompositions and Lucas chains, and a good mix of...
Arithmetic Considerations for Isogeny Based Cryptography
Joppe W. Bos, Simon Friedberger
In this paper we investigate various arithmetic techniques which can be used to potentially enhance the performance in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. Firstly, we give a systematic overview of techniques to compute efficient arithmetic modulo $2^xp^y\pm 1$. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the...
Secure Computation using Leaky Correlations (Asymptotically Optimal Constructions)
Alexander R. Block, Divya Gupta, Hemanta K. Maji, Hai H. Nguyen
Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by...
In Praise of Twisted Embeddings
Jheyne N. Ortiz, Robson R. de Araujo, Diego F. Aranha, Sueli I. R. Costa, Ricardo Dahab
Foundations
Our main result in this work is the extension of the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. We prove that our generalization for Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the addition of a new parameter, the...
In search of CurveSwap: Measuring elliptic curve implementations in the wild
Luke Valenta, Nick Sullivan, Antonio Sanso, Nadia Heninger
Cryptographic protocols
We survey elliptic curve implementations from several vantage points. We perform internet-wide scans for TLS on a large number of ports, as well as SSH and IPsec to measure elliptic curve support and implementation behaviors, and collect passive measurements of client curve support for TLS. We also perform active measurements to estimate server vulnerability to known attacks against elliptic curve implementations, including support for weak curves, invalid curve attacks, and curve twist...
Parameterization of Edwards curves on the rational field Q with given torsion subgroups
Linh Tung Vo
Foundations
This paper presents the basic concepts of the Edwards curves, twisted Edwards curves and the point addition laws on these curves. The main result is the parameterization of the Edward curve with the given torsion subgroup in the rational field Q.
Extending Oblivious Transfer with Low Communication via Key-Homomorphic PRFs
Peter Scholl
We present a new approach to extending oblivious transfer with communication complexity that is logarithmic in the security parameter. Our method only makes black-box use of the underlying cryptographic primitives, and can achieve security against an active adversary with almost no overhead on top of passive security. This results in the first oblivious transfer protocol with sublinear communication and active security, which does not require any non-black-box use of cryptographic...
On hybrid SIDH schemes using Edwards and Montgomery curve arithmetic
Michael Meyer, Steffen Reith, Fabio Campos
Public-key cryptography
Supersingular isogeny Diffie-Hellman (SIDH) is a proposal for a quantum-resistant key exchange. The state-of-the-art implementation works entirely with Montgomery curves and basically can be divided into elliptic curve arithmetic and isogeny arithmetic. It is well known that twisted Edwards curves can provide a more efficient elliptic curve arithmetic. Therefore it was hinted by Costello and Hisil, that by using only Edwards curves for isogeny and curve arithmetic, or a hybrid scheme, that...
Connecting Legendre with Kummer and Edwards
Sabyasachi Karati, Palash Sarkar
Public-key cryptography
Scalar multiplication on 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...
Efficient Optimal Ate Pairing at 128-bit Security Level
Md. Al-Amin Khandaker, Yuki Nanjo, Loubna Ghammam, Sylvain Duquesne, Yasuyuki Nogami, Yuta Kodera
Public-key cryptography
Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and...
Compression for trace zero points on twisted Edwards curves
Giulia Bianco, Elisa Gorla
Public-key cryptography
We propose two optimal representations for the elements of trace zero subgroups of twisted Edwards curves. For both representations, we provide efficient compression and decompression algorithms. The efficiency of the algorithm is compared with the efficiency of similar algorithms on elliptic curves in Weierstrass form.
Twisting Lattice and Graph Techniques to Compress Transactional Ledgers
Rémi Géraud, David Naccache, Răzvan Roşie
Applications
Keeping track of financial transactions (e.g., in banks and blockchains) means keeping track of an ever-increasing list of exchanges between accounts. In fact, many of these transactions can be safely “forgotten”, in the sense that purging a set of them that compensate each other does not impact the network’s semantic meaning (e.g., the accounts’ balances). We call nilcatenation a collection of transactions having no effect on a network’s semantics. Such exchanges may be archived and...
On desynchronised El Gamal algorithm
Vasyl Ustimenko
Families of stable cyclic groups of nonlinear polynomial transformations of affine spaces $K^n$ over general commutative ring $K$ of
increasing with $n$ order can be used in the key exchange protocols and related to them El Gamal multivariate cryptosystems.
We suggest to use high degree of noncommutativity of affine Cremona group and modify multivariate El Gamal algorithm via the usage of conjugations for
two polynomials of kind $g^k$ and $g^{-1}$ given by key holder (Alice) or giving...
Trapping ECC with Invalid Curve Bug Attacks
Renaud Dubois
Public-key cryptography
In this paper we describe how to use a secret bug as a trapdoor to design trapped ellliptic curve E(Fp). This trapdoor can be used to mount an invalid curve attack on E(Fp). E(Fp) is designed to respect all ECC security criteria (prime order,high twist order, etc.) but for a secret exponent the point is projected on another unsecure curve. We show how to use this trap with a particular type of time/memory tradeoff to break the ECKCDSA verication process for any public key of the trapped...
Efficient hash maps to \mathbb{G}_2 on BLS curves
Alessandro Budroni, Federico Pintore
When a pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_{T}$, on an elliptic curve $E$ defined over $\mathbb{F}_q$, is exploited for an identity-based protocol, there is often the need to hash binary strings into $\mathbb{G}_1$ and $\mathbb{G}_2$. Traditionally, if $E$ admits a twist $\tilde{E}$ of order $d$, then $\mathbb{G}_1=E(\mathbb{F}_q) \cap E[r]$, where $r$ is a prime integer, and $\mathbb{G}_2=\tilde{E}(\mathbb{F}_{q^{k/d}}) \cap \tilde{E}[r]$, where $k$ is the...
Quantum Key Search with Side Channel Advice
Daniel P. Martin, Ashley Montanaro, Elisabeth Oswald, Dan Shepherd
Secret-key cryptography
Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting.
We show how to `rewrite' an existing algorithm for computing the rank of a key after a side channel attack, such that it results in an enumeration algorithm that produces batches of keys that can be...
Twisted $\mu_4$-normal form for elliptic curves
David Kohel
Public-key cryptography
We introduce the twisted $\mu_4$-normal form for elliptic curves,
deriving in particular addition algorithms with complexity $9M + 2S$
and doubling algorithms with complexity $2M + 5S + 2m$ over a binary field.
Every ordinary elliptic curve over a finite field of characteristic 2
is isomorphic to one in this family.
This improvement to the addition algorithm is comparable to the
$7M + 2S$ achieved for the $\mu_4$-normal form,
and replaces the previously best known complexity of $13M + 3S$
on...
Double-base scalar multiplication revisited
Daniel J. Bernstein, Chitchanok Chuengsatiansup, Tanja Lange
This paper reduces the number of field multiplications required for scalar multiplication on conservative elliptic curves. For an average 256-bit integer n, this paper's multiply-by-n algorithm
takes just 7.47M per bit on twisted Edwards curves -x^2+y^2=1+dx^2y^2 with small d. The previous record, 7.62M per bit, was unbeaten for seven years.
Unlike previous record-setting algorithms, this paper's multiply-by-n algorithm uses double-base chains. The new speeds rely on advances in tripling...
Computing Optimal Ate Pairings on Elliptic Curves with Embedding Degree $9,15$ and $27$
Emmanuel Fouotsa, Nadia El Mrabet, Aminatou Pecha
Much attention has been given to efficient computation of pairings on elliptic curves with even embedding degree since the advent of pairing-based cryptography. The existing few works in the case of odd embedding degrees require some improvements.
This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees $k=9, 15 \mbox{ and } 27$ which have twists of order three. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower...
Impossibility of Simulation Secure Functional Encryption Even with Random Oracles
Shashank Agrawal, Venkata Koppula, Brent Waters
Public-key cryptography
In this work we study the feasibility of achieving simulation security in functional encryption (FE) in the random oracle model. Our main result is negative in that we give a functionality for which it is impossible to achieve simulation security even with the aid of random oracles.
We begin by giving a formal definition of simulation security that explicitly incorporates the random oracles. Next, we show a particular functionality for which it is impossible to achieve simulation security....
Degenerate Curve Attacks
Samuel Neves, Mehdi Tibouchi
Implementation
Invalid curve attacks are a well-known class of attacks against
implementations of elliptic curve cryptosystems, in which an
adversary tricks the cryptographic device into carrying out scalar
multiplication not on the expected secure curve, but on some other,
weaker elliptic curve of his choosing. In their original form, however,
these attacks only affect elliptic curve implementations using
addition and doubling formulas that are independent of at least one
of the curve parameters. This...
Twisted Polynomials and Forgery Attacks on GCM
Mohamed Ahmed Abdelraheem, Peter Beelen, Andrey Bogdanov, Elmar Tischhauser
Polynomial hashing as an instantiation of universal hashing is a widely employed method for the construction of MACs and authenticated encryption
(AE) schemes, the ubiquitous GCM being a prominent example. It is also
used in recent AE proposals within the CAESAR competition which aim at
providing nonce misuse resistance, such as POET. The algebraic structure
of polynomial hashing has given rise to security concerns: At
CRYPTO~2008, Handschuh and Preneel describe key recovery attacks, and...
Faster arithmetic on elliptic curves using Fp2. Application to GLV-GLS and NIST elliptic curves over Fp isomorphic to twisted Hessian curves over fields extension
Michał Wroński
Applications
In this article we present how we can use fast F_{p²} multiplication to speed-up arithmetic on elliptic curves. We use parallel computations for multiplication in F_{p²} which is not much slower than multiplication in F_{p}. We show two applications of this method.
In the first we show that using twisted Edwards curves over F_{p²} with fast computable endomorphism (GLV-GLS method) may be nowadays on of the fastest (or even the fastest) solution in hardware applications.
In the second we show...
Faster point scalar multiplication on NIST elliptic curves over GF(p) using (twisted) Edwards curves over GF(p³)
Michał Wroński
Implementation
In this paper we present a new method for fast scalar multiplication on elliptic curves over GF(p) in FPGA using Edwards and twisted Edwards curves over GF(p³). The presented solution works for curves with prime group order (for example for all NIST curves over GF(p)). It is possible because of using 2-isogenous twisted Edwards curves over GF(p³) instead of using short Weierstrass curves over GF(p) for point scalar multiplication. This problem was considered by Verneuil in [1], but in...
Using Modular Extension to Provably Protect Edwards Curves Against Fault Attacks
Margaux Dugardin, Sylvain Guilley, Martin Moreau, Zakaria Najm, Pablo Rauzy
Implementation
Fault injection attacks are a real-world threat to cryptosystems, in particular asymmetric cryptography. In this paper, we focus on countermeasures which guarantee the integrity of the computation result, hence covering most existing and future fault attacks. Namely, we study the modular extension protection scheme in previously existing and newly contributed variants of the countermeasure on elliptic curve scalar multiplication (ECSM) algorithms. We find that an existing countermeasure is...
Computing information on domain parameters from public keys selected uniformly at random
Martin Ekerå
Public-key cryptography
The security of many cryptographic schemes and protocols rests on the conjectured computational intractability of the discrete logarithm problem in some group <g> of prime order. Such schemes and protocols require domain parameters that specify <g> and a specific generator g. In this paper we consider the problem of computing information on the domain parameters from public keys selected uniformly at random from <g>.
We show that it is not possible to compute any information on the...
Twisted Hessian curves
Daniel J. Bernstein, Chitchanok Chuengsatiansup, David Kohel, Tanja Lange
Public-key cryptography
This paper presents new speed records for arithmetic on a large family of elliptic curves with cofactor 3: specifically, 8.77M per bit for 256-bit variable-base single-scalar multiplication when curve parameters are chosen properly. This is faster than the best results known for cofactor 1, showing for the first time that points of order 3 are useful for performance and narrowing the gap to the speeds of curves with cofactor 4.
Decaf: Eliminating cofactors through point compression
Mike Hamburg
Public-key cryptography
We propose a new unified point compression format for Edwards, Twisted Edwards and Montgomery curves over large-characteristic fields, which effectively divides the curve's cofactor by 4 at very little cost to performance. This allows cofactor-4 curves to efficiently implement prime-order groups.
Twist Insecurity
Manfred Lochter, Andreas Wiemers
Public-key cryptography
Several authors suggest that the use of twist secure Elliptic Curves automatically leads to secure implementations. We argue that even for twist secure
curves a point validation has to be performed.
We illustrate this with examples where the security of EC-algorithms is strongly degraded, even for twist secure curves.
We show that the usual blindig countermeasures against SCA are insufficient
(actually they introduce weaknesses)
if no point validation is performed,
or if an attacker has...
FourQ: four-dimensional decompositions on a Q-curve over the Mersenne prime
Craig Costello, Patrick Longa
We introduce FourQ, a high-security, high-performance elliptic curve that targets the 128-bit security level. At the highest arithmetic level, cryptographic scalar multiplications on FourQ can use a four-dimensional Gallant-Lambert-Vanstone decomposition to minimize the total number of elliptic curve group operations. At the group arithmetic level, FourQ admits the use of extended twisted Edwards coordinates and can therefore exploit the fastest known elliptic curve addition formulas over...
VLSI Implementation of Double-Base Scalar Multiplication on a Twisted Edwards Curve with an Efficiently Computable Endomorphism
Zhe Liu, Husen Wang, Johann Großschädl, Zhi Hu, Ingrid Verbauwhede
Implementation
The verification of an ECDSA signature requires a double-base scalar multiplication, an operation of the form $k \cdot G + l \cdot Q$ where $G$ is a generator of a large elliptic curve group of prime order $n$, $Q$ is an arbitrary element of said group, and $k$, $l$ are two integers in the range of $[1, n-1]$. We introduce in this paper an area-optimized VLSI design of a Prime-Field Arithmetic Unit (PFAU) that can serve as a loosely-coupled or tightly-coupled hardware accelerator in a...
Improved (Hierarchical) Inner-Product Encryption from Lattices
Keita Xagawa
Public-key cryptography
Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan~(Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen~(Eurocrypt 2010). Their IPE scheme supports inner-product predicates over $R^{\mu}$, where the ring is $R = \mathbb{Z}_q$. Several applications require the ring $R$ to be exponentially large and, thus, they set $q...
Improving the Polynomial time Precomputation of Frobenius Representation Discrete Logarithm Algorithms - Simplified Setting for Small Characteristic Finite Fields
Antoine Joux, Cécile Pierrot
Public-key cryptography
In this paper, we revisit the recent small characteristic discrete logarithm algorithms. We show that a simplified description of the algorithm, together with some additional ideas, permits to obtain an improved complexity for the polynomial time precomputation that arises during the discrete logarithm computation. With our new improvements, this is reduced to O(q^6), where q is the cardinality of the basefield we are considering. This should be compared to the best currently documented...
Reflections on Slide with a Twist Attacks
Itai Dinur, Orr Dunkelman, Nathan Keller, Adi Shamir
Secret-key cryptography
Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated variants of slide attacks which slide an encryption operation against a decryption operation. Designed by Biryukov and Wagner in 2000, these attacks were used against several cryptosystems, including DESX, the Even-Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework,...
The Q-curve Construction for Endomorphism-Accelerated Elliptic Curves
Benjamin Smith
Implementation
We give a detailed account of the use of \(\mathbb{Q}\)-curve reductions to construct elliptic curves over \(\mathbb{F}_{p^2}\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) endomorphisms.
Like GLS (which is a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding...
Fully Secure Attribute Based Encryption from Multilinear Maps
Sanjam Garg, Craig Gentry, Shai Halevi, Mark Zhandry
Public-key cryptography
We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies expressible as polynomial-size circuits. Previous ABE schemes for general circuits were proved secure only in an unrealistic selective security model, where the adversary is forced to specify its target before seeing the public parameters, and full security could be obtained only by complexity leveraging, where the reduction succeeds only if correctly guesses the adversary’s...
Publicly Evaluable Pseudorandom Functions and Their Applications
Yu Chen, Zongyang Zhang
We put forth the notion of \emph{publicly evaluable} pseudorandom functions (PEPRFs),
which can be viewed as a counterpart of standard pseudorandom functions (PRFs) in the public-key setting. Briefly, PEPRFs are defined over domain $X$ containing a language $L$ associated with a hard relation $\mathsf{R}_L$, and each secret key $sk$ is associated with a public key $pk$. For any $x \in L$, in addition to evaluate $\mathsf{F}_{sk}(x)$ using $sk$ as standard PRFs, one is also able to evaluate...
Selecting Elliptic Curves for Cryptography: An Efficiency and Security Analysis
Joppe W. Bos, Craig Costello, Patrick Longa, Michael Naehrig
Public-key cryptography
We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which help to improve the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current...
Computing Discrete Logarithms in F_{3^{6*137}} and F_{3^{6*163}} using Magma
Gora Adj, Alfred Menezes, Thomaz Oliveira, Francisco Rodríguez-Henríquez
We show that a Magma implementation of Joux's L[1/4+o(1)] algorithm
can be used to compute discrete logarithms in the 1303-bit finite field
F_{3^{6*137}} and the 1551-bit finite field F_{3^{6*163}} with very modest computational resources. Our F_{3^{6*137}} implementation was the first to illustrate the effectiveness of
Joux's algorithm for computing discrete logarithms in small-characteristic
finite fields that are not Kummer or twisted-Kummer extensions.
Twisting Edwards curves with isogenies
Mike Hamburg
Implementation
Edwards’ elliptic curve form is popular in modern cryptographic implementations thanks to their fast, strongly unified addition formulas. Twisted Edwards curves with a = −1 are slightly faster, but their addition formulas are not complete over Fp where p ≡ 3 (mod 4). In this short note, we propose that designers specify Edwards curves, but implement scalar multiplications and the like using an isogenous twisted Edwards curve.
Kurosawa-Desmedt Key Encapsulation Mechanism, Revisited and More
Kaoru Kurosawa, Le Trieu Phong
Public-key cryptography
While the hybrid public key encryption scheme of Kurosawa and Desmedt (CRYPTO 2004) is provably secure against chosen ciphertext attacks (namely, IND-CCA-secure), its associated key encapsulation mechanism (KEM) is widely known as not \CCA-secure. In this paper, we present a direct proof of IND-CCA security thanks to a simple twist on the Kurosawa-Desmedt KEM. Our KEM beats the standardized version of Cramer-Shoup KEM in ISO/IEC 18033-2 by margins of
-- at least 20\% in encapsulation speed,...
Faster Compact Diffie-Hellman: Endomorphisms on the x-line
Craig Costello, Huseyin Hisil, Benjamin Smith
Implementation
Abstract: We describe an implementation of fast elliptic curve scalar multiplication, optimized for Diffie–Hellman Key Exchange at the 128-bit security level. The algorithms are compact (using only x-coordinates), run in constant time with uniform execution patterns, and do not distinguish between the curve and its quadratic twist; they thus have a built-in measure of side-channel resistance. (For comparison, we also implement two faster but non-constant-time algorithms.) The core of our...
Efficient Pairings Computation on Jacobi Quartic Elliptic Curves
Sylvain Duquesne, Nadia El Mrabet, Emmanuel Fouotsa
Public-key cryptography
This paper proposes the computation of the Tate pairing,
Ate pairing and its variations on the special Jacobi quartic elliptic curve
Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller's
algorithm to compute the Tate pairing. We use the birational equivalence
between Jacobi quartic curves and Weierstrass curves, together with a
specific point representation to obtain the best result to date among
curves with quartic twists. For the doubling and addition steps in...
Families of fast elliptic curves from Q-curves
Benjamin Smith
We construct new families of elliptic curves over \(\FF_{p^2}\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) endomorphisms.
Our construction is based on reducing \(\QQ\)-curves---curves over quadratic number fields without complex multiplication, but with isogenies to their Galois conjugates---modulo inert primes.
As a first application of the...
A generalisation of Miller's algorithm and applications to pairing computations on abelian varieties
David Lubicz, Damien Robert
Foundations
In this paper, we use the theory of theta functions to generalize to
all abelian varieties the usual Miller's algorithm to compute a
function associated to a principal divisor. We also explain how to
use the Frobenius morphism on abelian varieties defined over a
finite field in order to shorten the loop of the Weil and Tate
pairings algorithms. This extend preceding results about ate and
twisted ate pairings to all abelian varieties. Then building upon
the two preceding ingredients, we...
Efficient and Secure Algorithms for GLV-Based Scalar Multiplication and their Implementation on GLV-GLS Curves (Extended Version)
Armando Faz-Hernandez, Patrick Longa, Ana H. Sanchez
We propose efficient algorithms and formulas that improve the performance of side-channel protected elliptic curve computations with special focus on scalar multiplication exploiting the Gallant-Lambert-Vanstone (CRYPTO 2001) and Galbraith-Lin-Scott (EUROCRYPT 2009) methods. Firstly, by adapting Feng et al.'s recoding to the GLV setting, we derive new regular algorithms for variable-base scalar multiplication that offer protection against simple side-channel and timing attacks. Secondly, we...
Speeding up Ate Pairing Computation in Affine Coordinates
Duc-Phong Le, Chik How Tan
At Pairing 2010, Lauter et al's analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates.
On the one hand, we improve Ate pairing computation over elliptic curves admitting an even twist by describing an $4$-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in...
Twisted Edwards-Form Elliptic Curve Cryptography for 8-bit AVR-based Sensor Nodes
Dalin Chu, Johann Großschädl, Zhe Liu, Volker Müller, Yang Zhang
Implementation
Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply...
We suggest the family of ciphers s^E^n, n=2,3,.... with the space of plaintexts (Z*_{2^s})^n, s >1 such that the encryption map is the composition of kind G=G_1A_1G_2A_2 where A_i are the affine transformations from AGL_n(Z_{2^s}) preserving the variety (Z*_{2^s)}^n , Eulerian endomorphism G_i , i=1,2 of K[x_1, x_2,...., x_n] moves x_i to monomial term ϻ(x_1)^{d(1)}(x_2)^{d(2)}...(x_n)^{d(n)} , ϻϵ Z*_{2^s} and act on (Z*_{2^s})^n as bijective transformations. The cipher is...
We survey various mathematical tools used in software works multiplying polynomials in \[ \frac{\mathbb{Z}_q[x]}{\left\langle {x^n - \alpha x - \beta} \right\rangle}. \] In particular, we survey implementation works targeting polynomial multiplications in lattice-based cryptosystems Dilithium, Kyber, NTRU, NTRU Prime, and Saber with instruction set architectures/extensions Armv7-M, Armv7E-M, Armv8-A, and AVX2. There are three emphases in this paper: (i) modular arithmetic, (ii)...
Decentralized payment systems have gradually received more attention in recent years. By removing the trusted intermediary used for accounting ledgers, those payment systems fundamentally empower users to control their assets. As privacy concerns grow, some cryptocurrencies are proposed to preserve the privacy of users. However, those cryptocurrencies also inadvertently facilitate illicit activities such as money laundering, fraudulent trading, etc. So it is necessary to design an auditing...
In this paper, we construct the first provably-secure isogeny-based (partially) blind signature scheme. While at a high level the scheme resembles the Schnorr blind signature, our work does not directly follow from that construction, since isogenies do not offer as rich an algebraic structure. Specifically, our protocol does not fit into the "linear identification protocol" abstraction introduced by Hauck, Kiltz, and Loss (EUROCYRPT'19), which was used to generically construct...
In this article, we discuss the decoding of Gabidulin and related codes from a cryptographic point of view, and we observe that these codes can be decoded solely from the knowledge of a generator matrix. We then extend and revisit Gibson and Overbeck attacks on the generalized GPT encryption scheme (instantiated with the Gabidulin code) for different ranks of the distortion matrix. We apply our attack to the case of an instantiation with twisted Gabidulin codes.
The MPC in the Head (MPCitH) paradigm has recently led to significant improvements for signatures in the code-based setting. In this paper we consider some modifications to a recent twist of MPCitH, called Hypercube-MPCitH, that in the code-based setting provides the currently best known signature sizes. By compressing the Hypercube-MPCitH five-round code-based identification scheme into three-rounds we obtain two main benefits. On the one hand, it allows us to further develop recent...
We define the Generic Group Action Model (GGAM), an adaptation of the Generic Group Model to the setting of group actions (such as CSIDH). Compared to a previously proposed definition by Montgomery and Zhandry (ASIACRYPT'22), our GGAM more accurately abstracts the security properties of group actions. We are able to prove information-theoretic lower bounds in the GGAM for the discrete logarithm assumption, as well as for non-standard assumptions recently introduced in the setting of...
In this work, we propose two post-quantum verifiable random functions (VRFs) constructions based on group actions and isogenies, one of which is based on the standard DDH assumption. VRF is a cryptographic tool that enables a user to generate a pseudorandom output along with a publicly verifiable proof. The residual pseudorandomness of VRF ensures the pseudorandomness of unrevealed inputs, even if an arbitrary number of outputs and proofs are revealed. Furthermore, it is infeasible to...
We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors. We give constructions of this primitive from a common template, which can be...
In this work we extend the known pseudorandomness of Ring-LWE (RLWE) to be based on ideal lattices of non Dedekind domains. In earlier works of Lyubashevsky et al (EUROCRYPT 2010) and Peikert et al (STOC 2017), the hardness of RLWE was based on ideal lattices of ring of integers of number fields, which are known to be Dedekind domains. While these works extended Regev's (STOC 2005) quantum polynomial-time reduction for LWE, thus allowing more efficient and more structured cryptosystems, the...
The bottleneck in the proving algorithm of most of elliptic-curve-based SNARK proof systems is the Multi-Scalar-Multiplication (MSM) algorithm. In this paper we give an overview of a variant of the Pippenger MSM algorithm together with a set of optimizations tailored for curves that admit a twisted Edwards form. We prove that this is the case for SNARK-friendly chains and cycles of elliptic curves, which are useful for recursive constructions. Our contribution is twofold: first, we optimize...
Multi-Scalar Multiplication (MSM) on elliptic curves is one of the primitives and bottlenecks at the core of many zero-knowledge proof systems. Speeding up MSM typically results in faster proof generation, which in turn makes ZK-based applications practical. We focus on accelerating large MSM on FPGA, and we present speed records for $\texttt{BLS12-377}$ on FPGA: 5.66s for $N=2^{26}$, sub-second for $N=2^{22}$. We developed a fully-pipelined curve adder in extended Twisted Edwards...
In this short note, we describe a process for halving a point on a twisted Edwards curve. This can be used to test whether a given point is in the subgroup of prime order $\ell$, which is used by some cryptographic protocols. On Curve25519, this new test is about twice faster than the classic method consisting of multiplying the source point by $\ell$.
Pairing-friendly curves with the lack of twists, such as BW13-P310 and BW19-P286, have been receiving attention in pairing-based cryptographic protocols as they provide fast operation in the first pairing subgroup $\mathbb{G}_1$ at the 128-bit security level. However, they also incur a performance penalty for hashing to $\mathbb{G}_2$ simultaneously since $\mathbb{G}_2$ is totally defined over a full extension field. Furthermore, the previous methods for hashing to $\mathbb{G}_2$ focus on...
SIDH is a key exchange algorithm proposed by Jao and De Feo that is conjectured to be post-quantum secure. The majority of work based on an SIDH framework uses elliptic curves in Montgomery form; this includes the original work by Jao, De Feo and Plût and the sate of the art implementation of SIKE. Elliptic curves in twisted Edwards form have also been used due to their efficient elliptic curve arithmetic, and complete Edwards curves have been used for their benefit of providing added...
In this short note we explore a particular behaviour of the CSIDH key exchange that leads to a very special form of (shared) key control via the use of the quadratic twists. This peculiarity contained in CSIDH with regard to quadratic twists was already noted in the original CSDIH work and used in several subsequent papers but we believe spelling out this in the form of an attack might be useful to the wider community.
We present two provably secure password-authenticated key exchange (PAKE) protocols based on a commutative group action. To date the most important instantiation of isogeny-based group actions is given by CSIDH. To model the properties more accurately, we extend the framework of cryptographic group actions (Alamati et al., ASIACRYPT 2020) by the ability of computing the quadratic twist of an elliptic curve. This property is always present in the CSIDH setting and turns out to be crucial in...
Recently, some studies have constructed one-coordinate arithmetics on elliptic curves. For example, formulas of the $x$-coordinate of Montgomery curves, $x$-coordinate of Montgomery$^-$ curves, $w$-coordinate of Edwards curves, $w$-coordinate of Huff's curves, $\omega$-coordinates of twisted Jacobi intersections have been proposed. These formulas are useful for isogeny-based cryptography because of their compactness and efficiency. In this paper, we define a novel function on elliptic...
In 2020, Bernard and Roux-Langlois introduced the Twisted-PHS algorithm to solve Approx-SVP for ideal lattices on any number field, based on the PHS algorithm by Pellet-Mary, Hanrot and Stehlé. They performed experiments for prime conductors cyclotomic fields of degrees at most 70, one of the main bottlenecks being the computation of a log-$\mathcal{S}$-unit lattice which requires subexponential time. Our main contribution is to extend these experiments to cyclotomic fields of degree up...
We provide the first isogeny-based group signature (GS) and accountable ring signature (ARS) that are provably secure in the quantum random oracle model (QROM). We do so by building an intermediate primitive called openable sigma protocol and show that every such protocol gives rise to a secure ARS and GS. Additionally, the QROM security is guaranteed if the perfect unique-response property is satisfied. Our design, with the underlying protocol satisfying this essential unique-response...
The security proofs of leakage-resilient MACs based on symmetric building blocks currently rely on idealized assumptions that hardly translate into interpretable guidelines for the cryptographic engineers implementing these schemes. In this paper, we first present a leakage-resilient MAC that is both efficient and secure under standard and easily interpretable black box and physical assumptions. It only requires a collision resistant hash function and a single call per message...
Pairings have been widely used since their introduction to cryptography. They can be applied to identity-based encryption, tripartite Diffie-Hellman key agreement, blockchain and other cryptographic schemes. The Acceleration of pairing computations is crucial for these cryptographic schemes or protocols. In this paper, we will focus on the Elliptic Net algorithm which can compute pairings in polynomial time, but it requires more storage than Miller’s algorithm. We use several methods to...
This article proposes four optimizations of indifferentiable hashing onto (prime-order subgroups of) ordinary elliptic curves over finite fields $\mathbb{F}_{\!q}$. One of them is dedicated to elliptic curves $E$ without non-trivial automorphisms provided that $q \equiv 2 \ (\mathrm{mod} \ 3)$. The second deals with $q \equiv 2, 4 \ (\mathrm{mod} \ 7)$ and an elliptic curve $E_7$ of $j$-invariant $-3^3 5^3$. The corresponding section plays a rather theoretical role, because (the quadratic...
This paper introduces fast algorithms for performing group operations on Edwards curves using FFT-based multiplication. Previously known algorithms can use such multiplication too, but better results can be achieved if particular properties of FFT-based arithmetic are accounted for. The introduced algorithms perform operations in extended Edwards coordinates and in Montgomery single coordinate.
This report considers combining three well-known optimization methods for elliptic curve scalar multiplication: Gallant--Lambert--Vanstone (GLV) for complex multiplication endomorphisms $[i]$ and $[i+1]$; 3-bit fixed windows (signed base 8); and Hisil--Wong--Carter--Dawson (HWCD) curve arithmetic for twisted Edwards curves. An $x$-only Diffie--Hellman scalar multiplication for curve $2y^2=x^3+x$ over field size $8^{91}+5$ has arithmetic cost $947\textbf{M} + 1086\textbf{S}$, where...
The crucial step in elliptic curve scalar multiplication based on scalar decompositions using efficient endomorphisms—such as GLV, GLS or GLV+GLS—is to produce a short basis of a lattice involving the eigenvalues of the endomorphisms, which usually is obtained by lattice basis reduction algorithms or even more specialized algorithms. Recently, lattice basis reduction is found to be unnecessary. Benjamin Smith (AMS 2015) was able to immediately write down a short basis of the lattice for the...
This article explores the use of elliptic curves with order 2r = 2 mod 4, which we call double-odd elliptic curves. This is a very large class, comprising about 1/4th of all curves over a given field. On such curves, we manage to define a prime order group with appropriate characteristics for building cryptographic protocols: - Element encoding is canonical, and verified upon decoding. For a 2n-bit group (with n-bit security), encoding size is 2n + 1 bits, i.e. as good as compressed points...
Approx-SVP is a well-known hard problem on lattices, which asks to find short vectors on a given lattice, but its variant restricted to ideal lattices (which correspond to ideals of the ring of integers $\mathcal{O}_{K}$ of a number field $K$) is still not fully understood. For a long time, the best known algorithm to solve this problem on ideal lattices was the same as for arbitrary lattice. But recently, a series of works tends to show that solving this problem could be easier in ideal...
Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary elliptic $\mathbb{F}_{\!q}$-curve of $j$-invariant $0$ such that $\sqrt{b} \in \mathbb{F}_{\!q}$. In particular, this condition is fulfilled for the curve BLS12-381 and for one of sextic twists of the curve BW6-761 (in both cases $b=4$). These curves are very popular in pairing-based cryptography. The article provides an efficient constant-time encoding $h\!: \mathbb{F}_{\!q} \to E_b(\mathbb{F}_{\!q})$ of an...
ABSTRACT In 2017, D. Ezhilmaran & V. Muthukumaran (E&M [1]) have proposed key agreement protocols based on twisted conjugacy search problem in Near – ring and they have claimed that one can extend 3 party key agreement protocol (3PKAP) to any number of parties. Unfortunately their protocol is not an extension of 3PKAP and we present this weakness in this paper. We also show that their proposed 3PKAP is practically infeasible. Their protocol is not extendable to large number of parties like...
This paper presents WAGE, a new lightweight sponge-based authenticated cipher whose underlying permutation is based on a 37-stage Galois NLFSR over $\mathbb{F}_{2^7}$. At its core, the round function of the permutation consists of the well-analyzed Welch-Gong permutation (WGP), primitive feedback polynomial, a newly designed 7-bit SB sbox and partial word-wise XORs. The construction of the permutation is carried out such that the design of individual components is highly coupled with...
The Lyness map is a birational map in the plane which provides one of the simplest discrete analogues of a Hamiltonian system with one degree of freedom, having a conserved quantity and an invariant symplectic form. As an example of a symmetric Quispel-Roberts-Thompson (QRT) map, each generic orbit of the Lyness map lies on a curve of genus one, and corresponds to a sequence of points on an elliptic curve which is one of the fibres in a pencil of biquadratic curves in the plane. We...
Constructing an elliptic curve of prime order has a significant role in elliptic curve cryptography. For security purposes, we need an elliptic curve of almost prime order. In this paper, we propose an efficient technique to generate an elliptic curve of nearly prime order. In practice, this algorithm produces an elliptic curve of order 2 times a prime number. Therefore, these elliptic curves are appropriate for practical uses. Presently, the most known working algorithms for generating...
Vélu's formulas for computing isogenies over Weierstrass model of elliptic curves has been extended to other models of elliptic curves such as the Huff model, the Edwards model and the Jacobi model of elliptic curves. This work continues this line of research by providing efficient formulas for computing isogenies over elliptic curves of Hessian form. We provide explicit formulas for computing isogenies of degree 3 and isogenies of degree l not divisible by 3. The theoretical cost of...
This article generalizes the simplified Shallue--van de Woestijne--Ulas (SWU) method of a deterministic finite field mapping $h\!: \mathbb{F}_{\!q} \to E_a(\mathbb{F}_{\!q})$ to the case of any elliptic $\mathbb{F}_{\!q}$-curve $E_a\!: y^2 = x^3 - ax$ of $j$-invariant $1728$. In comparison with the (classical) SWU method the simplified SWU method allows to avoid one quadratic residuosity test in the field $\mathbb{F}_{\!q}$, which is a quite painful operation in cryptography with regard to...
Within the Transport Layer Security (TLS) Protocol Version 1.3, RFC 7748 specifies elliptic curves targeted at the 128-bit and the 224-bit security levels. For the 128-bit security level, the Montgomery curve Curve25519 and its birationally equivalent twisted Edwards curve Ed25519 are specified; for the 224-bit security level, the Montgomery curve Curve448, the Edwards curve Edwards448 (which is isogenous to Curve448) and another Edwards curve which is birationally equivalent to Curve448...
This paper presents optimized software for constant-time variable-base scalar multiplication on prime-order Weierstraß curves using the complete addition and doubling formulas presented by Renes, Costello, and Batina in 2016. Our software targets three different microarchitectures: Intel Sandy Bridge, Intel Haswell, and ARM Cortex-M4. We use a 255-bit elliptic curve over $\mathbb{F}_{2^{255}-19}$ that was proposed by Barreto in 2017. The reason for choosing this curve in our software is that...
This paper explores a new way of instantiating isogeny-based cryptography in which parties can work in both the (p+1)-torsion of a set of supersingular curves and in the (p-1)-torsion corresponding to the set of their quadratic twists. Although the isomorphism between a given supersingular curve and its quadratic twist is not defined over GF(p^2) in general, restricting operations to the x-lines of both sets of twists allows all arithmetic to be carried out over GF(p^2) as usual....
The elliptic curve cryptography plays a central role in various cryptographic schemes and protocols. For efficiency reasons, Edwards curves and twisted Edwards curves have been introduced. In this paper, we study the properties of twisted Edwards curves on the ring $\mathbb{Z}/n\mathbb{Z}$ where $n=p^rq^s$ is a prime power RSA modulus and propose a new scheme and study its efficiency and security.
Elliptic curves are typically defined by Weierstrass equations. Given a kernel, the well-known Velu’s formula shows how to explicitly write down an isogeny between Weierstrass curves. However, it is not clear how to do the same on other forms of elliptic curves without isomorphisms mapping to and from the Weierstrass form. Previous papers have shown some isogeny formulas for (twisted) Edwards, Huff, and Montgomery forms of elliptic curves. Continuing this line of work, this paper derives an...
In this paper we present a comprehensive comparison between pairing-friendly elliptic curves, considering different curve forms and twists where possible. We define a measure of the efficiency of a parametrized pairing-friendly family that takes into account the number field sieve (NFS) attacks (unlike the $\rho$-value). This measure includes an approximation of the security of the discrete logarithm problem in $\mathbb F_{p^k}^*$, computed via the method of Barbulescu and Duquesne [4]. We...
In this paper we report on a new record class group computation of an imaginary quadratic field having 154-digit discriminant, surpassing the previous record of 130 digits. This class group is central to the CSIDH-512 isogeny based cryptosystem, and knowing the class group structure and relation lattice implies efficient uniform sampling and a canonical representation of its elements. Both operations were impossible before and allow us to instantiate an isogeny based signature scheme first...
The Kim-Barbulescu attack against pairings made it necessary to increase the key sizes of the most popular families of pairings : BN, BLS-12, KSS-16, KSS-18 and BLS-24. The computation of new key sizes was a slow process because it was done in two waves : first a series of theoretical estimations, then a wave of precise estimations based on practical models. In this paper, we propose an up-to-date security evaluation for more then hundred pairing friendly elliptic curves. We evaluate the...
Twisted Reed-Solomon (TRS) codes are a family of codes that contains a large number of maximum distance separable codes that are non-equivalent to Reed--Solomon codes. TRS codes were recently proposed as an alternative to Goppa codes for the McEliece code-based cryptosystem, resulting in a potential reduction of key sizes. The use of TRS codes in the McEliece cryptosystem has been motivated by the fact that a large subfamily of TRS codes is resilient to a direct use of known algebraic...
Modern cryptocurrencies such as Bitcoin and Ethereum achieve decentralization by replacing a trusted center with a distributed and append-only ledger (known as blockchain). However, removing this trusted center comes at significant cost of privacy due to the public nature of blockchain. Many existing cryptocurrencies fail to provide transaction anonymity and confidentiality, meaning that addresses of sender, receiver and transfer amount are publicly accessible. As the privacy concerns...
At Crypto 2016, Kaplan et al. proposed the first quantum exponential acceleration of a classical symmetric cryptanalysis technique: they showed that, in the superposition query model, Simon's algorithm could be applied to accelerate the slide attack on the alternate-key cipher. This allows to recover an n-bit key with O(n) quantum time and queries. In this paper we propose many other types of quantum slide attacks. First, we are able to quantize classical advanced slide attacks on Feistel...
This paper presents efficient formulas to compute Miller doubling and Miller addition utilizing degree-3 twists on curves with j-invariant 0 written in Hessian form. We give the formulas for both odd and even embedding degrees and for pairings on both $\mathbb{G}_1\times\mathbb{G}_2$ and $\mathbb{G}_2\times\mathbb{G}_1$. We propose the use of embedding degrees 15 and 21 for 128-bit and 192-bit security respectively in light of the NFS attacks and their variants. We give a comprehensive...
In this paper we give a comprehensive comparison between pairing-friendly elliptic curves in Jacobi Quartic and Edwards form with quadratic, quartic, and sextic twists. Our comparison looks at the best choices to date for pairings on elliptic curves with even embedding degree on both $\mathbb{G}_1 \times \mathbb{G}_2$ and $\mathbb{G}_2 \times \mathbb{G}_1$ (these are the twisted Ate pairing and the optimal Ate pairing respectively). We apply this comparison to each of the nine possible...
This paper addresses fast scalar multiplication for elliptic curves over finite fields. In the first part of the paper, we obtain several efficiently computable formulas for basic elliptic curves arithmetic in the family of twisted Edwards curves over prime fields. Our $2Q+P$ formula saves about $2.8$ field multiplications, and our $5P$ formula saves about $4.2$ field multiplications in standard projective coordinate systems, compared to the latest existing results. In the second part of the...
A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus one, by observing that its SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this paper we extend this work and significantly simplify their treatment. 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 a twisted...
Recently Castryck, Lange, Martindale, Panny, and Renes published CSIDH, a new key exchange scheme using supersingular elliptic curve isogenies. Due to its small key sizes, and the possibility of a non-interactive and a static-static key exchange, CSIDH seems very interesting for practical applications. However, the performance is rather slow. Therefore, we employ some techniques to speed up the algorithms, mainly by restructuring the elliptic curve point multiplications and by using twisted...
Two vectorial Boolean functions are ``CCZ-equivalent'' if there exists an affine permutation mapping the graph of one to the other. It preserves many of the cryptographic properties of a function such as its differential and Walsh spectra, which is why it could be used by Dillon et al. to find the first APN permutation on an even number of variables. However, the meaning of this form of equivalence remains unclear. In fact, to the best of our knowledge, it is not known how to partition a...
This paper introduces a novel implementation of the elliptic curve factoring method specifically designed for medium-size integers such as those arising by billions in the cofactorization step of the number field sieve. In this context, our algorithm requires fewer modular multiplications than any other publicly available implementation. The main ingredients are: the use of batches of primes, fast point tripling, optimal double-base decompositions and Lucas chains, and a good mix of...
In this paper we investigate various arithmetic techniques which can be used to potentially enhance the performance in the supersingular isogeny Diffie-Hellman (SIDH) key-exchange protocol which is one of the more recent contenders in the post-quantum public-key arena. Firstly, we give a systematic overview of techniques to compute efficient arithmetic modulo $2^xp^y\pm 1$. Our overview shows that in the SIDH setting, where arithmetic over a quadratic extension field is required, the...
Most secure computation protocols can be effortlessly adapted to offload a significant fraction of their computationally and cryptographically expensive components to an offline phase so that the parties can run a fast online phase and perform their intended computation securely. During this offline phase, parties generate private shares of a sample generated from a particular joint distribution, referred to as the correlation. These shares, however, are susceptible to leakage attacks by...
Our main result in this work is the extension of the Ring-LWE problem in lattice-based cryptography to include algebraic lattices, realized through twisted embeddings. We define the class of problems Twisted Ring-LWE, which replaces the canonical embedding by an extended form. We prove that our generalization for Ring-LWE is secure by providing a security reduction from Ring-LWE to Twisted Ring-LWE in both search and decision forms. It is also shown that the addition of a new parameter, the...
We survey elliptic curve implementations from several vantage points. We perform internet-wide scans for TLS on a large number of ports, as well as SSH and IPsec to measure elliptic curve support and implementation behaviors, and collect passive measurements of client curve support for TLS. We also perform active measurements to estimate server vulnerability to known attacks against elliptic curve implementations, including support for weak curves, invalid curve attacks, and curve twist...
This paper presents the basic concepts of the Edwards curves, twisted Edwards curves and the point addition laws on these curves. The main result is the parameterization of the Edward curve with the given torsion subgroup in the rational field Q.
We present a new approach to extending oblivious transfer with communication complexity that is logarithmic in the security parameter. Our method only makes black-box use of the underlying cryptographic primitives, and can achieve security against an active adversary with almost no overhead on top of passive security. This results in the first oblivious transfer protocol with sublinear communication and active security, which does not require any non-black-box use of cryptographic...
Supersingular isogeny Diffie-Hellman (SIDH) is a proposal for a quantum-resistant key exchange. The state-of-the-art implementation works entirely with Montgomery curves and basically can be divided into elliptic curve arithmetic and isogeny arithmetic. It is well known that twisted Edwards curves can provide a more efficient elliptic curve arithmetic. Therefore it was hinted by Costello and Hisil, that by using only Edwards curves for isogeny and curve arithmetic, or a hybrid scheme, that...
Scalar multiplication on 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...
Following the emergence of Kim and Barbulescu's new number field sieve (exTNFS) algorithm at CRYPTO'16 [21] for solving discrete logarithm problem (DLP) over the finite field; pairing-based cryptography researchers are intrigued to find new parameters that confirm standard security levels against exTNFS. Recently, Barbulescu and Duquesne have suggested new parameters [3] for well-studied pairing-friendly curves i.e., Barreto-Naehrig (BN) [5], Barreto-Lynn-Scott (BLS-12) [4] and...
We propose two optimal representations for the elements of trace zero subgroups of twisted Edwards curves. For both representations, we provide efficient compression and decompression algorithms. The efficiency of the algorithm is compared with the efficiency of similar algorithms on elliptic curves in Weierstrass form.
Keeping track of financial transactions (e.g., in banks and blockchains) means keeping track of an ever-increasing list of exchanges between accounts. In fact, many of these transactions can be safely “forgotten”, in the sense that purging a set of them that compensate each other does not impact the network’s semantic meaning (e.g., the accounts’ balances). We call nilcatenation a collection of transactions having no effect on a network’s semantics. Such exchanges may be archived and...
Families of stable cyclic groups of nonlinear polynomial transformations of affine spaces $K^n$ over general commutative ring $K$ of increasing with $n$ order can be used in the key exchange protocols and related to them El Gamal multivariate cryptosystems. We suggest to use high degree of noncommutativity of affine Cremona group and modify multivariate El Gamal algorithm via the usage of conjugations for two polynomials of kind $g^k$ and $g^{-1}$ given by key holder (Alice) or giving...
In this paper we describe how to use a secret bug as a trapdoor to design trapped ellliptic curve E(Fp). This trapdoor can be used to mount an invalid curve attack on E(Fp). E(Fp) is designed to respect all ECC security criteria (prime order,high twist order, etc.) but for a secret exponent the point is projected on another unsecure curve. We show how to use this trap with a particular type of time/memory tradeoff to break the ECKCDSA verication process for any public key of the trapped...
When a pairing $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_{T}$, on an elliptic curve $E$ defined over $\mathbb{F}_q$, is exploited for an identity-based protocol, there is often the need to hash binary strings into $\mathbb{G}_1$ and $\mathbb{G}_2$. Traditionally, if $E$ admits a twist $\tilde{E}$ of order $d$, then $\mathbb{G}_1=E(\mathbb{F}_q) \cap E[r]$, where $r$ is a prime integer, and $\mathbb{G}_2=\tilde{E}(\mathbb{F}_{q^{k/d}}) \cap \tilde{E}[r]$, where $k$ is the...
Recently, a number of results have been published that show how to combine classical cryptanalysis with quantum algorithms, thereby (potentially) achieving considerable speed-ups. We follow this trend but add a novel twist by considering how to utilise side channel leakage in a quantum setting. We show how to `rewrite' an existing algorithm for computing the rank of a key after a side channel attack, such that it results in an enumeration algorithm that produces batches of keys that can be...
We introduce the twisted $\mu_4$-normal form for elliptic curves, deriving in particular addition algorithms with complexity $9M + 2S$ and doubling algorithms with complexity $2M + 5S + 2m$ over a binary field. Every ordinary elliptic curve over a finite field of characteristic 2 is isomorphic to one in this family. This improvement to the addition algorithm is comparable to the $7M + 2S$ achieved for the $\mu_4$-normal form, and replaces the previously best known complexity of $13M + 3S$ on...
This paper reduces the number of field multiplications required for scalar multiplication on conservative elliptic curves. For an average 256-bit integer n, this paper's multiply-by-n algorithm takes just 7.47M per bit on twisted Edwards curves -x^2+y^2=1+dx^2y^2 with small d. The previous record, 7.62M per bit, was unbeaten for seven years. Unlike previous record-setting algorithms, this paper's multiply-by-n algorithm uses double-base chains. The new speeds rely on advances in tripling...
Much attention has been given to efficient computation of pairings on elliptic curves with even embedding degree since the advent of pairing-based cryptography. The existing few works in the case of odd embedding degrees require some improvements. This paper considers the computation of optimal ate pairings on elliptic curves of embedding degrees $k=9, 15 \mbox{ and } 27$ which have twists of order three. Mainly, we provide a detailed arithmetic and cost estimation of operations in the tower...
In this work we study the feasibility of achieving simulation security in functional encryption (FE) in the random oracle model. Our main result is negative in that we give a functionality for which it is impossible to achieve simulation security even with the aid of random oracles. We begin by giving a formal definition of simulation security that explicitly incorporates the random oracles. Next, we show a particular functionality for which it is impossible to achieve simulation security....
Invalid curve attacks are a well-known class of attacks against implementations of elliptic curve cryptosystems, in which an adversary tricks the cryptographic device into carrying out scalar multiplication not on the expected secure curve, but on some other, weaker elliptic curve of his choosing. In their original form, however, these attacks only affect elliptic curve implementations using addition and doubling formulas that are independent of at least one of the curve parameters. This...
Polynomial hashing as an instantiation of universal hashing is a widely employed method for the construction of MACs and authenticated encryption (AE) schemes, the ubiquitous GCM being a prominent example. It is also used in recent AE proposals within the CAESAR competition which aim at providing nonce misuse resistance, such as POET. The algebraic structure of polynomial hashing has given rise to security concerns: At CRYPTO~2008, Handschuh and Preneel describe key recovery attacks, and...
In this article we present how we can use fast F_{p²} multiplication to speed-up arithmetic on elliptic curves. We use parallel computations for multiplication in F_{p²} which is not much slower than multiplication in F_{p}. We show two applications of this method. In the first we show that using twisted Edwards curves over F_{p²} with fast computable endomorphism (GLV-GLS method) may be nowadays on of the fastest (or even the fastest) solution in hardware applications. In the second we show...
In this paper we present a new method for fast scalar multiplication on elliptic curves over GF(p) in FPGA using Edwards and twisted Edwards curves over GF(p³). The presented solution works for curves with prime group order (for example for all NIST curves over GF(p)). It is possible because of using 2-isogenous twisted Edwards curves over GF(p³) instead of using short Weierstrass curves over GF(p) for point scalar multiplication. This problem was considered by Verneuil in [1], but in...
Fault injection attacks are a real-world threat to cryptosystems, in particular asymmetric cryptography. In this paper, we focus on countermeasures which guarantee the integrity of the computation result, hence covering most existing and future fault attacks. Namely, we study the modular extension protection scheme in previously existing and newly contributed variants of the countermeasure on elliptic curve scalar multiplication (ECSM) algorithms. We find that an existing countermeasure is...
The security of many cryptographic schemes and protocols rests on the conjectured computational intractability of the discrete logarithm problem in some group <g> of prime order. Such schemes and protocols require domain parameters that specify <g> and a specific generator g. In this paper we consider the problem of computing information on the domain parameters from public keys selected uniformly at random from <g>. We show that it is not possible to compute any information on the...
This paper presents new speed records for arithmetic on a large family of elliptic curves with cofactor 3: specifically, 8.77M per bit for 256-bit variable-base single-scalar multiplication when curve parameters are chosen properly. This is faster than the best results known for cofactor 1, showing for the first time that points of order 3 are useful for performance and narrowing the gap to the speeds of curves with cofactor 4.
We propose a new unified point compression format for Edwards, Twisted Edwards and Montgomery curves over large-characteristic fields, which effectively divides the curve's cofactor by 4 at very little cost to performance. This allows cofactor-4 curves to efficiently implement prime-order groups.
Several authors suggest that the use of twist secure Elliptic Curves automatically leads to secure implementations. We argue that even for twist secure curves a point validation has to be performed. We illustrate this with examples where the security of EC-algorithms is strongly degraded, even for twist secure curves. We show that the usual blindig countermeasures against SCA are insufficient (actually they introduce weaknesses) if no point validation is performed, or if an attacker has...
We introduce FourQ, a high-security, high-performance elliptic curve that targets the 128-bit security level. At the highest arithmetic level, cryptographic scalar multiplications on FourQ can use a four-dimensional Gallant-Lambert-Vanstone decomposition to minimize the total number of elliptic curve group operations. At the group arithmetic level, FourQ admits the use of extended twisted Edwards coordinates and can therefore exploit the fastest known elliptic curve addition formulas over...
The verification of an ECDSA signature requires a double-base scalar multiplication, an operation of the form $k \cdot G + l \cdot Q$ where $G$ is a generator of a large elliptic curve group of prime order $n$, $Q$ is an arbitrary element of said group, and $k$, $l$ are two integers in the range of $[1, n-1]$. We introduce in this paper an area-optimized VLSI design of a Prime-Field Arithmetic Unit (PFAU) that can serve as a loosely-coupled or tightly-coupled hardware accelerator in a...
Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan~(Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen~(Eurocrypt 2010). Their IPE scheme supports inner-product predicates over $R^{\mu}$, where the ring is $R = \mathbb{Z}_q$. Several applications require the ring $R$ to be exponentially large and, thus, they set $q...
In this paper, we revisit the recent small characteristic discrete logarithm algorithms. We show that a simplified description of the algorithm, together with some additional ideas, permits to obtain an improved complexity for the polynomial time precomputation that arises during the discrete logarithm computation. With our new improvements, this is reduced to O(q^6), where q is the cardinality of the basefield we are considering. This should be compared to the best currently documented...
Slide attacks use pairs of encryption operations which are slid against each other. Slide with a twist attacks are more sophisticated variants of slide attacks which slide an encryption operation against a decryption operation. Designed by Biryukov and Wagner in 2000, these attacks were used against several cryptosystems, including DESX, the Even-Mansour construction, and Feistel structures with four-round self-similarity. They were further extended in 2012 to the mirror slidex framework,...
We give a detailed account of the use of \(\mathbb{Q}\)-curve reductions to construct elliptic curves over \(\mathbb{F}_{p^2}\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) endomorphisms. Like GLS (which is a degenerate case of our construction), we offer the advantage over GLV of selecting from a much wider range of curves, and thus finding...
We construct the first fully secure attribute based encryption (ABE) scheme that can handle access control policies expressible as polynomial-size circuits. Previous ABE schemes for general circuits were proved secure only in an unrealistic selective security model, where the adversary is forced to specify its target before seeing the public parameters, and full security could be obtained only by complexity leveraging, where the reduction succeeds only if correctly guesses the adversary’s...
We put forth the notion of \emph{publicly evaluable} pseudorandom functions (PEPRFs), which can be viewed as a counterpart of standard pseudorandom functions (PRFs) in the public-key setting. Briefly, PEPRFs are defined over domain $X$ containing a language $L$ associated with a hard relation $\mathsf{R}_L$, and each secret key $sk$ is associated with a public key $pk$. For any $x \in L$, in addition to evaluate $\mathsf{F}_{sk}(x)$ using $sk$ as standard PRFs, one is also able to evaluate...
We select a set of elliptic curves for cryptography and analyze our selection from a performance and security perspective. This analysis complements recent curve proposals that suggest (twisted) Edwards curves by also considering the Weierstrass model. Working with both Montgomery-friendly and pseudo-Mersenne primes allows us to consider more possibilities which help to improve the overall efficiency of base field arithmetic. Our Weierstrass curves are backwards compatible with current...
We show that a Magma implementation of Joux's L[1/4+o(1)] algorithm can be used to compute discrete logarithms in the 1303-bit finite field F_{3^{6*137}} and the 1551-bit finite field F_{3^{6*163}} with very modest computational resources. Our F_{3^{6*137}} implementation was the first to illustrate the effectiveness of Joux's algorithm for computing discrete logarithms in small-characteristic finite fields that are not Kummer or twisted-Kummer extensions.
Edwards’ elliptic curve form is popular in modern cryptographic implementations thanks to their fast, strongly unified addition formulas. Twisted Edwards curves with a = −1 are slightly faster, but their addition formulas are not complete over Fp where p ≡ 3 (mod 4). In this short note, we propose that designers specify Edwards curves, but implement scalar multiplications and the like using an isogenous twisted Edwards curve.
While the hybrid public key encryption scheme of Kurosawa and Desmedt (CRYPTO 2004) is provably secure against chosen ciphertext attacks (namely, IND-CCA-secure), its associated key encapsulation mechanism (KEM) is widely known as not \CCA-secure. In this paper, we present a direct proof of IND-CCA security thanks to a simple twist on the Kurosawa-Desmedt KEM. Our KEM beats the standardized version of Cramer-Shoup KEM in ISO/IEC 18033-2 by margins of -- at least 20\% in encapsulation speed,...
Abstract: We describe an implementation of fast elliptic curve scalar multiplication, optimized for Diffie–Hellman Key Exchange at the 128-bit security level. The algorithms are compact (using only x-coordinates), run in constant time with uniform execution patterns, and do not distinguish between the curve and its quadratic twist; they thus have a built-in measure of side-channel resistance. (For comparison, we also implement two faster but non-constant-time algorithms.) The core of our...
This paper proposes the computation of the Tate pairing, Ate pairing and its variations on the special Jacobi quartic elliptic curve Y^2 = dX^4 +Z^4. We improve the doubling and addition steps in Miller's algorithm to compute the Tate pairing. We use the birational equivalence between Jacobi quartic curves and Weierstrass curves, together with a specific point representation to obtain the best result to date among curves with quartic twists. For the doubling and addition steps in...
We construct new families of elliptic curves over \(\FF_{p^2}\) with efficiently computable endomorphisms, which can be used to accelerate elliptic curve-based cryptosystems in the same way as Gallant--Lambert--Vanstone (GLV) and Galbraith--Lin--Scott (GLS) endomorphisms. Our construction is based on reducing \(\QQ\)-curves---curves over quadratic number fields without complex multiplication, but with isogenies to their Galois conjugates---modulo inert primes. As a first application of the...
In this paper, we use the theory of theta functions to generalize to all abelian varieties the usual Miller's algorithm to compute a function associated to a principal divisor. We also explain how to use the Frobenius morphism on abelian varieties defined over a finite field in order to shorten the loop of the Weil and Tate pairings algorithms. This extend preceding results about ate and twisted ate pairings to all abelian varieties. Then building upon the two preceding ingredients, we...
We propose efficient algorithms and formulas that improve the performance of side-channel protected elliptic curve computations with special focus on scalar multiplication exploiting the Gallant-Lambert-Vanstone (CRYPTO 2001) and Galbraith-Lin-Scott (EUROCRYPT 2009) methods. Firstly, by adapting Feng et al.'s recoding to the GLV setting, we derive new regular algorithms for variable-base scalar multiplication that offer protection against simple side-channel and timing attacks. Secondly, we...
At Pairing 2010, Lauter et al's analysis showed that Ate pairing computation in affine coordinates may be much faster than projective coordinates at high security levels. In this paper, we further investigate techniques to speed up Ate pairing computation in affine coordinates. On the one hand, we improve Ate pairing computation over elliptic curves admitting an even twist by describing an $4$-ary Miller algorithm in affine coordinates. This technique allows us to trade one multiplication in...
Wireless Sensor Networks (WSNs) pose a number of unique security challenges that demand innovation in several areas including the design of cryptographic primitives and protocols. Despite recent progress, the efficient implementation of Elliptic Curve Cryptography (ECC) for WSNs is still a very active research topic and techniques to further reduce the time and energy cost of ECC are eagerly sought. This paper presents an optimized ECC implementation that we developed from scratch to comply...