Questions tagged [multivariate-cryptography]

A generic term for asymmetric cryptographic primitives based on multivariate polynomials over a finite field

Filter by
Sorted by
Tagged with
0
votes
0answers
27 views

How does the public-key generation work in the multivariate post-quantum digital signature GeMMS?

There are a few steps in the public-key generation of GeMSS that I am trying to understand. The first is the below equations (1). What does "$\theta_i$ forms a basis for $\mathbb{F}_{2^n}$ over $\...
3
votes
3answers
689 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 ...
4
votes
5answers
3k 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 ...
0
votes
0answers
23 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 (...
1
vote
1answer
41 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 ...
1
vote
0answers
46 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 ...
1
vote
1answer
102 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 ...
1
vote
1answer
76 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 \...
4
votes
0answers
68 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^{\...
3
votes
1answer
130 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 ...
2
votes
1answer
103 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
0answers
39 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 ...
1
vote
0answers
38 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 ...
4
votes
0answers
158 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=\...
2
votes
1answer
127 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 ...
0
votes
1answer
54 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 ...