该论文研究了随机线性码在广泛参数范围内的 discrepancy 性质,证明其几乎具备最优的 discrepancy 性能。作者提出了两个一般性定理:一个控制固定测试集的所有平移,另一个控制大片傅里叶伪随机测试集。作为应用,首先,在容量之上的列表译码场景中,随机线性码与非结构化随机码性能相当:对于有限域上的随机线性码,以高概率同时满足所有汉明球的交集大小与期望值相差很小,这扩展了 Blinovsky (1987) 关于覆盖半径的经典结果。其次,在素数域上,随机线性码在容量之上的零错误列表恢复中匹配非结构化随机码:以高概率同时满足所有矩形(每个坐标大小为 ℓ)的交集大小与期望值接近。由此推论,存在丰富的 n 方线性斜坡秘密共享方案,其隐私阈值约为 n/(2 log q),重建阈值约为 5n/(2 log q),且能抵御平衡局部泄漏;此前即使在该场景下,存在性结果也要求阈值高于 n/2。平移结果(因此列表译码应用)适用于任意有限域(甚至随 n 增长),而列表恢复和泄漏应用要求素数域在适度增长下成立(如 q ≤ n^{1/5-o(1)})。证明采用改进的二阶矩分析,跟踪添加随机生成元时交集大小的变化。本文适合密码学、编码理论及信息论安全领域的研究者阅读。
💡 推荐理由: 随机线性码在秘密共享中的泄漏弹性突破了传统阈值限制,为设计高鲁棒性、隐私保护的密码协议提供了理论基础,对安全存储和多方计算有实际意义。
🎯 建议动作: 研究跟进