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
14
votes
0answers
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 ...
11
votes
0answers
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.
...
8
votes
0answers
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 ...
7
votes
0answers
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 ...
3
votes
0answers
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 ...
3
votes
0answers
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.
3
votes
0answers
203 views
Homomorphic encryption over finite fields
I'm curious on the following question: let $\mathbb{F}_{2^n}$ be a finite field which is an extension of $\mathbb{F}_2$ with order of $n$, is there an encoding scheme $e:=\mathbb{F}_{2^n}\rightarrow \...
2
votes
0answers
136 views
Solving not so much overdetermined system of multivariate polynomial equations
I'm studying algorithms solving multivariate equations. I'm stuck in solving overdetermined set of quadratic equations. Concretely, with the number $n$ of variables, the number of equations is $m=\...
2
votes
0answers
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 ...
2
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ?
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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 :
...
1
vote
0answers
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 ...
1
vote
0answers
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 ...
1
vote
0answers
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]$$ ...
0
votes
0answers
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
0
votes
0answers
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(...
0
votes
0answers
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 =...
0
votes
0answers
44 views
Cryptographic properties of field multiplication (Continued)
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 ...
0
votes
0answers
33 views
Finding the relationship given by the generating elements of a non-abelian group (for a maximum case) where they correspond to finding cycles
Let $G=(\mathbb{Z}_p \times \mathbb{Z}_p) \rtimes_{\phi} \mathbb{Z}_q$, where $p$ and $q$ are odd distinct primes. Let $G$ be generated by the elements $s=(g_1,e_q)$ and $t=(e_p,g_3)$,
$g_1,e_p \in \...
0
votes
0answers
34 views
How to Solve Discret Log Computation Problem
Given $g^a$ in $Z_p$, it is hard to get the solution $a$. Everyone says yes, I wonder why it is hard. Could anyone give a specific mathematical way to show it is indeed hard?
0
votes
1answer
102 views
Is the following non-interactive zero-knowledge set membership protocol provable secure?
Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9).
The Verifier
-...
0
votes
0answers
54 views
How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?
A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
0
votes
0answers
367 views
Multiplicative inverse ($17^{-1} \mod 31$)?
So. Sorry for bothering you with such a simple question, but I can't really get this done.
It's just an exam question in which I need to use CRT in order to calculate the RSA signature of a msg m=101(...
0
votes
0answers
202 views
Discrete log in Galois Extension Field
I was reading 'Pinocchio Coin' paper by Danezis et al. where they have said,
"If we use the efficient pairing groups of Pinocchio, computing discrete logarithms in the exponent field $\mathbb{F}_p$ ...
-1
votes
1answer
588 views
Cube root modulo prime
I make research about big numbers in finite fields and I need to calculate a cube root modulo prime P for the number N:
...
-1
votes
1answer
127 views
How to find roots of equation $f(x)=0 \pmod p $, where $p$ is prime number?
$f(x)$is any nth degree equation $n>0$, how to find roots of $f(x)$ over prime modulo.
-2
votes
1answer
68 views
Given a point $c$ in a field $Z_p$. Can we get another value $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?
If we have a point in a field $c$. Can we get another value $c^{'}$ such that
$\left(c^{\prime}-c\right)$ is invertible in $Z_p$ ?
