惯性聚合 高效追踪和阅读你感兴趣的博客、新闻、科技资讯
阅读原文 在惯性聚合中打开

推荐订阅源

云风的 BLOG
云风的 BLOG
让小产品的独立变现更简单 - ezindie.com
让小产品的独立变现更简单 - ezindie.com
IT之家
IT之家
Recent Announcements
Recent Announcements
B
Blog
D
Docker
V
V2EX
GbyAI
GbyAI
L
LangChain Blog
博客园 - Franky
U
Unit 42
T
The Blog of Author Tim Ferriss
A
About on SuperTechFans
博客园 - 【当耐特】
Google DeepMind News
Google DeepMind News
H
Hackread – Cybersecurity News, Data Breaches, AI and More
Vercel News
Vercel News
博客园_首页
D
DataBreaches.Net
人人都是产品经理
人人都是产品经理
Y
Y Combinator Blog
量子位
Blog — PlanetScale
Blog — PlanetScale
罗磊的独立博客

cs.CR updates on arXiv.org

Agentic Vulnerability Reasoning on Windows COM Binaries From Beats to Breaches:How Offensive AI Infers Sensitive User Information from Playlists Undetectable Backdoors in Model Parameters: Hiding Sparse Secrets in High Dimensions When Embedding-Based Defenses Fail: Rethinking Safety in LLM-Based Multi-Agent Systems Token-Efficient Change Detection in LLM APIs Selfie-Capture Dynamics as an Auxiliary Signal Against Deepfakes and Injection Attacks for Mobile Identity Verification Trident: Improving Malware Detection with LLMs and Behavioral Features When Alignment Isn't Enough: Response-Path Attacks on LLM Agents RefusalGuard: Geometry-Preserving Fine-Tuning for Safety in LLMs Checkerboard: A Simple, Effective, Efficient and Learning-free Clean Label Backdoor Attack with Low Poisoning Budget Block-wise Codeword Embedding for Reliable Multi-bit Text Watermarking Secret Stealing Attacks on Local LLM Fine-Tuning through Supply-Chain Model Code Backdoors Enhancing Linux Privilege Escalation Attack Capabilities of Local LLM Agents Defusing the Trigger: Plug-and-Play Defense for Backdoored LLMs via Tail-Risk Intrinsic Geometric Smoothing Evaluating Jailbreaking Vulnerabilities in LLMs Deployed as Assistants for Smart Grid Operations: A Benchmark Against NERC Standards Behavioral Canaries: Auditing Private Retrieved Context Usage in RL Fine-Tuning FlexServe: A Fast and Secure LLM Serving System for Mobile Devices with Flexible Resource Isolation Breaking MCP with Function Hijacking Attacks: Novel Threats for Function Calling and Agentic Models Text Steganography with Dynamic Codebook and Multimodal Large Language Model An AI Agent Execution Environment to Safeguard User Data TwoHamsters: Benchmarking Multi-Concept Compositional Unsafety in Text-to-Image Models Fundamental Limitations of Favorable Privacy-Utility Guarantees for DP-SGD Symbolic Guardrails for Domain-Specific Agents: Stronger Safety and Security Guarantees Without Sacrificing Utility Hardening x402: PII-Safe Agentic Payments via Pre-Execution Metadata Filtering QShield: Securing Neural Networks Against Adversarial Attacks using Quantum Circuits Hijacking Text Heritage: Hiding the Human Signature through Homoglyphic Substitution Like a Hammer, It Can Build, It Can Break: Large Language Model Uses, Perceptions, and Adoption in Cybersecurity Operations on Reddit Private Seeds, Public LLMs: Realistic and Privacy-Preserving Synthetic Data Generation One Word at a Time: Incremental Completion Decomposition Breaks LLM Safety Measuring and Exploiting Contextual Bias in LLM-Assisted Security Code Review
Deterministic Hardness of Approximation of Unique-SVP and...
Yahli Hecht, Muli Safra · 2025-10-20 · via cs.CR updates on arXiv.org

We establish deterministic hardness of approximation results for the Shortest Vector Problem in $\ell_p$ norm ($\mathsf{SVP}_p$) and for Unique-SVP ($\mathsf{uSVP}_p$) for all $p > 2$. Previously, no deterministic hardness results were known, except for $\ell_\infty$. For every $p > 2$, we prove constant-ratio hardness: no polynomial-time algorithm approximates $\mathsf{SVP}_p$ or $\mathsf{uSVP}_p$ within a ratio of $\sqrt{2} - o(1)$, assuming $\textsf{3SAT} \notin \text{DTIME}(2^{O(n^{2/3}\log n)})$, and, $\textsf{Unambiguous-3SAT} \notin \text{DTIME}(2^{O(n^{2/3}\log n)})$. We also show that for any $\varepsilon > 0$ there exists $p_\varepsilon > 2$ such that for every $p \ge p_\varepsilon$: no polynomial-time algorithm approximates $\mathsf{SVP}_p$ within a ratio of $2^{(\log n)^{1- \varepsilon}}$, assuming $\text{NP} \nsubseteq \text{DTIME}(n^{(\log n)^\varepsilon})$; and within a ratio of $n^{1/(\log\log(n))^\varepsilon}$, assuming $\text{NP} \nsubseteq \text{SUBEXP}$. This improves upon [Haviv, Regev, Theory of Computing 2012], which obtained similar inapproximation ratios under randomized reductions. We obtain analogous results for $\mathsf{uSVP}_p$ under the assumptions $\textsf{Unambiguous-3SAT} \not\subseteq \text{DTIME}(n^{(\log n)^\varepsilon})$ and $\textsf{Unambiguous-3SAT} \not\subseteq \text{SUBEXP}$, improving the previously known $1+o(1)$ [Stephens-Davidowitz, Approx 2016]. Strengthening the hardness of $\textsf{uSVP}$ has direct cryptographic impact. By the reduction of Lyubashevsky and Micciancio [Lyubashevsky, Micciancio, CRYPTO 2009], hardness for $γ$-$\mathsf{uSVP}_p$ carries over to ${\frac{1}γ}$-$\mathsf{BDD}_p$ (Bounded Distance Decoding). Thus, understanding the hardness of $\textsf{uSVP}$ improves worst-case guarantees for two core problems that underpin security in lattice-based cryptography.