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.
58 questions
1
vote
1
answer
56
views
Why MDDH is DDH when k in Matrix D is 1?
I am reading a paper Multi-authority ABE for Non-monotonic Access Structures, when the author defines the DDH problem in preliminaries. The definition is
I find it is a type of Matrix DDH when $k=1$....
0
votes
1
answer
93
views
Questions about SIS hard problem
The definition of $\mathrm{SIS}_{q,n,m,\beta}$ problem is as below.
Let $A\in\mathbb{Z}_q^{n\times m}$ be an $n\times m$ matrix with entries in $\mathbb{Z}_q$ that consists of $m$ uniformly random ...
- 456
0
votes
0
answers
44
views
One way function bulit by singular matrices
Our one-way function $F:\mathbb{F}_q^{n\times n}\times \mathbb{F}_q^{n\times n}\to\mathbb{F}_q^{n\times n}$ differs from traditional OWFs, which focus on being hard to invert. Instead, ours aims to be ...
- 456
0
votes
0
answers
46
views
BGW Multiplication with byzantine adversaries
I have recently read about the BGW Multi-party Computation protocol, more specifically the multiplication gate by Gennaro et al (PDF here), however, some concepts raised questions.
Context: From what ...
0
votes
0
answers
56
views
Is there a square matrix with applications in Cryptography such that the determinant of this matrix is 0 and all its sub minors are non-singular?
I am looking for a square matrix whose determinant is 0, however, all sub-minors of this matrix are non singular. This matrix needs to have applications in Cryptography. The matrix may be over any ...
0
votes
2
answers
58
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
0
votes
1
answer
138
views
Can we make Discrete Log (significant) more secure by introducing non-commutative algebra (e.g. matrices, hypercomplex numbers, )
$$g^a = c \bmod{N} \text{ }\rightarrow \text{ }G_{i_1}G_{i_2}G_{i_3}...G_{i_n} = C \bmod N $$
At the Discrete Log problem we try to find the exponent ($a$) of a generator ($g$) over a finite filed....
- 453
1
vote
1
answer
160
views
Matrix multiplication circuit
I am trying to understand which operations are computable by an $\texttt{NC}^1$ circuit. However, I am struggling to understand whether there is such a circuit for multiplying a matrix with a vector ...
- 21
0
votes
1
answer
49
views
What is the best method to compose a set of matrices into one and then unambiguously decrypt it?
I am presented with the following problem:
Given a set of matrices $M = \{A^i_{m,n} : 0 < i < 101 \}$ design a procedure to compose all of them into one encrypted matrix $E_{m,n}$ and later ...
- 219
0
votes
0
answers
135
views
What is the recommended way to use fully homomorphic encryption which supports numpy matrix operations?
For a project I'm working on, I need to perform addition, subtraction and dot operations on relatively large encrypted 2x2 dimensional matrices.
The project is written in python and I am using the ...
- 1
1
vote
0
answers
64
views
How one can combine shift row and mix column to form a single matrix?
I am trying to combine the effect the shift row and mix column into a single matrix. The cipher that I am working with is skinny64 (untweaked version). I know that combining the effect of these two ...
0
votes
2
answers
85
views
Functional Encrypton: multiplying an encrypted vector by huge known matrix through inner product encrypton?
I'm solving a kernel ridge regression through a federated learning way.
Equation to solve the kernel ridge regerssion is dot((K+lambdaI)^-1,y).
So the aggregator of the problem knows the matrix A=(K+...
1
vote
1
answer
191
views
Questions on LWE with a repeated secret matrix S
Consider a formulation of LWE where we are given either $(x,S x+e)$ or $(x,u)$ --- where $S$ is an $m \times n$ secret/hidden matrix, $x$ is a randomly sampled $n \times 1$ vector, $e$ is an $m \times ...
- 397
0
votes
0
answers
32
views
Checking whether a particular group has an efficient, faithful representation as a matrix group
There are cryptographic protocols being developed for non-abelian groups. For some protocols it is necessary to know whether the group has an efficient representation as a matrix group (say, a matrix ...
0
votes
1
answer
208
views
Does matrix multiplication of hash digests admit manipulation of the result?
Take a sequence of byte buffers, hash each of them, interpret the hash digests as square matrices with 8-bit unsigned int elements, and (matrix) multiply them in order. Define the final matrix to be ...
- 103
0
votes
1
answer
110
views
Hard instances of matrix factorization
Are there any hard problems related to matrix factorization?
Suppose $E$ is hermitian with public eigenvectors such that $U^T\Lambda U = E$ with $U$ public but $E,\Lambda$ secret. Given $X$ secret, we ...
- 315
2
votes
1
answer
264
views
How to calculate the branch number of a linear mapping?
Is there an efficient algorithm which can be used to determine the branch number of any given linear mapping?
- 35
0
votes
0
answers
169
views
Matrix cipher - symmetric or asymmetric cryptosystem?
Matrix cipher is defined by:
a) Encryption: $C = K \times Z$, where $C$ is a cryptogram vector, $Z$ is a message vector and $K$ is encryption matrix (encryption key)
b) Decryption: $Z = K^{-1} \times ...
- 1
2
votes
1
answer
259
views
How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$
I have been reading about MDS matrices. It is defined as (paraphrased from Section 2.1)
An $n \times n$ matrix $M$ is MDS if and only if $bn(M) = n + 1$
where $bn$ (branch number) is defined as:
$bn(...
- 603
0
votes
0
answers
65
views
Confidential data encryption on Ethereum
I already built a supply chain that is able to collect product information on Ethereum. Now, that data can be confidential, but I still want to do matrix calculations on it. I came across homomorphic ...
- 1
1
vote
1
answer
594
views
Hill Cipher Plaintext Attack: Dealing with Non-uniqueness of Matrix Inverses?
I'm following along with my book. Here is an example of a plaintext attack from it:
It is known that:
plaintext = 'friday'
ciphertext= 'pqcfku'
$m$ = 2
We will use this to form the following matrix ...
- 135
-1
votes
1
answer
986
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{...
- 161
2
votes
3
answers
1k
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 ...
- 1,025
4
votes
0
answers
259
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,025
2
votes
2
answers
274
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 & ...
- 21
0
votes
1
answer
349
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
0
answers
243
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 ...
- 201
3
votes
0
answers
122
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
1
answer
256
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 ...
- 33
1
vote
1
answer
721
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,025
1
vote
0
answers
492
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 ...
- 11
1
vote
0
answers
75
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 :
...
- 121
2
votes
3
answers
977
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 ...
- 81
0
votes
1
answer
333
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$ ...
- 9,795
5
votes
1
answer
305
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 ...
- 9,795
2
votes
1
answer
152
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
3
answers
562
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 (...
- 204
5
votes
2
answers
4k
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?
- 53
3
votes
1
answer
707
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 ...
- 211
3
votes
1
answer
331
views
Why does AES use a Binary Field?
The key idea in AES is the use of matrix multiplication and the corresponding inverse (as opposed to Feistel). But the algorithm does that using a GF instead of simple modular arithmetic.
Is there ...
- 188
3
votes
1
answer
400
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 + ...
- 163
1
vote
0
answers
527
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 ...
- 455
2
votes
1
answer
158
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 ...
- 6,250
10
votes
1
answer
2k
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 ...
- 1,702
3
votes
1
answer
225
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?
$$\...
- 1,702
8
votes
2
answers
2k
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.
...
- 367
5
votes
1
answer
2k
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,702
2
votes
1
answer
1k
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 ...
- 233
1
vote
1
answer
5k
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 ...
- 13
0
votes
1
answer
630
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 ...
- 121