[Cryptography] Fwd: Re: A new digital signature scheme based on the RSA problem?

[Sergio Lerner]

On 16/12/2013 05:26 p.m., Jonathan Katz wrote:
> On Mon, 16 Dec 2013, Sergio Lerner wrote:
>
>> Hi!
>> This is my first message to the group, and I hope it doesn't bore you.
>>
>> Playing with RSA digital signatures I realized that the same system can
>> be used a bit differently and achieve the same security level (as far as
>> I see). I haven't read about this method before and it's near impossible
>> to google for a math formula. So this may be a very old broken digital
>> signature method, or it may be a brand new shinny candidate. If you find
>> any previous reference, let me know. The main idea is to use the hash of
>> the message as the public exponent, and everything else derives
>> naturally from that idea.
>>
>> *The RSAL Digital signature Scheme*
>
> <snip>
>
> Your scheme is similar to several schemes in the literature based on
> the so-called *strong RSA* assumption (as compared to the [regular]
> RSA assumption). See, for example:
>   http://www.research.ibm.com/people/s/shaih/pubs/ghr99.ps.gz

 Thank you Jonathan. Interesting previous reference. Nevertheless, the
scheme is not the same and there is a very important difference.

The Gannaro,Halevi,Rabin scheme relies on the fact that the hash digests
of H(x) must be divisor intractable, and following the formula on the
paper the H hash digest must be at least 16 384 bits for 128 bit
security (the probability is 2^-sqrt(k), lemma 1), so the modulus should
also be at least 16 384 bits. They "practically" (without proof) reduce
this to 512, noting that it would need 2^k/8 signatures to forge a
signature. So in fact they are claiming 64-bit security, which is not
enough nowadays. They would need a 1024 bit hash function for 128 bit
security on practice.

In my scheme I don't rely on divisor intractability property (in fact
one can freely have H(y)=H(x)*t), and that's the reason to make v
dependent on the message. And my scheme only relies on the RSA
assumption, not the strong RSA assumption, since once the v value is
fixed, the e value is also fixed, so the attacker cannot choose both e
and r simultaneously such that r^e =v, he can only choose r, after
having chosen e and v.

I'm I correct?

Best regards,
    Sergio.