# Questions tagged [finite-field]

A finite field is a mathematical construct based on a set of axioms which are held to be true. A number of interesting and useful properties arise from finite fields that makes them particularly suitable for use in cryptography, notably in block ciphers. Questions concerning finite fields should use this tag. Your question may concern finite fields if you are asking about AES, block ciphers or modular arithmetic.

36 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
174 views

### The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020

Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field Computation of a 30 750-Bit Binary Field Discrete Logarithm, Robert Granger and Thorsten ...
405 views

### How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time. ...
273 views

### Share Conversion between Different Finite Fields

Let us have any linear secret sharing scheme (LSSS) that works on some field $Z_{p}$, where p is some prime or a power of a prime e.g., Shamir Secret Sharing, Additive secret Sharing. The problem at ...
167 views

### GCM with reversed poly

These slides talk about how GCM can be sped up if one uses $x^{128}+x^{127}+x^{126}+x^{121}+1$ as the reduction polynomial instead of $x^{128}+x^7+x^2+x^1+1$. When one is doing that one needs to ...
212 views

### Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
155 views

### How to map the points of an elliptic curve cyclic group to $\mathbb{Z}_q$ using a hash function?

Let $E$ be an elliptic curve defined over $\mathrm{GF}(q)$, where $q=p^r$. Let $G$ be a cyclic group of points of $E$. Then how we can map points of $G$ into $\mathbb{Z}_q$ using a hash function.
203 views

338 views

### Construction of Isomorphism between Galois Fields

I am trying to create an isomorphism between GF($2^8$) and an extension field in GF($(2^4)^2$). The finite field GF($2^8$) uses the Rijndael(AES) irreducible polynomial.In this field I have found 128 ...
100 views

### How many Affine function can be made from $4 \times 4$ and $8 \times 8$ S-boxes?

The nonlinearity of an S-Box is defined as the non-linearity of its vectorial Boolean Function. Let $F$ be the hamming distance between the set of all non-constant linear combinations of component ...
33 views

### Determining order of the group for an elliptic curve defined over a finite field

I need to find out the order of the group for an elliptic curve. See the image for the question. The inequality condition after simplification leads to $-2 \sqrt{p} \leq m \leq2 \sqrt{p}.$ Also, the ...
21 views

### A related question to “relationship between generating elements given by cycles in Cayley graphs”

I am writing this question with reference to the post at Relationship between generating elements given by cycles in Cayley graph When considering the generating elements $g_qg_p$, does it have the ...
69 views

### Looking for a group where multiplicative inverse is hard but calculating multiple pairwise inverses is easy

I have an equation that comes up in trying to do an Attribute Based Encryption scheme, where users have certificates that sign off on attributes that are also watermarked. I perform a division to ...
47 views

### MULalpha and DIValpha operations in SNOW 3G

I'm not able to appreciate the importance of mul alpha and div alpha operations in feedback polynomial of LFSR in SNOW 3G. What problems or weakness do they help in mitigating and how ?
43 views

### Efficient fields over arithmetic circuits

What sort of fields is efficient over an arithmetic circuit? Efficient meaning that given a field $\mathbb{F}_p$, reduction (modulo) does not require many multiplications and preferably inversion was ...
100 views

### Numerical Algebraic geometry in the finite fields

Does the numerical algebraic geometry method work in the finite fields? I am working on this method to find a solution for a low-degree proximity testing problem. Would you please guide me how they ...
224 views

### How to use Galois LFSR to find multiplicative inverses

My question is how can a Galois Linear Feedback Shift Register be used to discover multiplicative inverses of polynomials? This is a homework assignment. Here is a list of things I did before asking ...
17 views

### Legendre conditions on the factors of the fundamental negative discriminant to minimize the 2-Sylow subgroup of the class group

If we know the prime factorisation of the fundamental negative discriminant $\Delta_K$, say $\Delta_K=p_1\cdot p_2 \cdots p_n$, then we are guaranteed that at least $2^{n-1}\mid h_K$, the class number ...
300 views

### Expressing a given linear transformation in Galois Field GF(256) in terms of another linear transformation with a different reduction polynomial

Before giving a better and detailed description of what I ask, let me first tell why I need what I am looking for: Intel processors already provide instructions (AES-NI) for very efficient AES ...
62 views

### Grøstl MixBytes Python implementation

I am trying to find an efficient way to implement the GrĆøstl matrix multiplication on python3. So far I have managed to get this result : ...
63 views

### Efficient proof of linear subspace membership

I am trying to find an efficient method of doing the following: Let $U$ be a $d$-dimensional linear subspace of $\mathbb{F}_q^n$. I want a protocol between a trusted party $T$, a prover $P$ and a ...
76 views

### Using quadratic residue to learn the sign of a field element

Given $x' \in \{-x, x\} \bmod q$ (where $q$ could be any prime of my choice), $s$ is a random element in the field, $y = x'\cdot s$ and $y' = \pm\sqrt{(x\cdot s)^2}\bmod q$ (i.e., both solutions to ...
176 views

### Can you provide an example in relation to Hidden Field Equations Multivariate?

I'm reading about Hidden Field Equations Multivariate scheme. My lecture states that the central map is a univariate polynomial $$P(X)=\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}p_{ij}x^{q^i+q^j} \in K[X]$$ ...
35 views

### Matrix multiplicative inverse

How to determine the inverse multiplicative matrix of the following two irreducible polynomials GF(2^8) x^8 + x^5 + x^3 + x^2 + 1 and x^8 + x^5 + x^4 + x^3 + x^2 + x +1
38 views

### Generalization of Bezout Identity for Polynomials

Let $i \in \{1,\ldots, n\}$, $f_i(x)$ be a univariate polynomial, and $g(x) = \mathsf{GCD}(f_1(x), \ldots,f_n(x))$. According to Bezout identity, there exists $a_i(x)$ such that: \sum_{i \in [n]}a_i(...
22 views

### How fast compute high degree power in finite field?

We need find y for some x on elliptical curve in cases: decompressing public key restoring public key from signature for given message hash, r and s. This algorithm uses power twice: first it is y1 =...
This question follows-up from this question/comment. Suppose, you are given $X \odot Y$, where $X~(\neq 0) \in \operatorname{GF}(2^{128})$ is random, $Y~(\neq 0) \in \operatorname{GF}(2^{128})$ is ...