让$ K $作为密钥生成算法。给定以一元表示的安全参数，$ 1 ^ k $，$ K（1 ^ k）$将输出密钥对$（pk; sk）$，分别称为公钥和私钥（或私钥）。
我的问题是：当我想实现密码系统时，我应该如何表示这个$ 1 ^ k $？当我实现密钥生成过程时，是否真的要求调用者向我传递一个字符串$ k $一位该过程将永远不会使用的位？而且，如果是这样，为什么会首先出现呢？
#1 楼
$ 1 ^ k $是一种形式主义，只会使理论家感到高兴。您可以放心地忽略它。在实际实施密码系统时，不要尝试传递字符串$ 1 ^ k $;。相反，您传递了安全参数$ k $（表示密钥生成算法需要多少加密强度）。我希望可以保留它，因为这没什么大不了的：这只是愚蠢的事情，在任何基本的概念意义上都不重要。但是在这一点上，您可能会说“嗯？”，所以我想我必须解释一下。
为什么会出现？出于完全愚蠢的原因。其唯一目的是帮助提醒理论家，密钥生成应高效：其运行时间应为安全性参数中的多项式。
更详细地说，我们希望密码系统的安全性是可参数化的（完全到目前为止）：例如，如果您想要80位安全性，则应该可以选择参数$ k = 80 $并获得相应的安全性。理论家还希望强加所有加密操作都非常有效（仍然相当合理）的要求：增加安全性参数不会使加密速度减慢太多。一些理论家在以渐进复杂性来衡量绩效的情况下工作（在实践中有些不合理，但我们可以放任不管，因为它仍然有用且可以理解）。因此，他们通过要求所有加密操作（密钥生成，加密，解密）的渐近运行时间在安全性参数中为多项式，从而使加密操作高效的要求正式化。
到目前为止，您关注吗？到目前为止，没有什么是完全不合理的-但要做好准备，这是可笑的部分。对于复杂性理论，我们的标准概念是指算法有效的含义是，算法的运行时间是该算法输入长度的多项式。理论家希望他们的形式化适合这种标准的复杂性理论框架。因此，他们通过将特殊的伪填充字符串作为输入传递给其长度由安全性参数指定的操作，从而使密码运算可以在多项式时间内运行。为什么要传递虚拟字符串？好吧，这些操作将完全忽略虚拟字符串，因此传递这个多余的无用字符串似乎完全没有意义。从实践的角度来看这是没有意义的，但是从理论学家的角度来看，它允许他们要求密码运算的运行时间在其输入长度上是渐近多项式的，并且自动遵循其运行时间是渐近多项式的在安全性参数中输入（因为它们是人为确保输入的长度与安全性参数相同）。就像我说的那样，它愚蠢而毫无意义，并且存在仅仅是为了使理论家感到高兴而已。当需要实施密码系统时，请忽略它。
P.S.也许我应该在这一点上告诉我，我有点理论家，有时这也使我感到高兴-但我仍然意识到，对于那些更关心使用加密而不是证明复杂性定理的人来说，这看起来多么愚蠢理论。
评论
$ \ begingroup $
您会在稍后的答案中找到答案，但是“您完全从实际实现中忽略了它” $ \ hspace {.6 in} $应该是“您使用$ k $而不是$ 1 ^ k $实际执行”。 $ \：$
$ \ endgroup $
–user991
13年5月1日在20:24
$ \ begingroup $
好的，@ RickyDemer！谢谢。我已经对其进行了编辑，我想我已对其进行了修复，但是如果我错过任何景点，请告诉我。
$ \ endgroup $
– D.W.
2013年5月1日20:30
$ \ begingroup $
虽然$ k $通常代表密钥生成算法所需的所需加密强度的数量是正确的，但它似乎代表了任何可能导致该方案的其他方面呈指数增长的参数。授予例如crypto.stackexchange.com/a/7853/1564
$ \ endgroup $
–亨里克·赫尔斯特伦
13年5月1日23:18
$ \ begingroup $
虽然答案已经很不错了，但是您可以添加一个数字示例以使其更清楚：如果您想用系数$ n $来缩放算法运行时，则添加$ n $本身会添加$ \ log n $位，例如$ n = 80 $二进制需要$ 7 $位。因此，输入长度上的任何多项式都将使用$ 7 $而不是$ 80 $。
$ \ endgroup $
– tylo
17年1月30日，11：52
#2 楼
正如密码学基础第2卷第366页的第二个脚注中提到的，为什么以一元形式$ 1 ^ k $给出安全参数$ k的解释是允许平滑过渡到完全不均匀的公式...特别是$ 1 ^ n $表示将使用$ n ^ {th} $电路
。
评论
$ \ begingroup $
为什么我们不能选择通常的二进制形式$ n $的$ n ^ {\ text {th}} $电路？
$ \ endgroup $
–PaŭloEbermann
2014-09-28 19:21
$ \ begingroup $
对于非均匀对手，程序的大小在输入长度中是多项式，因此要使其在$ n $中成为多项式，您需要使用一元表示形式，因为$ n $二进制形式的长度仅记录$ n $位。
$ \ endgroup $
– pg1989
16年6月23日在17:25
$ \ begingroup $
D.W.没错，不过-这是一种愚蠢的形式主义，并不重要。
$ \ endgroup $
– pg1989
16年6月23日在17:25
评论
您可能应该用$ k $的二进制表示形式来表示$ 1 ^ k $。 $ \：$相关：表达式$ 1 ^ n $作为函数参数意味着什么？
我对问题进行了更一般的编辑，以便对其他人也有帮助。 （事实证明，这个问题并不特定于McEliece密码系统。）