Formal Power Series on Algebraic Cryptanalysis

• URL: http://arxiv.org/abs/2007.14729v3
• Date: Fri, 20 Sep 2024 01:09:22 GMT
• Title: Formal Power Series on Algebraic Cryptanalysis
• Authors: Shuhei Nakamura,
• Abstract summary: The degree of regularity and an upper bound of the first fall degree are often used in cryptanalysis. We provide a theoretical assumption for the first fall degree of a computing system over a sufficiently large field.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the complexity estimation for an attack that reduces a cryptosystem to solving a system of polynomial equations, the degree of regularity and an upper bound of the first fall degree are often used in cryptanalysis. While the degree of regularity can be easily computed using a univariate formal power series under the semi-regularity assumption, determining an upper bound of the first fall degree requires investigating the concrete syzygies of an input system. In this paper, we investigate an upper bound of the first fall degree for a polynomial system over a sufficiently large field. In this case, we prove that the first fall degree of a non-semi-regular system is bounded above by the degree of regularity, and that the first fall degree of a multi-graded polynomial system is bounded above by a certain value determined from a multivariate formal power series. Moreover, we provide a theoretical assumption for computing the first fall degree of a polynomial system over a sufficiently large field.

Related papers

• Tensor cumulants for statistical inference on invariant distributions [49.80012009682584]
  We show that PCA becomes computationally hard at a critical value of the signal's magnitude. We define a new set of objects, which provide an explicit, near-orthogonal basis for invariants of a given degree. It also lets us analyze a new problem of distinguishing between different ensembles.
  arXiv  Detail & Related papers  (2024-04-29T14:33:24Z)
• The Complexity of Algebraic Algorithms for LWE [0.0]
  We revisit the Arora-Ge model to study complexity of Gr"obner basis computations on LWE systems. We generalize the Gr"obner basis algorithm of Semaev & Tenti to arbitrary systems with a finite degree of regularity.
  arXiv  Detail & Related papers  (2024-02-12T17:59:26Z)
• Solving Degree Bounds For Iterated Polynomial Systems [0.0]
  We prove regularity estimations for attacks on MiMC, Feistel-MiMC, Feistel-MiMC-Hash, Hades and GMiMC. Our bounds fall in line with the hypothesized complexity of Gr"obner basis attacks on these designs.
  arXiv  Detail & Related papers  (2023-10-05T16:10:14Z)
• 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)
• A Hybrid System for Systematic Generalization in Simple Arithmetic Problems [70.91780996370326]
  We propose a hybrid system capable of solving arithmetic problems that require compositional and systematic reasoning over sequences of symbols. We show that the proposed system can accurately solve nested arithmetical expressions even when trained only on a subset including the simplest cases.
  arXiv  Detail & Related papers  (2023-06-29T18:35:41Z)
• An Exponential Separation Between Quantum Query Complexity and the Polynomial Degree [79.43134049617873]
  In this paper, we demonstrate an exponential separation between exact degree and approximate quantum query for a partial function. For an alphabet size, we have a constant versus separation complexity.
  arXiv  Detail & Related papers  (2023-01-22T22:08:28Z)
• Renormalized von Neumann entropy with application to entanglement in genuine infinite dimensional systems [0.0]
  Von Neumann quantum entropy is finite and continuous in general, infinite dimensional case. The renormalized quantum entropy is defined by the explicit use of the Fredholm determinants theory. Several features of majorization theory are preserved under then introduced renormalization as it is proved in this paper.
  arXiv  Detail & Related papers  (2022-11-10T12:56:07Z)
• Unitary property testing lower bounds by polynomials [0.15229257192293197]
  We study unitary property testing, where a quantum algorithm is given query access to a black-box unitary. Characterizing the complexity of these problems requires new algorithmic techniques and lower bound methods. We present a unitary property testing-based approach towards an oracle separation between $mathsfQMA$ and $mathsfQMA(2)$.
  arXiv  Detail & Related papers  (2022-10-12T03:01:00Z)
• Tight Exponential Analysis for Smoothing the Max-Relative Entropy and for Quantum Privacy Amplification [56.61325554836984]
  The max-relative entropy together with its smoothed version is a basic tool in quantum information theory. We derive the exact exponent for the decay of the small modification of the quantum state in smoothing the max-relative entropy based on purified distance.
  arXiv  Detail & Related papers  (2021-11-01T16:35:41Z)
• Computational Barriers to Estimation from Low-Degree Polynomials [81.67886161671379]
  We study the power of low-degrees for the task of detecting the presence of hidden structures. For a large class of "signal plus noise" problems, we give a user-friendly lower bound for the best possible mean squared error achievable by any degree. As applications, we give a tight characterization of the low-degree minimum mean squared error for the planted submatrix and planted dense subgraph problems.
  arXiv  Detail & Related papers  (2020-08-05T17:52:10Z)
• Free Energy Wells and Overlap Gap Property in Sparse PCA [81.64027805404483]
  We study a variant of the sparse PCA (principal component analysis) problem in the "hard" regime. We show bounds on the depth of free energy wells for various Gibbs measures naturally associated to the problem. We prove that the Overlap Gap Property (OGP) holds in a significant part of the hard regime.
  arXiv  Detail & Related papers  (2020-06-18T17:18:02Z)

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.