Constructing permutation rational functions from isogenies

DOI10.1137/17M1135736MaRDI QIDQ3176494zbMATH OpenOpenAlexWikidataFDO

Authors Gaetan Bisson, Mehdi Tibouchi

Publication date 20 July 2018

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1707.06134

zbMATH Keywords

elliptic curvescryptographyisogeniespermutation rational functionsexceptional covers

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Isogeny (14K02)

Abstract: A permutation rational function $finmathbb{F}_q(x)$ is a rational function that induces a bijection on $mathbb{F}_q$, that is, for all $yinmathbb{F}_q$ there exists exactly one $xinmathbb{F}_q$ such that $f(x)=y$. Permutation rational functions are intimately related to exceptional rational functions, and more generally exceptional covers of the projective line, of which they form the first important example. In this paper, we show how to efficiently generate many permutation rational functions over large finite fields using isogenies of elliptic curves, and discuss some cryptographic applications. Our algorithm is based on Fried's modular interpretation of certain dihedral exceptional covers of the projective line (Cont. Math., 1994).

Recommendations

• Low-degree permutation rational functions over finite fields
• Tests for permutation functions
• On a type of permutation rational functions over finite fields
• Rational functions of degree four that permute the projective line over a finite field
• The rational function analogue of a question of Schur and exceptionality of permutation representations

Cites work

• scientific article; zbMATH DE number 3523640 (Why is no real title available?)
• scientific article; zbMATH DE number 1258344 (Why is no real title available?)
• scientific article; zbMATH DE number 691467 (Why is no real title available?)
• scientific article; zbMATH DE number 2086892 (Why is no real title available?)
• Deterministic encoding and hashing to odd hyperelliptic curves
• Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time
• Exceptional Covers and Bijections on Rational Points
• Impossibility of surjective Icart-like encodings
• Indifferentiable deterministic hashing to elliptic and hyperelliptic curves
• Modular polynomials via isogeny volcanoes
• The geometry of some parameterizations and encodings
• The place of exceptional covers among all diophantine relations
• The rational function analogue of a question of Schur and exceptionality of permutation representations

Cited in

(6)

• Permutable polynomials and rational functions
• The rational function analogue of a question of Schur and exceptionality of permutation representations
• Efficient inversion of rational maps over finite fields
• Permutation polynomials and elliptic curves
• Low-degree permutation rational functions over finite fields
• Arithmetically exceptional functions and elliptic curves

Describes a project that uses

Uses Software

• PARI/GP

This page was built for publication: Constructing permutation rational functions from isogenies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3176494)