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.
379
questions
-1
votes
0
answers
25
views
How to perform addition and multiplication in Python in finite field (GF) F_{2^2}
I am trying to code something using NMDS matrices. I need to find the minimum distance of a code. How can I do the same?
1
vote
1
answer
50
views
Near Maximum Distance Separable Code
I want to find the minimum distance of an $[8,4]$ Near MDS code over a finite field F_4 (NMDS Code is a type of linear code). I want to know which programming language has a built-in function that ...
2
votes
1
answer
232
views
Is there an algebra group (or ring) in which computing the inverse element is hard without some trapdoor information?
Specifically, I want an algebra group $G$ (or ring $R$) features:
Given elements $g,h\in G$ (or $R$ ), computing $g\cdot h \in G$ (or $R$ ) is easy.
Given an element $g \in G$ (or $R$ ), finding the ...
- 368
2
votes
2
answers
136
views
Elliptic curves over extension fields
I'm trying to understand which benefits can using of extension fields in elliptic curve cryptography bring over prime fields. Popular curves like secp256k1, curve25519, secp384r1 are defined over a ...
- 409
1
vote
1
answer
83
views
Convert multiplication in $GF(2^{128})$ to bitwise AND?
Suppose we have $GF(2^{128})=F_2[x]/(x^{128}+x^7+x^2+x+1)$ and $a,b,c \in GF(2^{128})$ with $a*b=c$, where * is multiplication in $GF(2^{128})$. Could we convert ...
- 11
0
votes
2
answers
98
views
Query about arithmetic finite fields
I was working on implementing shamir secret sharing in GF(2^256), According to my knowledge multiplication in a finite field is defined as mul(a,b) = (a*b)%mod, where mod is the irreducible polynomial....
- 33
1
vote
1
answer
102
views
learning with errors
If I talk about efficiency of system of learning with error, is it it fine for q to be composite in Z_q, the ring of integers. As when q would not be prime, Z_q will not be field anymore, won't it ...
- 63
1
vote
1
answer
150
views
On the bit security of elliptic curves
My understanding is that an elliptic curve $E$ over a finite field $\mathbf{F}_q$ has a bit security of $\sqrt{q}$ assuming Pollard rho or Baby-step giant-step. In this thread, it is explained that ...
- 13
2
votes
1
answer
81
views
Discrete log hardness when secret is multiplied by public value
Given y = g ^ x is discrete log hard on some finite field, is y = g ^ (kx) also equally secure if the value ...
- 23
0
votes
1
answer
135
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 ...
1
vote
1
answer
65
views
How to write monomials in $GF(2^n)$ as a system of equations in $GF(2)$
Let $F = GF(2^n)$ and $P(x) = x^e, P : F \rightarrow F$ be a monomial of degree $e$. How to write each bit of the output of $P$ as a function of input bits? In other words, how to write it as a system ...
- 161
1
vote
1
answer
86
views
How does big Galois groups yield better security in NTRU Prime?
I'm still kinda new to Galois theory so I apologize if this question is very obvious to some people.
Basically I'm reading this paper by the NTRU Prime team and in section 2.5 it's explaining how ...
- 13
1
vote
0
answers
82
views
Feldman Verifiable secret sharing verify [closed]
I recently started to learn about Shamir secret sharing and Feldman's VSS Scheme.
I know the concepts But I can't figure out how it works. mostly because many of modulates are with "p" and ...
- 83
5
votes
1
answer
249
views
Binary Elliptic Curves Point Doubling Formula - Calculate Lambda from P3
As I am studying ordinary (non-supersingular) binary elliptic curves in the Guide to ECC book by Hankerson (Section 3.1, page 81), for point doubling, the equations presented in the book are:
$x_3 = \...
- 53
3
votes
2
answers
181
views
"Supported groups" in RFC 8446 (TLS 1.3)
What is meant by "supported groups" in the section 4.2.7. "Supported Groups" of RFC 8446:
/* Finite Field Groups (DHE) */
ffdhe2048(0x0100), ffdhe3072(0x0101), etc:
Is the digits - ...
- 95
1
vote
1
answer
42
views
Can some cryptographic conclusions in the prime field be applied to the Galois field？
Such as integer factorization problem and discrete logarithm problem. Assuming a large polynomial is obtained by multiplying two generated polynomials, is it NP hard to decompose it into these two ...
- 23
2
votes
1
answer
82
views
Merkle tree alternating hash and polynomial
I want to get feedback on the security of a modified merkle tree data structure. Using the image above as a reference assume I have a random oracle function $H$. Assume $H$ outputs a value in $\mathbb{...
- 139
1
vote
1
answer
54
views
Prod Check Gadget in PLONK - any polynomial which satisfies the prod check seems to be the trivial polynomial
In Dan Boneh's PLONK Video - https://www.youtube.com/watch?v=vxyoPM2m7Yg he refers to the Prod Check Gadget
$\omega \in F_p$ is a primitive $k$-th root of unity ($\omega^{k-1} = 1$)
$H = \{1, \omega, \...
- 2,179
1
vote
1
answer
84
views
Hardening a polynomial checksum scheme
I have a checksum scheme that uses a simple polynomial summation as described here.
Basically I'll take a random value $R$ and a set of inputs $[v_0, v_1, v_2]$ and checksum it like $v_0*R + v_1*R^2 + ...
- 139
0
votes
0
answers
42
views
Why it is important the notion of equivalent divisors in pairing definitions?
Following the book Pairing for Beginners, the Tate pairing computation requirements are:
Let $P$ be an point on the $r$-torsion subgroup in $E(\mathbb{F}_q)$.
Let $f$ be a function whose divisor is $(...
- 722
1
vote
1
answer
86
views
Are you aware of cryptographic contexts (e.g., post-quantum) in which a square root $\sqrt{\cdot}$ must be computed in constant time?
Let $\mathbb{F}_q$ be a finite field of odd characteristic. I know that a constant-time implementation of the square root extraction $\sqrt{\cdot} \in \mathbb{F}_q$ is used in the context of hashing ...
- 395
1
vote
1
answer
38
views
Data fingerprint using multiple multilinear polynomials
Related to this question. I'm trying to find a way to use this fingerprint system without a second pre-image attack.
Assume I have a set of elements $V = [v_0, v_1, v_2]$ in $\mathbb{F}_p$. Assume the ...
- 139
2
votes
1
answer
106
views
If SNARKs generally work in finite fields, how are non integer values handled - say fixed point decimal numbers?
In Vitalik Buterin's write-up on SNARKs Quadratic Arithmetic Programs: from Zero to Hero, he writes
Note that the above is a simplification; “in the real world”, the addition, multiplication, ...
- 2,179
1
vote
0
answers
126
views
How to find square root of a point on elliptic curve over finite field?
Using spec256k1 curve, Is it possible to calculate square root of a point? And If so what point would I get if the result is not a whole number? For example Let G be generator point. square root of ...
user106642
4
votes
2
answers
366
views
Should tower field implementations use the x^k element representation?
I'm working on a friendly tower finite field implementation for educational purposes. The library should allow easy building of tower fields from smaller ones - a user may define $\mathbb F_q$ and ...
- 41
0
votes
1
answer
71
views
Galois field problem in Cryptography [closed]
This problem is related to Fields in Cryptography, My Question is why there is no multiplicative inverse for 2, isn't it 0.5?? or matters are diffrent if it was related to galois field ? I don't quite ...
1
vote
1
answer
251
views
Data fingerprint using polynomial and Schwartz-Zippel Lemma
I'm working on a protocol and am looking for a way to fingerprint a set of elements. All elements are evenly distributed across a finite field that is integers modulus $2^{256}$.
Assume I have a set ...
- 139
2
votes
1
answer
169
views
multiplicative inverse computations on binary galois fields yield partial result when sampled
I want to compute the multiplicative inverse of 0x2 over $GF(2^{233})$ in hardware.
To do so, I compute $a^{-1} = (a^{2^{m-1}-1})^{2}$. Here's the result of that ...
2
votes
0
answers
61
views
Division, scope finite fields polynomials in general vs. f.f. polynomials in ECC [closed]
A cryptography course covered among others following questions:
arithmetic of polynomials over $GF(2^m)$ fields - polynomials division
elliptic curves over field $GF(2^m)$
In scope of former point ...
- 21
1
vote
0
answers
43
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\...
- 499
2
votes
1
answer
296
views
Why can't RSA signatures be forged algebraically?
Compute $n = pq$ where p and q are prime. Fix $e$ to be coprime to $\phi(n)$. Compute $d = e^{-1} \pmod n$ and verify $ed \equiv \phi(n) \pmod n$. We sign the (hash of) a message with $s = h^{d}$. A ...
- 33
1
vote
2
answers
171
views
Proof that checking if $g^k\bmod p\ne1$ finds a generator of a cyclic group
In this post the top answer says that for $\mathbb Z_p^*$, $k$, the order of an element $g$, divides p-1. Then it was concluded that this entails we can check if $g$ is a generator by checking if $g^k\...
- 113
3
votes
0
answers
241
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 ...
- 31
1
vote
1
answer
113
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\} :...
- 11
1
vote
1
answer
422
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
61
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 ...
- 141
1
vote
0
answers
84
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
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 $\...
- 4,170
4
votes
2
answers
773
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 + ...
- 65
4
votes
2
answers
887
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?
- 55
1
vote
0
answers
41
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,487
1
vote
2
answers
94
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 ...
- 43
0
votes
1
answer
80
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
75
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?
- 25
0
votes
1
answer
77
views
How to calculate the inversion fucntion $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 ...
- 25
1
vote
2
answers
170
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) \...
- 33
2
votes
1
answer
639
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,211
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,211
1
vote
0
answers
129
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 $...
- 115
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 ...
- 115