Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors

• URL: http://arxiv.org/abs/2402.01082v1
• Date: Fri, 2 Feb 2024 00:48:27 GMT
• Title: Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors
• Authors: Samuel Stevens, Emily Wenger, Cathy Li, Niklas Nolte, Eshika Saxena, Fran\c{c}ois Charton, Kristin Lauter
• Abstract summary: Learning with Errors (LWE) is a hard math problem underlying post-quantum cryptography systems for key exchange and digital signatures. Prior work proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods -- better preprocessing, angular embeddings and model pre-training -- to improve these attacks.
• Score: 10.800552110718714
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning with Errors (LWE) is a hard math problem underlying recently standardized post-quantum cryptography (PQC) systems for key exchange and digital signatures. Prior work proposed new machine learning (ML)-based attacks on LWE problems with small, sparse secrets, but these attacks require millions of LWE samples to train on and take days to recover secrets. We propose three key methods -- better preprocessing, angular embeddings and model pre-training -- to improve these attacks, speeding up preprocessing by $25\times$ and improving model sample efficiency by $10\times$. We demonstrate for the first time that pre-training improves and reduces the cost of ML attacks on LWE. Our architecture improvements enable scaling to larger-dimension LWE problems: this work is the first instance of ML attacks recovering sparse binary secrets in dimension $n=1024$, the smallest dimension used in practice for homomorphic encryption applications of LWE where sparse binary secrets are proposed.

Related papers

• Benchmarking Attacks on Learning with Errors [9.031051362571436]
  Lattice cryptography schemes based on the learning with errors (LWE) hardness assumption have been standardized by NIST for use as post-quantum cryptosystems. We provide the first benchmarks for LWE secret recovery on standardized parameters, for small and low-weight (sparse) secrets. We extend the SALSA and Cool & Cruel attacks in significant ways, and implement and scale up MitM attacks for the first time.
  arXiv  Detail & Related papers  (2024-08-01T19:21:20Z)
• Enabling High-Sparsity Foundational Llama Models with Efficient Pretraining and Deployment [56.44025052765861]
  Large language models (LLMs) have revolutionized Natural Language Processing (NLP), but their size creates computational bottlenecks. We introduce a novel approach to create accurate, sparse foundational versions of performant LLMs. We show a total speedup on CPUs for sparse-quantized LLaMA models of up to 8.6x.
  arXiv  Detail & Related papers  (2024-05-06T16:03:32Z)
• FFN-SkipLLM: A Hidden Gem for Autoregressive Decoding with Adaptive Feed Forward Skipping [49.66872823080736]
  Autoregressive Large Language Models (e.g., LLaMa, GPTs) are omnipresent achieving remarkable success in language understanding and generation. To mitigate overload incurred during generation, several early-exit and layer-dropping strategies have been proposed. We propose FFN-SkipLLM, which is an input-adaptive feed-forward skipping strategy.
  arXiv  Detail & Related papers  (2024-04-05T02:35:43Z)
• The cool and the cruel: separating hard parts of LWE secrets [11.000531626756853]
  Known attacks on sparse binary LWE secrets include the sparse dual attack and the hybrid sparse dual-meet in the middle attack. In this paper, we provide a new statistical attack with low memory requirement.
  arXiv  Detail & Related papers  (2024-03-15T14:16:21Z)
• Alpaca against Vicuna: Using LLMs to Uncover Memorization of LLMs [61.04246774006429]
  We introduce a black-box prompt optimization method that uses an attacker LLM agent to uncover higher levels of memorization in a victim agent. We observe that our instruction-based prompts generate outputs with 23.7% higher overlap with training data compared to the baseline prefix-suffix measurements. Our findings show that instruction-tuned models can expose pre-training data as much as their base-models, if not more so, and using instructions proposed by other LLMs can open a new avenue of automated attacks.
  arXiv  Detail & Related papers  (2024-03-05T19:32:01Z)
• Bypassing the Safety Training of Open-Source LLMs with Priming Attacks [3.8023902618391783]
  In this paper, we investigate the fragility of SOTA open-source LLMs under simple, optimization-free attacks. Our proposed attack improves the Attack Success Rate on Harmful Behaviors, as measured by Llama Guard, by up to $3.3times$ compared to baselines.
  arXiv  Detail & Related papers  (2023-12-19T16:47:12Z)
• Dynamic Sparse No Training: Training-Free Fine-tuning for Sparse LLMs [67.38165028487242]
  We introduce Dynamic Sparse No Training (DSnoT), a training-free fine-tuning approach to fine-tune large language models (LLMs) Inspired by the Dynamic Sparse Training, DSnoT minimizes the reconstruction error between the dense and sparse LLMs. Our paper offers fresh insights into how to fine-tune sparse LLMs in an efficient training-free manner and open new venues to scale the great potential of sparsity to LLMs.
  arXiv  Detail & Related papers  (2023-10-13T07:38:52Z)
• SmoothLLM: Defending Large Language Models Against Jailbreaking Attacks [99.23352758320945]
  We propose SmoothLLM, the first algorithm designed to mitigate jailbreaking attacks on large language models (LLMs) Based on our finding that adversarially-generated prompts are brittle to character-level changes, our defense first randomly perturbs multiple copies of a given input prompt, and then aggregates the corresponding predictions to detect adversarial inputs.
  arXiv  Detail & Related papers  (2023-10-05T17:01:53Z)
• A Simple and Effective Pruning Approach for Large Language Models [58.716255689941896]
  Large Languages Models (LLMs) are natural candidates for network pruning methods. Existing methods, however, require either retraining, or solving a weight reconstruction problem reliant on second-order information. We introduce a novel, straightforward yet effective pruning method, termed Wanda (Pruning by Weights and activations), designed to induce sparsity in pretrained LLMs.
  arXiv  Detail & Related papers  (2023-06-20T17:18:20Z)
• SALSA PICANTE: a machine learning attack on LWE with binary secrets [8.219373043653507]
  We present PICANTE, an enhanced machine learning attack on LWE with sparse binary secrets. PICANTE recovers secrets in much larger dimensions (up to $n=350$) and with larger Hamming weights. While PICANTE does not threaten NIST's proposed LWE standards, it demonstrates significant improvement over SALSA.
  arXiv  Detail & Related papers  (2023-03-07T19:01:01Z)
• SALSA: Attacking Lattice Cryptography with Transformers [6.229340901386596]
  We propose SALSA: a machine learning attack on LWE-based cryptographic schemes. SALSA can fully recover secrets for small-to-mid size LWE instances with sparse binary secrets, and may scale to attack real-world LWE-based cryptosystems.
  arXiv  Detail & Related papers  (2022-07-11T11:35:43Z)

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.