Benchmarking Attacks on Learning with Errors

• URL: http://arxiv.org/abs/2408.00882v2
• Date: Thu, 10 Oct 2024 15:48:45 GMT
• Title: Benchmarking Attacks on Learning with Errors
• Authors: Emily Wenger, Eshika Saxena, Mohamed Malhou, Ellie Thieu, Kristin Lauter,
• Abstract summary: 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.
• Score: 9.031051362571436
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Lattice cryptography schemes based on the learning with errors (LWE) hardness assumption have been standardized by NIST for use as post-quantum cryptosystems, and by HomomorphicEncryption.org for encrypted compute on sensitive data. Thus, understanding their concrete security is critical. Most work on LWE security focuses on theoretical estimates of attack performance, which is important but may overlook attack nuances arising in real-world implementations. The sole existing concrete benchmarking effort, the Darmstadt Lattice Challenge, does not include benchmarks relevant to the standardized LWE parameter choices - such as small secret and small error distributions, and Ring-LWE (RLWE) and Module-LWE (MLWE) variants. To improve our understanding of concrete LWE security, we provide the first benchmarks for LWE secret recovery on standardized parameters, for small and low-weight (sparse) secrets. We evaluate four LWE attacks in these settings to serve as a baseline: the Search-LWE attacks uSVP, SALSA, and Cool & Cruel, and the Decision-LWE attack: Dual Hybrid Meet-in-the-Middle (MitM). We extend the SALSA and Cool & Cruel attacks in significant ways, and implement and scale up MitM attacks for the first time. For example, we recover hamming weight $9-11$ binomial secrets for KYBER ($\kappa=2$) parameters in $28-36$ hours with SALSA and Cool\&Cruel, while we find that MitM can solve Decision-LWE instances for hamming weights up to $4$ in under an hour for Kyber parameters, while uSVP attacks do not recover any secrets after running for more than $1100$ hours. We also compare concrete performance against theoretical estimates. Finally, we open source the code to enable future research.

Related papers

• Denial-of-Service Poisoning Attacks against Large Language Models [64.77355353440691]
  LLMs are vulnerable to denial-of-service (DoS) attacks, where spelling errors or non-semantic prompts trigger endless outputs without generating an [EOS] token. We propose poisoning-based DoS attacks for LLMs, demonstrating that injecting a single poisoned sample designed for DoS purposes can break the output length limit.
  arXiv  Detail & Related papers  (2024-10-14T17:39:31Z)
• Style Outweighs Substance: Failure Modes of LLM Judges in Alignment Benchmarking [56.275521022148794]
  Post-training methods claim superior alignment by virtue of better correspondence with human pairwise preferences. We attempt to answer the question -- do LLM-judge preferences translate to progress on other, more concrete metrics for alignment, and if not, why not? We find that (1) LLM-judge preferences do not correlate with concrete measures of safety, world knowledge, and instruction following; (2) LLM-judges have powerful implicit biases, prioritizing style over factuality and safety; and (3) the supervised fine-tuning stage of post-training, and not the PO stage, has the greatest impact on alignment.
  arXiv  Detail & Related papers  (2024-09-23T17:58:07Z)
• Prompt Leakage effect and defense strategies for multi-turn LLM interactions [95.33778028192593]
  Leakage of system prompts may compromise intellectual property and act as adversarial reconnaissance for an attacker. We design a unique threat model which leverages the LLM sycophancy effect and elevates the average attack success rate (ASR) from 17.7% to 86.2% in a multi-turn setting. We measure the mitigation effect of 7 black-box defense strategies, along with finetuning an open-source model to defend against leakage attempts.
  arXiv  Detail & Related papers  (2024-04-24T23:39:58Z)
• 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)
• PAL: Proxy-Guided Black-Box Attack on Large Language Models [55.57987172146731]
  Large Language Models (LLMs) have surged in popularity in recent months, but they have demonstrated capabilities to generate harmful content when manipulated. We introduce the Proxy-Guided Attack on LLMs (PAL), the first optimization-based attack on LLMs in a black-box query-only setting. Our attack achieves 84% attack success rate (ASR) on GPT-3.5-Turbo and 48% on Llama-2-7B, compared to 4% for the current state of the art.
  arXiv  Detail & Related papers  (2024-02-15T02:54:49Z)
• SALAD-Bench: A Hierarchical and Comprehensive Safety Benchmark for Large Language Models [107.82336341926134]
  SALAD-Bench is a safety benchmark specifically designed for evaluating Large Language Models (LLMs) It transcends conventional benchmarks through its large scale, rich diversity, intricate taxonomy spanning three levels, and versatile functionalities.
  arXiv  Detail & Related papers  (2024-02-07T17:33:54Z)
• Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors [10.800552110718714]
  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.
  arXiv  Detail & Related papers  (2024-02-02T00:48:27Z)
• 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)
• 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)
• 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)

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.