1
$\begingroup$

I have seen this paper: A New Signature Scheme Based on Multiple Hard Number Theoretic Problems by Ismail and Tahat:

In this paper, we propose a new signature scheme based on two hard number theoretic problems, factoring and discrete logarithms.

It seems that it is a dramatically more secure signature scheme. Looking for thoughts/insights as to how useful/safe it actually is.

$\endgroup$
  • $\begingroup$ I have edited your question to quote a claim from the paper and removed the question about supersingular isogenies, which is in my opinion a separate issue you should ask in a new question (if still interested). $\endgroup$ – otus Sep 12 '15 at 12:44
6
$\begingroup$

Although I can't see any immediate weaknesses, I also don't see how it adds significant value over DSA (while being significantly slower).

It claims to be based on two hard problems, discrete log and factoring. However, it doesn't give any particular proof that if you could forge signatures, you can solve both problems. It also doesn't look particularly likely; if you can solve the problem of finding a value $K$ where $K^K = x \bmod p$ (for a fixed $x$), you can forge (by selecting a random $\nu$, computing $x = g^{\nu^e}y^{h(M)^2}$ and then solving for $K$), and it would appear unlikely that this problem would be reducible to the discrete log or the factorization problem.

In addition, while it is true that discrete log and factoring are different problems, they are related. The paper claims that "it is very unlikely that factoring and discrete logarithms can be efficiently solved simultaneously", however it is not actually that implausible that an advance would solve both. For example, a dramatic speedup of the Number Field Sieve may solve both (as that algorithm can be modified to work against both problems). Alternatively, if someone builds a Quantum Computer, well, both problems are then solved.

In addition, their algorithm doesn't appear to run nearly as quickly as DSA (which is not a particularly efficient signature algorithm). Here's why: their algorithm can be viewed as a DSA variant, except that they work in a composite subgroup (rather than the prime subgroup that DSA works in). Here's the rub: their subgroup must necessarily be large (as it must be hard to factor their subgroup; otherwise one of the problems they're relying on is easy). So, instead of having a 256 bit subgroup (which we may work with DSA), they need to work in a 2048 bit subgroup. Because the time taken to compute, say, $K^K$ is proportional to the size of the subgroup, their scheme would take 8 times longer than DSA.

Also, at points their algorithm description is a bit goofy. Take their signature generation algorithm; it would appear that the three steps they have listed could be summarized as $\nu = (Kr - xh(M)^2)^d$. This alternative formulation would better than halve the time (as you don't have to compute a modular square root, and we do one modular exponentiation step; they do it twice); and you don't have to worry what to do if $Kr$ happens not to be a quadratic residue. The only reason I can think of to use their formulation would be to add some sort of side channel resistance; however if you're concerned with that, well, there's got to be a cheaper way.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.