A New Variant of the Winternitz One Time Signature Scheme Based on Graded Encoding Schemes

Hossein Oraei; Massoud Hadian Dehkordi

Paper 2019/212

A New Variant of the Winternitz One Time Signature Scheme Based on Graded Encoding Schemes

Hossein Oraei and Massoud Hadian Dehkordi

Abstract

The Winternitz one-time signature (WOTS) scheme, which can be described using a certain number of so-called ``function chains", plays an important role in the design of both stateless and stateful many-time signature schemes. This work introduces WOTS^GES, a new WOTS type signature scheme in which the need for computing all of the intermediate values of the chains is eliminated. This significantly reduces the number of required operations needed to calculate the algorithms of WOTS^GES. To achieve this results, we have used the concept of ``leveled" multilinear maps which is also referred to as graded encoding schemes. In the context of provable security, we reduce the hardness of graded discrete-logarithm (GDL) problem to the EU-CMA security of WOTS^GES in the standard model.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Preprint. MINOR revision.
Keywords: graded encoding schemes multi-linear maps GDL problem digital signatures one-time signature schemes EU-CMA security
Contact author(s): hossein_oraei @ mathdep iust ac ir
History: 2019-02-27: received
Short URL: https://ia.cr/2019/212
License: CC BY

BibTeX

@misc{cryptoeprint:2019/212,
      author = {Hossein Oraei and Massoud Hadian Dehkordi},
      title = {A New Variant of the Winternitz One Time Signature Scheme Based on Graded Encoding Schemes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/212},
      year = {2019},
      url = {https://eprint.iacr.org/2019/212}
}