General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
General Linear Group Action on Tensors: A Candidate for Post-Quantum Cryptography
复制标题
张量上的一般线性群作用：后量子密码学的候选者
DOI：
10.1007/978-3-030-36030-6_11
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Yun, A.
中科院分区：
文献类型：
--
作者：
Ji, Z.;Qiao, Y.;Song, F.;Yun, A.
从 Brassard 和 Yung (Crypto’90) 的单向群体行为框架开始，我们重新审视基于群体行为构建密码学。由于经典算法（例如图同构）和量子算法（例如离散对数）的进步，以前的单向群动作的几个候选者不再成立。我们提出张量上的一般线性群动作作为基于群动作构建密码学的新候选者。最近的工作（Futorny–Grochow–SergeichukLin. Alg. Appl.，2019）表明，底层算法问题，即张量同构问题，是编码理论、计算群论和多元密码学等领域产生的几个同构测试问题中最难的一个。我们通过对最先进的启发式算法、理论算法、硬度结果以及量子算法的综合研究，提出了证明该提案可行性的证据。然后，我们引入了一种称为伪随机群动作的新概念，以进一步开发基于群动作的密码学。简而言之，给定一个群体作用于集合S，我们假设很难区分（s，t）的两个分布，要么是均匀选择的，要么是随机选择的，并且是应用随机群体作用的结果。当专门针对特定的群体行动时，这包含了经典的决策 Diffie-Hellman 假设。我们仔细分析了支持通过张量上的一般线性群作用实例化该假设的各种攻击策略。最后，我们构造了几个密码原语，例如数字签名和伪随机函数。我们基于单向群行为假设和伪随机群行为假设给出了量子安全证明。
Starting from the one-way group action framework of Brassard and Yung (Crypto’90), we revisit building cryptography based on group actions. Several previous candidates for one-way group actions no longer stand, due to progress both on classical algorithms (e.g., graph isomorphism) and quantum algorithms (e.g., discrete logarithm).We propose thegeneral linear group action on tensorsas a new candidate to build cryptography based on group actions. Recent works (Futorny–Grochow–SergeichukLin. Alg. Appl., 2019) suggest that the underlying algorithmic problem, thetensor isomorphism problem, is the hardest one among several isomorphism testing problems arising from areas including coding theory, computational group theory, and multivariate cryptography. We present evidence to justify the viability of this proposal from comprehensive study of the state-of-art heuristic algorithms, theoretical algorithms, hardness results, as well as quantum algorithms.We then introduce a new notion calledpseudorandom group actionsto further develop group-action based cryptography. Briefly speaking, given a groupGacting on a setS, we assume that it is hard to distinguish two distributions of (s,t) either uniformly chosen from, or wheresis randomly chosen fromSandtis the result of applying a random group action ofons. This subsumes the classical Decisional Diffie-Hellman assumption when specialized to a particular group action. We carefully analyze various attack strategies that support instantiating this assumption by the general linear group action on tensors.Finally, we construct several cryptographic primitives such as digital signatures and pseudorandom functions. We give quantum security proofs based on the one-way group action assumption and the pseudorandom group action assumption.
登录
查看更多内容
三次形式和张量作用的不变量度数的指数下界
影响因子：
1.7
作者：
Derksen, Harm;Makam, Visu
通讯作者：
Makam, Visu
DOI：
10.1007/978-3-540-74456-6_31
发表时间：
2007
期刊：
International Symposium on Mathematical Foundations of Computer Science
影响因子：
--
作者：
R. Hartung;C. Schnorr
通讯作者：
C. Schnorr
矩阵不变量和半不变量的轨道闭合分离算法
影响因子：
1.3
作者：
Derksen, Harm;Makam, Visu
通讯作者：
Makam, Visu
基于恒定查询弱 PRF 的 PRF：最小化高效对称密码学的假设
DOI：
--
发表时间：
2008
期刊：
International Conference on the Theory and Application of Cryptology and Information Security
影响因子：
--
作者：
U. Maurer;Stefano Tessaro
通讯作者：
Stefano Tessaro
DOI：
10.1007/978-3-030-26951-7_27
发表时间：
2019-08
期刊：
--
影响因子：
--
作者：
James Bartusek;Fermi Ma;Mark Zhandry
通讯作者：
James Bartusek;Fermi Ma;Mark Zhandry