我查看了几种签名方案（最常见的是 DSA、ECDSA），并且想知道是否存在具有以下属性的方案：
我什至不在乎多个签名是否对一个文本有效，只要它们可以使用公钥进行验证。
我的直觉是，“存在”安全本质上与加密密钥的大小相关，而加密密钥本身对签名的大小有影响。据我所见，ECDSA 提供的签名比具有相同安全级别的 DSA 更短，但对于我来说，签名仍然太大......
欢迎任何想法/签名方案的链接。
编辑：我也曾在某个时候读过 BLS，但无法真正确定是否能够获得一个足够安全且签名长度小于 50 位的方案。
edit2：我应该补充一点，目标是将其用于 OTP 方案，因此要签名的消息的大小会很小（< 512 字节），并且冲突不会是一个大问题：假设双方都知道消息，我希望其中一个使用非常短的签名来验证另一个是否有私钥。
您不能拥有少于 50 位的安全签名方案。演示：攻击者可以枚举所有 50 位的序列，直到找到匹配项。事实上，数字签名的一点是验证算法可以由每个人计算，因为它只使用公钥（根据定义，公钥是公开的）。
从理论上讲，最好的希望是n位的签名，以保证2 n的安全性。传统的不可行阈值是n = 80位，但技术的不断进步往往会提高这一点。现代密码学家倾向于跳到 128 位，因为这是 2 的幂，因此很漂亮（尽管有康德，但大多数审美判断都是相对的）。不过，100 位在相当长的一段时间内应该是安全的。
在被认为是安全的已知签名算法中，BLS目前是同类中最好的；对于2 n的安全级别，它将生成大小为 2n位的签名，因此您正在考虑至少 160 到 200 位大小的签名。有一些算法可以低于（下降到大约1.4*n），但它们有相当长的破损和修复和再次破损的历史（我说的是 SFLASH 及其同类），所以不建议使用它们，并且有没有直接可用的标准。
另一种可能性是将RSA 与 ISO/IEC 9796-2 padding一起使用。正如链接的文章所示，它的使用有一些微妙之处。这种签名方案是一种“带恢复”的方案，这意味着虽然签名相当庞大（如果使用 1024 位 RSA 密钥，则为 1024 位），它还可以嵌入一些已签名的数据；因此，如果您的问题是关于将签名附加到消息，那么此方案将产生相对较低的开销。正如文章所解释的，你得到2 61保护 22 字节（即 176 位）的签名开销；为了获得良好的安全性，您必须使用输出大小为 224 位的散列函数，从而导致 240 位的签名开销——不如等效强度 BLS 的 200 位，但更好比 DSA 或 ECDSA 的 400 位（对于仍然相同的强度级别）。
短签名的问题在于它更容易发生冲突。您也不能轻易地使其运行时间过长（通过使用慢速散列或增加迭代），因为文件大小可能相差几个数量级。如果你让它足够慢以安全地签署“你好”，那么签署 50 GB 的蓝光版本将会非常困难。因此，留给我们的最简单的选择是增加比特数，从而增加在算法没有被破坏的情况下发生冲突所需的尝试次数。
还值得注意的是，密钥的大小与签名的大小无关。散列的大小决定了签名的大小，因为签名是文件的散列，然后用私钥加密，这样公钥就可以解密它并将其与自己计算的散列进行比较。只要您不使用需要填充的加密方案，签名的长度就完全与密钥大小无关。
编辑：好的，对于更新的问题，听起来您实际上并不是在寻找签名。签名采用文件的哈希值，然后使用私钥对其进行加密，因此 a) 其他人可以验证文件没有更改，b) 其他人可以验证您对文件的证明。这是有效的，因为有人无法制作另一个适合相同哈希值的文件。
您正在寻找的是一个挑战/响应，它可以验证密钥是否由试图进入的人持有。这通常使用对称密钥而不是非对称密钥来完成，并且时间戳被加密然后散列以减少长度。问题是减少长度的散列会抛弃公共/私有系统，因为双方都必须能够执行该操作。我想可以从私钥签名中得出一个简短的输出，但我觉得它比使用对称密钥要弱得多（没有可证明的原因，但据我所知还没有这样做过）。
这个方向的最新成果是标题恰当的论文“ The Shortest Signatures Ever ”（ePrint:2016/911），它使用了多元密码学。它声称可以在 80 位安全级别上实现 110 位签名。但是，该方案有以下缺点：
除了较短的签名大小之外，一个潜在的优势是：
如果您真的需要非常短的签名并且可以忍受这些缺点，那么您可以尝试一下。但是请注意，密码学本质上是一门保守的学科。除非你真的需要，否则你最好坚持一个经过验证的方案。
(EC)DSA 的替代方案是 Schnoor 签名方案，其原始形式将签名大小从 4t-bit 减少到 3t-bit，用于推测 2 t -bit安全性和每个密钥最多 2 t/2 个签名。例如，在 96 位安全级别，签名需要 36 个字节。
参考描述是：Claus-Peter Schnorr，Efficient Signature Generation by Smart Cards，密码学杂志，1991。注意到该方案适用于 DL 问题很难解决的任何阶 $q$ 组。
我在这个问题中讨论了一些可能的变体：
最后两个更改旨在增强安全性参数（狭窄的 t 位公共散列在两个加盐散列之间）；他们的目标不是消除特定设置中的弱点。