Empirical security of the HIMMO scheme

Abstract

ABSTRACT: One of the main issues to be addressed in cryptography is key establishment, due to its importance for private key cryptography. Public key has overcome this problem in general, but there are still many cases where it cannot be applied, e.g. when memory and computation requirements are a limitation. One of the challenges to deal with is to develop a system for key establishment as efficient and secure as possible, since the situation described is becoming more usual now. In 1987 Matsumoto and Imai introduced a good alternative: the key predistribution schemes (KPS), which define a new model to establish the key. It has two major advantages: first, the key generation use the identity of the receptor node, that is, it is identity-based, which means that it also works as node authentication; secondly, because it is identity-based the key is established non-interactively, which saves a lot of communications between nodes. In this thesis we present the concept of KPS along with some examples, one of whom we study in detail, the HIMMO scheme. We give some background of lattice theory, analyze a potential vulnerability to a lattice-based attack related to the closest vector problem and finally, give some evidence of this cryptosystem’s security.

RESUMEN: Uno de los principales problemas a tratar en criptografía es el establecimiento de claves debido a su importancia en criptografía de clave privada. Los protocolos de clave pública han solucionado este problema en gran medida, pero quedan muchos casos en los que no puede aplicarse, por ejemplo cuando tenemos limitaciones de recursos computacionales. Uno de los mayores desafíos es el de crear un sistema de establecimiento de claves lo más seguro y eficiente posible, dado que esta situación es cada vez más común. En 1987, Matsumoto e Imai desarrollaron los esquemas de predistribución de claves (KPS), que constituyen una buena alternativa a la clave pública y definen un nuevo modelo de establecimiento de claves. Tiene dos grandes ventajas: en primer lugar, al generar las claves se utiliza la identidad del nodo a contactar, es decir, son esquemas basados en identidades, con lo que la identidad del emisor queda automáticamente autenticada; en segundo lugar, y precisamente gracias a ser basado en identidades, el establecimiento de la clave se realiza de manera no interactiva, lo cual nos ahorra muchas comunicaciones entre nodos. En esta memoria presentamos el concepto de KPS junto a algunos ejemplos, uno de los cuales, el esquema HIMMO, estudiaremos con más detalle. Haremos una introducción a la teoría de retículos para analizar una posible vulnerabilidad relacionada con el problema del vector más cercano (CVP) y, finalmente, daremos indicios de la seguridad de este criptosistema.