论文标题
关于加密小组动作中问题的硬度的注释
A Note on the Hardness of Problems from Cryptographic Group Actions
论文作者
论文摘要
给定密码组的动作，我们表明，除非多项式层次结构崩溃，否则组动作逆问题（GAIP）和其他相关问题不能是NP-HARD。我们通过随机自我还原和互动证明的设计来显示这一点。由于加密组动作是许多安全协议的基础，因此该结果既是某些加密假设的最差复杂性的上限，又是证明最坏情况和平均情况中的硬度的证据。我们还指出了与图形同构和其他相关NP中间问题的链接。
Given a cryptographic group action, we show that the Group Action Inverse Problem (GAIP) and other related problems cannot be NP-hard unless the Polynomial Hierarchy collapses. We show this via random self-reductions and the design of interactive proofs. Since cryptographic group actions are the building block of many security protocols, this result serves both as an upper bound on the worst-case complexity of some cryptographic assumptions and as proof that the hardness in the worst and in the average case coincide. We also point out the link with Graph Isomorphism and other related NP intermediate problems.
