格上的伪随机函数新构造：基于短整数解问题

"这篇论文基于短整数解问题(SIS)在格理论的基础上提出了两种新的伪随机函数构造方法。这两种构造分别具有并行化和低公钥尺寸的特点，且都具有小模数，并且在安全性方面是可证明的。与之前A Banerjer，C Peikert和A Rosen在EUROCRYPT 2012提出的方案相比，新方法的密钥量更小，同时通过避免使用凑整技术，提高了伪随机函数的生成效率。关键词包括伪随机函数、格理论、短整数解问题和混合论证。" 在密码学中，伪随机函数(PRF)扮演着至关重要的角色，因为它们是构建加密算法和安全协议的基础。PRF应该在数学上难以区分于真正的随机函数，以确保其在安全性上的可靠性。这篇论文关注的是在格理论背景下构造PRF，这是一个在密码学中越来越受到重视的领域，因为格问题被认为是难解的，适合用于安全基础。 短整数解问题(SIS)是格理论中的一个重要难题，它要求找到一个向量集，使得集合内所有向量的欧几里得范数最小，而这些向量的坐标都是小整数。该问题的困难性被用来作为构造密码体制的硬度假设。 论文中提出的第一个PRF构造利用了树状伪随机综合器的思想，这允许函数的并行计算，从而提高效率。并行化在现代计算环境中尤为重要，因为它可以充分利用多核处理器的能力，降低计算时间。 第二个构造虽然采用串行方式，但它优化了公钥的大小，这对于存储和传输公钥来说是个显著的优点，尤其是在资源受限的环境中。小模数的特性则意味着计算过程中涉及到的数值范围较小，可能有助于减少计算复杂性和提高效率。 论文还指出，新提出的PRF方案相比于2012年EUROCRYPT会议上A Banerjer等人的工作，具有更少的密钥量。减少密钥量不仅可以降低存储需求，还可以减少密钥管理的复杂性，这是密码系统设计中的一个重要考虑因素。此外，新方法避免了凑整技术，这通常会引入额外的计算开销，因此提高了函数生成的速度。 混合论证可能是指论文中结合了不同的理论和方法来证明这些新PRF的安全性。这样的方法通常需要深入的理论分析和数学证明，以确保在实际应用中的安全性。 这篇研究为密码学领域提供了一种新的、基于格的伪随机函数构造，这些函数在安全性、效率和资源需求方面都有所改进，对于密码学研究和应用具有重要意义。