Cryptography and Security · Cross-listed from cs.RO
Building Trustworthy Household Robots through Open-World Safety
Yu-Lin Tsai, Muxi Lyu, Roei Herzig et al. (+3 more)
Foundation models are expanding
robot capabilities, enabling
robots to handle more diverse objects, follow sophisticated instructions, and operate in complex environments. These advances bring us to a future in which
robots become part of everyday household life. However, cluttered, dynamic household environments also expose
robots to unfamiliar objects, tasks, and interactions, making reliable zero-shot task completion an ongoing challenge for robotics research. From a security perspective, we argue for open-world safety: household
robots should preserve specified safety requirements in unseen situations, including when they cannot complete the requested task. Safety protections must account for context and interactions that persist across actions and tasks. In this position paper, we examine why existing safety methods can fail to provide this protection. Protection can fail through misinterpreted context, overlooked past interactions, or stopping and recovery strategies that become unsafe under unfamiliar conditions. We therefore propose a research agenda to specify, learn, and ground safety requirements, enforce them with reliable recovery, and evaluate the generalization of such protections. We call for household
robots whose safety protections remain reliable beyond the situations, context, and history used to train and develop them, to achieve open-world safety.
Read the full abstract ▾
All authors Yu-Lin Tsai, Muxi Lyu, Roei Herzig, Koushik Sen, Raluca Ada Popa, David Wagner
Cryptography and Security
Pincer: Resource Authorization for Agents using a Digital Twin
Mayank Rathee, Alexander Stepanov, Shalin Madabhavi et al. (+3 more)
Coding
agents have become increasingly long-horizon, autonomous, reliant on general-purpose shell and maintain their own persistent
memory for self-improvement. While these capabilities have made the
agents powerful, they have also made them harder to defend against external adversaries. Defenses that restrict this architecture — typed tools, information-flow control, or policy prediction engines — give up too much functionality to be adopted.
Agents deployed today (e.g. Claude, Codex) rely on a combination of user-mediated and automode sandboxing as their primary defense. In user-mediated sandboxing, user-maintained policies decay over time and repeated permission requests cause user fatigue, while auto mode's tool-call classifiers learn no user-specific policy and are not meant to defend against
adversarial setups. Pincer is a new defense that operates at the resource layer and works alongside existing defenses at the tool-call layer like the auto mode. At the core of Pincer lies a digital twin, an isolated-context model that automatically learns and enforces dynamic user-specific least-privilege policies. The digital twin keeps continually learning the user's preferences allowing it to act as the user's proxy for the
agent's permission requests. To emulate the learning phase, we propose a new usercentric
dataset with examples following a multi-day transcript of user-
agent interaction. Our evaluation shows that Pincer performs strongly on both security and utility in comparison to several baselines which includes variants of LLM judges and adaptations of Conseca (HotOS '25). We highlight attack types where Pincer's design leads to a significant security improvement compared to all other baselines, while outperforming the baselines even for other types of attacks.
Read the full abstract ▾
All authors Mayank Rathee, Alexander Stepanov, Shalin Madabhavi, Jinhao Zhu, Raluca Ada Popa, Ion Stoica
Cryptography and Security
Out of Sync, Out of Sight: Phantom State Attacks against IIoT Intrusion Detection
Sabrine Ennaji, Elhadj Benkhelifa and Nadia Kabachi
Machine learning-based intrusion detection systems (IDS) are critical for securing Industrial Internet of Things (IIoT) environments. Most
adversarial research against them perturbs the feature vector or the traffic that produces it, and depends on gradient access, repeated model queries, or a learned model of benign traffic. A smaller line of work reshapes packet timing without querying the detector, but makes malicious traffic mimic a learned model of benign timing. Across these approaches, one assumption of industrial monitoring pipelines has received little
attention: temporal synchronization. An IDS reconstructs operational state by aggregating telemetry into sliding or tumbling windows, so its view depends not only on what is observed but on when each observation falls relative to a window boundary. We introduce the Phantom State Attack (PSA), which exploits that dependence under a passive, zero-query threat model. Rather than modifying packets, perturbing features, querying the classifier, or fitting any model of benign traffic, PSA injects bounded timing drift calibrated to the attack flow's own inter-arrival variability, moving observations across the nearest window boundary by the minimal shift needed. The IDS then reconstructs a phantom state that diverges from the true process state. We evaluate PSA on ToN-IoT and CIC IIoT 2025 (DataSense), against Random Forest, MLP and XGBoost, measuring detection degradation, synchronization distortion, stealth, and attacker cost. PSA degrades detection on flows carrying enough packets for window-boundary redistribution, and leaves others almost unchanged, so its effect is conditional. A query-based baseline reaches higher raw success but needs many queries per window, while PSA needs none. The results identify temporal aggregation as an attack surface reachable under weaker assumptions than prior evasion techniques.
Read the full abstract ▾
Cryptography and Security
CITADEL: CWE-Guided Insertion of Hardware Trojans via Analysis of DFG-Enabled LLMs
Jayanth Thangellamudi, Raghul Saravanan, Sudipta Paria et al. (+2 more)
The increasing sophistication of Hardware Trojans (HTs) and system-level vulnerabilities poses significant risks to modern integrated
circuits. However, constructing realistic HT scenarios, remains a substantial burden: researchers must manually analyze complex RTL structures, identify plausible weaknesses, and craft stealthy, synthesizable insertions that preserve functional correctness. This paper introduces CITADEL CWE-Guided Insertion of Trojans via Analysis of DFG-Enabled LLMs, a framework that leverages Large
Language Models (LLMs) and Data Flow Graphs (DFGs) to automate CWE-grounded HT synthesis. CITADEL uses structured CWE semantics together with DFG-derived structural context to assist the user in identifying relevant vulnerabilities, localize the module surrounding the chosen insertion point, and perform intent-conditioned RTL modification. The framework produces minimal, synthesizable, and interface-preserving HTs with ultra-rare triggers. Experimental evaluation across diverse RTL designs demonstrates that all generated HTs are 100% syntactically correct, remain undetectable under large-scale random simulation, and are functionally triggerable under their intended activation conditions. These results highlight CITADEL as a scalable and principled method for generating realistic HT
benchmarks.
Read the full abstract ▾
All authors Jayanth Thangellamudi, Raghul Saravanan, Sudipta Paria, Swarup Bhunia, Sai Manoj P D
Cryptography and Security
SideKernel: A Usable microVM Sandbox for AI Coding Agents on macOS
Dimitrios Prasakis
AI coding
agents are untrusted system components, yet they require autonomy on the developer machines they run on. This contradiction is a security problem. Sandboxes provide an isolated environment, but for local macOS development, the existing local, open-source options for AI coding
agents are few in number and cumbersome to use. I conducted a formative online user survey which indicates that fewer than 40% of AI coding
agent users run their
agents in a sandbox and identifies the top usability barriers hindering AI coding
agent sandbox adoption. These findings are used to develop SideKernel: an open-source, local, microVM-based macOS sandbox for AI coding
agents designed for usability. To evaluate SideKernel, I compiled a list of sandboxes available on the
market and filtered it against five inclusion criteria. Then I performed a comparative analysis between SideKernel and the sandboxes that satisfy these criteria, across 23 capability tests derived from the usability barriers revealed by the user survey. I discovered that only a few sandboxes are similar to SideKernel, and that among those, Docker Sandboxes and SideKernel score highest on capability features related to usability. A secondary contribution of this paper is a survey of the existing solution space for local, open-source, microVM-based macOS sandboxes for AI coding
agents.
Read the full abstract ▾
Cryptography and Security
SoK: Stablecoins in the Quantum Era
Panagiotis Chatzigiannis, Navid Alamati, Suvradip Chakraborty et al. (+1 more)
Stablecoins support payments, trading, collateral, and cross-chain settlement across the digital-asset ecosystem. They also concentrate value behind issuer, custody, upgrade, oracle, and bridge keys while inheriting the
quantum vulnerabilities of host-chain accounts, consensus, rollups, and
privacy systems. This paper presents a Systematization of Knowledge (SoK) on post-
quantum stablecoins. We develop a stablecoin-specific threat model, map cryptographic dependencies to monetary control surfaces, and classify migration choices along three dimensions: who can authorize a change, where the change must occur, and whether it is hybrid, post-
quantum native, or an encapsulation of a classical component. We emphasize an authority-liability gap: the party able to migrate a component is often different from the holders, exchanges, protocols, or issuers that bear the loss if it fails. We review the relevant cryptographic primitives, but distinguish general blockchain failures from their stablecoin-specific effects. We also examine recent blockchain and issuer-controlled interoperability proposals, and relate migration choices to redemption, continuity, and intervention requirements under current stablecoin regulation. Our findings identify open problems in aggregate and threshold authorization, operation-specific security levels and costs, dormant and wrapped supply, private and compliance-enabled transfers, and measurement of
quantum-vulnerable stablecoin exposure.
Read the full abstract ▾
All authors Panagiotis Chatzigiannis, Navid Alamati, Suvradip Chakraborty, Duc V. Le
Cryptography and Security
Evaluating and Improving the Robustness of Large Language Models to Input Sequence Variations
Narek Maloyan
Large
language models (LLMs) in production systems face
prompt injections, trojans (backdoors), and manipulation of automatic quality metrics. This thesis develops models, methods, and
algorithms for evaluating and improving LLM robustness to
adversarial input sequence variations. We propose R_stab(f), a generative robustness metric based on the Jensen-Shannon divergence between per-step output distributions under small input perturbations. For localized attacks we prove V(h) <= 1 - R_class(h), where R_class(h) is the probability that a decision operator h keeps its decision under small perturbations. For non-localized attacks we propose a calibrated empirical model. For LLM-as-a-Judge systems we develop ASA, an adaptive evolutionary black-box attack that reaches an attack success rate (ASR) of up to 73.8%, with transfer between open models up to 62.6%. On Trojan Detection Challenge 2023 data (Pythia-1.4B), surrogate triggers reach REASR ~0.99 while recall of the true triggers is ~0.17 against a baseline of ~0.14. On SaTML CTF 2024 we systematize four classes of bypasses of multi-layer defenses, which reduce the ASR from 90% to 15-25%. Committees of 5-7 heterogeneous models reduce the ASR for Gemma-3-4B by 47-55 percentage points, to 19.3% with 7 models. For agentic systems based on the Model Context Protocol (MCP), we propose AttestMCP, which attests tool calls with HMAC-protected packets at under 0.1 ms per call, and the Commit Boundary isolation pattern. On the MCPBench
benchmark of 847 scenarios they reduce the average ASR from 53.7% to 12.4%. The methods are implemented in the JudgeGuard and TrojanArmor software suites and the MCPSec module.
Read the full abstract ▾
Cryptography and Security
Mitigating Private Data Leakage in LLMs with Whiteout
Anna Yoo Jeong Ha, Ronik Bhaskar, Haitao Zheng et al. (+1 more)
Modern large
language models (LLMs) are trained on massive, largely unfiltered
datasets, including content scraped from nearly every accessible website and user inputs. As a result, LLMs often memorize and reproduce personally sensitive information (PSI) such as birth dates, phone numbers, and home addresses. This leads to significant
privacy risks, particularly for high-profile individuals such as executives, politicians, and judges. Existing mitigations largely rely on machine unlearning. However, these methods often remove more information than needed, degrade model utility and safety, and are highly vulnerable to attacks. This paper presents Whiteout, a practical tool that, upon requests by individuals, prevents LLMs from regurgitating their genuine PSIs, by overwriting them using precise and carefully designed obfuscation samples. We evaluate Whiteout on modern LLMs of varying sizes and makers, including a widely-used OpenAI model. Results show that Whiteout effectively prevents disclosure of the targeted PSIs, has negligible impact on model utility and safety, and outperforms existing alternatives. We also test Whiteout against a wide range of countermeasures, from black-box attacks like jailbreaking to white-box adaptive attacks like relearning and quantization. Finally, we conclude with a discussion on the security and ethical implications of Whiteout.
Read the full abstract ▾
All authors Anna Yoo Jeong Ha, Ronik Bhaskar, Haitao Zheng, Ben Y. Zhao
Cryptography and Security
Unifying Privacy Accounting: Information Equivalence and Information Loss
Buxin Su, Qiaoshi Yang, Yiding Su et al. (+1 more)
Differential
privacy (DP) admits several notions, but the choice among them may affect both
privacy analysis and utility. In this paper, we consider four mainstream curve-based
privacy notions within a unified information-theoretic framework. For a fixed ordered pair of output distributions, we establish information equivalence among the two directional
privacy profiles of $(\varepsilon,\delta)$-DP, the pair of hypothesis-testing trade-off functions, and the extended
privacy-loss distribution. The exact Rényi differential
privacy (RDP) curve joins this equivalence class whenever it is finite at some order greater than one. Under this mild condition, choosing among these notions changes only their semantic interpretation and computational requirements. In contrast, taking the maximum of the directional
privacy profiles or compressing the RDP curve into a single zero-concentrated differential
privacy (zCDP) parameter can lose information. We quantify the information loss between the exact RDP curve and its zCDP bound for standard noise mechanisms. This gap is zero for Gaussian noise but generally positive for Gaussian-mixture, Laplace, discrete Gaussian, and Poisson-subsampled Gaussian mechanisms. Moreover, this gap grows linearly with the number of independently composed mechanisms. Our information-theoretic perspective has practical consequences. At the same certified
privacy level, retaining the full RDP curve rather than using zCDP reduces the required noise variance by up to $45\%$ for Gaussian-mixture noise in workloads comparable in size to the American Community Survey. For DP-SGD on Fashion-MNIST under Poisson subsampling, an RDP-based
privacy accountant improves test accuracy by up to $8.73$ percentage points compared to a zCDP-based accountant when both are calibrated to the same $(\varepsilon,\delta)$ guarantee.
Read the full abstract ▾
All authors Buxin Su, Qiaoshi Yang, Yiding Su, Chendi Wang
Cryptography and Security
Hop-Decayed Influence: New Vulnerabilities of Structural Auxiliary Indexing in GraphRAG Pipelines with LLM
Jisung Park, John Le and Heath Cooper
GraphRAG pipelines construct auxiliary structures during offline indexing–semantic summaries, hierarchical edges, and pre-computed scores–that determine how
retrieval is prioritised at query time. Prior attacks target only instance-level components (nodes, edges, triples), overlooking these schema-level structures. We formalise Auxiliary Schema-Level Entity as a novel attack surface and propose the 3S Framework (Semantics, Structure, Scoring) for its systematic exploitation. Our Hop-Decayed Influence (HDI) attack identifies high-impact targets through query-aware influence propagation and corrupts their auxiliary structures post-indexing. Across two
benchmarks (HotpotQA, 2WikiMultiHopQA) and two architectures (Microsoft GraphRAG, HippoRAG2), HDI achieves 88-94% attack success rate while modifying as few as 0.016% of auxiliary structures. Each modification affects up to 6.00 queries (Schema Leverage Ratio), demonstrating 1:N amplification unavailable to instance-level attacks. Manipulated structures evade perplexity and paraphrase defenses with over 99% evasion rate, as they remain linguistically coherent system-generated artifacts. These results reveal that auxiliary schema-level entities receive implicit trust without runtime validation, constituting a structural blind spot in current GraphRAG defenses. https://github.com/Jisung-Pacific/HDI-GraphRAG-Attack.
Read the full abstract ▾
Cryptography and Security
MIRROR: Multipath Quorum Integrity for LLM Multi-Agent Communication
Ryuichi Yamafuji Lun, Jingzhen Wang, Shreyas Kolte et al. (+1 more)
Inter-
agent communication is central to Large
Language Model Multi-
Agent Systems (LLM-MAS), but it introduces an underexplored vulnerability:
Agent-in-the-Middle (AiTM) attacks that manipulate messages in transit without compromising the
agents themselves. Prior work reports Attack Success Rates (ASR) approaching 100% on structured tasks. Existing defenses rely on semantic validation, which requires additional inference and can block benign outputs, or on transport-layer encryption, which does not help when an intermediary legitimately terminates TLS. We present MIRROR, a communication-layer integrity primitive that replicates a single canonicalized payload across k logical routes and accepts a message only when a strict majority of routes report the same digest. MIRROR uses unkeyed hashing and so authenticates nothing on its own, since an active on-path adversary can always recompute a digest over a payload it has modified. All integrity derives from the assumption that honest routes form a majority. The digest serves only to make witness routes constant-size and to bind the recovered payload to the quorum-agreed value under second-preimage resistance. We give the guarantee under a route-compromise bound alpha < 0.5, and extend it to correlated routes, where the quantity that matters is the size of the largest shared-failure group and not the route count. We further show that availability and integrity degrade at the same threshold: below alpha = 0.5, quorum-denial and message-dropping adversaries cannot block honest traffic. Across MMLU, HumanEval, and MBPP on two frameworks and four communication
topologies, and in a MetaGPT deployment against a production API, MIRROR reduces ASR to 0% below the threshold at 1x LLM
token cost. LLM-as-a-Judge costs 35x in the same deployment, and blocks up to 44.2% of benign outputs in the
topology sweep.
Read the full abstract ▾
All authors Ryuichi Yamafuji Lun, Jingzhen Wang, Shreyas Kolte, Ruiteng Li
Cryptography and Security
Intent-Hiding Jailbreaks: An Information-Theoretic Framework for Compositional Attacks
Fengwei Tian and Ravi Tandon
Recent work has shown that large
language models (LLMs) can be vulnerable to jailbreak attacks in which harmful intent is obscured through composition with benign tasks. A harmful request refused in isolation may elicit a different response when embedded within a larger, seemingly benign query. We study these compositional intent-hiding jailbreaks from an information-theoretic perspective. Our formulation associates each task with an estimated probability of being judged harmful: the average over the full task collection defines the prior probability of harmful intent, while the average over a selected bundle containing the target defines the posterior. Selecting auxiliary tasks so that these averages agree, which we call prior-posterior matching, leaves the estimated intent unchanged even though the harmful target remains in the bundle. We study two settings that differ in whether query construction is part of the optimization. In the query-independent setting, tasks are selected without regard to how they will be expressed in the final query. We show that exact prior-posterior matching under a bundle-size constraint is computationally hard, derive an optimal water-filling solution for fractional weights, and characterize the smallest bundle satisfying a prescribed safety threshold. In the query-dependent setting, task selection and query construction are considered jointly, and intent concealment and target preservation are evaluated on the resulting query. We evaluate jailbreak effectiveness and preservation of the target behavior across bundle sizes, query generators, and several open-source models. These results show that compositional queries can elicit target behaviors beyond the direct-request baseline under the evaluated search budgets, while revealing a trade-off: as bundle size increases, response-level target preservation tends to decrease for several models.
Read the full abstract ▾
Cryptography and Security · Cross-listed from cs.LG
From Mathematical to Executable Certificates for Machine Unlearning
Ziyu Zhao, Xinyu Wang, Xiaowen Chang et al. (+1 more)
Machine unlearning is needed when data must be removed because of deletion requests, outdated records, or data-quality concerns, while retraining from scratch can be costly. Certified machine unlearning methods provide mathematical guarantees, while deployed systems release concrete finite-precision artifacts produced by software. To bridge the gap between mathematical guarantees and practical deployment, we introduce Executable Release Certification (ExecCert), a release-time layer that certifies the candidate artifact considered for release. ExecCert either closes a method's native certificate for the executed candidate or applies Retraining-Reference Release Verification (RRV) to certify fidelity to current retain-set retraining. Sequential deletion makes the latter nontrivial because the exact retain-set reference and the stored numerical state evolve separately. For frozen representations with a mutable ridge head, we develop an incremental realization of RRV that maintains certified evidence across deletion requests rather than reconstructing it at each release. On four published unlearning implementations, ExecCert preserves valid certificates, changes release decisions, tightens conservative bounds, and identifies the retraining-reference fidelity supported by concrete outputs. In sequential-service experiments, RRV eliminates false releases caused by stored-equation verification while closely tracking realized error, and incremental certification remains cheaper than both fresh and maintained verified-factor alternatives once release checks become sufficiently frequent.
Read the full abstract ▾
All authors Ziyu Zhao, Xinyu Wang, Xiaowen Chang, Yixuan He
Cryptography and Security · Cross-listed from cs.AI
Fast Models, Slow Evidence: A Paired and Self-Audited Evaluation of System-1 Decision Models for LLM Agent Harnesses
Jiawei Li
Agent harnesses make many small, typed decisions per task: which model to call, which tool to use, whether retrieved text is relevant, whether an input carries an injection. System-1 decision models answer such questions in a single forward pass with class probabilities, promising large cost and latency savings over LLM calls. We present a paired evaluation of an open-weight (Laya) and a hosted (Jev) System-1 model on 11
agent decision points built from 18 public sources: 7,283 base cases plus 6,640 robustness variants, with byte-identical inputs, paired tests, and cross-hardware and cross-day reproducibility checks. Jev is significantly more accurate on 9 of 11 decision points (+10.8 to +46.0 pp). Neither model beats chance on zero-shot model routing, and they tie on RAG relevance gating. Laya changes 30% of its answers when the option order is reversed and degrades sharply with many or similar candidates (31% at 50 nearest-neighbour tools, vs. 98% for Jev on items with a unique correct tool). We also audit our own pipeline. Three analysis errors and one design confound distorted headline deployment claims: an omitted pre-screen cost (reported 23.9% saving, actual 4.3%), gate accuracy reported as end-to-end quality (58% vs. 98%), in-sample thresholds (5% target, up to 17% held-out misses), and a "channel effect" on injection false positives that vanishes with channel-native content. Two other suspected confounds did not change the conclusions. All cases, raw outputs and analysis code are available at https://github.com/David-DL-Space/sys1-eval.
Read the full abstract ▾
Cryptography and Security · Cross-listed from cs.CL
KaliBench: A Fine-Grained Benchmark for Cybersecurity Tool Use on Kali Linux with Runtime-Free Verifiable Rewards
Pengfei Li, Naufal Suryanto, Sicheng Zhang et al. (+1 more)
LLMs are increasingly applied to cybersecurity workflows, where they are expected to translate analysts' intent into tool invocations. However, existing evaluations focus on knowledge-based assessments or end-to-end agentic tasks, and do not directly measure LLMs' ability to generate executable commands for real-world cybersecurity tools. This gap is critical because cybersecurity operations rely on strict command-line interfaces (CLIs), where minor syntax errors, incorrect flag–value bindings, or argument misordering can invalidate execution. We introduce KaliBench, a fine-grained
benchmark and
dataset for natural-
language–to–CLI translation on Kali Linux, comprising 8,504 query–command pairs spanning 1,642 tools across 23 capability dimensions and 5 security phases. KaliBench is constructed via a manuscript-grounded pipeline with deterministic canonicalization and alias-aware evaluation, enabling precise and reproducible assessment of tool selection and argument construction. To ensure both semantic correctness and practical executability, we develop a multi-stage verification pipeline that combines LLM-based validation, sandboxed terminal execution, and human-in-the-loop refinement. Building on these fine-grained, deterministic signals, KaliBench further enables runtime-free verifiable rewards for training. Across three evaluation modes and 24 configurations of general-purpose and security-focused open-weight models, no open-weight model exceeds 42% exact-command accuracy in the unrestricted setting, highlighting the difficulty of accurate CLI-based cybersecurity tool use without explicit tool hints. We further show that supervised fine-tuning and reinforcement learning with verifiable rewards derived from KaliBench significantly improve an 8B model and achieve performance comparable to a 685B MoE model.
Read the full abstract ▾
All authors Pengfei Li, Naufal Suryanto, Sicheng Zhang, Muzammal Naseer
Cryptography and Security · Cross-listed from quant-ph
Quantum Advantage for Two-Party Differential Privacy
Daniel Alabi and Emil T. Khabiboulline
We introduce information-theoretically private
quantum protocols for two-party Hamming distance when both parties must output the same estimate. Classically, for input length $n$, information-theoretic protocols require $\Omega(\sqrt{n})$ error under pure differential
privacy and $\Omega(\sqrt{n}/\log n)$ error under strong approximate differential
privacy, whereas computational security permits $O(1)$ error. In Klauck's honest, nonpreemptive, message-preserving model, we give an $O(n)$-communication
quantum protocol with pure $\varepsilon$
quantum differential
privacy (QDP) and expected error at most $\frac{2}{\sinh \varepsilon}+\gamma$, for every $\gamma>0$. For approximate $(\varepsilon, \delta)$ QDP, an exact hockey-stick divergence calculation yields strictly smaller error, while preserving the $O(1)$-versus-$\Omega(\sqrt{n}/\log n)$ separation for $\delta=o(1/n)$. Thus,
quantum communication achieves $O(1)$ information-theoretic error, matching the accuracy available classically only under computational assumptions. The main construction uses a guarded coherent round trip and an equal-Gram rigidity principle that prevents an honest player from retaining input-dependent complementary information. We separate this model from weaker prescribed-channel
privacy, which already admits an exact classical realization, and from fully retention-robust security, against which measurement-and-abort attacks remain possible. Therefore, we identify preservation of non-orthogonal
quantum messages as a resource for
privacy.
Read the full abstract ▾
Cryptography and Security · Cross-listed from quant-ph
Lower Bounds for Preprocessing Attacks on Quantum Cryptography
Fangqi Dong and Alex Lombardi
We prove near-optimal lower bounds for preprocessing attacks on
quantum cryptography in the random oracle model. Specifically, we show that a $T$-query adversary with $S$
qubits of non-uniform advice can recover a random key $k$ from the $n$-
qubit binary phase state $|\psi_k\rangle \propto \sum_{x} R(k,x) |x\rangle$ with probability at most $O(\frac{T^2 + \sqrt{ST}}{N})$ for $N=2^n$. In contrast, the best known bound for post-
quantum one-way functions is $O(\frac{T^2 + ST}{N})$, with a trivial attack at $S = N$. This demonstrates a new advantage of
quantum cryptography over classical cryptography: $n$
qubits of communication suffice for security against preprocessing attacks with space up to $N^2$ rather than $N$. Our methodology is simple: express the optimal preprocessing attack as the operator norm of a random
matrix, and bound this value in expectation over the random oracle via the trace-moment method. These trace moments have a natural interpretation using compressed oracles [Zhandry, Crypto 2019], which we then analyze. This can be viewed as a simplification and generalization of the approach of Liu [Eurocrypt 2023] for proving the security of post-
quantum cryptography against preprocessing attacks. We also prove the following results: (1) We tighten Liu's analysis of post-
quantum PRGs in QROM, achieving a distinguishing advantage bound of $O(\frac{T^2}N + \sqrt{\frac{ST}N})$. (2) For
unitary synthesis, we extend the one-query lower bound of Lombardi-Ma-Wright [STOC 2024] to hold against adversaries that can make one arbitrary function query along with polynomially many (adaptive) queries to the random oracle, either before or after the function query. This also interprets the original LMW24 result in terms of compressed oracles. (3) Finally, we prove a tight $O(\frac{\sqrt{S}}N)$ bound for the pseudorandomness of random binary phase states against space $S$ distinguishers.
Read the full abstract ▾