Cryptanalysis of PLWE based on zero-trace quadratic roots

• URL: http://arxiv.org/abs/2312.11533v2
• Date: Fri, 31 Oct 2025 16:07:01 GMT
• Title: Cryptanalysis of PLWE based on zero-trace quadratic roots
• Abstract summary: We extend two of the attacks on the PLWE problem presented in (Y. Elias, K. E. Lauter, E. Ozman, and K. E. Stange)<n>Our attack exploits the fact that the trace of the root is zero and has overwhelming success probability as a function of the number of samples taken as input.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We extend two of the attacks on the PLWE problem presented in (Y. Elias, K. E. Lauter, E. Ozman, and K. E. Stange, Ring-LWE Cryptography for the Number Theorist, in Directions in Number Theory, E. E. Eischen, L. Long, R. Pries, and K. E. Stange, eds., vol. 3 of Association for Women in Mathematics Series, Cham, 2016, Springer International Publishing, pp. 271-290) to a ring $R_q=\mathbb{F}_q[x]/(f(x))$ where the irreducible monic polynomial $f(x)\in\mathbb{Z}[x]$ has an irreducible quadratic factor over $\mathbb{F}_q[x]$ of the form $x^2+\rho$ with $\rho$ of suitable multiplicative order in $\mathbb{F}_q$. Our attack exploits the fact that the trace of the root is zero and has overwhelming success probability as a function of the number of samples taken as input. An implementation in Maple and some examples of our attack are also provided.

Related papers

• The Condition-Number Barrier in Sparse Least Squares [77.64108812086542]
  In [AS21], Axiotis and Sviridenko conjectured that the linear dependence on the restricted condition number in convex optimization cannot be improved by a sparse-time algorithm.<n>We establish their conjectured lower bound for least-squares objectives, conditional on the randomized exact-volume Small-Set Expansion Hypothesis.
  arXiv  Detail & Related papers  (2026-08-03T17:57:01Z)
• Cryptanalysis of the Legendre Pseudorandom Function over Extension Fields [0.0]
  The Legendre Pseudorandom Function (PRF) is a highly efficient cryptographic primitive built upon the Legendre symbol.<n>Recent interest has shifted toward instantiations over extension fields $mathbbF_pr$.<n>This paper presents the first comprehensive cryptanalysis of the single-degree Legendre PRF operating over $mathbbF_pr$.
  arXiv  Detail & Related papers  (2026-04-06T16:35:32Z)
• Semigroup action based on skew polynomial evaluation with applications to Cryptography [0.0]
  We introduce an action of the skew ring $mathbbF_q[X;, right]$ over $mathbbF_q$ based on its valuation and the concept of left skew product of functions.<n>We exploit this fact in order to build a public key exchange protocol that is secure in Canetti and Krawczyk model.
  arXiv  Detail & Related papers  (2025-12-02T10:08:50Z)
• Information-Computation Tradeoffs for Noiseless Linear Regression with Oblivious Contamination [65.37519531362157]
  We show that any efficient Statistical Query algorithm for this task requires VSTAT complexity at least $tildeOmega(d1/2/alpha2)$.
  arXiv  Detail & Related papers  (2025-10-12T15:42:44Z)
• Surrogate to Poincaré inequalities on manifolds for dimension reduction in nonlinear feature spaces [49.1574468325115]
  We aim to approximate a continuously differentiable function $u:mathbbRd rightarrow mathbbRm$ by a composition of functions $fcirc g$ where $g:mathbbRd rightarrow mathbbRm$, $mleq d$, and $f : mathbbRm rightarrow mathbbRR$.<n>For a fixed $g$, we build $f$ using classical regression methods, involving evaluations
  arXiv  Detail & Related papers  (2025-05-03T12:37:27Z)
• Multiplicative character sums over two classes of subsets of quadratic extensions of finite fields [6.5990719141691825]
  We improve estimates for character sums $sumlimits_g inmathcalGchi(f(g))$, where $mathcalG$ is either a subset of $mathbbF_qr$ of sparse elements.<n>These estimates can be used to prove the existence of primitive elements in $mathcalG$ in the standard way.
  arXiv  Detail & Related papers  (2025-02-20T10:40:48Z)
• 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)
• On the resilience of the quadratic Littlewood-Offord problem [5.3390449198644445]
  We study the statistical resilience of the anti-concentration properties of Rademacher computations in face of adversarial noise. Special emphasis is put on bilinear and quadratic forms, for which strengthened estimates are attained.
  arXiv  Detail & Related papers  (2024-02-16T08:27:55Z)
• 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)
• Quantum Oblivious LWE Sampling and Insecurity of Standard Model Lattice-Based SNARKs [4.130591018565202]
  The Learning Errors With Errors ($mathsfLWE$) problem asks to find $mathbfs$ from an input of the form $(mathbfAmathbfs+mathbfe$) We do not focus on solving $mathsfLWE$ but on the task of sampling instances. Our main result is a quantum-time algorithm that samples well-distributed $mathsfLWE$ instances while provably not knowing the solution.
  arXiv  Detail & Related papers  (2024-01-08T10:55:41Z)
• A Unified Framework for Uniform Signal Recovery in Nonlinear Generative Compressed Sensing [68.80803866919123]
  Under nonlinear measurements, most prior results are non-uniform, i.e., they hold with high probability for a fixed $mathbfx*$ rather than for all $mathbfx*$ simultaneously. Our framework accommodates GCS with 1-bit/uniformly quantized observations and single index models as canonical examples. We also develop a concentration inequality that produces tighter bounds for product processes whose index sets have low metric entropy.
  arXiv  Detail & Related papers  (2023-09-25T17:54:19Z)
• Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials [93.59919600451487]
  "Statistical-computational gaps" occur in many statistical inference tasks. We consider a model for random order-3 decomposition where one component is slightly larger in norm than the rest. We show that tensor entries can accurately estimate the largest component when $ll n3/2$ but fail to do so when $rgg n3/2$.
  arXiv  Detail & Related papers  (2022-11-10T00:40:37Z)
• Learning a Single Neuron with Adversarial Label Noise via Gradient Descent [50.659479930171585]
  We study a function of the form $mathbfxmapstosigma(mathbfwcdotmathbfx)$ for monotone activations. The goal of the learner is to output a hypothesis vector $mathbfw$ that $F(mathbbw)=C, epsilon$ with high probability.
  arXiv  Detail & Related papers  (2022-06-17T17:55:43Z)
• Topological phases of unitary dynamics: Classification in Clifford category [0.0]
  A quantum cellular automaton (QCA) or a causal unitary is by definition an automorphism of local operator algebra. A Clifford QCA is one that maps any Pauli operator to a finite tensor product of Pauli operators.
  arXiv  Detail & Related papers  (2022-05-18T18:00:38Z)
• Depth and Feature Learning are Provably Beneficial for Neural Network Discriminators [3.04585143845864]
  We show that deep GAN discriminators are able to distinguish distributions that shallow discriminators cannot distinguish. This confirms that feature learning is beneficial for discriminators.
  arXiv  Detail & Related papers  (2021-12-27T19:03:22Z)
• Statistical Query Lower Bounds for Tensor PCA [10.701091387118023]
  In the PCA problem introduced by Richard and Montanari, one is given a dataset consisting of $n$ samples $mathbbEmathbfT_1:n$ of i.i.d. Perkins Gaussian tensors of order $k$ with the promise that $mathbbEmathbfT_1:n$ is a rank-1. The goal is to estimate $mathbbE mathbfT_1$, but no time estimator is known. We provide a sharp analysis of the optimal sample complexity
  arXiv  Detail & Related papers  (2020-08-10T13:14:34Z)
• Learning Over-Parametrized Two-Layer ReLU Neural Networks beyond NTK [58.5766737343951]
  We consider the dynamic of descent for learning a two-layer neural network. We show that an over-parametrized two-layer neural network can provably learn with gradient loss at most ground with Tangent samples.
  arXiv  Detail & Related papers  (2020-07-09T07:09:28Z)
• Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals [49.60752558064027]
  We study the fundamental problems of agnostically learning halfspaces and ReLUs under Gaussian marginals. Our lower bounds provide strong evidence that current upper bounds for these tasks are essentially best possible.
  arXiv  Detail & Related papers  (2020-06-29T17:10:10Z)

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.