Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based PQC

• URL: http://arxiv.org/abs/2411.00067v1
• Date: Thu, 31 Oct 2024 14:01:02 GMT
• Title: Masking Gaussian Elimination at Arbitrary Order, with Application to Multivariate- and Code-Based PQC
• Authors: Quinten Norga, Suparna Kundu, Uttam Kumar Ojha, Anindya Ganguly, Angshuman Karmakar, Ingrid Verbauwhede,
• Abstract summary: We provide a masking scheme for Gaussian Elimination (GE) with back substitution to defend against first- and higher-order attacks. We propose a masked algorithm for transforming a system of linear equations into row-echelon form. We evaluate the overhead of our countermeasure for several post-quantum candidates and their different security levels.
• Score: 4.655421225385125
• License:
• Abstract: Digital signature schemes based on multivariate- and code-based hard problems are promising alternatives for lattice-based signature schemes due to their smaller signature size. Hence, several candidates in the ongoing additional standardization for quantum secure digital signature (DS) schemes by the NIST rely on such alternate hard problems. Gaussian Elimination (GE) is a critical component in the signing procedure of these schemes. In this paper, we provide a masking scheme for GE with back substitution to defend against first- and higher-order attacks. To the best of our knowledge, this work is the first to analyze and propose masking techniques for multivariate- or code-based DS algorithms. We propose a masked algorithm for transforming a system of linear equations into row-echelon form. This is realized by introducing techniques for efficiently making leading (pivot) elements one while avoiding costly conversions between Boolean and multiplicative masking at all orders. We also propose a technique for efficient masked back substitution, which eventually enables a secure unmasking of the public output. We evaluate the overhead of our countermeasure for several post-quantum candidates and their different security levels at first-, second-, and third-order, including UOV, MAYO, SNOVA, QR-UOV, and MQ-Sign. Notably, the operational cost of first-, second-, and third-order masked GE is 2.3x higher, and the randomness cost is 1.2x higher in MAYO compared to UOV for security levels III and V. We also show detailed performance results for masked GE implementations for all three security versions of UOV on the Arm Cortex-M4 and compare them with unmasked results. Our first-order implementations targeting UOV parameters have overheads of factor 6.5x, 5.9x, and 5.7x compared to the unprotected implementation for NIST security level I, III, and V.

Related papers

• VDOO: A Short, Fast, Post-Quantum Multivariate Digital Signature Scheme [0.8643517734716606]
  We present a post-quantum digital signature algorithm based on solving multivariate equations. We show that our carefully chosen parameters can resist all existing state-of-the-art attacks. This is the smallest signature size among all known post-quantum signature schemes of similar security.
  arXiv  Detail & Related papers  (2023-12-15T04:58:10Z)
• On the Masking-Friendly Designs for Post-Quantum Cryptography [5.781461941357047]
  Masking is a well-known and provably secure countermeasure against side-channel attacks. The performance overhead of integrating masking countermeasures is heavily influenced by the design choices of a cryptographic algorithm. We show that the design decisions have a significant impact on the efficiency of integrating masking countermeasures into lattice-based cryptography.
  arXiv  Detail & Related papers  (2023-11-14T10:00:58Z)
• Fairness-Driven Optimization of RIS-Augmented 5G Networks for Seamless 3D UAV Connectivity Using DRL Algorithms [8.296140341710462]
  We study the problem of joint active and passive beamforming for reconfigurable intelligent surface (RIS)-assisted massive multiple-input multiple-output systems. We propose two novel algorithms to address this problem.
  arXiv  Detail & Related papers  (2023-11-14T06:43:36Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [70.26374282390401]
  Decoding the original signal (i.e., hidden chain) from the noisy observations is one of the main goals in nearly all HMM based data analyses. We present Quick Adaptive Ternary (QATS), a divide-and-conquer procedure which decodes the hidden sequence in polylogarithmic computational complexity.
  arXiv  Detail & Related papers  (2023-05-29T19:37:48Z)
• Automated Verification of Correctness for Masked Arithmetic Programs [7.9330271653905235]
  We study the problem for masked arithmetic programs over Galois fields of characteristic 2. We propose an automated approach based on term rewriting, aided by random testing and SMT solving. We implement the approach as a new tool FISCHER and carry out extensive experiments on various benchmarks.
  arXiv  Detail & Related papers  (2023-05-26T02:55:46Z)
• ConvMAE: Masked Convolution Meets Masked Autoencoders [65.15953258300958]
  Masked auto-encoding for feature pretraining and multi-scale hybrid convolution-transformer architectures can further unleash the potentials of ViT. Our ConvMAE framework demonstrates that multi-scale hybrid convolution-transformer can learn more discriminative representations via the mask auto-encoding scheme. Based on our pretrained ConvMAE models, ConvMAE-Base improves ImageNet-1K finetuning accuracy by 1.4% compared with MAE-Base.
  arXiv  Detail & Related papers  (2022-05-08T15:12:19Z)
• Random Hash Code Generation for Cancelable Fingerprint Templates using Vector Permutation and Shift-order Process [3.172761915061083]
  We propose a non-invertible distance preserving scheme based on vector permutation and shift-order process. A shift-order process is then applied to the generated features in order to achieve non-invertibility and combat similarity-based attacks. The generated hash codes are resilient to different security and privacy attacks whilst fulfilling the major revocability and unlinkability requirements.
  arXiv  Detail & Related papers  (2021-05-21T09:37:54Z)
• Multi-Discriminator Sobolev Defense-GAN Against Adversarial Attacks for End-to-End Speech Systems [78.5097679815944]
  This paper introduces a defense approach against end-to-end adversarial attacks developed for cutting-edge speech-to-text systems. First, we represent speech signals with 2D spectrograms using the short-time Fourier transform. Second, we iteratively find a safe vector using a spectrogram subspace projection operation. Third, we synthesize a spectrogram with such a safe vector using a novel GAN architecture trained with Sobolev integral probability metric.
  arXiv  Detail & Related papers  (2021-03-15T01:11:13Z)
• Joint Deep Reinforcement Learning and Unfolding: Beam Selection and Precoding for mmWave Multiuser MIMO with Lens Arrays [54.43962058166702]
  millimeter wave (mmWave) multiuser multiple-input multiple-output (MU-MIMO) systems with discrete lens arrays have received great attention. In this work, we investigate the joint design of a beam precoding matrix for mmWave MU-MIMO systems with DLA.
  arXiv  Detail & Related papers  (2021-01-05T03:55:04Z)
• NOMA in UAV-aided cellular offloading: A machine learning approach [59.32570888309133]
  A novel framework is proposed for cellular offloading with the aid of multiple unmanned aerial vehicles (UAVs) Non-orthogonal multiple access (NOMA) technique is employed at each UAV to further improve the spectrum efficiency of the wireless network. A mutual deep Q-network (MDQN) algorithm is proposed to jointly determine the optimal 3D trajectory and power allocation of UAVs.
  arXiv  Detail & Related papers  (2020-10-18T17:38:48Z)
• RIS Enhanced Massive Non-orthogonal Multiple Access Networks: Deployment and Passive Beamforming Design [116.88396201197533]
  A novel framework is proposed for the deployment and passive beamforming design of a reconfigurable intelligent surface (RIS) The problem of joint deployment, phase shift design, as well as power allocation is formulated for maximizing the energy efficiency. A novel long short-term memory (LSTM) based echo state network (ESN) algorithm is proposed to predict users' tele-traffic demand by leveraging a real dataset. A decaying double deep Q-network (D3QN) based position-acquisition and phase-control algorithm is proposed to solve the joint problem of deployment and design of the RIS.
  arXiv  Detail & Related papers  (2020-01-28T14:37:38Z)

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.