Ed25519-MR应该易于使用，快速，具有强大的安全性，并努力远离专利雷区，因为
[Ed25519]是带有附录的签名方案：它为签名的消息添加了512位的签名，以实现128位的推测安全性。 Message-Recovery变体会将一些已签名的消息嵌入到签名中，消息的所谓可恢复部分是成功验证的副产品，无需显式传输。我们希望最大程度地减少整体已签名消息的大小。
已提出具有椭圆曲线离散对数系列的消息恢复功能的签名方案，并获得了专利和标准化（请参见参考书目），包括ECNR（Nyberg-Rueppel）， ECMR（Miyaji），ECAO（阿部-冈本），ECPV（Pintsov-Vanstone，又名ECPVS，PVSSR，ECSSR-PV），ECKNR（KCDSA / Nyberg-Rueppel），其名称分别为[ISO 9796-3]。 >
添加：对于带有附录的签名方案可以实现的收益，我感到困惑。我对[PV1999]和[AO1999]的理解是，对于$ b $位的安全性和任意消息，ECPV和ECAO将$ b $位嵌入到$ 4b $位签名中；当我对其他方案的了解有限时，有人希望嵌入$ 2b $位。
参考文献（可能是椭圆曲线）具有消息恢复功能的离散对数签名。
[NR1993]：Kaisa Nyberg和Rainer A.Rueppel，在CCS 1993的议事过程中，一种基于DSA给出消息恢复的新签名方案；
[NR1994]：id。，基于签名的消息恢复方案离散对数问题，在1994年EuroCrypt会议上进行；
[US'725]：Rainer A. Rueppel和Kaisa Nyberg，数字签名方法和密钥协商方法，US 5,600,725。
[M1995a]和[M1995b]：Atsuko Miyaji，基于离散对数问题的消息恢复签名方案中的弱点（续），在IEICE TF中；
[Mi1996a]：id。，适用于IEICE中消息恢复方案的签名方程式TF;
[Mi1996b]：id。，等效于椭圆曲线上DSA的消息恢复签名方案，在AsiaCrypt 1996的诉讼中；
[Mi1997]：id。，对消息恢复签名进行伪造的另一种对策在IEICE TF中；
[JP'357]：Miyaji Mitsuko，消息解码类型的签名系统，JP Pub。＃H09-034357；
[JP'492]：id。，签名系统，JP Pub。 ＃H09-160492。
[AO1999]：安倍雅之（Masayuki Abe）和冈本达明（Tatsuaki Okamoto），在AsiaCrypt 1999诉讼中以消息恢复作为离散对数的安全签名方案；
[AO2001] id。， ID。，在IEICE TF中；
[JP'178]：id。，消息恢复类型签名系统及其程序存储介质，JP Pub。＃2001-134178。
[PV1999] ：里昂·平佐夫和斯科特·范斯顿e，数字时代的邮政税收，在FC 2000中进行；
[PV2000]：id。，提交给IEEE P1363a的文档，包括[PVSSR-D2]和[PVSSR-D3]。
[BJ2001]：Daniel RL Brown和Don B. Johnson，带有部分消息恢复的签名方案的正式安全证明，在CT-RSA 2001诉讼中；草案：[BJ2000-02]，[BJ2000-06]。
[P1363a]：IEEE Standard 1363a-2004-公钥密码术规范-修订1：其他技术。
[ISO ISO9796-3]：ISO / IEC9796-3：2006，信息技术—安全技术—提供消息恢复的数字签名方案—第3部分：基于离散对数的机制。 HTML和PDF的免费预览。
[X9.92-1]：ANS X9.92-1-2009（2017年再次确认，据报道没有变化）。金融服务业的公共密钥密码术-提供部分消息恢复的数字签名算法-第1部分：椭圆曲线平佐夫-凡斯通签名（ECPVS）。
[Ed25519]：Daniel J. Bernstein，Niels Duif，Tanja Lange，Peter Schwabe，杨博银，高速高安全性签名，在CHES 2011诉讼中。
#1 楼
修复有限字段$ k $和$ k'$，例如$ k = \ mathbb F_p $和$ k'= \ mathbb F_ {p ^ 2} $由$ \ mathbb F_p [i] /（i ^ 2 + 1表示）$，其中$$ p = 36 u ^ 4 + 36 u ^ 3 + 24 u ^ 2 + 6 u + 1 $$ for $ u = -2 ^ {62}-2 ^ {55}-1 $。修正以乘法形式写的组$ G $，例如$（\ mathbb F_ {p ^ {12}}）^ \ times $。固定椭圆曲线$ E / k $和$ E'/ k'$，例如$ E / k：y ^ 2 = x ^ 3 + 2 $和$ E'/ k'：y ^ 2 = x ^ 3 + 2 /（1 + i）$，带有双线性映射$ e \冒号E（k）\时间E'（k'）\到G $，说是泰特（Tate）配对。将随机函数$ H \冒号\ {0,1 \} ^ * \修复为E（k）$，例如说$ m \ mapsto {+} x ^ {-1}（\ operatorname {SHA256}（m））$ ，其中$ {+} x ^ {-1}（x_0）$是$ E（k）$上的点，其中$ x $坐标为$ x_0 $，字典上最小的$ y $坐标。在大质数阶的E'（k'）$中定点$ G \。 （曲线$ E / k $及其扭曲$ E'（k'）$的这种选择通常被称为BN（2，254）。）公钥是编码$的字节\在$ E'（k'）$上的点$ A $下划线A $。在$ \下划线A $下的消息$ m $的签名是满足$ e（\ sigma，G）= e（的E（k）$中元素$ \ sigma \中元素$ \ underline \ sigma $的字节编码H（\ underline A \ mathbin \ Vert m），A）。$$
私钥是编码秘密标量$ a $的$ \ underline a $的字节；相应的公钥为$ \下划线A = \下划线{[a] G} $。要使用私钥$ \下划线a $对消息$ m $进行签名，签名者需要计算$ \ sigma = [a] H（A \ mathbin \ Vert m）$。这会产生签名，因为
\开始{align *}
e（\ sigma，G）
＆= e（[a] H（\下划线A \ mathbin \ Vert m），G ）\\
＆= e（H（\下划线A \ mathbin \ Vert m），G）^ a \\
＆= e（H（\下划线A \ mathbin \ Vert m），[ a] G）\\
＆= e（H（\下划线A \ mathbin \ Vert m），A）
\ end {align *}
通过$ e $的双线性。
请注意，在上述参数的选择中，可以通过将$ x $坐标的254位编码与单个位组合以区分两个可能的$ y，将签名编码为32个字节，甚至仅用255位。 $坐标。 （可以使用Decaf等技术对曲线点进行进一步压缩，留给读者练习。）
因此，您的预算中还剩下32字节和1位，即64字节Ed25519签名对消息的一部分进行编码，从而可以在64字节的签名中恢复32字节（加上1位）的消息！
然后让我们将Mr. Signature定义为64字节的字符串$ \下划线\ sigma \ mathbin \ Vert m $满足$$ e（\ sigma，G）= e（H（\ underline A \ mathbin \ Vert m），A），$$允许通过$ \ underline \恢复邮件sigma \ mathbin \ Vert m \ mapsto m $。
（我在开玩笑吗？也许吧！）
评论
$ \ begingroup $
我需要考虑降低安全性的细节。但是我完全了解了消息恢复过程以及变体概念的超弹性。从元角度来看：我投票赞成，但这是一个危险的斜坡。
$ \ endgroup $
–fgrieu♦
17 Sep 12'在4:32
$ \ begingroup $
我是秃鹰。我盘旋在危险的斜坡上吃早餐！
$ \ endgroup $
–吱吱作响的s骨
17年9月13日在17:39
$ \ begingroup $
BN *和Ed25519，是吗？这些如何结合？ ed25519是否存在$ e（\ cdot，\ cdot）$？ AFAIK Curve / Ed25519不友好配对。
$ \ endgroup $
–cypherfox
18年5月7日在16:23
$ \ begingroup $
@cypherfox这是个玩笑。唯一的关系是涉及椭圆曲线。
$ \ endgroup $
–吱吱作响的s骨
18年5月7日在16:25
$ \ begingroup $
@SqueamishOssifrage Aww。没有新的魔法。 :(
$ \ endgroup $
–cypherfox
18年5月7日在16:26
评论
一个人也许可以将Keccak的状态大小减少到512位，保持64位的宽度，theta和chi的索引将从mod 5更改为mod 3，phi和rho需要通过调整来减小，iota可以如果保持不变，则可以通过删除XOR并替换为修改的theta（通过扭曲的theta定义）并将先前的值插入IV（应检查的部分）来实现可逆的域扩展。或者节省时间，并说1600位签名是可以接受的。输出永远不会被截断（仅整个状态），整个消息都可以恢复！@back_seat_driver：作为具有单独的签名和验证密钥的公共密钥签名方案，它究竟如何工作？
@SqueamishOssifrage我不确定，这听起来像是目标是对一条消息进行哈希处理，该消息将产生至少与消息的一部分匹配的摘要？我很困惑地解决了这个问题。
最近的这篇论文也许可以回答您的问题？它基于[AO1999]，但是您提到的[JP'178]专利已同时失效。