The authors have done a great job in presenting a potentially high-impact work. The paper studies signature schemes that are secure in the random oracle model, particularly those based on the Fiat-Shamir (heuristic) technique.

It first presents “three digital signature schemes with tight security reductions”; the schemes are typically more efficient due to the tight reduction. The first two are respectively based on Girault et al.’s short exponent discrete log-based scheme [1] and Lyubashevsky’s scheme [2] relying “on the worst-case hardness of the shortest vector problem in ideal lattices.” The third one, proposed by the authors, is “based on the hardness of the subset sum problem.” The authors also define a lossy identification scheme and give a general transformation framework that converts a lossy identification scheme into a signature scheme with tight security reduction.

The paper is filled with sufficient concrete protocols and formal proofs. The authors did a great job of presenting and formalizing different schemes in a common framework.

This work will have a great impact on (efficient) signature schemes, particularly in simplifying the construction and proof of the security of signature schemes. It is a worthwhile read.