该论文研究量子算法中「查询次数与内存（量子比特）之间的权衡」这一核心问题。经典背景下，对于均匀随机函数 f:[N]→[N]，BHT 算法用 O(N^{1/3}) 次查询加上一张 O(N^{1/3}) 规模的量子可访问经典表即可找到碰撞，而仅用对数空间的 Grover 搜索需要 O(√N) 次查询。介于这两个极端之间的最优查询—空间权衡长期是公开难题。作者在「标签对称算法」这一受限但自然的类中彻底解决了该问题：所谓标签对称，是指算法把函数 f 的输出标签视为可互换。作者证明，任何做出 T 次查询、使用 S 个量子比特、以常数概率在均匀随机函数上找到碰撞的标签对称算法，必须满足 T=Ω(N^{1/3}) 且 T²S=Ω(N log N)。当 M=N 时，这两个下界被一种空间高效的 BHT 实现所达到，因此在该算法类中是最优的。作为副产物，作者导出 Element Distinctness（元素唯一性判定）搜索版本的对应权衡：对 f:[n]→[n²]，任何标签对称算法必须满足 T=Ω(n^{2/3}) 且 T²S=Ω(n² log n)，与 Ambainis 量子游走算法的上界吻合，同样达到最优。技术路线上，作者发展了「空间敏感的压缩预言机（compressed oracle）」技术：压缩预言机以不断演化的数据库叠加态记录算法已学到的信息；借助标签对称性与表示论，作者证明使用 S 个量子比特的算法实际上只能有效保留约 O(S/log N) 条无碰撞数据库条目的信息，将该估计代入压缩预言机论证即得到上述权衡。该结果属于量子查询复杂度与时空下界的理论研究，作者未涉及任何具体密码系统的攻击实现或实验评估。

本文研究二元域 F2 上多元二次方程系统（MQ 系统）的解计数及其与复杂度理论的关系。判定一个平方二次系统（方程数等于变量数）是否有解是经典的 NP 完全问题，其困难性是构造后量子密码方案的基石。令 MQ_0(n) 和 MQ_1(n) 分别表示 n 个变量、n 个方程且无解或恰有一解的平方二次系统集合。已知这两个集合对应语言的复杂性不同，且当 n 趋于无穷大时，二者规模之比趋近于 1。本文给出了这一极限现象的显式有限 n 界：对于所有 n，有 |MQ_0(n)| < |MQ_1(n)| ≤ (1 + 1/(2^n - 1)) |MQ_0(n)|。更一般地，考虑所有次数不超过 d 的 n 元多项式函数构成的空间 Q_d，平方系统由 Q_d^n 中的 n 个函数构成。定义 α_k 为恰好有 k 个平方根的此类系统数量，则对于任意 2 ≤ d ≤ n，同样成立 α_0 < α_1 ≤ (1 + 1/(2^n - 1)) α_0。证明方法融合了拟阵论与编码理论：将 (F2)^n 视为 Q_d 的评价拟阵的底层集，α_0 和 α_1 可表示为拟阵的特征多项式；随后利用 Whitney 型反号对合证明，α_1 - α_0 若低于 α_1/2^n，则唯一导致偏差的项来自拟阵的端口（port）元素。这些元素可识别为 Reed-Muller 码 RM(n-d-1,n)=RM(d,n)^⊥ 中的最小支撑权字。最终估计依赖于 MacWilliams 恒等式、码的最小距离界 2^{d+1} 以及偶权重结构。该结果严格证明了 MQ_1 系统的数量始终略多于 MQ_0 系统，但差距不超过一个指数小的因子，这对深入理解 MQ 问题在密码学中的困难性具有重要意义，也为拟阵与编码理论的交叉应用提供了一个新的范例。

本文研究量子信息理论中两种伪随机性概念——统计伪随机性（以酉 t-design 为代表）与计算伪随机性（以伪随机酉 PRU 为代表）之间的关系。此前已知的 PRU 构造通常需要将统计随机化成分（如酉 2-design）与经典密码学原语结合，以产生计算伪随机性，这暗示统计随机性可能是计算随机性的必要前提。本文的主要贡献是证明统计伪随机性并非计算伪随机酉的必要条件：作者将现有构造中的酉 2-design 层替换为甚至不构成状态 1-design 的系综，但要求其满足一种称为“区分性”（distinctness）的性质，并证明该性质是任何 PRU 必须具备的。他们通过纠缠版本的“反集中”（anticoncentration）来刻画区分性，并证明区分性已经捕获了 PRU 在相干性和虚实性（imaginarity）上的约束；同时识别出某些输入类别（包括某些最大纠缠态）会使虚实性障碍消失，从而允许实数值 PRU 存在。作为应用，作者利用区分性缺失来约束随机相位-Hadamard 系综被猜想为 PRU 的可能性。该工作深化了对量子伪随机性基本结构的理解，并为构造更轻量级 PRU 提供了新途径。适合量子信息理论、量子密码学和复杂性理论研究者阅读。

本文提出了一种基于复杂性理论构建空间证明（Proof of Space, PoS）的新框架。空间证明由Dziembowski等人于CRYPTO 2015引入，是一个两阶段协议，允许证明者向高效的验证者证明其已分配大量持久性内存来存储某些信息。现有所有PoS协议的安全性通常仅在随机预言机模型或特定临时密码学假设下得到证明。本文旨在减少对随机预言机的依赖，通过结合去随机化假设与密码学假设来构建PoS。作者给出了一个基础性框架，并提供了几个简单实例化。主要结果显示：在假设(a) E=DTIME[2^{O(n)}]对指数规模非确定性电路困难（该假设此前用于证明AM=NP），以及(b)存在抗碰撞哈希函数的条件下，可以构造非平凡的空间证明。此外，若进一步假设(c)存在针对P的SNARG（简洁非交互式论证），则可构造具有近乎最优参数和交互模式的空间证明。该工作将空间证明的安全性基础从随机预言机模型拓展到更广泛的复杂性理论假设，属于理论计算机科学与密码学交叉领域的贡献。适合对密码学基础、去随机化理论以及区块链中资源证明机制感兴趣的研究人员阅读。

本论文从密码学实践视角出发，系统性地研究了短描述（如密钥、证书）的“可验证复杂性”问题。在密码协议中，密钥或证书通常要求能够在有限时间（多项式时间）内完成展开或验证，否则一个紧凑表示即使理论上存在，也无法在实际有界时间协议中提供操作保障。作者形式化定义了“见证复杂性”（witness complexity）γ(x)，即字符串在通用图灵机上几乎所有最短描述的最小运行时间。γ(x)与香农熵和Kolmogorov复杂度KC有本质区别：低KC未必意味着低γ；可能存在KC很低但γ很高的字符串（例如需要超多项式时间才能展开的描述）。论文证明了γ(x)在多项式因子下具有不变性；并且基于P≠NP假设，给出了条件分离结果；同时利用KC的不可计算性得到了无条件下界。进一步，通过对类相关变体γ_P的表征，证明了γ(x)完全刻画了P与NP的关系（即P=NP当且仅当γ_P可多项式时间计算）。对于结构化的NP族，论文展示了多项式时间可计算性。第二部分发展了伴随度量，并证明了文法大小与推导代价之间的无条件差距，从而将γ(x定位为衡量密钥和证书实用性的关键指标。该工作为密码学中“短但不可用”的描述提供了理论工具，有助于理解哪些紧凑表示能在有界时间内可靠使用。

本文提出对Impagliazzo五世界理论的一种密码学扩展。Impagliazzo的五世界框架沿着单一轴（即密码原语的存在性）对计算假设进行分类，且所有世界都隐含一个默认假设：包括敌手在内的每一方都观测完整的输入，即观测者始终处于最高层级（O_top）。这一假设过于自然以至于从未被明确陈述。本文首次将其显式化，并通过引入第二个正交轴——观测轴（基于先前工作提出的观测者层级）来放松该假设。放松假设后揭示了结构现象，例如在五世界框架中无法表达的崩溃关系：P^{O_prof} = NP^{O_prof} ⊂ P。本文证明该崩溃关系在所有五个世界中无条件成立，表明观测盲性与计算困难性是独立的。进一步，定义了观者世界W_O，对所有世界-观测者对进行分类，识别出标记单元格(a)-(d)，并引入参数化族W_O^ε以建模观测不变量的部分违反。该框架还与物理信息限制（包括热力学、量子及宇宙学边界）形成接口。该研究适合对计算复杂性理论、密码学基础及计算假设分类感兴趣的读者。

本文研究可扩展伪随机酉矩阵（PRU）的构造问题，即安全性参数可独立于维度（或输入比特长度）变化的PRU族。目前尚不清楚是否存在这样的构造。作者证明，如果通过当前主流范式（随机预言机模型）可以构造可扩展PRU，那么Aaronson-Kuperberg酉合成问题——量子复杂性理论中一个关于实现任意酉矩阵是否能有效简化为计算布尔函数的长期未决问题——将有肯定解。具体地，作者形式化了ROM-PRU的概念，即在随机预言机模型中统计安全的PRU。所有已知的密码学安全PRU构造都基于ROM-PRU。作者建立了ROM-PRU、近似酉设计、酉群上的ε-网以及酉合成问题之间的新联系。特别地，他们证明任何酉合成算法（因此任何ROM-PRU）必须使用输入长度为(2 - o(1)) log d比特的经典预言机，其中d是要实现的酉矩阵的维度。这一下界排除了文献中所有现有的可扩展PRU候选方案。这些联系表明ROM-PRU为研究伪随机酉矩阵提供了一个富有成果的理想化模型。本文的研究对量子密码学基础、随机性生成和量子复杂性理论具有重要理论意义。