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
0answers
30 views

MULalpha and DIValpha operations in SNOW 3G

I'm not able to appreciate the importance of mul alpha and div alpha operations in feedback polynomial of LFSR in SNOW 3G. What problems or weakness do they help in mitigating and how ?
1
vote
1answer
39 views

What does MULx operation in SNOW 3G correspond to?

According to the spec, MULx operation is defined as - MULx maps 16 bits to 8 bits. Let V and c be 8-bit input values. Then MULx is defined: If the leftmost (i.e. the most significant) bit of V ...
1
vote
1answer
57 views

Computational Complexity: ECC multiplication vs Modular multiplication

How does performing scalar multiplication on an elliptic curve compare to exponentiation in a multiplicative group modulo a prime? I.e. on a given elliptic curve of size $|t|$, what's the complexity ...
0
votes
1answer
47 views

Get points of an Elliptic Curve defined over a Finite Field on Twisted Edwards Extended Coordinates

I'm working on a crypto library, and I need to perform some tests for the implementation of: Point Addition. Point Subtraction. Point Doubling. Scalar Mul Point. The operations are performed on ...
1
vote
0answers
45 views

Constructing Low-Density Parity-Check Codes of length $n$ and minimum distance = $\delta n$ over $GF(q)$? [closed]

I am looking for a way to construct an LDPC (Low-Density Parity-Check) Code $C$ of length $n$ and minimum distance $d_C$ that scales linearly to $n$, meaning $d_C = \delta n$ for $\delta \in (0,1)$. ...
10
votes
0answers
237 views

How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time. ...
0
votes
1answer
63 views

Explanation of trace function $\operatorname{Tr}_m(x) = x^{2^{m}} \oplus x$

The following statement is from a paper (Partitions in the S-Box of Streebog and Kuznyechik) about S-Boxes: For all $ x \in \operatorname{GF}(2^{n})$, it holds that $x^{2^{n}} \oplus x = 0$. If $...
1
vote
1answer
38 views

Does any problem arise when the order of an elliptic curve is equal to its prime field modulus? [duplicate]

Regarding cryptographic schemes in elliptic curve cryptography, is there a problem with having the order of an elliptic curve being equal to its prime field modulus? That is, an elliptic curve where $...
3
votes
0answers
66 views

Group Rings on Cryptography

Let $R[G]$ or $RG$ be the group ring where $R=F_q$ and $G$ is any group. Let $Dim(V)=\vert G \vert$. It's clear that $V$ has $\vert R \vert^{\vert G \vert}$ distinct $\vert G \vert$-tuples. This ...
2
votes
0answers
89 views

Solving not so much overdetermined system of multivariate polynomial equations

I'm studying algorithms solving multivariate equations. I'm stuck in solving overdetermined set of quadratic equations. Concretely, with the number $n$ of variables, the number of equations is $m=\...
2
votes
1answer
81 views

Are there any security risks in using Elliptic Curves defined over fields $\mathbf{F}_{p^n}$ where $n>1$

I've recently been studying elliptic curves, and I've found that most of the current implementations use fields $\mathbf{Z_p}$ or in some cases $\mathbf{F}_{2^n}$. All the reasons I've seen for not ...
0
votes
0answers
18 views

What is the difference between these pairings classifications?

I know the basic definitions of bilinear groups. For example, there is a bilinear pairing that uses elliptic curves and has the following properties: For $G_1$, and $G_2$ are cyclic groups of prime ...
3
votes
2answers
182 views

How are these AES MixColumn multiplication tables calculated?

I'm using the mul2, mul3, mul9, mul11, mul13 and mul14 tables for the MixColumn and InvMixColumn steps in AES-128. However, I got these off some Github repository, and now I'm looking for an actual ...
3
votes
1answer
50 views

Is inversion always cheap with Twisted Edwards curves?

I'm reading on Jubjub, which is planned for the next upgrade of Zcash. It is based on a Twisted Edwards curve with parameters $a = -1$ and $d = −(10240/10241)$. The reading says Jubjub does not need ...
2
votes
2answers
113 views

Why aren't Complex number fields used in cryptography?

Most of the cryptography is limited to use of real integer fields. Complex numbers are seldom used. Is there any reason for it? Wouldn't complex numbers provide more structure? If there is already ...
1
vote
0answers
55 views

How do I find an efficient sqrt algorithm for primes? [closed]

For example, If my prime was congruent to 3 mod 5. Is there a list where I can find for these primes which do not take the form 3 mod 4? Edit: Excluding the general tonelli-shanks algorithm
0
votes
1answer
52 views

Is the following non-interactive zero-knowledge set membership protocol provable secure?

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9). The Verifier -...
-2
votes
1answer
36 views

Given a point $c$ in a field $Z_p$. Can we get another value $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$?

If we have a point in a field $c$. Can we get another value $c^{'}$ such that $\left(c^{\prime}-c\right)$ is invertible in $Z_p$ ?
1
vote
1answer
67 views

Is there a concept of embedding degree for non-pairing based elliptic curves?

From this post, I learned the concept of embedding degree. Intuitively, if embedding degree of an elliptic curve $E(F_p)$ is $k$, it means there is a way to transform points in $E(F_p)$ to $F_{p^k}$. ...
-1
votes
1answer
51 views

Elliptic curve over prime field with high order roots of unity

Suppose I have an elliptic curve defined over a prime field $\operatorname{GF}(p)$ where $p$ is a large prime (e.g. 256-bit). Suppose also that $p = kn +1$, where $n$ is a relatively large power of $2$...
-1
votes
1answer
45 views

Finding a prime field with n-th roots of unity

How can I find the smallest prime $p$, such that field $GF(p)$ has $n$-th roots of unity? For example, I know that for $p=2^{256} - 351 \times 2^{32} + 1$ there exit roots of unity for $n=2^{32}$. ...
2
votes
1answer
92 views

Standard basis representation of elements in binary field

In Remark B.1 from this paper it says: We assume canonical representation for binary fields $\mathbb{F}$, given by an irreducible polynomial and a primitive element $g \in \mathbb{F}$ for it (i.e., ...
1
vote
0answers
42 views

How to find multiplicative inverse of a hexadecimal number in the finite field GF(2^8)? [duplicate]

I am new to cryptography. As I was reading a note regarding S-box construction, I found a step mentioning multiplicative inverse of a number in the finite field GF(2^8). I couldn't understand it!! Can ...
0
votes
1answer
46 views

How to calculate the order of the subgroup?

Given a curve with points over GF(p), a subgroup of prime order q and a co-factor h. How do I calculate the size of q which is ...
1
vote
1answer
27 views

Cost model for different curve models

Is there a cost model for each curve model and their conversions? For example: Take the curve models: Projective, Completed, Extended, Affine. Is there a table which shows how many multiplications, ...
1
vote
0answers
37 views

Efficient fields over arithmetic circuits

What sort of fields is efficient over an arithmetic circuit? Efficient meaning that given a field $\mathbb{F}_p$, reduction (modulo) does not require many multiplications and preferably inversion was ...
0
votes
1answer
56 views

Computing a sextic twist

Let $(x,y) \in E'_{\mathbb{F}_{p^2}}$ be a point of the sextic twist. I am currently trying to compute: $\psi : (x, y) \leftarrow (\mu^2x,\mu^3y)$ with $\mu \in \mathbb{F}_{p^{12}}$ the root of $(Y^...
1
vote
1answer
40 views

ECDSA over $\mathbb{F}_{p^n}$ for $n>1$. How to calculate $r$ and $s$

I'm having some trouble understanding how to calculate $r$ and $s$ as specified in the wikipedia page for ECDSA (https://en.wikipedia.org/wiki/Elliptic_Curve_Digital_Signature_Algorithm) We can see ...
0
votes
1answer
65 views

Is the One Time Pad secure in additive Rings?

Let's assume all operations are done on $\mathbb{Z}_p$ where $p$ is a large non-prime number. To mask a value $a$, we do the following: Pick a uniformly random value: $r$, from the ring. Do as ...
1
vote
1answer
80 views

What is the inverse function of the finite field GF($2^3$) and GF($2^4$)?

I am currently reading a paper Cryptanalysis of a Theorem Decomposing the Only Known Solution to the Big APN Problem. In this paper, they mention that they used $I$ which is the inverse of the finite ...
0
votes
0answers
37 views

Explanation of Gallant-Lambert-Vanstone method / Endomorphism speedups [duplicate]

Can someone explain how the Gallant-Lambert-Vanstone method works (or which literature explains it)? It is also unclear to me how the Frobenius endomorphism can be used in some cases for a speedup. ...
0
votes
0answers
47 views

How can a node establish pairwise shared key with other nodes using its own polynomial share together with other's public values?

A server has a symmetric bivariate polynomial $ F(x, y) = \sum_{{i,j}=0}^{t-1}a_{i,j}x^iy^j$ $\in GF(p)[X, Y] $ of degree $t-1$. For simpliciy, $ F(x, y) = a_{0,0}+a_{1,0} x+a_{0,1}y+ a_{1,1}xy$ mod ...
2
votes
1answer
62 views

What is the difference between the 23 bi-affine and the 39 fully quadratic equations of the rijndael sbox?

In Cryptanalysis of Block Ciphers with Overdefined Systems of Equations Nicolas Courtois and Josef Pieprzyk define 23 so called bi-affine equations (in Appendix A of the paper) between the input x and ...
3
votes
1answer
248 views

Relationship between Fibonacci LFSR and Galois LFSR

I'm studying about LFSR and have some troubles understanding LFSRs. For Galois LFSR, it is clear that LFSR just multiplies $x$, the primitive element of $GF(2^n)$, so that it makes all the elements ...
0
votes
1answer
120 views

Does a Finite Field of 36 elements exist? [duplicate]

I'm having a little trouble understanding the finite fields theory, so I'm sorry if my question would seem a little stupid. I wanted to know if a finite field of 36 elements could exist. Basically, I ...
1
vote
1answer
79 views

Inverse of an element in a RSA group

Consider a RSA group $Z_N$ for $N=pq$, where $p,q$ are large prime numbers. Under strong RSA assumption, can an adversary efficiently compute the inverse of a random element $z$ from $Z_N$ without ...
4
votes
1answer
83 views

Difficulty of forging MACs based on linear functions over $GF\left(2^n\right)$

This is a homework question, therefore I'm not expecting full solutions, just general guidance. I want to build a one-time MAC using universal hashing. I defined my hash functions as: $h_{a,b}:\...
3
votes
1answer
118 views

Elliptic curves on finite fields

I've been reading: https://github.com/bellaj/Blockchain/blob/6bffb47afae6a2a70903a26d215484cf8ff03859/ecdsa_bitcoin.pdf On page 22 it shows an eliptic curve over F17. I have added the orange lines ...
5
votes
2answers
110 views

Why does libSTARK use binary fields as opposed to prime fields for zk-SNARKs?

zk-STARKs make use of FRI for low degree testing of polynomials. The zk-STARKs paper states on page 11: we stress that ZK-STARK could also operate over prime fields but we have not realized this ...
1
vote
1answer
87 views

What is the difference between subtracting the modulus from a scalar field element and reducing it?

When implementing a Field element, we define the necessary operations on the data structure. One function that I see is a "scalar reduce" function, which effectively reduces a random scalar so that ...
0
votes
0answers
58 views

Prove I know a value v in a set s.t. K = H(v) [duplicate]

Is it possible to prove that I know a value v in a finite set, such that the hash of the value v is K. Where v is private and K is public
9
votes
1answer
255 views

how does BearSSL's GCM modular reduction work?

BearSSL (in src/hash/ghash_ctmul.c) seems to be doing a modular reduction that I don't completely understand. Here's the code: ...
0
votes
1answer
96 views

Why only non-prime order fields have small subgroup attacks?

Why don't prime-order curves have small subgroup attacks? It seems that I can choose a Generator such that it has a small order, maybe 2 points, and so an attack could generate all of the points in ...
1
vote
1answer
107 views

For an elliptic curve, what is the difference between the base field modulus $Q$ and subgroup $r$

What is the difference between the basefield modulus $Q$ and a subgroup of prime order $r$? They are all fields, but what is their relevance to the curve they are defined upon? How does this relate ...
7
votes
0answers
134 views

GCM with reversed poly

These slides talk about how GCM can be sped up if one uses $x^{128}+x^{127}+x^{126}+x^{121}+1$ as the reduction polynomial instead of $x^{128}+x^7+x^2+x^1+1$. When one is doing that one needs to ...
-1
votes
1answer
116 views

find additive inverse of modular arithmetic [closed]

For a set to be called as a ring, it should have the following properties closed commutative associative Identity existence Inverse existence but how is Z7 a ring, as there aren't any inverse ...
7
votes
2answers
946 views

Should we use IANA groups 14 (MODP), 25, and 26 (ECP)?

By looking at SonicWall Knowledge Base article Key exchange (DH) Groups Supported - Site to Site VPN: It appears that our firewall supports DH group 25, and 26. Almost everywhere I've seen, they've ...
5
votes
1answer
563 views

Why doesn't the GCM spec use a more efficient multiplication algorithm?

NIST SP 800-38D § 6.3 Multiplication Operation on Blocks describes a multiplication algorithm that, in my testing, appears to be a good amount slower then algorithm 2.40 (arbitrary reduction ...
1
vote
1answer
71 views

GHASH with a finite field multiplication algorithm in reverse order

NIST SP 800-38D § 6.4 GHASH Function describes the GHASH algorithm thusly: Prerequisites: block $H$, the hash subkey. Input: bit string $X$ such that len($X$) = $128m$ for some positive ...
0
votes
1answer
48 views

modular reduction algorithm over $F_{2^m}$ doesn't seem to work when order of polynomial being reduced is small

I was considering algorithm 2.40 (arbitrary reduction polynomials) in the Guide to Elliptic Curve Cryptography and... it doesn't appear to work when the order of the polynomial you're trying to ...