Revisiting Atomic Patterns for Elliptic Curve Scalar Multiplication Revealing Inherent Vulnerability to Simple SCA

• URL: http://arxiv.org/abs/2412.03218v1
• Date: Wed, 04 Dec 2024 11:13:04 GMT
• Title: Revisiting Atomic Patterns for Elliptic Curve Scalar Multiplication Revealing Inherent Vulnerability to Simple SCA
• Abstract summary: kP operation is the basic operation in all Elliptic Curve based cryptographic protocols.<n>In this work, we investigated the resistance of a kP algorithm implemented in hardware using Longa's atomic patterns.
• Score: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Elliptic Curve Scalar Multiplication denoted as kP operation is the basic operation in all Elliptic Curve based cryptographic protocols. The atomicity principle and different atomic patterns for kP algorithms were proposed in the past as countermeasures against simple side-channel analysis. In this work, we investigated the resistance of a kP algorithm implemented in hardware using Longa's atomic patterns. We analysed its simulated power trace. We show in the example of our kP implementation for the NIST EC P-256 that the field squaring operations are distinguishable from the field multiplications even if they are performed by the same field multiplier, due to the addressing of the second multiplicand. This inherent vulnerability of atomic patterns can be successfully exploited for revealing the scalar k.

Related papers

• Preventing Distinguishability between Multiplication and Squaring Operations [0.0]
  Scalar multiplication kP is a critical operation in Elliptic Curve Cryptosystems.<n>Despite strategies based on atomic patterns to enhance security, the binary kP algorithms remain susceptible to simple Side-Channel Analysis (SCA)<n>This vulnerability arises independent of the multiplication method used.<n>We implemented and analysed two mitigation techniques: one involving data redirection and another focusing on bus reloading.
  arXiv  Detail & Related papers  (2026-04-29T11:04:56Z)
• Horizontal SCA Attacks on Binary kP Algorithms using Chevallier-Mames Atomic Blocks [0.0]
  We show that binary right-to left and left-to-right kP algorithms, when implemented with Chevallier-Mames atomic block patterns, are still vulnerable to single-trace SCA attacks.<n>The vulnerability remains true for the left-to-right kP algorithm with projective coordinate randomization.
  arXiv  Detail & Related papers  (2026-04-24T10:42:12Z)
• 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)
• Regularized Online RLHF with Generalized Bilinear Preferences [68.44113000390544]
  We consider the problem of contextual online RLHF with general preferences.<n>We adopt the Generalized Bilinear Preference Model to capture preferences via low-rank, skew-symmetric matrices.<n>We prove that the dual gap of the greedy policy is bounded by the square of the estimation error.
  arXiv  Detail & Related papers  (2026-02-26T15:27:53Z)
• Block encoding of sparse matrices with a periodic diagonal structure [67.45502291821956]
  We provide an explicit quantum circuit for block encoding a sparse matrix with a periodic diagonal structure.<n>Various applications for the presented methodology are discussed in the context of solving differential problems.
  arXiv  Detail & Related papers  (2026-02-11T07:24:33Z)
• Resource analysis of Shor's elliptic curve algorithm with an improved quantum adder on a two-dimensional lattice [7.999752490202695]
  Quantum computers have the potential to break classical cryptographic systems.<n>We propose a carry-lookahead quantum adder that achieves Toffoli depth $log n + loglog n + O(1)$ with only $O(n)$ ancillas.<n>We perform a comprehensive resource analysis of Shor's elliptic curve algorithm on two-dimensional lattices.
  arXiv  Detail & Related papers  (2025-10-27T11:02:10Z)
• Efficient learning of bosonic Gaussian unitaries [3.1022255067547877]
  We present the first time-efficient for learning bosonic Gaussian unitaries with a rigorous analysis.<n>Our algorithm produces an estimate of the unknown unitary that is accurate to small worst-case error.
  arXiv  Detail & Related papers  (2025-10-07T02:42:40Z)
• Practical Investigation on the Distinguishability of Longa's Atomic Patterns [0.0]
  We implement a binary elliptic curve scalar multiplication kP algorithm with Longa's atomic patterns for the NIST elliptic curve P-256. We measured and analysed an electromagnetic trace of a single kP execution on a microcontroller.
  arXiv  Detail & Related papers  (2024-09-18T10:48:31Z)
• Distinguishability Investigation on Longa's Atomic Patterns when used as a Basis for Implementing Elliptic Curve Scalar Multiplication Algorithms [0.0]
  This thesis delves into the investigation of Longa's atomic patterns applied within Elliptic Curve scalar multiplication algorithms. The research employs these atomic patterns in practical implementation on a microcontroller. A significant contribution of this work is the identification and correction of several discrepancies in Longa's original atomic patterns.
  arXiv  Detail & Related papers  (2024-09-10T19:52:57Z)
• Cryptographically Secure Pseudo-Random Number Generation (CS-PRNG) Design using Robust Chaotic Tent Map (RCTM) [2.0448353403141515]
  This paper presents a novel method to generate cryptographically secure pseudo-random numbers (CSPRNG) using a robust chaotic tent map (RCTM) Various statistical tests are performed that ascertain the randomness of generated secure pseudo-random bits.
  arXiv  Detail & Related papers  (2024-08-10T15:16:00Z)
• Fast Shapley Value Estimation: A Unified Approach [71.92014859992263]
  We propose a straightforward and efficient Shapley estimator, SimSHAP, by eliminating redundant techniques. In our analysis of existing approaches, we observe that estimators can be unified as a linear transformation of randomly summed values from feature subsets. Our experiments validate the effectiveness of our SimSHAP, which significantly accelerates the computation of accurate Shapley values.
  arXiv  Detail & Related papers  (2023-11-02T06:09:24Z)
• Near-optimal quantum circuit construction via Cartan decomposition [4.900041609957432]
  We show the applicability of the Cartan decomposition of Lie algebras to quantum circuits. This approach can be used to synthesize circuits that can efficiently implement any desired unitary operation.
  arXiv  Detail & Related papers  (2022-12-25T17:01:13Z)
• A Variational Quantum Attack for AES-like Symmetric Cryptography [69.80357450216633]
  We propose a variational quantum attack algorithm (VQAA) for classical AES-like symmetric cryptography. In the VQAA, the known ciphertext is encoded as the ground state of a Hamiltonian that is constructed through a regular graph.
  arXiv  Detail & Related papers  (2022-05-07T03:15:15Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• Robust and Provably Monotonic Networks [0.0]
  We present a new method to constrain the Lipschitz constant of dense deep learning models. We show how the algorithm was used to train a powerful, robust, and interpretable discriminator for heavy-flavor decays in the LHCb realtime data-processing system.
  arXiv  Detail & Related papers  (2021-11-30T19:01:32Z)
• Sinkhorn Natural Gradient for Generative Models [125.89871274202439]
  We propose a novel Sinkhorn Natural Gradient (SiNG) algorithm which acts as a steepest descent method on the probability space endowed with the Sinkhorn divergence. We show that the Sinkhorn information matrix (SIM), a key component of SiNG, has an explicit expression and can be evaluated accurately in complexity that scales logarithmically. In our experiments, we quantitatively compare SiNG with state-of-the-art SGD-type solvers on generative tasks to demonstrate its efficiency and efficacy of our method.
  arXiv  Detail & Related papers  (2020-11-09T02:51:17Z)
• Orbital MCMC [82.54438698903775]
  We propose two practical algorithms for constructing periodic orbits from any diffeomorphism. We also perform an empirical study demonstrating the practical advantages of both kernels.
  arXiv  Detail & Related papers  (2020-10-15T22:25:52Z)
• Preparation of excited states for nuclear dynamics on a quantum computer [117.44028458220427]
  We study two different methods to prepare excited states on a quantum computer. We benchmark these techniques on emulated and real quantum devices. These findings show that quantum techniques designed to achieve good scaling on fault tolerant devices might also provide practical benefits on devices with limited connectivity and gate fidelity.
  arXiv  Detail & Related papers  (2020-09-28T17:21:25Z)
• Understanding Implicit Regularization in Over-Parameterized Single Index Model [55.41685740015095]
  We design regularization-free algorithms for the high-dimensional single index model. We provide theoretical guarantees for the induced implicit regularization phenomenon.
  arXiv  Detail & Related papers  (2020-07-16T13:27:47Z)

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.