本论文从密码学实践视角出发，系统性地研究了短描述（如密钥、证书）的“可验证复杂性”问题。在密码协议中，密钥或证书通常要求能够在有限时间（多项式时间）内完成展开或验证，否则一个紧凑表示即使理论上存在，也无法在实际有界时间协议中提供操作保障。作者形式化定义了“见证复杂性”（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为研究伪随机酉矩阵提供了一个富有成果的理想化模型。本文的研究对量子密码学基础、随机性生成和量子复杂性理论具有重要理论意义。