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

• Fast Multiplication and the PLWE-RLWE Equivalence for an Infinite Family of Cyclotomic Subextensions [6.487242614495099]
  We prove the equivalence between the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems. We also describe a fast integers for computing the product of two elements in the ring of the maximal real subfield.
  arXiv  Detail & Related papers  (2024-10-01T15:32:02Z)
• Parallel Quantum Signal Processing Via Polynomial Factorization [3.1981483719988235]
  We develop a Quantum Parallel Signal Processing algorithm. Our algorithm parallelizes the computation of $texttr (P(rho)$ over $k$ systems and reduces the query depth to $d/k$, thus enabling a family of time-space tradeoffs for QSP. This furnishes a property estimation suitable for quantum computers, and is realized at the expense of increasing the number of measurements by factor $O(textpoly(d) 2(k) )$.
  arXiv  Detail & Related papers  (2024-09-27T17:54:30Z)
• 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)
• Provably learning a multi-head attention layer [55.2904547651831]
  Multi-head attention layer is one of the key components of the transformer architecture that sets it apart from traditional feed-forward models. In this work, we initiate the study of provably learning a multi-head attention layer from random examples. We prove computational lower bounds showing that in the worst case, exponential dependence on $m$ is unavoidable.
  arXiv  Detail & Related papers  (2024-02-06T15:39:09Z)
• 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)
• 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)
• 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.