From RMA schme to CMA scheme

Scheme 1: m length is k+q(k)
Scheme 2: m length is q(k)

KG: call 2 times Scheme1.KG
Scheme2.pk=(l.pk,r.pk)
Scheme2.sk=(l.sk,r.sk)

SG: r={0,1}[k]
l.m={0,1}[q]
r.m=m xor l.m
l.sig=scheme1.sign(l.sk,r+l.m)
r.sig=scheme2.sign(r.sk,r+r.m)
scheme2.sig=(r,l.m,r.m,l.sig,r.sig)

VER:

1. m=l.m xor r.m
2. scheme1.ver(l.pk,r+l.m,l.sig) true
3. scheme2.ver(r.pk,l.sig,r.sig) true

说明：

• +和Java里的语法一样，对字符串表示连结
• 利用低安全级别的方案1去构造高安全级别的方案2
• 方案1两次生成密钥
• 方案1能签更长的消息，所以要选一个随机串去填充
• 随机生成一个长度为q的左消息，