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.

Filter by
Sorted by
Tagged with
9
votes
5answers
3k views

Why are finite fields so important in cryptography?

I am just getting into cryptography and currently learning by trying to implement some crypto algorithms. Currently implementing the Shamir secret sharing algorithm, what I have noticed is that finite ...
1
vote
2answers
56 views

Permutation polynomial

I want to find a linearized polynomial as my permutation polynomial in GF(2^n). I know that the only root should be 0. So, is there any way to find such polynomial instead of choosing a random one and ...
0
votes
1answer
59 views

Are Shamir shares independent?

Assume we have a secret $s \in Z_p$. We generate the set of secret shares $\{ (x_i, s_i) \}_{i=1}^{N}$ according to a $(N,k)$ Shamir's scheme. The evaluations are generated according to the following ...
1
vote
0answers
36 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 ...
2
votes
3answers
218 views

Pohlig-Hellman: While solving in a subgrp, why is multiplication done mod the parent group's $p$ while the exponent is expanded as per $p_i$ of subgrp

In the Pohlig-Hellman algorithm, we take a Discrete Log Problem (DLP) in a group & solve it in subgroups $p_1^{n_1}$, $p_2^{n_2}$, $p_3^{n_3}$ etc & then combine it with the Chinese Remainder ...
2
votes
3answers
143 views

Where to apply Montgomery Multiplication in GF(2^n)

I'm optimizing a Reed Solomon decoding library for several polynomials in $\operatorname{GF}(2^k)$, $k\in\{8,10,12\}$. Reading about the Montgomery Multiplication from Çetin K. Koç & Tolga Acar's ...
1
vote
2answers
86 views

Multiparty Computation to calculate addition of shares without revealling individual shares

I have $n$ persons, each holding a secret integer $x_i$ ($i$ from $1$ to $n$) and I'm looking for a way for them to jointly compute the sum of these secrets without revealing to each other their ...
0
votes
1answer
67 views

Finding Multiplicative Inverse In Field

Consider the finite set Z_257 of non-negative integers less than 257. The number 257 is a prime, so Z_257 forms a field with addition and multiplication mod 257. How can I use the Extended Euclidean ...
2
votes
1answer
63 views

How does table size impact table lookup speed?

Are there good discussions of how cache pressure impacts large 64k-ish lookup tables used in erasure coding and sometimes signature verification? I'll focus on erasure coding in small characteristic ...
2
votes
1answer
88 views

Constant Time algorithms for $\mathbb{Z}/m\mathbb{Z}$, $\mathbb{Z}/m\mathbb{Z}[x]$, and $\mathbb{Z}/m\mathbb{Z}[x] / (f(x))$?

I want to implement some (lattice based) protocols to better familiarize myself with a programming language (Rust). These tend to do arithmetic over rings like $\mathbb{Z}/m\mathbb{Z}$, or "...
0
votes
0answers
30 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 ...
5
votes
2answers
322 views

Must a line hitting two points on the elliptic curve over a finite field hit another point by continuation?

The Arstechnica article title as "A (relatively easy to understand) primer on elliptic curve cryptography" claims this; In fact, you can still play the billiards game on this curve and dot ...
2
votes
1answer
96 views

Problem with the signature of message using ECDSA over GF(2^m)

I'm trying to set up an ECDSA with Elliptic Curves over $\operatorname{GF}(2^m)$ with an example of toy with the following values: Using the Weierstrass equation on binary finite fields. $$E: y^2 + x*...
4
votes
2answers
152 views

Doubt on elliptic curve over a finite field and binary representation

I'm a programmer, i.e. agnostic to the mathemathics behind most of cryptographic scheme, but I'm trying to remediate. I'm writing this premise for any possible error or imprecision that I probably put ...
0
votes
0answers
47 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
1
vote
2answers
124 views

Question about the proof of the change of base formula for the discrete logarithm

I was looking at the proof of a change of base formula for the discrete logarithm in this paper (page 6, 4th bullet indent). In the intruduction, the paper states: Let $F_q$ be a finite field of order ...
0
votes
0answers
42 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(...
4
votes
1answer
283 views

Why Abstract Algebra in Cryptography?

I come from an engineering background, but not from computer science or anything to do with pure math. I studied applied math in college--never abstract algebra, number theory, or discrete math, ...
1
vote
1answer
131 views

Solving Diffie-Hellman vs DLP

I'm wondering what is the current knowledge regarding the difficulty of solving the Diffie-Hellman problem (DHP). Obvisously solving the DLP (discrete log) is at least as hard as solving the DH ...
0
votes
0answers
25 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
1answer
25 views

On the hardness of addition when the elements of a field is represented by the powers of generator and possible any existant scheme

We can represent elements of a finite field $F$ in various ways polynomial basis and normal basis. There is one other; generator-based representation and this is based on the fact that the ...
2
votes
2answers
217 views

How to find the co-efficients of a function within Zp[x]?

I am a newbie in Finite Field arithmetic and while trying to implement an Elliptic Curve Cryptography based ABE scheme in a programming language, I am unable to understand how to implement function ...
6
votes
2answers
1k views

Need help understanding math behind Rijndael S-Box

in Rijndael SubBytes() step all bytes of input block are substituted based on a lookup table S-Box. S-Box is initialized by taking all elements of $GF(2^8)$, ...
0
votes
0answers
51 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 ...
2
votes
1answer
306 views

Cryptographic properties of field multiplication

While reading about AES-GCM, I discovered there is a multiplication over $\operatorname{GF}(2^{128}$). My question is about its cryptographic properties, such as: Take a random element $X$ from $\...
5
votes
2answers
216 views

Why use prime number $q$ such $q$| $(p-1)$ in discrete logarithm based schemes?

In discrete logarithm based schemes on finite field we have a prime number $q$ that divides $p-1$ and $q$ is to specify a subgroup with the order $q$. But why do we do that? Why do not we work on the ...
4
votes
1answer
201 views

How does Montgomery reduction work?

I want to reduce a multi-precision integer $x$ modulo a prime $p$, very fast. Performing the traditional Euclidean division for only calculating the modulo, is inefficient and modular reduction is at ...
3
votes
2answers
469 views

Distribution of the Difference of Uniformly Random Elements

In the search to decision reduction of 'On Ideal Lattices and Learning with Errors over Rings', the authors implicitly use the fact that the difference of distinct, uniformly random elements of a (...
2
votes
1answer
275 views

Complexity of Gaussian Elimination over a Finite Field

I read somewhere that the complexity of solving a Linear $n\times n$ system over a Finite Field $\Bbb F_q$ using Gaussian Elimination is $\mathcal{O}(n^3)$ operations in $\Bbb F_q$. What's the role of ...
2
votes
1answer
1k views

Multiplicative inverse in ${GF}(2^4)$

I want to create a $4\times4$ multiplicative inverse table in $GF(2^4)$. The primitive polynomial given is $P(x)= x^4+x+1$ (NOTE: the values in the table need to be in hexadecimal format, hence I'll ...
14
votes
0answers
218 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 ...
3
votes
2answers
516 views

Constant time multiplication in GF(2^8)

I am trying to implement AES in C; I would like to make it resistant to side-channel attacks but I can't implement the multiplication in constant time. My current code: ...
7
votes
1answer
529 views

How do client and server agree on the values of p and g during DHE exchange?

How do the communicating parties using Finite Field DHE agree on the values of the $p$ and $g$ variables? Are their values fixed for each DHE group? Reading through the TLS 1.3 RFC (8446), the client ...
0
votes
0answers
34 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
1answer
63 views

In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?

Shamir's Secret Sharing Scheme uses arithmetic in a finite field of prime order. In a secret image sharing scheme, what are the advantages of Galois field $\mathrm{GF}(p^m)$ over finite field $ F_p$?
4
votes
1answer
163 views

Itoh Tsuji algorithm

I'd like to use the Itoh-Tsujii algorithm for a dynamic substitution table, but I do not get the following line: $$r\ \gets\ (p^m - 1)\,/\,(p - 1)$$ And why can $r$ be used to calculate the ...
1
vote
1answer
55 views

RSA assumption and relationship given by generating elemts of a Cayley graph

I have read a very interesting description of computation related to the RSA group as follows. "By the Chinese remainder theorem, we have that: $$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\...
3
votes
1answer
149 views

Is there a multiplicative group of integers modulo p in which the discrete logarithm is easy?

The complexity of computing discrete logarithms in a multiplicative group modulo a prime $p$ is assumed to be sub-exponential time. The complexity is determined by $q$, the biggest factor of the group ...
1
vote
0answers
36 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 ...
4
votes
1answer
119 views

Distinguishing between a Polynomial and a Laurent Polynomial

Let $f(x) \in \mathbb{Z}_p[x]$ (for a prime $p \gg d$) be a polynomial of degree $d$, and let $g(x)$ be a Laurent polynomial with the same degree and only the first negative exponent term ($g(x) = \...
2
votes
1answer
121 views

Diffie-Hellman with Galois field

I Google around and can't find any page mentioning Diffie-Hellman with Galois field $GF(p^n)$ with $n>1$. Is there a reason for this? For example, wouldn't Diffie-Hellman with $GF(2^n)$ be ...
4
votes
1answer
85 views

Relationship between generating elements given by cycles in Cayley graph

The strong RSA assumption is that the following problem is hard to solve. "Given a randomly chosen RSA modulus $n$ and a random $z \in \mathbb{Z}_n^*$, find $r>1$ and $y \in \mathbb{Z}_n^*$ such ...
0
votes
1answer
35 views

Decoding in Reed solomon codes

I have code encoded in GF(7) with primitive 5 Сf(4,1,0,4,5,5). (last four symbols is redundancy) While decoding using DFT we use formula $$ С_k=N^{-1}*c(z^{-kj}) $$ example: $$ C_1 = c(5^{-1*j})/6 ...
1
vote
1answer
423 views

Prime fields vs non-prime fields

I was watching this class about AES in this LINK and I was trying to grasp the concept of prime fields, which is a finite field with prime order $p$. The non-prime field part (order is $p^n$) is ...
3
votes
1answer
125 views

Inversion in $GF(2^{10})$ Using Composite Fields

I'm designing a circuit that uses many $GF(2^{10})$ inverters. Normally for this sort of thing I use lookup tables. (Itoh-Tsujii is not efficient for these smaller fields.) This application is for ...
0
votes
0answers
38 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?
4
votes
1answer
409 views

Prove that the $x^8+x^4+x^3+x+1$ is irreducible over $\mathbb{Z}_2[x]$

I am new to this field. I am doing some cryptography course and have encountered $\text{GF}(2^8)$ in the famous AES algorithm. Although I do not have a strong relevant math background with this stuff(...
1
vote
1answer
81 views

How to make this cipher strong?

Suppose I have an arbitrary 256 bit number $m$ another secret number $k$ of the same bit length, and then I multiply them both modulo a 256 bit prime number $p$ to get $c$ as follows: $$ c = (m\cdot k)...
1
vote
0answers
71 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 ...
2
votes
1answer
86 views

Finding subgroup in elliptic curve over finite field $ \mathbb{F}_{11}$

For elliptic curve $ y^2 = x^3 +3x+7$ I found the finite group $ E(\mathbb{F}_{11})= \left\{ \mathcal{O}, (1,0),(5,2),(5,9),(8,2),(8,9),(9,2),(9,9),(10,5),(10,6) \right\}$. I have to find a ...

1
2 3 4 5
7