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
0 votes
1 answer
64 views

Is product of two linear combinations over a finite field information hiding?

Suppose we have a 32-bit message $ M=(m_1,..m_{32}) \in \{0, 1\}^{32} $ and we have secrets $ F_{i, b} $ and $ G_{i, b} $ (2x32+2x32=128 secrets in total). $$ \forall 1 \leq i \leq 32, b \in \{0, 1\} :...
1 vote
1 answer
380 views

Diffie-Hellman over $GF(2^{128})$

Can I use Diffie-Hellman over, say, $GF(2^{128}) \bmod$ irreducible poly in $GF(2^{128})$ instead of $GF(p)$? If not, why? Or increase it to $GF(2^{2^{\text{whatever}}})$.
1 vote
2 answers
50 views

Linear complexity of real and complex sequences

In cryptography output sequences of stream ciphers are binary valued (or more generally finite field valued). However mathematically sequences over real and complex variables can also be generated by ...
1 vote
0 answers
61 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-...
  • 11
0 votes
0 answers
26 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 $\...
  • 4,090
0 votes
0 answers
23 views

Optimal frequency of modulo operation in finite field arithmetic implementation

I'm trying to implement finite field arithmetic to use it in Elliptic Curve calculations. Since all that's ever used are arithmetic operations that commute with the modulo operator, I don't see a ...
  • 35
2 votes
2 answers
469 views

Are all quadratic twists of an elliptic curve equivalent?

I'm studying ECC, so this is focused on elliptic curves over finite fields. I've always seen the quadratic twist $E'$ of an elliptic curve $E$ defined as the elliptic curve with equation $dy^2=x^3 + ...
  • 35
4 votes
2 answers
712 views

Why are binary extension fields preferred for Shamir secret sharing?

It is known that Shamir's secret sharing works over any finite field but I don't get it why binary extension fields are preferred?
  • 43
1 vote
0 answers
31 views

How is point addition for points of elliptic curve in $\mathbb{F}_p$ carried out technically? [duplicate]

From a very basic introduction text to elliptic curve cryptography point arithmetic is derived from "standard analysis": The (negative) sum of $P_1$ and $P_2$ is defined as the Point $P_3$, ...
  • 1,447
1 vote
2 answers
63 views

How to safely and randomly iterate a key derived from Scrypt?

I'm developing a way to deterministically generate private keys for arbitrary elliptic curves based on some user-input (a brain-wallet). Currently, I'm using the Scrypt password hashing algorithm with ...
  • 13
0 votes
1 answer
71 views

Can form of elliptic curve digital signature equation be simpler?

I am curious why equations for signing/validating with ECDSA have forms they have. Is it possible to use simpler equation that have same properties. For example, this is an equation I found in the ...
0 votes
1 answer
63 views

How to caculate the inverse of function $x^3$ in $\mathbb{F}_{2^n}$

How to caculate the inverse of function $x^3$ in $\mathbb{F}_{2^n}$?, Any monomial $x^d$ is a permutation in the field $\mathbb{F}_{2^n}$ iff $gdc(d,2^{n}-1)=1$,why?
0 votes
1 answer
34 views

How to calculate the inversion fuction S:S:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_{2^n},with S(x)=x^{-1}

The S-box is defined as the generalised inverse function $S:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_{2^n}$,in quotient ring $\mathcal{R}:=\mathbb{F}_{2^n}[X]/(X^{2^n}-X)$ with $S(x)=x^{-1}$, is ...
1 vote
2 answers
61 views

Why use negacyclic convolutions for polynomial multiplication instead of regular convolutions?

When multiplying polynomials from $\mathbb{Z}_q[X] / (X^n-1) $, the discrete NTT is used because: $$ f \cdot g = \mathsf{NTT}_n^{-1}\left( \mathsf{NTT}_n\left(f\right) * \mathsf{NTT}_n\left(g\right) \...
2 votes
1 answer
138 views

Carry-less multiplication vs. multiplication in $GF(2^k)$

I implemented carry-less multiplciation using the CLMUL instruction set. This is similarly fast to simple modulo multiplication. But computating the result mod some polynomial is still very slow. I do ...
  • 1,043
9 votes
2 answers
2k views

On what Galois field AES really works?

I'm trying to understand the GF theory, but every time I come across information about AES it all makes no sense. In my opinion $GF(2^8)$ defines any polynomial of the form: $a_{7} x^7 + a_{6} x^6 + ...
  • 1,043
1 vote
0 answers
69 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 $...
5 votes
1 answer
1k views

Can there be identical elliptic curve groups of points from different irreducible polynomials in binary extension fields?

Let $E$ be an elliptic curve over a binary extension field $GF(2^m)$, with constructing polynomial $f(z)$ be an irreducible, primitive polynomial over $GF(2)$, and let $G(x_g,y_g)$ be a generator ...
0 votes
0 answers
94 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 ...
  • 111
0 votes
0 answers
29 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 ...
  • 1
0 votes
1 answer
98 views

Find multiplicative inverse in Galois field $2^8$ using extended Euclides algorithms

I'm dealing with Galois fields $GF(2^{8})$ and need help finding a polynomial $r^{-1}(x)$ such that $r^{-1}(x) r(x) \equiv 1 \mod m(x)$, where: $m(x) = x^{8} + x^{4} + x^{3} + x + 1$ $r(x) = u(x) - ...
4 votes
1 answer
149 views

Given a cycle $x \mapsto x^a$ with his starting point $x_1$. Can another starting point $x_2$ be transformed to generate the same cycle?

A cyclic sequence can be produced with $$s_{i+1} = s_i^a \mod N$$ with $N = P \cdot Q$ and $P = 2\cdot p+1$ and $Q = 2\cdot q+1$ with $P,Q,p,q$ primes. and $a$ a primitive root of $p$ and $q$. The ...
  • 475
2 votes
1 answer
77 views

Any way to find $g,P$ for max cycle size in Blum–Micali with $x_{i+1} = g^{x_i} \mod P $ and $x_0 = g$?

For some $g$ and prime $P$ the sequence $$x_{i+1} = g^{x_i} \mod P $$ $$ x_0 = g$$ can contain all numbers from $1$ to $P-1$ and with this it is a pseudo-random permutation of those numbers (EDIT: ...
  • 475
2 votes
1 answer
41 views

How difficult is finding $i$ for sequence $s_{i} = g^{s_{i-1}} \mod P$ with $s_0 = g$ for given value $v\in [1,P-1]$

Assuming we found a constant $g$ and a prime $P$ which is able to produce all values from $1$ to $P-1$ with it's sequence $$s_{i} = g^{s_{i-1}} \mod P$$ $$s_0 = g$$ How many steps are needed to ...
  • 475
2 votes
1 answer
69 views

How difficult is finding $i$ in tetration $^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\cdot^{g}}}}_i\equiv v \mod P$ for $v\in[1,P-1]$

EDIT: I messed up something (see comments at answer). This question contains some false statements EditEnd. For tetration modulo prime $P$ $$^{i}g = g\uparrow \uparrow i = \underbrace{g^{g^{\cdot\cdot\...
  • 475
4 votes
0 answers
83 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 ...
  • 141
0 votes
1 answer
79 views

Finding collisions of polynomial rolling hashes

A polynomial hash defines a hash as $H = c_1a^{k-1} + c_2a^{k-2} ... + c_ka^0$, all modulo $2^n$ (that is, in $GF(2^n)$). For brevity, let $c$ be a $k$ dimensional vector (encapsulating all the ...
2 votes
1 answer
67 views

homomorphic mapping from $F_{p^n}$ to $Z_{p^n}$

Is it possible to have a homomorphic mapping from $F_{p^n}$ to ${\mathbb Z}_{p^n}$ that preserves both the add and multiplication operators? Or if we relax requirement, can we have a homomorphic ...
  • 57
2 votes
2 answers
118 views

Cyclic codes as ideals of a quotient ring

I'm finding the algebra behind cyclic codes somewhat tricky. The starting point is easy enough: $C\subseteq \mathbb F_q^n$ is cyclic if any cyclic shift of a codeword $c\in \mathbb F_q^n$ is still in $...
1 vote
1 answer
78 views

Understanding the algebra behind GCM's security

I would like to understand the algebra behind GCM's security. Before I ask my questions, let me state my understanding of the math behind GCM. If correct, my questions are at the end; if incorrect, ...
0 votes
0 answers
47 views

Secure multi-party computation made simple - questions

The scheme that I refer to is from this paper. A secret $s\in D$ is obtained by splitting s into a random sum. We have (actually linear) for any $k$ this $k$-out-of-$k$ secret-sharing scheme: Select $...
1 vote
2 answers
194 views

In AES-256, what exactly forms the extension field $GF(2^8)$?

My question is a little difficult to describe, so let me first start with an analogy In an elliptic curve over a finite field, there are 2 groups - the first group is a finite field over which the ...
  • 1,823
2 votes
2 answers
457 views

Program to find the inverse of polynomial [closed]

Can anyone tell me how to find the inverse of a given polynomial using python programming? Ex: input given is to find the inverse of (x^2 + 1) modulo (x^4 + x + 1). the output should be : (x^3 + x + 1)...
1 vote
2 answers
119 views

What is the meaning of $F_{p^k}$ and the elliptic curve over it, $E(F_{p^k})$?

In pairing based cryptography, there will be the finite field $F_{p^k}$ where $p$ is prime number and $k$ is an integer. The elliptic curve is constructed on that finite field as $E(F_{p^k})$. For ...
0 votes
1 answer
66 views

Structure of composition of permutations

If $P_1, P_2$ are finite permutations, what can we say about $P_3 = P_1 \cdot P_2$? That is, what properties of the composition of permutations can be inferred from the properties of the permutations ...
2 votes
2 answers
188 views

A field element as the exponent of a group element

The R1CS constraints are expressed over finite fields. Many proofing systems, such as zk-SNARK, use prover keys such as $g^{\alpha^0}, g^{\alpha^1}, ..., g^{\alpha^n}$ where $\alpha$ is a field ...
  • 57
1 vote
1 answer
227 views

How to find integer point of a ec curve in a given range?

I was looking inside the basics of ecc and found the examples from Internet either uses continuous domain curve or use a very small prime number p like 17 in a ...
1 vote
0 answers
77 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 ...
  • 13
0 votes
2 answers
83 views

Algebraic Normal Form of a function in $\operatorname{GF}(2^{n})$

Consider the function $f(x)=x^{2k+1}$ in $\operatorname{GF}(2^{n})$ for $n$ odd and $\gcd(k,n)=1$, which is differentially 2-uniform function. For $n=3$, $k=1$, I want to find the Algebraic Normal ...
  • 13
2 votes
1 answer
232 views

Poly1305 reuse of r

Poly1305 uses $r, r^2, r^3$ and $r^4$. I understand this if $r$ is a generator of the finite field. But since $r$ can be any random non-zero number, won't its exponents be non-uniform distributed? ...
0 votes
1 answer
86 views

Understanding non-linearity in Salsa20 over various rings

In his design of Salsa20, Bernstein writes to ensure non-linearity he chose 32-bit addition (breaking linearity over $Z/2$), 32-bit xor (breaking linearity over $Z/2^32), and constant-distance 32-bit ...
1 vote
1 answer
594 views

How to calculate the order of secp256k1?

The elliptic curve secp256k1 is defined as $y^2 = x^3 + 7$. The prime for the field is set to: ...
  • 113
3 votes
2 answers
358 views

Recognize whether two random values are raised to the same power

Alice selects two random numbers from a finite field $Z_p$ : $a$ and $b$. Bob does one of the two following steps randomly (sometimes he does step 1; sometimes step 2): He chooses a random number $r$ ...
6 votes
1 answer
711 views

How to determine if a point is just a point or a valid public key?

In ECC, specifically over finite fields, in my mind there must be other points that exist that still yield $y^2 \bmod p=x^3 + ax + b \bmod p$ to be true but are never used because the Generator Point (...
2 votes
2 answers
128 views

Discrepancy $δ$ in the Berlekamp-Massey Algorithm

I have a question regarding to the Berlekamp–Massey algorithm. Can someone guide me to understand the idea/intuition of this algorithm? According to the explanation in Wikepedia, in each iteration, ...
1 vote
0 answers
28 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 ...
0 votes
0 answers
28 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 ...
11 votes
5 answers
4k 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 ...
  • 121
1 vote
2 answers
106 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 ...
  • 53
0 votes
1 answer
106 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
2 3 4 5
7