Cryptology ePrint Archive: Report 2006/410
Galois Field Commitment Scheme
Alexandre Pinto and André Souto and Armando Matos and Luís Antunes
Abstract: In  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
Category / Keywords: cryptographic protocols / Commitment, Authentication, Unconditional Security, Galois Field.
Date: received 13 Nov 2006
Contact author: alx at dcc fc up pt
Available format(s): PDF | BibTeX Citation
Version: 20061113:120151 (All versions of this report)
Short URL: ia.cr/2006/410
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]