Cryptology ePrint Archive: Report 2012/194

A Multivariate based Threshold Ring Signature Scheme

Albrecht Petzoldt and Stanislav Bulygin and Johannes Buchmann

Abstract: In \cite{SS11}, Sakumoto et al. presented a new multivariate identification scheme, whose security is based solely on the MQ-Problem of solving systems of quadratic equations over finite fields. In this paper we extend this scheme to a threshold ring identification and signature scheme. Our scheme is the first multivariate scheme of this type and generally the first multivariate signature scheme with special properties. Despite the fact that we need more rounds to achieve given levels of security, the signatures are at least twice shorter than those obtained by other post-quantum (e.g. code based) constructions. Furthermore, our scheme offers provable security, which is quite a rare fact in multivariate cryptography.

Category / Keywords: public-key cryptography / Threshold Ring Signature, Post-Quantum Cryptography, Multivariate Cryptography, MQ Problem

Date: received 11 Apr 2012

Contact author: apetzoldt at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20120413:064237 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]