Digital signature schemes are used to guarantee for non-repudiation and authenticity of any kind of data like documents, messages or software. 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. The main idea of
WOTS scheme is the use of a limited number of function chains, all of which
begin at some random values. 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. More precisely, to compute each algorithm
of the proposed scheme, we only need to calculate one intermediate value. 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.
We expect these results to increase the efficiency of Winternitz based digital signature schemes.