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

389 questions
Filter by
Sorted by
Tagged with
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}$.
1 vote
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 ...
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 ...
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 ...
1 vote
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 ...
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 ...
• 103
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 ...
1 vote
96 views

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 - ...
• 95
1 vote
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 ...
• 23
96 views

• 2,181
1 vote
85 views

• 732
1 vote
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 ...
1 vote
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
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, ...
• 2,181
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 ...
• 41
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 ...
1 vote
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 ...
• 139
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 ...
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 ...
• 21
1 vote
44 views

• 113
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 ...
1 vote
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
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}}})$.
1 vote
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 ...
• 141
1 vote
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-...
• 11
32 views

• 95