Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [matrix-multiplication]

Matrix multiplication indicates a row-by-column multiplication, where the entries in the Xth row of A are multiplied by the corresponding entries in the Yth column of B and then adding the results.

0
votes
0answers
39 views

Problem while decrypting Hill cipher

I have a plaintext "monday" and ciphertext "IKTIWM" and $m=2$. I want to find the key of the Hill cipher. I made a matrix $$ \begin{bmatrix} a_1 & a_2 \\ a_3 & a_4 \end{bmatrix}\begin{...
1
vote
3answers
223 views

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

I have a very basic knowledge on time complexity and even less on programming, so please bear with me. I am interested to know the time complexity in big-O notation of some of the basic operations in ...
4
votes
0answers
107 views

Why are matrices so common in symmetric encryption?

Matrices have been used in symmetric ciphers since the Hill Cipher (before?) all the way up to modern ciphers such as Twofish and AES. I understand matrices can be invertible, therefore making them ...
1
vote
2answers
44 views

Simple question about the branch number of the matrix

what is the branch number of the binary identity matrix? For example, $ I $ is 4x4 binary identity matrix, \begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & ...
-1
votes
1answer
85 views

One-way hashing using singular matrices?

In matrix encoding, we convert our message into some numerical value and then create a matrix out of those numbers. The matrice encryption is based on the fact that a matrix multiplied by its inverse ...
4
votes
0answers
213 views

Is the matrix step of GNFS still the hardest part?

When the factorization of RSA-768 was announced in December 2009: the sieving took about 24 months and the matrix step took 119 days (4 months). So sieving took about 6 times as long. This is despite ...
4
votes
0answers
95 views

Proof of knowledge of exponentiations

I am reading a paper of Furukawa and Sako, "An efficient scheme for proving a shuffle" from 2001. This paper writes a protocol for verifiable shuffling in mixnets. Their protocol make use of ...
1
vote
1answer
80 views

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

I am having trouble understanding part of the UOV scheme, i get how it works except for when it comes to composing the core map F with an affine transformation say T, which i understand to be an ...
1
vote
1answer
137 views

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

I recently learned AES uses $x^4 +1$ to reduce the multiplications in the MixCol layer. However, I used $p(x) = x^8 + x^4 + x^3 + x + 1$ not knowing it was the wrong polynomial and got the correct ...
1
vote
0answers
162 views

Expressing a given linear transformation in Galois Field GF(256) in terms of another linear transformation with a different reduction polynomial

Before giving a better and detailed description of what I ask, let me first tell why I need what I am looking for: Intel processors already provide instructions (AES-NI) for very efficient AES ...
1
vote
0answers
56 views

Grøstl MixBytes Python implementation

I am trying to find an efficient way to implement the Grøstl matrix multiplication on python3. So far I have managed to get this result : ...
1
vote
3answers
173 views

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

I need to write a procedure for calculating the MixColumns's operation result in the following form: $M*X^T,$ where $M$ is a 128x128 binary matrix, $X$ is a 128-bit vector (the state). My question ...
0
votes
1answer
193 views

Matrix Trapdoor AB+BA

I believe I'm probably not the first person to think of using this as a trapdoor. Let $R$ be a square matrix ring, and $S$ a commutative subgroup of its multiplicative monoid. Let $P \in R$ ...
6
votes
1answer
181 views

How difficult is inverting a non-square matrix?

Partially inspired by ring learning with errors (RLWE), I am trying to construct a cryptosystem that requires the use of a non-invertible matrix. Of the methods I've thought of to generate a matrix ...
2
votes
1answer
93 views

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

The proof is here on page 66, lemma 20. I found the same mistake in other sources also. It claims that GGH decryption will fail only if $\lceil R^{-1}e\rfloor \not =0$. Here $R$ is the "good" private ...
0
votes
3answers
195 views

Optimal MDS matrix - circulant or recursive?

One of the special matrix in $GF(2^q)$ is MDS matrix which can be used in the cryptography like mix column of AES. Two forms of MDS matrices are circulant and recursive. Which form of MDS matrix (...
4
votes
2answers
1k views

Advantages of Montgomery Ladder-based Scalar Multiplication

I do not quite understand what the greatest advantages are of using the Montgomery ladder algorithm for scalar multiplication? Can someone help me out?
3
votes
1answer
339 views

Prove the branch of number of Advanced Encryption Standard

In the Advanced Encryption Standard (AES) document: page 27 section 7.3.1, It defines branch number. It said " Let F be a linear transformation acting on byte vectors and let the byte weight ...
3
votes
0answers
133 views

Twofish MDS multiplication

I wasted the last 2 days finding literature and/or some illustrative explanations on how to perform correct multiplications against the MDS-Matrix in Twofish over $\operatorname{GF}(256)$ with $x^8 + ...
1
vote
0answers
230 views

Complexity of computing homomorphic encrypted matrix multiplication

Given two players $P_1 , P_2$ . In our setting $P_1$ poses two encrypted matrices $M_{1_{k \times k}},M_{2_{k \times k}}$ over field $F$, and the encryption has additive homomorphic property, over ...
1
vote
1answer
66 views

Is DL difficult under the group of Unimodular matrices?

Is discrete logarithm assumed to be computationally hard in a non-abelian group as the subgroup of the general linear group under matrix multiplication formed by the unimodular matrices? The two ...
10
votes
1answer
792 views

How to calculate active s-boxes from branch number?

If MDS in AES has branch number 5 (so 5 active s-boxes in 2 rounds), wouldn't that mean 4 rounds of AES has $5*2=10$ active s-boxes? AES paper says it has 25 ($5^2$?) active s-boxes in 4 rounds. How ...
2
votes
1answer
104 views

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

In this paper authors claim that {0,1}-matrices are almost-MDS (have branch number n - 1) on when n is 2, 3, or 4. For example, how can this two matrices have the same branch number? $$\begin{pmatrix}...
7
votes
1answer
823 views

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

The only way I see it possible to do the matrix-multiplication in the MixColumns operation of AES is by shifting the bits in the multiplied number, and then reduce with the polynomial if needed. ...
4
votes
1answer
657 views

What is the branch number of this matrix?

We have the following matrix: $$\begin{pmatrix}0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{pmatrix}$$ What is the branch number? Is this a MDS marix?
1
vote
1answer
627 views

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

AES MixColumns is done by multiplying a $4 \times 4$ matrix and a column of the AES state (a vector). Addition and multiplication are done in $\operatorname{GF}(2^8)$. In the paper White-box AES, the ...
1
vote
1answer
2k views

Affine transformation in AES: Matrix representation

I know that the affine transformation of the AES can be represented both as a polynomial evaluation over $\operatorname{GF}(2^8)$ and as a matrix-vector multiplication (see, e.g., p.212 C.4 of The ...
0
votes
1answer
335 views

Direct sum of Binary numbers In Mixcolumns

I have just started learning cryptography and I am trying to make sense of the direct sum on some binary numbers. I am trying to find a column of a state space after a Mixcolumns operation has been ...
2
votes
1answer
463 views

Hill Cipher question

Recently, I was given three ciphers to crack for my cryptography class. At this point, I have guessed that one of them is likely a Hill cipher (probably 3x3, as that is the most complex we have done ...
2
votes
1answer
228 views

Constructing of 16x16 Involutory Binary Matrices of Branch Number 7

In the PDF “Algebraic Construction of 16×16 Binary Matrices of Branch Number 7 with One Fixed Point”, it was given that: ...
2
votes
1answer
6k views

Hill cipher cryptanalysis - known plaintext known key size

Hello I want to know how to go about this problem I know the plaintext "abcdef" and the ciphertext. The key size is 2. I really can't figure out how to find the key for decrypting and encrypting.
1
vote
2answers
411 views

hill cipher encryption way 1x3 plaintext matrix

Can someone help me with a Hill cipher? When do I have to use: 1x3 plain text matrix (p1, p2, p3) * 3x3 key matrix 3x3 key matrix * 3x1 plain text matrix Or they are both correct? I tried to ...
8
votes
1answer
269 views

Matrix key exchange

Given is a square matrix $M$ over a field $F$, we have a key exchange with the following conditions: Person $X$ sends a message to Person $Y$: $C_{1}=AM$, where $A$ is a randomly chosen square matrix....
1
vote
1answer
156 views

A substitution based on a matrix vector product

I choose at random an invertible square matrix A of size 128 in GF(2). I want to use this matrix as a substitution box. Is this a non linear transformation ? I've seen that substitution boxes are ...
2
votes
1answer
107 views

What happen if a asymmetric crypto-system deals with only one key

Assume there is a crypto algorithm that deals with matrices to encrypt and decrypt. Regardless of the specification of such algorithm, what if the algorithm assumes that two parties can securely agree ...
2
votes
1answer
2k views

How to multiply a matrix of bits with another?

For example, assume I have two 4x4 matrices of bits: 1 1 1 1 1 1 1 0 0 0 0 0 0 1 1 1 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 0 I want to apply ...