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
0 answers
33 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
1 vote
1 answer
118 views

Ring Learning With Errors : why is it called ring and referred it as Ring LWE

I am curious about the structure of the quotient ring in Ring LWE. So $R=\mathbb Z[x]/(x^n+1)$, where $x^n+1$ is an irreducible polynomial and $n$ is a power of 2. So, this structure would not be a ...
user479610's user avatar
0 votes
0 answers
52 views

Multiplication of two Shamir Secret Shares [closed]

In Shamir Secret Sharing, I'm trying to figure out that how can I multiply a constant and shares with different mods (fields) and obtain the multiplication of this constant and secret? Assume ...
Semiramis's user avatar
0 votes
0 answers
43 views

Finite Field Arithmetic _ Montgomery reduction

In an attempt to understand the mathematical operations related to encryption with elliptic curves, in particular finite field arithmetic (Modular reduction) I found in the Montgomery reduction that ...
Nawras Hussein's user avatar
1 vote
1 answer
124 views

How to calculate Legendre Symbol in secp256k1 Elliptic Curve

In this answer by fkraiem he proves a property that: $a^{(p-1)/2} = 1$ if and only if $x$ is even But this doesn't seem to work in my test with the secp256k1 Elliptic Curve. Here is my Python 2 ...
Devanshu Linux's user avatar
0 votes
2 answers
51 views

What weaknesses are worth investigating in this non-linear matrix cipher?

I have an interesting cipher based on matrix products that I've not seen before. Given plaintext bytes $p\in[0,255]$, pad to a perfect square length and write into the entries of an $n\times n$ matrix ...
flinty's user avatar
  • 103
0 votes
1 answer
93 views

In multiplicative subgroup Fp* of an elliptic curve does multiplying an element make it leave the subgroup?

In the case of an Elliptic curve over a GF(p) which has order n and multiplicative group of n-1 elements, does multiplication of an element of a subgroup of order q where q is a divisor of n-1 with a ...
immigrantswede's user avatar
1 vote
0 answers
96 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
3 votes
1 answer
120 views

Problem with efficiency of projective coordinates in Elliptic Curve arithmetic

Ok sort of long post incoming. Will go slow to make it as clear as possible I'm trying to build a C library for Elliptic Curve Arithmetic. Since the idea is to learn from the process, I decided to ...
popeye's user avatar
  • 95
3 votes
0 answers
112 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
0 votes
0 answers
55 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
53 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
1 vote
1 answer
62 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 ...
Kurious Koder's user avatar
2 votes
1 answer
247 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 ...
ming alex's user avatar
  • 368
2 votes
2 answers
173 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 ...
pacman's user avatar
  • 429
1 vote
1 answer
99 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 ...
Halulu's user avatar
  • 11
0 votes
2 answers
106 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....
CipherNewbie's user avatar
1 vote
1 answer
125 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 ...
user479610's user avatar
1 vote
1 answer
160 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 ...
bobby's user avatar
  • 13
2 votes
1 answer
83 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 ...
ManishB's user avatar
  • 23
0 votes
1 answer
149 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
1 answer
66 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 ...
Mairon's user avatar
  • 161
1 vote
1 answer
91 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 ...
faust's user avatar
  • 13
1 vote
0 answers
95 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 ...
user109261's user avatar
5 votes
1 answer
273 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 = \...
prairie99's user avatar
3 votes
2 answers
203 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 - ...
LUN's user avatar
  • 95
1 vote
1 answer
43 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 ...
ZhuJerry's user avatar
2 votes
1 answer
96 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{...
vimwitch's user avatar
  • 139
1 vote
1 answer
56 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, \...
user93353's user avatar
  • 2,181
1 vote
1 answer
85 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 + ...
vimwitch's user avatar
  • 139
0 votes
0 answers
45 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 $(...
Bean Guy's user avatar
  • 732
1 vote
1 answer
89 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 ...
Dimitri Koshelev's user avatar
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 ...
vimwitch's user avatar
  • 139
2 votes
1 answer
121 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, ...
user93353's user avatar
  • 2,181
4 votes
2 answers
368 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 ...
tk2928's user avatar
  • 41
0 votes
1 answer
87 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 ...
Mohamed Mohamed Mourad Abdel W's user avatar
1 vote
1 answer
254 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 ...
vimwitch's user avatar
  • 139
2 votes
1 answer
188 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 ...
thatbangaloreanguy's user avatar
2 votes
0 answers
70 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 ...
Lilkp2's user avatar
  • 21
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
2 votes
1 answer
313 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 ...
Jeffrey's user avatar
  • 33
1 vote
2 answers
194 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\...
John Rawls's user avatar
3 votes
0 answers
280 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
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\} :...
Parsa G's user avatar
  • 11
1 vote
1 answer
426 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}}})$.
Arthur Strong's user avatar
1 vote
2 answers
62 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 ...
Viren Sule's user avatar
1 vote
0 answers
87 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
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,230
4 votes
2 answers
821 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 + ...
popeye's user avatar
  • 95
5 votes
2 answers
942 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?
Archies's user avatar
  • 65

1
2 3 4 5
8