它很简单，比DSA签名或我能找到的任何其他带有附录的签名方案紧凑25％。当与任意非冗余消息一起使用时，我所理解的具有消息恢复功能的基于DL的签名方案（该DL-MR参考书目的子集）在紧凑性方面没有击败它。 br />它对竞争者有什么弊端（除了长期的专利问题）？
为什么后来的博览会默默地使用$ 2t $位的哈希值，而使用$ 4t $位的签名，包括学者[HAC1996]和当前的国际标准[ISO14888]（对原始哈希的狭义性含糊不清的不安之情）？
是否存在一种安全性可以说等同于DSA的方案（或者更好， DLP或相关），但具有原始Schnorr签名方案的紧凑性？如果不是，那么如何用最后提出的较小修改来证明某些内容，从而对每个消息的秘密生成进行非随机化，使用依赖于公钥的哈希，并将哈希值加倍以用于验证的指数？ >
Schnorr签名书目
[Sc89a]：Claus-Peter Schnorr，一种用于在数据交换系统中进行用户识别以及电子签名的生成和验证的方法，欧洲的EP0383985专利登记簿，1989年；
[Sc89b]：id，在Crypto 1989中进行的智能卡的有效标识和签名；
[Sc90a]：id。，用于标识用户以及生成和标识用户的方法验证数据交换系统中的电子签名，1990年，欧洲专利注册簿中的EP0384475；
[Sc90b]：同上，在数据交换系统中用于识别订户以及生成和验证电子签名的方法，美国专利4,995,082；
[Sc91]：同上，通过智能卡进行有效签名生成，在密码学杂志，1991.
[HAC96]：Alfred J. Menezes，Paul C. van Oorschot，Scott A. Vanstone应用密码学手册，1996年，第11.5.3节。
[PS96]：David Pointcheval，Jacques Stern，签名方案的安全证明，在Crypto 1996诉讼中；
[PS00]：id。，《数字签名和盲签名的安全性论点》，《密码学杂志》，2000年。 br />
[BN06]：Mihir Bellare，Gregory Neven，在ACM的CCS 2006诉讼中使用普通公钥模型中的多重签名和一般的分叉引理。
[NSW09 ]：Gregory Neven，Nigel Smart，Bogdan Warinschi，Schnorr签名的哈希函数要求，在《数学密码学杂志》上，2009年。实体需要一种散列函数，而不仅仅是哈希函数，它需要具有随机前缀的抵抗能力。ePrint2015。 >
[KMP16]：Eike Kiltz，Daniel Masny，潘嘉欣，来自标识方案的签名的最佳安全证明，在Crypto 2016诉讼中。
[ISO14888]：ISO / IEC 14888- 3（当前为2016年第3版），信息技术-安全技术-带有附录的数字签名-第3部分：基于离散对数的机制，在ISO（预览）和IEC（预览）处。
原始Schnorr签名方案
基于[Sc91]。注意到该方案适用于DL问题较难的任何订单$ q $组，但我们使用原始符号及其示例，即所选消息设置中的假定安全复杂度$ t = 72 $位。
一次初始化：
$ \ $ 2 $$位的原始$ q $（例如，超过140位的$ q $）
质数$ p $和$ q $除以$ p-1 $（例如，超过512位的$ p $，带有警告）
生成器$ \ $$订单$ q $;即$ \ alpha ^ q \ equiv1 \ pmod p $，$ \ alpha \ ne1 \ pmod q $
单向哈希函数$ h：\ mathbb Z_p ^ * \ times \ {0， 1 \} ^ * \ to \ {0,1 \} ^ t $$
散列$ h $必须使得对于任何固定的$ x $，函数$ m \ to h（x，m）$是单向的（对于固定的$ x $，其耐原像）。 $ h（x，m）$应该是大约均匀分布的，至少要考虑$ x $的$ \ lceil \ log_2q \ rceil $（现代密码哈希满足这些要求）。
密钥设置（每个用户）：
选择私钥$ s $（均匀地）随机放入$ \ {1,2，\ dots，q \} $
发布公共密钥$ v \ gets \ alpha ^ {-s} \ bmod p $
消息签名$ m $：
选择$ r $（均匀地）随机放在$ \ {1,2，\ dots，q \} $
$ x \ gets \ alpha ^ r \ bmod p $
$ e \ gets h（x，m）$
$ y \得到r + s \，e \ bmod q $
输出签名$（e，y）$
验证涉嫌消息$ m $，签名$ {e，y）$，已验证公钥$ v $
$ \ bar x \ gets \ alpha ^ y \，v ^ e \ bmod p $
检查$ e = h（\ bar x，m）$
正版签名检查是因为$ \ bar x \ equiv \ alpha ^ y \， v ^ e \ equiv \ alpha ^ {r + s \，e} \，\ alpha ^ {-s \，e} \ equiv \ alpha ^ r \ equiv x \ pmod p $。
在$ r $秘密且一致地随机且$ y = r + s \，e \ bmod q $的情况下，对$（y，e）$本身的了解不会泄漏任何内容$ s $。请参阅该文章，以获取其他有关安全性方面的论点，这些论点全部是：可行的攻击有效，但代价至少为$ 2 ^ t $哈希或破坏DLP或显然更复杂的问题，另外还涉及$ h $。
注意：[Sc89a]，[Sc90a]和[Sc91]（但不包括[Sc89b]）提到该系统可以移调到其他组，例如椭圆曲线组。
暂定：加强Schnorr签名方案
我提出了三个独立的更改，它们保持相同的签名大小。总体目标是提高安全性，并可能使其降低为所用组中的DLP。
替换在$ \ {1,2，\ dots，q中随机选择$ r $ \} $签名时，由$ r = \ operatorname {mac}（s，m）$加上$ \ operatorname {mac}：\ {1,2，\ dots，q \} \ times \ {0,1 \} ^ * \ to \ {1,2 \ dots，q \} $。
合理性：消除对RNG的需求，而这种失败是（EC）DSA中灾难的一种经过实践检验的配方。这种去随机化技术已用于许多现代签名方案中，包括Ed25519（归因于George Barwood，1997年2月，sci.crypt）。
使$ h $依赖于公钥$ v $，并针对安全性在ROM中;因此$ h：\ mathbb Z_p ^ * \ times \ mathbb Z_p ^ * \ times \ {0,1 \} ^ * \ to \ {0,1 \} ^ t $，结果记为$ h_v（x，m） $
合理性：更好地支持每个公钥$ 2 ^ {t / 2} $个所选签名的安全性声明；不能使用具有哈希属性的游戏，因为哈希变得相对便宜。
添加哈希函数$ h'$取决于公钥$ v $和消息$ m $，从而将$ e $扩展到$ q的宽度$使用前$。$ h'：\ {1,2，\ dots，q \} \ times \ {0,1 \} ^ t \ times \ {0,1 \} ^ * \ to \ {1,2， \ dots，2 ^ {\ left \ lfloor \ log_2（q）\ right \ rfloor} \} $，结果记为$ h_v'（e，m）$
签名被修改为执行$ y \ gets r + s \，h_v'（e，m）\ bmod q $
修改验证以执行$ \ bar x \ gets \ alpha ^ y \，v ^ {h_v'（e，m）} \ bmod p $
理论值：
引入$ h'$可以使$ v $在验证中的$ v $指数在$ m $变化时到达大部分指数域，而不是小数其中$ 2 ^ {-t} $，希望可以帮助重用[PS96]或[NSW09]中的安全性参数。
使用“ Shamir的把戏”时，由于额外的宽度导致签名验证成本的增加很低$ \ alpha ^ y \，v ^ {h_v'（e，m）} \ bmod p $中组合两个模幂的方法。
仅对$ h $的第二次过早映像攻击就不再导致伪造（如果没有$ h'$，则这种暴力攻击可能是蛮力的，预计$ h $的$ 2 ^ t $会调用$ h $，而$ m $会被更改，并且没有组操作）。
相对较窄的$ e $被屏蔽在两个散列之间。
注意：散列大$ m $的开销可能$ \ operatorname {mac}（s，m）$（仅用于签名者），$ h_v（x，m）$和$ h_v'（e，m）$之间共享，方法是使用$ m $宽$ \ ge2t $作为中间的通用步骤。
#1 楼
您的帖子让我有些困惑，我认为您是从错误的角度考虑的。是否有一种安全性可以等同于DSA的方案（或者更好的是DLP）或相关），但具有原始Schnorr签名方案的紧凑性？
是的，Schnorr签名。它们确实是您应该做的。从理论上和直观上讲，这是正确的做法，这与可怕的（DS）DSA计划相反。 Schnorr签名确实降低了基础组中的DLP（请参阅[PS96]），尽管不是很严格。我的感觉是，DSA只是绕开Schnorr专利的一种手段，而现在这已经不复存在了，DSA应该接受它。让我尝试稍微支持这些主张。
首先让我们看看Schnorr签名。我们首先考虑Schnorr识别方案来定义它们。在一个DLP很难的小组中，它使我们能够以交互的方式证明离散日志的知识，而无需透露有关离散日志本身的任何信息。从数学上讲，它是正确的，您可以降低其对DLP的安全性。它是一个交互式协议，但是我们可以通过应用Fiat-Shamir启发式方法使其非交互式。同样，DLP的减少仍然存在。通过在挑战中包含一条消息，我们获得了签名方案。
现在，让我们来看一下ECDSA。我们在有限域$ \ mathbb {F} _p $上的椭圆曲线上工作，得到素数$ p $，假设我们有一个定点$ n $的基点$ G $。协议的类型如下：
从$ [1，n-1] $
中选择均匀随机的$ k $计算$（x_1，y_1）= k \倍G $
计算$ r = x_1 \ bmod n $。
让我们考虑一下这里发生了什么。从$ [1，n-1] $中选择$ k $是有意义的，因为这将是一些秘密的离散日志。然后用$ k $对$ G $求幂也很有意义，因为$ G $已订购了$ n $。然后我们计算$ r = x_1 \ bmod n $。考虑一下您在这里做什么，然后意识到这毫无意义。元素$ x_1 $在$ \ mathbb {F} _p $中，那么为什么要减少此模$ n $？从数学上来说，这完全是愚蠢的。如果$ x_1 $位于$ \ mathbb {F} _ {p ^ 2} $或更大的字段中怎么办？然后，该操作变得更没有意义了。由于这毫无意义，因此几乎不可能为该方案提供安全性证明（据我所知，没有人知道）。
总而言之，真正的问题应该是人们为什么仍在使用（EC）DSA（是的，我意识到可能存在遗留问题）？这是Schnorr的格式错误，应该会成为过去的错误。
让我也尝试解决您的其他问题。
什么缺点对竞争者（超越长期的专利问题）有争议吗？
这里有一些要说的。首先，描述方案的方式不一定是必须完成的方式。签名可以是$（x，y）$，而不是$ 4t $。实际上，在我看来，这是自然的起点，而散列则是这种方式的“压缩”版本。我相信这实际上将是更常见的做法，因为它允许批量签名验证（而散列版本则不允许）。
此外，获得足够的随机性可能并不容易$ r $一律随机。取而代之的是，您可以选择它是伪随机的，作为一些适当事物的哈希。最后，您可以在$ e $的计算中包括公钥，因此$ e \ leftarrow h（x，m，v）$可以防止多目标攻击。
我所做的只是描述EdDSA签名方案。实际上，它只是一个Schnorr签名，并应用了上述更改。
为什么大多数最新的博览会静默地使用2t位散列，从而使用4t位签名
我无法给出确切的答案，但我相信一段时间以来，尚不清楚哈希值应赋予适当的安全级别多长时间。
但是，正如我上面所说，4美元t $位签名大小可能是最常见的。
我提出了三个独立的更改，它们保持相同的签名大小。
第一个EdDSA中应用了两个。我不确定第三点是什么。 $ e $和$ v $的值是公共的，为什么我们要关心它们的结构？
评论
$ \ begingroup $
如果现代博览会是$ 4t $而不是$ 3t $，因为“有一阵子不清楚哈希应该持续多久”，那么这意味着原始博览会是不安全的（或者可能无法证明是安全的？） ;此更改必须具有一定的理由，因为它在大小上有很大的缺点！另外：如果签名是$（x，y）$而不是原始的$（h（x，m），y）$，那么对于EC组，其中$ x $是$ 2t $，其大小为$ 4t $，但比（$> 9t）$大得多，其中$ \ mathbb Z_p ^ * $被认为是（$ q $的订单子集）；还是在散列之前$ x $被截断为$ 2t $或$ t $？
$ \ endgroup $
–fgrieu♦
17年6月25日在22:07
$ \ begingroup $
@fgrieu不，原来（现在）还可以。该方案在随机Oracle模型中具有安全性证明，因此尚不清楚您应实际使用哪种哈希来实例化此方案。安全的做法是使用$ 2t $位的输出，提供抗碰撞能力，但是事实证明这是不必要的，因此$ t $位的哈希就足够了。至少那是neven.org/papers/schnorr.pdf本文所描述的方式。
$ \ endgroup $
–曲线爱好者
17年6月25日在23:40
$ \ begingroup $
@fgrieu的确，我大部分时候都在考虑EC案。对于其他组，压缩可能更有价值！同样，请注意，压缩在这里并不是圣杯，因为它也有缺点（即没有批量验证）。
$ \ endgroup $
–曲线爱好者
17年6月25日在23:42
$ \ begingroup $
非常感谢Neven / Smart / Warinschi的论文！它提到并试图解决困扰我的问题：“但是很难从（Pointcheval / Stern's）证明中得出关于H的输出长度的任何指导，因为它仅考虑将哈希函数映射到$ \ mathbb Z_q $”。我的暂定修改3尝试这样做，同时使用$ h_v'\ circ h_v $并在完整的$ \ mathbb Z_q $中输出，同时保留$ t $位的$ e = h_v（x，m）$。
$ \ endgroup $
–fgrieu♦
17-6-26在6:20
#2 楼
经过数周研究，根据问题的扩展书目，对我自己的问题作了部分回答。历史记录
最初提出的Schnorr签名方案是用$ t $位哈希（$ 3t $位签名），在安全性证明发生异常的时间。 [PS96]使用新近推出的Forking Lemma，假设基本离散对数很难，证明了$ 2t $位理想散列的安全性；这可能就是为什么当代博览会和[ISO14888]使用此哈希宽度的原因。 [BN06]定义通用分叉引理，并将其应用到具有$ 2t $位随机预言的多用户设置中。
[NSW09]取得进展；它：
概述了使用General Forking Lemma和[BN06]的其他结果进行的$ t $位理想散列的安全性证明（在随机Oracle模型中）。 >说明散列的必要（在ROM中）和充分的（在通用组模型中）安全性条件的证明：随机前缀前映像（RPP）和随机前缀第二前映像（RPSP）安全性（与第一前映像和第二前映像不同）通过实验加上一个随机前缀的原像）；他们的证明是针对$ 2t $位哈希和$ \ log_2（q）\ ge2t $（然后是严格的）；或$ t $位哈希和$ \ log_2（q）\ ge3t $。
为$ 2t $的Merkle-Damgård哈希表示国家安全性（无证据要求，也没有特定的$ \ log_2（q）$绑定）位被截断为$ t $位（请注意，以前显示$ t $位Merkle-Damgård哈希具有最佳的$ 3t / 4 $ -security wrt RPP）。
[Br15 ]表现出病理性的$ t $位RPP和RPSP哈希值，使$ \ log_2（q）= 2t $不安全，并指出它不会使[NSW09]中的任何内容无效。
[Be15]独立指出在多用户设置中某些声称的安全证明（不在问题的书目中）证明是不正确的，并指出以固定长度的公钥表示形式启动散列数据是一种安全的解决方法。 >
[KMP16]引用了许多其他来源，进一步剖析了不同模型中的安全性；并显示[Be15]中提到的问题可以基本修复，从而允许在多用户设置中进行签名而无需访问公钥。
[ISO14888]标准化了SDSA，EC-SDSA和EC -FSDSA，具有标准的$ 2t $位散列和$ \ log_2（q）\ approx2t $。 SDSA代表Schnorr数字签名算法（参考[Sc89b] [Sc91]），EC代表椭圆曲线变体，F代表完整。 EC-SDSA存在两种变体，用作签名$ h（\ Pi_X \ | \ Pi_Y \ | m）$（参考[Sc91]）或$ h（\ Pi_X \ | m）$（参考[NSW09]）。 EC-FSDSA使用$ \ Pi_X \ | \ Pi_Y $作为签名的第一个组成部分（参考[Sc91]，即使我仅在身份验证协议中发现它也是如此；这是在CurveEnthusiast的答案中被描述为自然起点的变体） ）。
Wrapup
与竞争对手相比，Schnorr签名方案没有发现明显的技术缺陷。但是，如ETSI TS 119312 V1.2.1（2017-05）所述，由于先前的专利问题（美国专利4,995,082已于2008年2月到期），Schnorr签名并不常用。
最初的Schnorr签名方案以$ t $位哈希作为签名的组成部分，而DLP较难的组在随机Oracle模型中被证明是安全的，这是理想的选择。散列（认为包括实际的不间断的$ 2t $位哈希被截断为$ t $位）；在具有RPP和RSPP散列但具有$ \ log_2（q）\ approx3t $（因此$ 4t $位签名）的通用组模型中；对于实用的哈希和$ \ log_2（q）\ approx2t $（因此$ 3t $位签名）没有已知的中断。
通过$ 2t $位理想哈希证明该方案是安全的；并在具有RPP和RSPP哈希值和$ \ log_2（q）\ approx2t $（因此$ 4t $位签名）的通用组模型中。
如问题的改进1中那样，用确定性变量代替随机生成的$ r $已成为学术上公认的惯例（[ISO14888]既未考虑也未明确禁止它）。
用户设置，建议以固定大小的公钥表示形式开始散列。
评论
$ \ begingroup $
如Kiltz等人所证明的，您还可以展示Schnorr的严格的多用户安全性而无需密钥前缀。在加密货币16中：eprint.iacr.org/2016/191
$ \ endgroup $
– DrLecter
17年7月16日在6:15
评论
也许我会误解这一点，但是确定性签名绝对是不安全的，因为它们琐碎地允许得出以下结论：如果两个签名（相同密钥）相等，则消息很可能相等。出于同样的原因，对于任何加密算法，您都应该始终使用随机（或至少伪随机，但几乎仍是唯一的）IV。 （当然，对哈希函数进行随机化很容易，并且所产生的方案至少应受较差的RNG的影响。）@Ame Vogel：不泄露消息信息不是签名方案的标准目标。而且，如果这是必需的，那么仅凭不确定性签名方案是不够的。以RSASSA-PSS为例：这是一种不确定的签名方案，但是它确实允许通过对签名进行测试来测试消息是否相同（该测试需要公钥，但是那是公共的）。