# 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.

302 questions
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 "...
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 ...
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 ...
1answer
96 views

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, ...
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 ...
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 =...
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 ...
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 ...
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)$, ...
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 ...
1answer
306 views

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$?
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 ...
1answer
55 views

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 ...
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 ...
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?
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(...
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)...
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 ...
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 ...