推荐 3.6
Conf: 50%
本文继续研究一类称为“快速函数”的线性大小电路可计算的函数,这些函数共享随机函数的有用性质,但更具确定性,适合密码学应用。作者在两个主要方向上进行了推广和改进: 1. 构造了任意常数 t 的快速 t-独立哈希函数,其代数次数为 log2 t(在 F2 上),同时在渐近电路大小和次数上达到最优。这优于之前的工作,降低了电路深度,同时保持线性大小。 2. 简化并改进了 ITCS 2026 中关于快速码及其快速对偶的构造,使其满足 Gilbert-Varshamov 界,且失败概率可忽略,支持一般域和码率、系统编码以及快速通用编码器。此外,还强化了组合列表解码等更强随机性质,通过构造快速线性函数族实现:对于任意常数 t,任意 t 个线性无关的输入映射为均匀且统计独立的输出,此前仅对 t=1 已知。 作者展示了这些结果在密码学中的应用,包括:第一个在完美安全多方计算中电路复杂度与参与方数量线性缩放的非平凡协议,以及计算加密矩阵-向量乘积的最优渐近电路复杂度的协议。 本文适合密码学理论研究者、安全多方计算协议设计者以及对伪随机函数和编码理论感兴趣的学者阅读。
💡 推荐理由: 本文首次同时优化了快速有界独立函数的电路大小和代数次数,并构造了更加实用且适用范围更广的快速码族,为密码学中高效、安全的多方计算和加密计算提供了理论支撑,有望推动相关协议的实际部署。
🎯 建议动作: 研究跟进
排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.6)