On the additive index of the Diffie-Hellman mapping and the discrete logarithm
Pierre-Yves Bienvenu, Arne Winterhof · 2026
Read On the additive index of the Diffie-Hellman mapping and the discrete logarithm by Pierre-Yves Bienvenu, Arne Winterhof (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-13034.txt.
Introduction
Pierre-Yves Bienvenu and Arne Winterhof study how complex two key crypto maps are. One map is the Diffie-Hellman map, used to set shared keys. The other is the discrete log, the hard reverse task that keeps such keys safe. Both act inside a finite field, a closed set of numbers with fixed size.
Past work scored these maps by traits such as degree, how sparse they are, and a times based index. In 2022 Reis and Wang added a new score, the additive index, for maps of a finite field to itself. Bienvenu and Winterhof take up that new score for the two crypto maps. Their results help map where the true hard core of these tasks lies.
Catalog record
| CREATOR | Pierre-Yves Bienvenu, Arne Winterhof |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 52 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-13034
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
On the additive index of the Diffie-Hellman mapping and the discrete logarithm Pierre-Yves Bienvenu, Arne Winterhof Abstract . Several complexity measures such as degree, sparsity and multiplicative index for cryptographic functions including the Diffie-Hellman mapping and the discrete logarithm in a finite field have been studied in the literature. In 2022, Reis and Wang introduced another complexity measure, the additive index, of a self-mapping of a finite field. In this paper, under certain conditions, we determine lower bounds on the additive index of the univariate Diffie-Hellman mapping and a self-mapping of 𝔽 q {\mathbb{F}}_{q} which can be identified with the discrete logarithm in a finite field. 1. Introduction For the whole paper, we fix a prime number p and an integer n\geq 1 and put q=p^{n} . Every notion of linear algebra should be understood with respect to the ground field {\mathbb{F}}_{p} . 1.1. Diffie-Hellman mapping and discrete logarithm For a divisor T of q-1 , let \gamma\not=0 be an element of (multiplicative) order T in the finite field {\mathbb{F}}_{q} with q elements. Then the Diffie-Hellman mapping to the base \gamma is the bivariate function D(X,Y) defined by D(\gamma^{x},\gamma^{y})=\gamma^{xy},\quad 0\leq x,y\leq T-1. Any efficient way of calculating D(\gamma^{x},\gamma^{y}) for a large set of pairs (x,y) would have an important impact to public-key cryptography, in particular, the Diffie-Hellman key-exchange could be attacked, see for example [ 11 , Chapter 3] . However, there are several results in the literature that this is not the case in view of several complexity measures for D , see in particular the monograph [ 14 ] . For example, it can be shown that D(X,Y) cannot be represented by a low-degree polynomial (for large T ), see [ 2 , 16 ] . The univariate Diffie-Hellman mapping to the base \gamma is the function d=d_{\gamma} defined by d(\gamma^{x})=\gamma^{x^{2}},\quad 0\leq x\leq T-1. Since D(\gamma^{x},\gamma^{y})^{2}=d(\gamma^{x+y})d(\gamma^{x})^{-1}d(\gamma^{y})^{-1},\quad 0\leq x,y\leq T-1, and both inversion in {\mathbb{F}}_{q}^{*}={\mathbb{F}}_{q}\setminus\{0\} and square-root finding can be done in (probabilistic) polynomial time, see for example [ 1 , Sections 5.4, 7.1 and 7.2] , any fast evaluation method for d(\gamma^{x}) would lead to one for D(\gamma^{x},\gamma^{y}) . Again any univariate polynomial which interpolates d(X) on a large subset must have large degree as well as large sparsity, see [ 9 , 10 , 14 ] and references therein. Moreover, the discrete logarithm or index of \gamma^{x} to the base \gamma is {\rm ind}_{\gamma}(\gamma^{x})=x,\quad 0\leq x\leq T-1. If T<p , in particular, if q=p is a prime, we may identify the discrete logarithm with a mapping from the subgroup of {\mathbb{F}}_{q}^{*} of order T into \{0,1,\ldots,T-1\}\subset{\mathbb{F}}_{q} , however, for non-prime q we get only the discrete logarithm modulo the characteristic p of {\mathbb{F}}_{q} and lose information about the exact integer value of the discrete logarithm. Hence, it is more natural to study the following mapping: Let (\beta_{1},\ldots,\beta_{n}) be an ordered basis of {\mathbb{F}}_{q} over {\mathbb{F}}_{p} and \xi_{x}=x_{1}\beta_{1}+\cdots+x_{n}\beta_{n} whenever x=x_{1}+x_{2}p+\cdots+x_{n}p^{n-1},\quad 0\leq x_{i}<p, be an ordering of the elements of {\mathbb{F}}_{q} . For a fixed element \gamma of {\mathbb{F}}_{q}^{*} of order T the discrete logarithm ind γ can be identified with a mapping P of the subgroup of {\mathbb{F}}_{q}^{*} of order T into {\mathbb{F}}_{q} defined by P(\gamma^{x})=\xi_{x},\quad x=0,1,\ldots,T-1. More recently, the multiplicative index of f(X)=d(X) and f(X)=P(X) was studied in [ 6 ] , that is the index of the largest subgroup S of G such that f(X)X^{-r} is constant on each coset of S for some positive integer r . In this paper we prove similar results on the additive index introduced by Reis and Wang in [ 13 ] for d(X) and P(X) , respectively. In fact, in the spirit of the references mentioned above, we provide lower bounds (depending on m ) for the additive index of any self-mapping of {\mathbb{F}}_{q} that coincides with either of these mappings on all but m elements of their domain \langle\gamma\rangle , that is interpolation polynomials of these two mappings. 1.2. The additive index A polynomial over {\mathbb{F}}_{q} of the form M(X)=\sum_{j=0}^{n-1}a_{j}X^{p^{j}},\quad a_{j}\in{\mathbb{F}}_{q}, is called linearised (or p -polynomial ), see for example [ 12 , Section 2.1.6] . Note that M(X) is an {\mathbb{F}}_{p} -linear map if we consider {\mathbb{F}}_{q} a vector space, that is, M(a\xi+b\zeta)=aM(\xi)+bM(\zeta),\quad a,b\in{\mathbb{F}}_{p},\quad\xi,\zeta\in{\mathbb{F}}_{q}. In fact a simple counting argument shows that any {\mathbb{F}}_{p} -endomorphism of {\mathbb{F}}_{q} ( {\mathbb{F}}_{p} -linear self-mapping of {\mathbb{F}}_{q} ) is induced by a linearised polynomial; we provide the details in the appendix (Proposition 13 ). A linearised polynomial is sparse and has at most n non-zero coefficients. Moreover, in a normal basis representation, calculating p^{j} th powers is just a shift of coordinates and thus considered free, see for example [ 8 , Section 2.3] . Hence linearised polynomials can be efficiently evaluated in O(n) \mathbb{F}_{q} -operations in normal basis representation and in O(n^{2}\log p) \mathbb{F}_{q} -operations using repeated squaring, see [ 1 , Section 5.4] , taking an arbitrary basis representation. Here, as usual, f=O(g) means |f|\leq cg for some constant c>0 . Sometimes we also use f\ll g or g\gg f instead. If the implied constant may depend on some parameter \varepsilon , we write f\ll_{\varepsilon}g . A mapping F:{\mathbb{F}}_{q}\rightarrow{\mathbb{F}}_{q} is of additive index p^{k} and codimension k if there is a linearised polynomial M(X)\in{\mathbb{F}}_{q}[X] and a linear subspace U_{0} of dimension n-k with disjoint cosets U_{i} , i=0,1,\ldots,p^{k}-1 , such that F(\xi)=M(\xi)+a_{i},\quad\xi\in U_{i},\quad i=0,1,\ldots,p^{k}-1, for some a_{0},a_{1},\ldots,a_{p^{k}-1}\in{\mathbb{F}}_{q} , see [ 13 , Definition 4.2] . Remark . The counting argument alluded to above reveals that M may be assumed to have degree at most p^{n-k-1} , see Corollary 7 in the appendix. Note that a mapping of additive index p^{k} and codimension k is also a mapping of additive index p^{k^{\prime}} and codimension k^{\prime} for any k^{\prime} with k\leq k^{\prime}\leq n . The least codimension of F is the smallest k such that F has codimension k . Then p^{k} is the least additive index of F . Thus if the least codimension is 0 , the mapping F is simply an {\mathbb{F}}_{p} -affine function. In the contrary, if the least codimension is as large as possible, that is n , the mapping F shows no linear behaviour. It is worth noting that when q is large, the proportion of maps {\mathbb{F}}_{q}\rightarrow{\mathbb{F}}_{q} that have codimension strictly less than n among all self-mappings of {\mathbb{F}}_{q} becomes vanishingly small, see Corollary 9 in the appendix. A generic mapping {\mathbb{F}}_{q}\rightarrow{\mathbb{F}}_{q} has therefore least codimension n , and a mapping of codimension <n is very much untypical, “non-random”. Besides degree, sparsity and multiplicative index, the additive index is therefore another measure for the complexity of a function, that is, its unpredictability and thus suitability in cryptography. Partly we will use a slight abuse of terminology when we write additive index instead of least additive index. Moreover, the additive index of the functions d or P , respectively, which are defined only on a subset of {\mathbb{F}}_{q} , refers to any function on {\mathbb{F}}_{q} which coincides with d or P on this subset. 1.3. Statement of some results and structure of the paper We have a variety of results dealing with various cases – different regimes according to the cardinality T of \langle\gamma\rangle as a function of q , different methods according to