11 votes
Accepted

Advantages of Montgomery Ladder-based Scalar Multiplication

Synthetically, the advantages of the Montgomery ladder are that it is simple and fast. If you look at X25519, the Diffie-Hellman algorithm applied to Curve25519 and described in RFC 7748, you will see ...
user avatar
7 votes
Accepted

Why does AES use a Binary Field?

Well, there would be two possible ways to use modular arithmetic: You could do the arithmetic modulo $2^n$. However, that has some nasty properties (not all elements have multiplicative inverses, ...
user avatar
  • 132k
6 votes
Accepted

How do Käsper and Schwabe's Bitsliced AES Mixcolumns work?

Slide #8 in the presentation you linked to describes the way Käsper and Schwabe pack the bits of the AES data blocks into CPU registers. According to the slide, what they're doing is processing eight ...
user avatar
6 votes
Accepted

What is the branch number of this matrix?

The matrix is not MDS over $GF(2)$; No binary MDS codes exist and non nonbinary (over $GF(2^n)$ MDS codes would have this generator whose scalar entries are in the field $GF(2)$). Over $GF(2^n)$ The ...
user avatar
  • 16.4k
5 votes
Accepted

Prove the branch of number of Advanced Encryption Standard

The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument. We have two definitions for MDS (Maximum Distance Separable) ...
user avatar
  • 304
4 votes
Accepted

How to calculate active s-boxes from branch number?

Khazad has an $8\times 8$ MDS matrix $A$ used as the diffusion layer. The augmented matrix $[I|A]$ generates a $[n,k,d]=[16,8,9]$ MDS code over $GF(2^8).$ The implications are: The minimum number of ...
user avatar
  • 16.4k
4 votes
Accepted

How do we reduce the multiplications in the AES mix column layer using $x^4 +1$

The $x^4+1$ is implicit in the matrix. What you are doing is that you consider formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ for $z_i$ elements of the field $\mathbb{F}_{256}$, and a ...
user avatar
4 votes

How can I get the binary form of AES's MDS matrix in MixColumns tranformation?

Concretely, given an element $x \in$ GF($2^8$), to multiply it by 2, we simply do a left shift and xor with 0b100011011 if the result of the shift gets above 0b11111111 (255). To multiply by 3, we ...
user avatar
  • 121
4 votes

What is the time complexity of the basic components of a symmetric cipher?

I cannot find anything simple on time complexity for cryptographic components (functions?) as describable above You wont really find anything because those components are generally not described that ...
user avatar
  • 12.7k
4 votes

How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$

Let $\bf A$ be an $n \times n$ binary matrix. Let we want to check that whether $\bf A$ is an MDS matrix over the finite field $\mathbb{F}_{2^k}$ for some $k$? The necessary condition is that $k\mid n$...
user avatar
  • 233
3 votes

What is the time complexity of the basic components of a symmetric cipher?

You may need to specify your model of computation to make your question answerable. In some models bitwise XOR is ${\rm O}(n)$ in the number of bits being XORed; it others it can be ${\rm O}(1)$, ...
user avatar
3 votes
Accepted

How can I get the binary form of AES's MDS matrix in MixColumns tranformation?

Here is a Sage code that creates the MDS matrix over $F_2$. ...
user avatar
3 votes

How can I get the binary form of AES's MDS matrix in MixColumns tranformation?

This question can be used to get what you want. There we use bytes (so expand those to bits) and you have to use extra XOR's (i.e. binary additions) to get the field multiplications.
user avatar
3 votes

Why are $\{0,1\}$-matrices almost-MDS only when n is 2, 3, or 4?

From the article on page 5; Theorem 1 Let $A:{GF(2^m)}^n \to {GF(2^m)}^n$ be an $n\times n \{0,1\}$-matrix over $GF(2^m)$. Then the branch number of $A$ is at most $\frac{2n+4}{3}$. Let $A$ be the ...
user avatar
3 votes

Hill Cipher question

You would need (at least) 3 pairs of vectors in order to determine the 3*3 matrix.
user avatar
3 votes
Accepted

How to calculate the branch number of a linear mapping?

As explained in the answer to the question here the branch number of a linear mapping $$ A:F_q^n \rightarrow F_q^n, \quad x\mapsto A\cdot x $$ is the minimum weight of the linear code generated by the ...
user avatar
  • 16.4k
3 votes
Accepted

Questions on LWE with a repeated secret matrix S

The distinguishing problem with a single sample $x$ is impossible. This is because for any non-zero $x$ and any $u$ there exists an $S$ such that $Sx=u$. ETA 20220405: For the broader question of ...
user avatar
  • 10.5k
2 votes
Accepted

How to perform AES MixColumns as matrix multiplication in GF(2) (boolean values)?

Assume that we have to compute $M\times x$, where $M$ is a $n\times n$ matrix, and $x$ is a $n\times 1$ vector, all entries of $M$ and $x$ are in $GF(2^8)$. We have: $$ M\times x = M \times \left( \...
user avatar
  • 233
2 votes

Affine transformation in AES: Matrix representation

In literature there are 2 ways to show the affine transform for a given polynomial, and that depends on the location of the MSB in the input as a polynomial. The polynomial representation of the full ...
user avatar
  • 12.7k
2 votes

Direct sum of Binary numbers In Mixcolumns

You misunderstand $(02) \cdot 10000100$; it is not integer multiplication (resulting in a 9 bit integer); instead, it is multiplication in $GF(2^8)$ (which results in an element in $GF(2^8)$, which ...
user avatar
  • 132k
2 votes
Accepted

Matrix Trapdoor AB+BA

How difficult is it to find $b$? If the matrices within $R$ are of dimension $n \times n$, then we can express the equation $u = a \cdot b + b \cdot a$ as $n^2$ linear equations over the finite field ...
user avatar
  • 132k
2 votes
Accepted

How difficult is inverting a non-square matrix?

As far as I know, there is no well-behaved and canonical topology on finite fields that would enable a consistent and useful definition of pseudoinverse. The main point in computing pseudoinverses ...
user avatar
  • 16.4k
2 votes
Accepted

Found a mistake in a proof about when GGH will decrypt incorrectly

Okay, this was a really stupid mistake by me. I got confused because some sources use notation where $R$ and $B$ have the basis vectors as rows. However Goldreich, Goldwasser and Halevi have the basis ...
user avatar
2 votes

Optimal MDS matrix - circulant or recursive?

my answer is extension to circulant and recursive. one property measure to the optimal implementation of MDS matrix in cryptography is the cost of xor (number of xors required to fully implement the ...
user avatar
  • 1,990
2 votes
Accepted

UOV signature scheme, how does the affine transformation work? What does the composition of the core map and the affine map yield?

The secret polynomials are multivariate polynomials whose oil-oil terms have coefficient zero. You can represent it as a sum of terms, or as a vector-matrix-vector product. Take for example the ...
user avatar
  • 1,370
2 votes
Accepted

What is the time complexity of the basic components of a symmetric cipher?

I assume a cipher has a total time complexity. Where can I find the time complexities of a given cipher, especially DES, PRESENT and AES? And is there available time complexities per round of these ...
user avatar
  • 43.4k
2 votes

Simple question about the branch number of the matrix

Yes, its branch number is 2, which is the minimal possible branch number. Note that every permutation matrix (that is, one element per row or column is one, all others are zero) has branch number 2.
user avatar
  • 334
2 votes

Simple question about the branch number of the matrix

Yes. This a degenerate matrix that provides no mixing and has minimal branch number.
user avatar
  • 16.4k
2 votes
Accepted

Problem while decrypting Hill cipher

These modular equations are not uniquely solvable: $$\begin{bmatrix}7&2\\ 10& 20\end{bmatrix}, \begin{bmatrix}7&2\\ 23& 7\end{bmatrix}, \begin{bmatrix}20&15\\ 10& 20\end{...
user avatar

Only top scored, non community-wiki answers of a minimum length are eligible