Message encoding algorithms for Winternitz signatures

Abstract

Considerando um determinado conjunto de parâmetros para o esquema de assinatura única de Winternitz (Wots), a complexidade total da geração e verificação de uma assinatura é constante e independente do documento a ser assinado. Esses custos são devidos ao número de iterações de uma função f , executados sobre elementos de uma chave privada. No entanto, o custo de geração de assinatura por si só pode ser diferente do custo da verificação de assinatura, dependendo diretamente do documento de entrada. Este trabalho apresenta uma nova variante do esquema Wots, permitindo o ajuste desses custos. Ou seja, aumenta-se o tempo de geração de assinatura em favor de uma verificação mais rápida ou vice-versa. O número total de repetições de f para parâmetros específicos do esquema podem ser reduzidos, ocasionando também uma redução do custo de geração de chaves. Na contribuição principal deste trabalho, permite-se escolher um custo fixo de execuções de f , inalterado para qualquer mensagem de entrada. Experimentos mostram que as propostas têm impacto substancial em esquemas de assinatura baseados em árvores de Merkle, como Xmss. Além disso, se f for uma função de direção única, resistente à segunda pré-imagem e indetectável, prova-se formalmente que o esquema é Existentially Unforgeable under a Chosen Message Attack (EU-CMA).

Abstract: It is known that, for a given set of parameters, the overall complexity for generating and verifying a signature is constant and independent of the document being signed, for the Winternitz onetime signature scheme (Wots). These costs are due to the number of chained iterations of a function f. However, the cost for signature generation alone is slightly different from signature verification, and these depend on the message to be signed. We introduce a new variant for Wots, which allows the adjustment of these costs, i.e. increase the overall signature generation time in favor of faster verification or vice-versa. We decrease the total number of iterations of f for some parameters, reducing the cost of key generation as well. Our main contribution allows one to choose a fixed cost with respect to the number of evaluations of f, unchanged for any input message. Our experiments show that these proposals substantially impact Merkle Tree based signature schemes, such as Xmss. Additionally, we give a formal proof that our scheme is Existentially Unforgeable under a Chosen Message Attack (EU-CMA), assuming that f is one way, second preimage resistant and undetectable function.