Questions tagged [multivariate-cryptography]
A generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field
26 questions
1
vote
0
answers
112
views
Is polynomial the answer?
Lattice, Code, MQ - these types of cryptosystems are essentially polynomial.
Lattice: degree-1, constrain on the solution, (need to have small norms)
Code, MQ: finding polynomial solutions.
...
- 11.5k
1
vote
0
answers
62
views
Why do MQ-based signature schemes sign an image, and not a preimage?
In multivariate signature schemes like UOV and its variants, the signer signs a message $t\in \mathbb{F}_p^m$ by demonstrating a preimage $s\in \mathbb{F}_p^n$ such that $\mathcal{P}(s)=t$, for a ...
- 111
3
votes
0
answers
64
views
Signing failure probability of SNOVA
UOV and SNOVA are two multivariate digital signatures that are currently considered by NIST for potential standardization.
They are based on the hardness of solving a set of multivariate quadratic ...
- 358
2
votes
0
answers
61
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 ...
- 11.5k
0
votes
1
answer
81
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
154
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 ...
- 117
1
vote
1
answer
212
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
85
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
54
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\...
- 295
2
votes
1
answer
131
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}...
- 966
2
votes
1
answer
634
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 ...
- 327
4
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 ...
- 57
0
votes
0
answers
208
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
122
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 ...
- 11.5k