Questions tagged [multivariate-cryptography]
A generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field
23 questions
2
votes
0
answers
48
views
I just want a post-quantum permutation and I don't care about efficiency. Can multivariate reciprocals help me?
Let's say there's an application that require a public-key permutation, and we can throw all other requirements away, and design one out of reciprocal multivariate system. Is this viable? If yes, how ...
- 9,795
0
votes
1
answer
63
views
How to transform a univariate polynomial over $\mathbb{F}_{2^n}$ into a multivariate Boolean polynomial over $\mathbb{F}_2^n$
# sage
F=GF(2^8,'a')
R=PolynomialRing(F,"x,y")
R.inject_variables()
f=x*y-1
How can we transform $f$ into multivariable Boolean polynomials over $\...
- 25
3
votes
1
answer
98
views
Multivariate Cryptography: What is the secret oil space in the MAYO signature scheme?
IN UOV schemes, I understand that you need to choose a secret subspace $O \in \mathcal{F}^q_n$ such that $P(\mathbf{o}) = 0$ for all $\mathbf{o} \in O$. According to the paper Improved cryptanalysis ...
1
vote
1
answer
168
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
63
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
50
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\...
- 275
2
votes
1
answer
110
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}...
- 845
2
votes
1
answer
593
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
6
votes
3
answers
2k
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 ...
- 317
5
votes
5
answers
6k
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 ...
- 67
0
votes
0
answers
127
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
89
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 ...
- 9,795
1
vote
0
answers
81
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
140
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
92
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
81
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
261
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
134
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 ...
1
vote
0
answers
45
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
47
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
265
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
158
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
68
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 ...
- 9,795