On efficient normal bases over binary fields

• URL: http://arxiv.org/abs/2402.11544v1
• Date: Sun, 18 Feb 2024 11:06:20 GMT
• Title: On efficient normal bases over binary fields
• Authors: Mohamadou Sall, M. Anwar Hasan,
• Abstract summary: Binary field extensions are fundamental to cryptography, code-based cryptography, and error-correcting codes. In this paper, we explore other forms of bases $mathbbF_2n$ over $mathbbF$ to demonstrate efficient implementation of operations within different ranges.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Binary field extensions are fundamental to many applications, such as multivariate public key cryptography, code-based cryptography, and error-correcting codes. Their implementation requires a foundation in number theory and algebraic geometry and necessitates the utilization of efficient bases. The continuous increase in the power of computation, and the design of new (quantum) computers increase the threat to the security of systems and impose increasingly demanding encryption standards with huge polynomial or extension degrees. For cryptographic purposes or other common implementations of finite fields arithmetic, it is essential to explore a wide range of implementations with diverse bases. Unlike some bases, polynomial and Gaussian normal bases are well-documented and widely employed. In this paper, we explore other forms of bases of $\mathbb{F}_{2^n}$ over $\mathbb{F}_2$ to demonstrate efficient implementation of operations within different ranges. To achieve this, we leverage results on fast computations and elliptic periods introduced by Couveignes and Lercier, and subsequently expanded upon by Ezome and Sall. This leads to the establishment of new tables for efficient computation over binary fields.

Related papers

• VLWE: Variety-based Learning with Errors for Vector Encryption through Algebraic Geometry [1.3824176915623292]
  Lattice-based cryptography is a foundation for post-quantum security. This work introduces Variety-LWE (VLWE), a new structured lattice problem based on algebraic geometry. We prove VLWE's security by reducing it to multiple independent instances, demonstrating resilience against classical and quantum attacks.
  arXiv  Detail & Related papers  (2025-02-11T06:04:24Z)
• Code Generation for Cryptographic Kernels using Multi-word Modular Arithmetic on GPU [0.5831737970661138]
  Homomorphic encryption (FHE) and zero-knowledge proofs (ZKPs) are emerging as solutions for data security in distributed environments. This paper presents a formalization of multi-word modular arithmetic (MoMA), which breaks down large bit-width integer arithmetic into operations on machine words.
  arXiv  Detail & Related papers  (2025-01-13T18:15:44Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  Formal language theory pertains specifically to recognizers. It is common to instead use proxy tasks that are similar in only an informal sense. We correct this mismatch by training and evaluating neural networks directly as binary classifiers of strings.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Quantum inspired factorization up to 100-bit RSA number in polynomial time [0.0]
  We attack the RSA factorization building on Schnorr's mathematical framework. We factorize RSA numbers up to 256 bits encoding the optimization problem in quantum systems. Results do not currently undermine the security of the present communication infrastructure.
  arXiv  Detail & Related papers  (2024-10-21T18:00:00Z)
• Three-Input Ciphertext Multiplication for Homomorphic Encryption [6.390468088226496]
  Homomorphic encryption (HE) allows computations directly on ciphertexts. HE is essential to privacy-preserving computing, such as neural network inference, medical diagnosis, and financial data analysis. This paper proposes 3-input ciphertext multiplication to reduce complexity of computations.
  arXiv  Detail & Related papers  (2024-10-17T13:40:49Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose arbitrary exponentials into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions. We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  Recently proposed quantum algorithm arXiv:2206.14999 is based on semidefinite programming (SDP) We generalize the SDP-inspired quantum algorithm to sum-of-squares. Our results show that our algorithm is suitable for large problems and approximate the best known classicals.
  arXiv  Detail & Related papers  (2024-08-14T19:04:13Z)
• Reverse That Number! Decoding Order Matters in Arithmetic Learning [49.5504492920404]
  Our work introduces a novel strategy that reevaluates the digit order by prioritizing output from the least significant digit. Compared to the previous state-of-the-art (SOTA) method, our findings reveal an overall improvement of in accuracy while requiring only a third of the tokens typically used during training.
  arXiv  Detail & Related papers  (2024-03-09T09:04:53Z)
• Multiparameter Persistent Homology-Generic Structures and Quantum Computing [0.0]
  This article is an application of commutative algebra to the study of persistent homology in topological data analysis. The generic structure of such resolutions and the classifying spaces are studied using results spanning several decades of research.
  arXiv  Detail & Related papers  (2022-10-20T17:30:20Z)
• Finite-Function-Encoding Quantum States [52.77024349608834]
  We introduce finite-function-encoding (FFE) states which encode arbitrary $d$-valued logic functions. We investigate some of their structural properties.
  arXiv  Detail & Related papers  (2020-12-01T13:53:23Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)

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.