Efficient Scalable Oversight via Rewinding
Scalable oversight asks how a weak verifier can check the outputs of computations performed by more powerful AI systems.
#cs.CC
共收录 36 条相关情报。
← 返回所有主题Classical Verification of Quantum Computation Beyond the Polynomial Hierarchy
It is not known whether a classical polynomial-time verifier can verify arbitrary polynomial-time quantum computations w
Bounds on polynomial approximations of the discrete logarithm function
We revisit a classical result of Coppersmith and Shparlinski showing bounds on how well polynomials can approximate the
Concrete Functions in Private Simultaneous Quantum Messages: Quantum Advantages and Structural Limitations
Private simultaneous quantum messages (PSQM) provide a minimal model of noninteractive secure multiparty quantum computa
Black Hole Radiation Decoding in the Haar Random Oracle Model
We prove optimal query bounds for recovering a single qubit from black-hole radiation in the Haar random oracle model, w
Explicit Nonlinear Functions beyond the Fourier bound
We study the problem of constructing highly nonlinear vectorial maps $F: \mathbb F_2^n \to \mathbb F_2^m$. Concretely, w
Unitary complexity in polynomial space
We show that if quantum commitments exist, then either there is no polynomial-time solution to the unitary synthesis pro
Time-space lower bounds for breaking quantum cryptography
本论文研究量子密码学在随机预言机模型（ROM）下的时间-空间下界，属于可证明安全与量子复杂性交叉的理论工作。作者考虑如下设定：敌手在预处理阶段可获取 S 个量子比特的非均匀建议（advice），随后在随机预言机上进行 T 次查询，目标是从
Can AI Oversight Be Zero Knowledge?
本文研究一个交叉性问题: 当 AI 系统基于机密数据产生输出时(论文举的两个例子是: 依据医疗记录给出适岗/履职能力评估, 以及依据分子的秘密结构预测候选药物的性质), 我们既希望验证这些输出是否计算正确, 又不希望泄露底层敏感数据。已有的
Trapdoored Clifford Operators and Applications
随机 Clifford 算子在量子计算中用途极广：随机基准测试（randomized benchmarking）、经典影子（classical shadows）、量子认证等协议都依赖对 n 量子比特 Clifford 群上的均匀随机采样。但
Verifiable quantum advantage based on polynomials with planted structures
该论文研究的是量子优势（quantum advantage）理论中的一个核心开放问题：是否存在一类量子优势协议，其资源需求与随机电路采样（random circuit sampling, RCS）相当，同时又能仅凭量子计算输出的经典数据被经
Security Properties of Neural Networks as Decision Problems
该论文从计算复杂性角度重新审视已部署神经网络的安全认证问题。验证文献长期聚焦鲁棒性等少量性质，但作者指出实际部署中还存在一类未被系统分类的决策问题：模型是否携带训练阶段植入的后门、存储参数故障是否会把网络推入不安全状态、输出是否泄露输入中的
On quantum interactive proofs with a laconic prover
本文研究带简洁证明者（laconic prover）的两消息量子交互证明系统，即证明者单次回复长度被严格限制为 ℓ 比特时的可验证问题类。经典情形由 Goldreich、Vadhan 与 Wigderson（CC 2002）引入，刻画了证明
Collision Detection is Instance $\widetilde{O}$ptimal Under the Birthday Threshold
该论文研究一个源自密码学理论的基础问题：关于哈希函数的结构性知识，能否加速对它的黑盒碰撞检测？作者从「实例最优性」（instance optimality）这一超越最坏情况分析的极端标准切入。实例最优性要求存在单一算法，使其在每一个具体输入
Improved lower bounds for decomposable randomized encoding
该论文研究可分解随机编码（Decomposable Randomized Encoding, DRE）的规模下界问题。DRE 是一种密码学原语：给定函数 f，n 个参与方共享随机串，各自仅对自身输入做本地编码，最终编码集合只泄露 f(x1,
Tight Time-Space Lower Bounds for Collision Finding and Element Distinctness under Label Symmetry
该论文研究量子算法中「查询次数与内存（量子比特）之间的权衡」这一核心问题。经典背景下，对于均匀随机函数 f:[N]→[N]，BHT 算法用 O(N^{1/3}) 次查询加上一张 O(N^{1/3}) 规模的量子可访问经典表即可找到碰撞，而仅
A Note on Binary Quadratic Systems and their relation to complexity theory
本文研究二元域 F2 上多元二次方程系统（MQ 系统）的解计数及其与复杂度理论的关系。判定一个平方二次系统（方程数等于变量数）是否有解是经典的 NP 完全问题，其困难性是构造后量子密码方案的基石。令 MQ_0(n) 和 MQ_1(n) 分别
Distinctness threshold for pseudorandom unitaries
本文研究量子信息理论中两种伪随机性概念——统计伪随机性（以酉 t-design 为代表）与计算伪随机性（以伪随机酉 PRU 为代表）之间的关系。此前已知的 PRU 构造通常需要将统计随机化成分（如酉 2-design）与经典密码学原语结合，
Overcoming the Randomness-Utility Trade-off in Answering Differentially Private Linear Queries
差分隐私（Differential Privacy）为数据分析提供严格的隐私保证，但在回答大量线性查询时，必须在隐私预算、响应精度和随机位数之间权衡。经典机制（如 Hardt 与 Talwar 提出的 K-范数机制）虽能在给定隐私预算 ε
SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules
本文研究分圆环上的格问题计算复杂性。具体而言，作者证明了在二维全秩自由子模上，以 ℓ2-范数定义的判定型最短向量问题（SVP）是 NP-完全的。设 q 为模 4 余 3 的素数，ζ_q 为本原 q 次单位根，K=Q(ζ_q)，环 O_K=Z