First of all, thanks everyone for the interest in the paper. I am one of the authors, and we're also working on its real implementation with a Bitcoin wallet (hopefully by end of the year).
Mathematically, it is an interesting piece of work. However, not only will be made more or less obsolete by Schnorr signatures as HeRetiK says,
You're probably right on this. Though, before the Schnorr upgrade is effectively available, the solution we propose can be of help. And (even though irrelevant to Bitcoin) this is applicable to any ECDSA and EdDSA signature for other coins.
First of all, it still requires trust. It is essentially a 2-of-3 system, meaning the "Service Provider" and "Recovery Server" can collaborate to steal the user's funds.
You're technically right. But in real life I believe it's quite difficult that a "Service Provider" (e.g., a company operating in the field) and a "Recovery Server" (e.g., a traditional bank) would collude to steal users funds.
One thing to be aware of though is technology vs operating procedures. In our paper, we identify the "Recovery Server" as a trustworthy third-party entity.
However, from a technological standpoint, nothing precludes to have the "Recovery Server" handled by the user him/herself. In this case, the user is sure that s/he is in full control (having 2 pieces of information out of 3), and it still allows for emergency recovery (e.g., in case of inheritance) with the "Service Provider" if the "Recovery Server" is given to the heirs.