Questions tagged [multivariate-cryptography]
A generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field
20
questions
1
vote
1
answer
90
views
Post-quantum secure trapdoor function
I am looking for examples post-quantum secure trapdoor functions. Ideally, the inversion knowing the trapdoor should be "simple" in the sense that it can be computed by a circuit in NC^1.
- 21
1
vote
2
answers
57
views
Is it possible to solve a linear polynomial in a finite field
Say that in $\mathbb{F}_{999,999,000,001}$ I have an equation $0 = ax - b$ where $a$ and $b$ are random values from the field.
Is it possible to solve this equation for $x$ using the Extended ...
- 139
1
vote
0
answers
44
views
Question about Mesquite signature size?
I have a question regarding William Wang's paper Shorter Signatures from MQ. According to him the (maximum) signature size is:
$$
2\kappa +
3\kappa\cdot \lceil\tau\log\frac{M}{\tau}\rceil
+
\tau\cdot\...
- 243
2
votes
1
answer
104
views
Hidden field equations - existence of zeroes
Let $\mathbb{F}_q$ be a finite field of size $q$ (prime), and $\mathbb{F}_{q^n}$ be a degree-$n$ algebraic extension of $\mathbb{F}_q$.
Let $F$ be a polynomial function $\mathbb{F}_{q^n} \to \mathbb{F}...
- 835
2
votes
1
answer
336
views
Sage code for finding generator matrix of MDS code
Let $L$ be an $[n,k]$ code. A $k\times n$ matrix $G$ whose rows form a basis for $L$ is called a generator matrix for $L$.
A linear $[n,k,d]$ code with largest possible minimum distance is called ...
- 23
5
votes
3
answers
1k
views
Why do Problems for Post-Quantum algorithms have to be NP-Hard?
The mathematical problems used for Post-Quantum Cryptography problems I came across, are NP-complete, e.g.
Solving quadratic equations over finite fields
short lattice vectors and close lattice ...
- 297
4
votes
5
answers
5k
views
Why do we use groups, rings and fields in cryptography?
I'm a student of Masters in Cyber Security. I have a habit to understand things from their first principles (at the very beginning). Kindly use any simple mathematical example to answer because I have ...
- 57
0
votes
0
answers
66
views
Fundamentals of XL algorithm
I am trying to understand XL algorithm and F4/F5 algorithms for solving multivariate polynomial systems.
Is XL related to the Grobner basis?
I would be grateful if anyone could suggest me the topics (...
- 21
1
vote
1
answer
65
views
The mathematical similarity and difference between code-based PKE and multivariate DSS
In code-based public key encryption schemes, a public key is formed by matrix-multiplying 2 linear matrices to the left and right side of a easily decodeable error-correcting code, so that it'll be ...
- 8,648
1
vote
0
answers
64
views
Kernel attack on MinRank - How do we check if we can stop?
I have some trouble understanding how Kernel Attack to MinRank is implemented.
MinRank: Let $k, n, r$ be positive integers, and let $M_0, M_1, \dots, M_k$ be $n \times n$ matrices with entries in a ...
- 11
1
vote
1
answer
128
views
Why all multivariate schemes restrict themselves to polynomials of degree 2
If we note all multivariate schemes restrict themselves
to polynomials of degree 2.
I was wondering why they do it. After looking on the internet, I came to know that they do it for the efficiency.
My ...
- 309
1
vote
1
answer
86
views
What are the security implications of knowing the private polynomial $\mathcal{F}$
First, affine transformations $S,T$ are defined by $S=A_1+v_s, T=A_2+v_t$. Let the private polynomial function $\mathcal{F}$ be known. The short description of the public key map is $P(X) = T \circ \...
- 898
4
votes
0
answers
78
views
Help with cryptanalysis of branching in schemes based on Multivariate Public Key Cryptography
I'm familiarized with the structure of branching found in Multivariate Cryptography, as it allows us to partition a $n$-tuple over $F_{q}$ into a $k$-tuple where the $i$-th element is in $F_{q^{\...
- 898
3
votes
1
answer
230
views
Multivariate cryptography - easily invertible quadratic map
I am reading through multivariate cryptography and in every source I have seen, the secret map $P$ is described as "easily invertible" or "easy to invert".
What exactly does it mean "easily ...
- 167
2
votes
1
answer
122
views
Why does solving the underlying polynomial system "break" the multivariate cryptosystem
I was wondering why exactly does solving a polynomial system (directly or indirectly) "break" a multivariate cryptosystem as a digital signature.
I realize that the exact reason differs from system ...
- 25
1
vote
0
answers
44
views
Dedekind sum is a product of sawtooth function [closed]
"The Dedekind sum is a product of a sawtooth function." This sentence does not make sense to me. A sawtooth is a kind of wave for sound generation. But in the realms of cryptography, the Dedekind sum ...
- 11
1
vote
0
answers
46
views
Algorithms for solving systems of quadratic multivariate polynomials
What are the best algorithms for solving systems of $k$ polynomials equations where these are quadratic multivariate polynomials on $k$ variables?
I've encountered such systems on my research and I'm ...
- 898
4
votes
0
answers
228
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=\...
- 173
2
votes
1
answer
148
views
Multivariate Cryptography: Security of the affine transform T
In this question, I'd like to discuss the security of the last transformation $T$ employed in the construction of a MV-scheme. MVCrypto is based on solving a system of polynomial equations, but ...
- 898
0
votes
1
answer
61
views
Associative Multivariate Permutation
Popular multivariate schemes are constructed by having a several easy-to-invert functions/maps as parivate key, and their composition as the public key.
When signing, the hash, or a padded form of ...
- 8,648