A new multivariate primitive from CCZ equivalence
- URL: http://arxiv.org/abs/2405.20968v1
- Date: Fri, 31 May 2024 16:15:02 GMT
- Title: A new multivariate primitive from CCZ equivalence
- Authors: Marco Calderini, Alessio Caminata, Irene Villa,
- Abstract summary: Two secret affine invertible $mathcal S,mathcal T$ are applied to a set of $mathcalF$.
The equivalences $mathcal G$ and $mathcal F$ are said to be affine equivalent.
- Score: 1.8024397171920885
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Multivariate Cryptography is one of the main candidates for Post-quantum Cryptography. Multivariate schemes are usually constructed by applying two secret affine invertible transformations $\mathcal S,\mathcal T$ to a set of multivariate polynomials $\mathcal{F}$ (often quadratic). The secret polynomials $\mathcal{F}$ posses a trapdoor that allows the legitimate user to find a solution of the corresponding system, while the public polynomials $\mathcal G=\mathcal S\circ\mathcal F\circ\mathcal T$ look like random polynomials. The polynomials $\mathcal G$ and $\mathcal F$ are said to be affine equivalent. In this article, we present a more general way of constructing a multivariate scheme by considering the CCZ equivalence, which has been introduced and studied in the context of vectorial Boolean functions.
Related papers
- Neural network learns low-dimensional polynomials with SGD near the information-theoretic limit [75.4661041626338]
We study the problem of gradient descent learning of a single-index target function $f_*(boldsymbolx) = textstylesigma_*left(langleboldsymbolx,boldsymbolthetarangleright)$ under isotropic Gaussian data.
We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ of arbitrary link function with a sample and runtime complexity of $n asymp T asymp C(q) cdot d
arXiv Detail & Related papers (2024-06-03T17:56:58Z) - Word Linear Complexity of sequences and Local Inversion of maps over finite fields [0.0]
This paper develops the notion of vector valued sequences over finite fields $ff$ as an extension of Linear Complexity$ of their ensembles.
It shows that the matrix minimal can be used with iteratively generated vector valued by maps $F:ffn at a given $ffn$ in $ffn$ for solving the unique local inverse $x$ in $ffn$ when the sequence is periodic.
arXiv Detail & Related papers (2023-11-11T14:06:23Z) - Riemannian Langevin Monte Carlo schemes for sampling PSD matrices with
fixed rank [5.0397419406319095]
We present two explicit schemes to sample matrices from Gibbs distributions on $mathcal Sn,p_+$.
We also provide examples of energy functions with explicit Gibbs distributions that allow numerical validation of these schemes.
arXiv Detail & Related papers (2023-09-08T02:09:40Z) - The complexity of solving a random polynomial system [3.420117005350141]
In this paper there is an overview on a general algorithm used to solve a multivariate system.
We then speak about random systems and in particular what "random" means to us.
We give an upper bound on both the degree of regularity and the solving degree of such random systems.
arXiv Detail & Related papers (2023-09-07T17:14:59Z) - Quantum and classical low-degree learning via a dimension-free Remez
inequality [52.12931955662553]
We show a new way to relate functions on the hypergrid to their harmonic extensions over the polytorus.
We show the supremum of a function $f$ over products of the cyclic group $exp(2pi i k/K)_k=1K$.
We extend to new spaces a recent line of work citeEI22, CHP, VZ22 that gave similarly efficient methods for learning low-degrees on hypercubes and observables on qubits.
arXiv Detail & Related papers (2023-01-04T04:15:40Z) - Two-body Coulomb problem and $g^{(2)}$ algebra (once again about the
Hydrogen atom) [77.34726150561087]
It is shown that if the symmetry of the three-dimensional system is $(r, rho, varphi)$, the variables $(r, rho, varphi)$ allow a separation of variable $varphi$ and eigenfunctions.
Thoses occur in the study of the Zeeman effect on Hydrogen atom.
arXiv Detail & Related papers (2022-12-02T20:11:17Z) - Shallow neural network representation of polynomials [91.3755431537592]
We show that $d$-variables of degreeR$ can be represented on $[0,1]d$ as shallow neural networks of width $d+1+sum_r=2Rbinomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1[binomr+d-1d-1d-1d-1[binomr+d-1d-1d-1d-1
arXiv Detail & Related papers (2022-08-17T08:14:52Z) - Low-degree learning and the metric entropy of polynomials [49.1574468325115]
We prove that any (deterministic or randomized) algorithm which learns $mathscrF_nd$ with $L$-accuracy $varepsilon$ requires at least $Omega(sqrtvarepsilon)2dlog n leq log mathsfM(mathscrF_n,d,|cdot|_L,varepsilon) satisfies the two-sided estimate $$c (1-varepsilon)2dlog
arXiv Detail & Related papers (2022-03-17T23:52:08Z) - Classical Codes and Chiral CFTs at Higher Genus [0.0]
We derive explicit expressions for the higher genus partition functions of a specific class of CFTs: code CFTs.
This work provides a step towards a full understanding of the constraints from higher genus modular invariance on 2d CFTs.
arXiv Detail & Related papers (2021-12-09T19:00:04Z) - Small Covers for Near-Zero Sets of Polynomials and Learning Latent
Variable Models [56.98280399449707]
We show that there exists an $epsilon$-cover for $S$ of cardinality $M = (k/epsilon)O_d(k1/d)$.
Building on our structural result, we obtain significantly improved learning algorithms for several fundamental high-dimensional probabilistic models hidden variables.
arXiv Detail & Related papers (2020-12-14T18:14:08Z) - Learning sums of powers of low-degree polynomials in the non-degenerate
case [2.6109033135086777]
We give a learning algorithm for an arithmetic circuit model from a lower bound for the same model, provided certain non-degeneracy conditions hold.
Our algorithm is based on a scheme for obtaining a learning algorithm for an arithmetic circuit model from a lower bound for the same model.
arXiv Detail & Related papers (2020-04-15T06:18:41Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.