Semigroup action based on skew polynomial evaluation with applications to Cryptography

• URL: http://arxiv.org/abs/2512.02603v1
• Date: Tue, 02 Dec 2025 10:08:50 GMT
• Title: Semigroup action based on skew polynomial evaluation with applications to Cryptography
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Through this work we introduce an action of the skew polynomial ring $\mathbb{F}_{q}\left[X; σ, δ\right]$ over $\mathbb{F}_{q}$ based on its polynomial valuation and the concept of left skew product of functions. This lead us to explore the construction of a certain subset $\mathcal{T}(X)\subset\mathbb{F}_{q}\left[X; σ, δ\right]$ that allow us to control the non-commutativity of this ring, and exploit this fact in order to build a public key exchange protocol that is secure in Canetti and Krawczyk model.

Related papers

• Analytical Angle-Finding and Series Expansions for Quantum Signal Processing via Orthogonal Polynomial Theory [0.5156484100374059]
  Quantum signal processing is a powerful framework in quantum algorithms, playing a central role in Hamiltonian simulation and related applications.<n>We characterize the achievable bases in terms of their orthogonality or biorthogonality with respect to a functional admitting an integral representation.<n>Explicit expressions for the quantum signal processing angles are derived for families of sequences.
  arXiv  Detail & Related papers  (2026-05-06T18:00:26Z)
• 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)
• Stabilizing Fixed-Point Iteration for Markov Chain Poisson Equations [49.702772230127465]
  We study finite-state Markov chains with $n$ states and transition matrix $P$.<n>We show that all non-decaying modes are captured by a real peripheral invariant subspace $mathcalK(P)$, and that the induced operator on the quotient space $mathbbRn/mathcalK(P) is strictly contractive, yielding a unique quotient solution.
  arXiv  Detail & Related papers  (2026-01-31T02:57:01Z)
• Low-degree lower bounds via almost orthonormal bases [47.83594448785856]
  Low-degrees have emerged as a powerful paradigm for providing evidence of statistical--computational gaps across a variety of high-dimensional statistical models.<n>In this work, we propose a more direct proof strategy.
  arXiv  Detail & Related papers  (2025-09-11T11:07:36Z)
• $p$-Adic Polynomial Regression as Alternative to Neural Network for Approximating $p$-Adic Functions of Many Variables [55.2480439325792]
  A regression model is constructed that allows approximating continuous functions with any degree of accuracy.<n>The proposed model can be considered as a simple alternative to possible $p$-adic models based on neural network architecture.
  arXiv  Detail & Related papers  (2025-03-30T15:42:08Z)
• Gauging $\mathbb{Z}_N$ symmetries of Narain CFTs [0.0]
  We investigate the gauging of a $mathbbZ_N$ symmetry in lattice conformal field theories (CFTs)<n>As an application, we identify a class of codes that yield self-dual bosonic CFTs under the orbifolding by a $mathbbZ_N$ symmetry.
  arXiv  Detail & Related papers  (2025-03-27T14:11:02Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We present a novel characterization of rank, grounded in the well-known Transformer architecture.<n>We show that the rank of a function $f$ corresponds to the minimum number of emphChain of Thought steps required by a single-layer Transformer.<n>We also introduce the notion of the multi-head rank that captures multi-head single-layer transformers, and perform the analysis of PAC-learnability of the classes of functions with bounded multi-head rank.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• 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)$<n>We prove that a two-layer neural network optimized by an SGD-based algorithm learns $f_*$ with a complexity that is not governed by information exponents.
  arXiv  Detail & Related papers  (2024-06-03T17:56:58Z)
• A new multivariate primitive from CCZ equivalence [1.8024397171920885]
  Multivariate Cryptography is one of the candidates for Post-quantum Cryptography.<n>In this article, we present a more general way of constructing a multivariate scheme by considering the CCZ.
  arXiv  Detail & Related papers  (2024-05-31T16:15:02Z)
• Cryptanalysis of PLWE based on zero-trace quadratic roots [0.0]
  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.
  arXiv  Detail & Related papers  (2023-12-15T16:22:59Z)
• Algebraic Aspects of Boundaries in the Kitaev Quantum Double Model [77.34726150561087]
  We provide a systematic treatment of boundaries based on subgroups $Ksubseteq G$ with the Kitaev quantum double $D(G)$ model in the bulk. The boundary sites are representations of a $*$-subalgebra $Xisubseteq D(G)$ and we explicate its structure as a strong $*$-quasi-Hopf algebra. As an application of our treatment, we study patches with boundaries based on $K=G$ horizontally and $K=e$ vertically and show how these could be used in a quantum computer
  arXiv  Detail & Related papers  (2022-08-12T15:05:07Z)
• The Schr\"odinger Bridge between Gaussian Measures has a Closed Form [101.79851806388699]
  We focus on the dynamic formulation of OT, also known as the Schr"odinger bridge (SB) problem. In this paper, we provide closed-form expressions for SBs between Gaussian measures.
  arXiv  Detail & Related papers  (2022-02-11T15:59:01Z)

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.