# Security of a signature scheme based on both factoring and discrete logarithms

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.

• 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). – otus Sep 12 '15 at 12:44

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, 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.