SHF: Small: A New Approach for Hardware Design of High-Precision Discrete Gaussian Sampling

新的密码系统可以提高日常应用的安全水平和隐私保证。然而，这些系统通常需要以前不存在的新构建块。高斯分布的高精度采样是一个耗时且关键的组成部分，必须通过定制的硬件解决方案有效地实现。必须保证得到的解决方案的统计准确性符合加密安全要求。此外，开发的解决方案必须足够灵活，以支持多种当前和潜在的未来应用。现有的硬件设计无法满足这些条件。本项目将通过硬件设计、算法、统计和密码学的交叉方法来解决这个问题。成功完成拟议的活动将是迈向可证明安全采样器设计的自动化解决方案的重要一步。该项目将与其他几所大学合作，帮助硬件安全领域的劳动力发展。该项目的成果将公开，并有可能提供给其他机构，例如NIST。在这个项目中，将开发新的采样器硬件设计，以支持基于格子的密码系统，如后量子密码和同态加密应用。尽管在密码学和其他应用中对均匀分布的采样进行了深入的研究，但对非均匀分布（如高斯分布）的采样的研究却少得多，高斯分布是基于格的密码系统所特有的。为此，该项目将首先探索新的算法方法，以简化高斯抽样技术中使用的随机搜索过程。然后，该项目将探索优化搜索的近似技术，同时尽量减少对统计偏差的影响。此外，该项目将寻求完整的设计自动化解决方案，可以为给定的参数集创建优化的采样硬件。生成的解决方案将被映射到可重构硬件，并与早期的建议进行基准测试，以比较开销和节省。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

New cryptographic systems can improve the security level and privacy assurance of everyday applications. These systems, however, often require new building blocks that did not exist earlier. High-precision sampling from Gaussian distributions is one such time-consuming and critical building block that has to be implemented efficiently with customized hardware solutions. The statistical accuracy of the resulting solutions must be guaranteed to abide by cryptographic security requirements. Moreover, the developed solutions must be flexible enough to support multiple current and potential future applications. Existing hardware designs cannot meet these conditions. This project will address this problem by a cross-cutting approach on hardware design, algorithms, statistics, and cryptography. Successful completion of the proposed activity will be a significant step towards automated solutions for provably-secure sampler designs. The project will help workforce development in the area of hardware security in collaboration with several other universities. The results of the project will be made open-source and will potentially be made available to other agencies, e.g., NIST.In this project, new sampler hardware designs will be developed to support lattice-based cryptographic systems such as those in post-quantum cryptography and homomorphic-encryption applications. Although sampling from uniform distributions has been thoroughly studied in the context of cryptography and other applications, there are significantly fewer works on sampling from non-uniform distributions such as the Gaussian distribution, which is unique to lattice-based cryptosystems. To that end, the project will first explore novel algorithmic approaches that simplify the random-search process used in Gaussian-sampling techniques. The project will then explore the approximation techniques that optimize the search while minimizing the impact on statistical deviations. Furthermore, the project will seek full design-automation solutions that can create optimized sampling hardware for a given set of parameters. The resulting solutions will be mapped to reconfigurable hardware and benchmarked against earlier proposals to compare the overheads and savings.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.