Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

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.

56 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
18 votes
0 answers
514 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 ...
kelalaka's user avatar
  • 48.7k
13 votes
0 answers
497 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. ...
SEJPM's user avatar
  • 46.1k
10 votes
0 answers
479 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 ...
DaWNFoRCe's user avatar
  • 872
9 votes
0 answers
251 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 ...
neubert's user avatar
  • 2,927
4 votes
0 answers
128 views

Security of ECDLP using elliptic curves over an extension field

It is known that, for an elliptic curves $E$ defined over a prime field $\mathbb{F}_p$ such that $E(\mathbb{F}_p)$ is a prime number, the best algorithms (beside some specific cases) for solving the ...
DDT's user avatar
  • 141
4 votes
0 answers
246 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=\...
wooa0923's user avatar
  • 173
3 votes
0 answers
118 views

How do you securely implement a finite field?

I'm not sure if this question belongs here or to StackOverflow. Please flag it if not. I'm trying to implement a standalone library for finite field arithmetic of prime and prime power order as a way ...
tur11ng's user avatar
  • 962
3 votes
0 answers
351 views

Fast polynomial multiplication over finite field GF(2^n)

I wonder if there is a more efficient polynomial multiplication than Karatsuba over the finite field $\operatorname{GF}(2^n)$. Brief research on this topic gave me a few results on fast multiplication ...
Lukie Boy's user avatar
3 votes
0 answers
321 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 ...
kub0x's user avatar
  • 898
3 votes
0 answers
177 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.
syed burhan's user avatar
3 votes
0 answers
436 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 ...
Aditya Pradeep's user avatar
3 votes
0 answers
261 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 \...
Paul's user avatar
  • 243
2 votes
0 answers
28 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 ...
Papa Delta's user avatar
2 votes
0 answers
119 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 ...
sam's user avatar
  • 21
1 vote
0 answers
39 views

I want to find the Zero Value Points on SECP256R1 curve... Is there an alternative to Chien's method of finding roots over large Finite Fields?

This PDF explains that on certain elliptic curves, there exists ZVP (Zero Value Points) that cause zero value registers during the scalar-to-point multiplication (i.e during the double operation or ...
Cyth's user avatar
  • 11
1 vote
0 answers
41 views

How to know the number of digits in the decimals place in elliptic curve division result?

$p$ - is the order of the finite field $n$ - is the order of the group. Private keys can range from $1$ (the generator point $G$) to $n - 1$. All the private keys ($Priv$) lie in certain ranges of 2. $...
Maltoon Yezi's user avatar
1 vote
0 answers
99 views

Number of elements in cyclic group that satisfy an exponent

I'm having trouble with solving the following question: Given two distinct prime numbers $p, q$ where $(p-1)$ and $(q-1)$ are not divisible by $3$, define $n=pq$. For how many elements in $\mathbb Z^*...
Eatay Mizrachi's user avatar
1 vote
1 answer
183 views

Multi party computation over ring and fields

I am recently reading about multi party computation and its various existing protocols. From what I understand, all the arithmetic operations are performed over a field or a ring such that when two ...
Sumana bagchi's user avatar
1 vote
0 answers
44 views

Is it secure if I disclose an element equals 1 modulo p in Zn?

Let $n = pq$, $p,q$ are two large primes, then $\mathbb{Z}_n^*\cong \mathbb{Z}_p^* \times \mathbb{Z}_q^*$. We disclose $n$ and keep $p, q$ secret. Is it secure if we disclose a random element $a$: $a\...
Bob's user avatar
  • 509
1 vote
0 answers
96 views

LPN over non-binary fields

With regard to LPN over non-binary fields like $\mathbb{F}_3,\mathbb{F}_5,\cdots$, are there any studies about that ? We also would like to know any articles that have a formal definition of the non-...
mathcat's user avatar
  • 11
1 vote
0 answers
138 views

Can we solve the ECC DLP if we can distinguish whether the doubling of a public key is accompanied by reduction (modulo n) or not?

Let $E$ be an elliptic curve over a prime or a binary extension field $GF(2^m)$, and let $G(x_g,y_g)$ be a generator point on the curve. Let $Q$ be an arbitrary point $Q = r*G$, with $r$ scalar, and $...
G. Stergiopoulos's user avatar
1 vote
0 answers
50 views

Algorithm that solves a system of linear equations over finite fields when a parameter is needed

I was reading Kipnis' and Shamir's paper on Cryptanalysis of the HFE Public Key Cryptosystem by Relinearisation and I wanted to implement the example at the end in Octave without using any additional ...
David's user avatar
  • 11
1 vote
0 answers
82 views

Proving a function in $\operatorname{GF}(2^n)$ is differentially k-uniform

I want to show that $F(x) = x^{-1}$ in $\operatorname{GF}(2^{n})$ is differentially 4-uniform for even $n$, and is differentially 2-uniform for odd $n$, without looking at the Differential ...
midmotor's user avatar
1 vote
0 answers
30 views

A finite group with a threshold functionality

I am trying to find a generator of a finite group that its powers devides the group into two parts. For example look at the last row of this table that shows the powers of 10 in the group Z_19. You ...
Mahsa Bastankhah's user avatar
1 vote
0 answers
244 views

Multiplication in Tower Field $GF(2^4)^2$

I'm currently reading an article which deals with "Squeezing Polynomial Masking into Tower Fields " for performing an efficient multiplication of elements in $GF(2^8)$. Thereby it is ...
ratbald_meyer_1995's user avatar
1 vote
0 answers
48 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 ...
SARTHAK GUPTA's user avatar
1 vote
0 answers
87 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 ...
Rob's user avatar
  • 349
1 vote
0 answers
58 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 ?
Akash's user avatar
  • 71
1 vote
0 answers
55 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 ...
WeCanBeFriends's user avatar
1 vote
0 answers
119 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 ...
user avatar
1 vote
0 answers
404 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 ...
bkoodaa's user avatar
  • 629
1 vote
0 answers
478 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 ...
mami's user avatar
  • 11
1 vote
0 answers
70 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 : ...
user51428's user avatar
  • 121
1 vote
0 answers
77 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 ...
Ward Beullens's user avatar
1 vote
0 answers
83 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 ...
RevFlash's user avatar
  • 101
1 vote
0 answers
181 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]$$ ...
juaninf's user avatar
  • 2,711
0 votes
1 answer
69 views

wrting algorithm for torsion group elements

Yesterday,I took an exam. There are two questions I received very low points. I will write the first question in this post. The question says let $E:y^2:x^3+kx+1$ in GF(p) be an elliptic curve where p ...
user avatar
0 votes
0 answers
71 views

Why do we use elliptic curves instead of just the discrete logarithm problem?

We have a cyclic field Fp where p is a prime number, a generator g, and an order n. A generator is an element such that $g^n=1$. A random number x has been chosen as the private key, selected from the ...
Saku's user avatar
  • 101
0 votes
0 answers
50 views

How to calculate Cardinality of an Elliptic curve over $\mathbb Z_{23}$

How to calculate Cardinality of an Elliptic curve over $\mathbb Z_{23}$. $E: y^2 = x^3 + x + 1$ defined over $\mathbb Z_{23}$.
Sanjai Kumar's user avatar
0 votes
0 answers
70 views

AES encryption step: calculate the byte substitution process

I am a self learner and tried to learn AES, so I have a book written in my native language. It has some practical examples about finite fields and AES. It has a question that asks me to calculate the ...
user avatar
0 votes
0 answers
76 views

AES SBOX Masking in Python

I am trying to create an AES Sbox masking based on this paper. In the paper, they tried to mask the sbox described in this other paper. The inversion is been done in GF(4). I know that it is mostly ...
John's user avatar
  • 1
0 votes
0 answers
32 views

Trustless deterministic fingerprint of additive subgroup of $GF(2^n)$

Suppose I have $k$ blocks $B_i$ each consisting of $n$ bits. For erasure code purposes I'd like to be able to produce a computationally binding deterministic hash/fingerprint/digest $H$ such that $\...
orlp's user avatar
  • 4,290
0 votes
0 answers
114 views

Hashing and Password Cracking

I was playing a game on cryptography where I encountered this problem: Hashed Value of password: 24 109 76 35 22 94 83 25 106 104 73 87 56 38 56 50 10 92 58 84 44 88 24 112 125 121 125 43 122 55 106 ...
Turing101's user avatar
  • 111
0 votes
0 answers
31 views

Checking whether a particular group has an efficient, faithful representation as a matrix group

There are cryptographic protocols being developed for non-abelian groups. For some protocols it is necessary to know whether the group has an efficient representation as a matrix group (say, a matrix ...
Buddhini Angelika's user avatar
0 votes
0 answers
77 views

Pedersen commitment on binary field $GF(2^n)$

I am curious whether one can do Pedersen commitment on $GF(2^n)$. One method I thought of was to get a prime order multiplicative subgroup of $GF(2^n)$. But for efficiency and security, what would be ...
Sean's user avatar
  • 99
0 votes
0 answers
75 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
great shark's user avatar
0 votes
0 answers
31 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 =...
Andrzej's user avatar
  • 59
0 votes
0 answers
55 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 ...
hola's user avatar
  • 603
0 votes
0 answers
36 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 \...
Buddhini Angelika's user avatar
0 votes
0 answers
45 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?
bono_silhouette's user avatar