“School of Mathematics”

Back to Papers Home
Back to Papers of School of Mathematics

Paper   IPM / M / 16321
School of Mathematics
  Title:   Uniform encodings to elliptic curves and indistinguishable point representation
  Author(s):  Reza Rezaeian Farashahi (Joint with M. Fadavi)
  Status:   Published
  Journal: Des. Codes Cryptogr.
  Year:  2020
  Pages:   DOI: 10.1007/s10623-020-00753-8
  Supported by:  IPM
Many cryptographic protocols which are based on elliptic curves require to efficiently encode bit-strings into the points of a given elliptic curve such that the encoding function satisfies computability, regularity, and samplability, or generally admissibility. All the admissible encoding functions from the finite field Fq are restricted to the class of elliptic curves with a non-trivial l-torsion Fq-rational point, where l∈2,3. Therefore, there is no admissible encoding function to the class of many cryptographically interesting elliptic curves of prime order. In this paper, we present an admissible 2:1 encoding function from the set 0,1,…,q−12 to the Fq-rational points of arbitrary elliptic curves. We also propose an injective encoding function to elliptic curves with a non-trivial Fq
-rational point of order two, that acts the same as the Bernstein et al.’s injective encoding function. Conversely, occasionally we have to transmit points of a known curve through an insecure channel. Traditional methods for transferring points enable an adversary to recognize patterns in the transmitted data. Consequently, one finds valuable information to attack the cryptosystem using the network traffic. By the help of the inverse of the injective encoding functions, Bernstein et al. introduced an interesting solution to this problem, namely Elligator. In this paper, we present an indistinguishable elliptic curve point representation using our given encoding function, which unlike the previous well-known encoding functions is not injective but covers almost all of elliptic curves over odd characteristic finite fields. Indeed, since we proposed a 2:1 encoding function to elliptic curves in short Weierstrass form, we have to select one pre-image randomly and transmit its corresponding bit-string instead of the point.

Download TeX format
back to top
scroll left or right