Extended Security Arguments for Signature Schemes

It is known how to transform certain canonical three-pass identification schemes into signature schemes via the Fiat---Shamir transform. Pointcheval and Stern showed that those schemes are existentially unforgeable in the random-oracle model leveraging the, at that time, novel forking lemma. Recently, a number of 5-pass identification protocols have been proposed. Extending the above technique to capture 5-pass identification schemes would allow to obtain novel unforgeable signature schemes. In this paper, we provide an extension of the forking lemma (and the Fiat---Shamir transform) in order to assess the security of what we call $$n$$n-generic signature schemes. These include signature schemes that are derived from certain $$(2n+1)$$(2n+1)-pass identification schemes. In doing so, we put forward a generic methodology for proving the security of a number of signature schemes derived from $$(2n+1)$$(2n+1)-pass identification schemes for $$n\ge 2$$n?2. As an application of this methodology, we obtain two new code-based existentially-unforgeable signature schemes, along with a security reduction. In particular, we solve an open problem in multivariate cryptography posed by Sakumoto, Shirai and Hiwatari at CRYPTO 2011.