Zero-knowledge authentication schemes from actions on graphs, groups, or rings

Thumbnail Image

Date

Authors

Journal Title

Journal ISSN

Volume Title

Publisher

Abstract

Description

We propose a general way of constructing zero-knowledge authentication schemes from actions of a semigroup on a set, without exploiting any specific algebraic properties of the set acted upon. Then we give several concrete realizations of this general idea, and in particular, we describe several zero-knowledge authentication schemes where forgery (a.k.a. impersonation) is NP-hard. Computationally hard problems that can be employed in these realizations include (Sub)graph Isomorphism, Graph Colorability, Diophantine Problem, and many others.

Keywords

Cryptography and Security, 94A62, 68P25

Citation

URI

http://salesiana.dossiersoluciones.com/handle/123456789/154669

Consulte el texto completo en el siguiente enlace:

https://arxiv.org/abs/0802.1661
 http://arxiv.org/abs/0802.1661

Collections

arXiv