#tensor

共收录 1 条相关安全情报。

← 返回所有主题
👥 作者: Yuxuan Liu, Youming Qiao, Gang Tang, Chuanqi Zhang

本文受随机图上经典的植入团(planted clique)问题启发,把这一平均情形复杂性范式推广到有限域上的张量,提出「植入式完全迷向空间问题」(planted totally-isotropic space problem)。设定如下:令 U ≅ F_q^n 与 W ≅ F_q^m 为有限域 F_q 上的有限维向量空间,给定 d ∈ N,先随机选取一个 d 维子空间 V ≤ U,再构造一个随机交错双线性映射 φ: U×U → W,并施加约束 φ(V,V)=0,即 V 是 φ 的一个完全迷向空间;算法的目标是恢复这个被隐藏的 V。作者基于 Pham–Qiao–Wigderson–Wigderson 关于随机张量的概率分析工作(进行中),首次系统研究该问题的算法硬度。主要结果包括:当取 m = ⌈n/log n⌉ 时,若 d ≥ n/2,该问题存在平均情形多项式时间算法,其关键在于借助非交换秩问题(non-commutative rank problem)的近期进展;同时作者还给出一个时间复杂度为 q^{O(n log n)} 的通用算法。除理论分析外,作者使用多项式方程组求解(polynomial-system solving)方法开展了算法实验,据此提出猜想:当 d = ⌈n/C⌉、常数 C ≥ 3 时,植入式完全迷向空间问题是(指数级)计算困难的。基于该计算硬度证据,作者进一步探索了植入张量问题及相关植入张量问题的密码学应用,仿照 Abram–Beimel–Ishai–Kushilevitz–Narayanan(TCC'23)基于植入子图的构造,给出了基于植入张量问题的私有同时消息(PSM)协议与秘密分享协议。在相同安全级别下,基于植入子图的协议其公共信息规模比基于植入张量的协议(中等程度地)指数级更大,而两类协议的通信开销只相差多项式因子。

💡 推荐理由: 该工作提出一种新的平均情形计算困难假设,并据此构造 PSM 与秘密分享协议,公共信息规模显著优于同类植入子图方案。对密码协议设计与新硬度假设的可用性评估有参考价值。

🎯 建议动作: 研究跟进

排序因子: 来自 arXiv 其他板块 (+2) | Community 数据源 (+1) | LLM 评分加成 (+0.4)