题目：基于非完美随机源的密码学原语的安全性研究

    密码学是信息安全的核心。密码学原语包括：哈希函数、消息认证码、签名方案、抽取器、加密方案、承诺、秘密分享、差分隐私、密钥生成函数、伪随机数生成器等。传统的密码学原语理想地假设秘密服从均匀随机分布。然而，在现实世界中往往并非如此。例如，若秘密源为生物数据、物理源、部分泄露的秘密等时，相应的分布并不服从均匀分布。这样的一些分布构成的集合称为“非完美随机源”。
    因此，我们面临的一个根本性的问题是：基于非完美随机源的密码学原语是否仍然具有安全性？从该问题出发，本文对此展开了系统而深入的研究。本文的主要研究工作和创新点如下：

    （一）引入了一个直观的、模块化的和统一的研究框架，研究了基于一般的非完美随机源的传统隐私（包括抽取器、加密、承诺、秘密分享方案）和差分隐私的（不）可能性结果。
    本文定义了源（source）的可表达性（expressiveness）和可分离性（separability）的概念，并得到如下结果：(a) 强的传统隐私和差分隐私的不可能性结果可归约为某种程度的可表达性； (b) 可表达性可归约为可分离性；不可分离性与“弱位抽取” 等价；(c) 尽管一些具体的源（例如 Santha-Vazirani（SV）源）的可分离性已隐含在某些文献中，本文得到了几种重要的源（包括一般的“块源”）的新的可分离性。从而导出了基于更广泛的源的传统隐私的（改进的）不可能性结果，以及第一个基于切合实际的源（包括多数“块源”，而非 SV 源）的差分隐私的不可能性结果。由此得出的一个推论是: 任何允许（传统或差分）隐私的非完美随机源均可得到某种确定性的位抽取。

    （二）构造了基于偏差-控制受限（Bias-Control Limited, 简记为 BCL）源的差分隐私机制，并研究了该机制的差分隐私性和效用性。
    本文引入一个新的性质，称为紧致的 BCL-一致采样（consistent sampling），并证明了：若基于 BCL 源的机制满足该性质，则该机制具有差分隐私性。即使 BCL 源退化为 Santha-Vazirani 源时，本文的证明也比 Dodis 等人（CRYPTO’12）的证明更为直观和简单。进一步，本文利用一种新的截断技术和算术编码，构造了一种具体的差分隐私机制，并分析了该机制的差分隐私性和效用性。

    （三）研究了基于弱随机密钥的 Rényi 熵和扩展的计算熵的密码学原语的安全性问题。
    密码学原语的安全性用某个函数的期望来衡量，在理想世界中称为完美期望，在现实世界中称为弱期望。本文以 Hölder 不等式作为基本工具，得到以下结论：当 Rényi 熵或扩展的计算熵的熵缺损（弱随机密钥的位长与熵之差）足够小时，弱期望比完美期望差不了多少。本文还利用 Rényi 熵来扩展密钥生成函数，并研究了当考虑密钥生成函数时，上述结论如何应用于具体的密码学原语。 

    （四）对 Raz 引入的抽取器的误差估计进行了改进，在此基础上给出了种子更短的非延展抽取器 (Non-Malleable Extractor) 及其应用。
    本文基于 Cohen 等人（CCC’12）的方法，构造了(1016,1/2)−安全的非延展抽取器 nmExt : {0, 1}1024 × {0, 1}d → {0, 1}，其中秘密的熵为 1016，种子长度为 d = 19。而根据 Cohen 等人的结论：种子长度大于等于 46/63 + 66。本文还对 Cohen 等人给出的一般的构造方法中的参数进行了改进，并对参数的限制条件进行了简化。本文还研究了其在非延展编码和隐私放大协议中的应用。