Constructing permutation rational functions from isogenies

DOI10.1137/17M1135736zbMATH Open1428.11208arXiv1707.06134OpenAlexW2963758330WikidataQ129509421 ScholiaQ129509421MaRDI QIDQ3176494FDOQ3176494

Authors: Gaetan Bisson, Mehdi Tibouchi 

Publication date: 20 July 2018

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

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).

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The rational function analogue of a question of Schur and exceptionality of permutation representations
• Indifferentiable deterministic hashing to elliptic and hyperelliptic curves
• Modular polynomials via isogeny volcanoes
• The place of exceptional covers among all diophantine relations
• Title not available (Why is that?)
• Title not available (Why is that?)
• Exceptional Covers and Bijections on Rational Points
• The geometry of some parameterizations and encodings
• Impossibility of Surjective Icart-Like Encodings
• Deterministic encoding and hashing to odd hyperelliptic curves
• Encoding points on hyperelliptic curves over finite fields in deterministic polynomial time

Cited In (3)

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

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)