给定一个小组$ G $，一个小组$ H \ leq G $，以及一个集合$ X $，我们说一个函数$ f：G \ Rightarrow X $分隔所有$ g $的coset，如果对于所有$ g_1，g_2 \ in G $，$ f（g_1）= f（g_2）$当且仅如果$ g_1H = g_2H $。
隐藏的子组问题：假设$ G $是一个组，$ X $是一个有限集，而$ f：G \ Rightarrow X $一个函数，使得存在一个子组$ H \ leq G $，其中$ f $分隔$ H $的子集。函数$ f $是通过oracle给出的。使用从$ f $的oracle评估中获得的信息，确定$ H $的生成集。
尽可能用英语，$ G $是一个组，这意味着它满足某些条件，例如在一个操作下有一个恒等式和逆元。在此，未指定操作。因此，我们有一些集合$ X $不一定要满足这些条件，还有$ f $一个将$ G $组映射到$ X $的函数。
陪同服装例如$ gH $是由特定$ g $操作的所有$ H $的集合，因此$ gH = {gh：h \ in H，g} $。 $ Hg $是另一种排序方式，之所以存在是因为组不需要是阿拉伯字母。
因此，如果将函数应用于组成员，则此拆分功能$ f $确保每个陪集被唯一映射它并得出相同的结果，当应用于相关的陪伴时，它也必须得出相同的结果。这样就可以确定，如果我正确理解的话，每个陪集实际上都映射到$ X $中的一组唯一元素。
因此，HSP本质上就是在给定$ G $的情况下查找$ H $的任务， $ f $和$ X $（如果我正确遵循的话）。
那么，撇开一个显而易见的单向问题“如果您知道$ H $”的问题，HSP将如何影响加密？具体来说，除了发现$ X $中的$ H $集之外，我还没有看到HSP的特殊直接用途，但是我在密码学的讨论中经常碰到它，尤其是对本文的奇怪链接或参考。最后，在HSP摘要中，除了密码学的影响之外，我是否还缺少其他任何内容？
#1 楼
据我了解，HSP是一个很难解决的问题：某些类型的HSP（即在阿贝尔群体中运行的HSP）可以（理论上）在量子上有效地求解。计算机（假设可以建造一个）；
许多类型的公钥密码系统可以简化为HSP：如果可以解决HSP，则可以破解密钥。
尤其是整数因式分解和离散对数（在任何包含椭圆曲线的阿贝尔群中）可以简化为HSP，而不是阿贝尔群，因此在量子计算机上很容易被破坏。这并不是真正的新事物：Shor的算法已经做到了。恰巧Shor的算法是HSP的特例。
有趣的是，可以在非阿贝尔群上将晶格约简还原为HSP，对此尚无有效的算法。因此，这种形式主义实际上是在说明为什么基于格的算法可以在后量子世界中生存的原因。
在您对HSP的总结中，可能会添加两个细节：“查找
H”的真正含义是“查找” G的一组元素生成H“（即H是G的最小子组，其中包含所有这些元素）；并且：“ given f”的意思是“给出了实现f的黑匣子，并且可以在任何输入上重复调用它。” #2 楼
在密码学中，您不仅在乎一些问题很难解决，而且还容易产生困难的实例。例如，为什么人们不使用NP完全问题进行加密？ NP完全问题从渐近地说有两个原因，可以为您带来更大的信心：如果任何NP完全问题被分解为P，那么因式分解也变为P。因子分解是量子多项式时间（BQP），但是BQP和NP之间的关系未知。相反，存在一个更加隐蔽的问题，即许多NP完全问题具有太多的简单案例，无法快速找到困难的实例。
隐藏子组问题也有许多简单的情况。实际上，有一些有趣的算法可用于识别非阿贝尔有限组，这些算法可以通过求解有限子组的分类来解决存在多项式时间解的隐藏子组问题。
#3 楼
隐藏的分组问题对于理解基于配对的非交互式零知识证明非常有用。为了安全地使用隐藏的子组问题，您将需要一条合适的大组合阶椭圆曲线，因此在实践中，由于实现速度非常慢，您可能不会打扰。但是，使用HSP进行的解释和数学相对可以理解，因此对于教学目的很有用。请参阅Jens Groth的演讲http://research.microsoft.com/apps/video/default.aspx?id=103365
评论
我们可以说HSP是此处介绍的决策版本子组问题：goo.gl/wOiCzR（BGN密码系统）@curious如果这是一个问题，请随意填写并提出问题:)您只需要点击“问问题”按钮。如果是答案，我想听听更多，请在下面随时回答。甚至Q与可接受的答案也可以改善。