Encoding to Legendre curve, Kummer Line and twisted Edwards curve

For applications of elliptic curve cryptography in censorship circumvention, the traffic generated by a cryptographic protocol must appear indistinguishable from uniformly random strings to blend in with random traffic. To address this challenge, previous works have proposed various mappings that map finite field elements to elliptic curve points, focusing primarily on short Weierstrass, Montgomery, and (twisted) Edwards curve forms. In this article, we primarily focus on the Legendre curve $ \mathsf{E}_\lambda: y^2 = x(x-1)(x-\lambda) $ targeting the Kummer lines, ensuring no exception points and a constant-time algorithm. We present two such mappings: Elligator-L3 and Elligator-L1. Elligator-L3 maps elements of a prime field $ \mathbb{F}_q $, where $ q\equiv3\pmod4 $, to a Legendre curve $ \mathsf{E}_\lambda $ with $ \chi(\lambda) = -1 $, while Elligator-L1 maps elements of $ \mathbb{F}_q $, where $ q\equiv1\pmod4 $, to $ \mathsf{E}_\lambda $ with $ \chi(\lambda) = 1 $. We also extend these mappings to Kummer lines, resulting in Elligator-K3 and Elligator-K1.Previously, Bernstein et al. [2] proposed two efficient encoding-decoding functions: Elligator-1 and Elligator-2. Elligator-1 maps elements of a prime field $ \mathbb{F}_q $ with $ q\equiv3\pmod4 $ to an Edwards curve $ E_{1, d}: x^2 + y^2 = 1 + dx^2y^2 $ with $ \chi(d) = -1 $ and vice versa. Elligator-2, in contrast, considers Montgomery curves over a prime field and can be extended to twisted Edwards curves. However, to operate on any element of the prime field, Elligator-2 requires primes of the form $ 1\pmod4 $. Addressing this, we propose a new map, Elligator-T, which enables encoding from a prime field $ \mathbb{F}_q $ with $ q\equiv3\pmod4 $ to a complete twisted Edwards curve with no exception points. Further, we extend it to a $ y $-coordinate only mapping called Elligator-T$ _y $.Elligator-T is crucial in verifiable XEdDSA (VXEdDSA) signatures [25]. However, VXEdDSA requires the computation of square roots to manage compressed point representations. To overcome this, we introduce the verifiable quotient Edwards curve Digital Signature Algorithm (VqEdDSA), which utilises Elligator-T$ _y $ and relies solely on $ y $-coordinate arithmetic. VqEdDSA eliminates the need for square root computations, replacing them with a few field multiplications. We propose several twisted Edwards curves and squared Kummer lines over prime fields for cryptographic applications, leveraging the newly introduced Elligator maps.