Paper 2006/410

Galois Field Commitment Scheme

Alexandre Pinto, André Souto, Armando Matos, and Luís Antunes

Abstract

In [3] the authors give the first mathematical formalization of an unconditionally secure commitment scheme. Their construction has some similarities to one used to build authentication codes, so they raise the question whether there is some relation between commitment schemes and authentication schemes. They conjecture that authentication schemes with arbitration can be used, but they stress that the information flows are different. In this paper, we show that there is indeed a relation between unconditionally secure commitment schemes and unconditionally secure authentication schemes, and that an unconditionally secure commitment scheme can be built from such an authentication scheme and an unconditionally secure cipher system. This parallel is then used to analyse a new attack against commitment schemes that is the counterpart of the impersonation attack in an authentication system. To investigate the opposite direction, we start by defining an optimal commitment system and showing that this must be a resolvable design commitment scheme as proposed in the aforementioned paper. Then, a proof is given that the resolvable design commitment schemes are a composition of an authentication system and a cipher system and the conclusion follows that this is the case for all optimal commitment systems. We prove that there is a commitment scheme based on Galois Fields that uses the One-Time Pad as the cipher system, which to our knowledge is new in the literature. The main technique in the proof is the construction of an appropriate design for any n, originating an authentication system that is perfectly secure against deception attacks of levels 0 and 1. The commitment scheme here proposed uses only very simple operations and can be very efficiently implemented both in hardware and software. Finally, we give a brief look at the possibility of building commitment schemes from other primitives.