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

• URL: http://arxiv.org/abs/2411.00067v3
• Date: Thu, 23 Jan 2025 16:53:50 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. All novel gadgets are proven secure in the $t$-probing model.
• 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 small signature size. Gaussian Elimination (GE) is a critical operation 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. All novel gadgets are proven secure in the $t$-probing model. Additionally, 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.3$\times$ higher, and the randomness cost is 1.2$\times$ higher in MAYO compared to UOV for security levels III and V. In contrast, these costs are similar in UOV and MAYO for one version of level I. 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 masked implementation targeting UOV parameters has an overhead of factor 15.1$\times$, 15.2$\times$, and 15.4$\times$ compared to the unprotected implementation for NIST security level I, III, and V.

Related papers

• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  We present a $textbfMA-OSMA$ algorithm to transfer the discrete submodular problem into a continuous optimization. We also introduce a projection-free $textbfMA-OSEA$ algorithm, which effectively utilizes the KL divergence by mixing a uniform distribution. Our algorithms significantly improve the $(frac11+c)$-approximation provided by the state-of-the-art OSG algorithm.
  arXiv  Detail & Related papers  (2025-02-07T15:57:56Z)
• A Safe Screening Rule with Bi-level Optimization of $\nu$ Support Vector Machine [15.096652880354199]
  We propose a safe screening rule with bi-level optimization for $nu$-SVM. Our SRBO-$nu$-SVM is strictly deduced by integrating the Karush-Kuhn-Tucker conditions. We also develop an efficient dual coordinate descent method (DCDM) to further improve computational speed.
  arXiv  Detail & Related papers  (2024-03-04T06:55:57Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  We propose a novelgreedy bandit (SGB) algorithm for multi-armed bandit problems when no extra information other than the joint reward of the selected set of $n$ arms at each time $tin [T]$ is observed. SGB adopts an optimized-explore-then-commit approach and is specifically designed for scenarios with a large set of base arms.
  arXiv  Detail & Related papers  (2023-12-13T11:08:25Z)
• 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)
• TDPP: Two-Dimensional Permutation-Based Protection of Memristive Deep Neural Networks [17.126478919408132]
  Non-volatility of memristive devices may expose the DNN weights stored in memristive crossbars to potential theft attacks. This paper proposes a two-dimensional permutation-based protection (TDPP) method that thwarts such attacks.
  arXiv  Detail & Related papers  (2023-10-10T20:22:17Z)
• Blockwise Stochastic Variance-Reduced Methods with Parallel Speedup for Multi-Block Bilevel Optimization [43.74656748515853]
  Non-stationary multi-block bilevel optimization problems involve $mgg 1$ lower level problems and have important applications in machine learning. We aim to achieve three properties for our algorithm: a) matching the state-of-the-art complexity of standard BO problems with a single block; (b) achieving parallel speedup by sampling $I$ samples for each sampled block per-iteration; and (c) avoiding the computation of the inverse of a high-dimensional Hessian matrix estimator.
  arXiv  Detail & Related papers  (2023-05-30T04:10:11Z)
• 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)
• Mask Transfiner for High-Quality Instance Segmentation [95.74244714914052]
  We present Mask Transfiner for high-quality and efficient instance segmentation. Our approach only processes detected error-prone tree nodes and self-corrects their errors in parallel. Our code and trained models will be available at http://vis.xyz/pub/transfiner.
  arXiv  Detail & Related papers  (2021-11-26T18:58:22Z)
• Correcting Momentum with Second-order Information [50.992629498861724]
  We develop a new algorithm for non-critical optimization that finds an $O(epsilon)$epsilon point in the optimal product. We validate our results on a variety of large-scale deep learning benchmarks and architectures.
  arXiv  Detail & Related papers  (2021-03-04T19:01:20Z)
• A Sharp Analysis of Model-based Reinforcement Learning with Self-Play [49.88233710867315]
  We present a sharp analysis of model-based self-play algorithms for multi-agent Markov games. We design an algorithm -- Optimistic Nash Value Iteration (Nash-VI) for two-player zero-sum Markov games. We further adapt our analysis to designing a provably efficient task-agnostic algorithm for zero-sum Markov games.
  arXiv  Detail & Related papers  (2020-10-04T15:27:39Z)

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.