A note on a signature system based on probabilistic logic

20October 1980

INFORMATIONPROCESSINGLETTERS

Vdume I 1. number2

A NOTE ON A SIIGNA’WRE SYSTEM BASED ON PROBABILISTIC LOGIC

Ernst LEI% Dqnzrtnrmtof Con~prrtmScience, University of Ihrrstort, Central Campus, Houston, TX 77004, U.S.A. Rc&wl

I I,cbruary 1980

Sipnafurc ,yctcms, information transfer, privacy, security, cryptography

E is extended to K+ X K + K as l’ollows:

1. introduction

E(M,w) = E(E(wl * . . . w,,_+w,), l

The objective of this note is to comment on and to modify a scheme for producing digitalized signatures, gropased by Rabin! in [ 2). We do not require the rsoder to know this paper, although its knowledge might be helpful. However, we will expect the reader to hc f%riliar with the problem of digitalized si’gnaturcs, in general, and the motivation behind it. We pain;f wf ,. _iha! any public key system can be modified to :abtam a signature system (see [l I); fhis yields another approach to signatures, given in [3 1. In Section 2 we outline Rabin’s method. In Sections 3 and 4 we discuss the general requirements any signature system should satisfy and indicate why Rabin’s method does not satisfy them. In Section 5 we describe our modification and demonstrate that it meets all the requirements.

1,

The central concept of Rabin’s method ([2]) is an encoding function t,:KXK-+K, where K = (0, 1jk and k is some fixed integer. If x, w E K, E(x, w) is called an encoding of word w by use of key x. A message M i6 a sequence of m words WiE K,m> 1. * ...

-w,

ai = E(x~, I),

i = 1, . .. . L,

and B computes

2. Rabin’s method

‘W2

for m > 2.

Three assumptions must be made about E: (I) Given x, w E K, E(x, w) can be rapidly computed. (2) Given a sequence of pairs (xi, E(xi, w)), i = I , “., n, it is intractably hard to produce a pair (x,.,+1, E(x,+l , w)) with x,+1 f xi for all i E (1, . .. . n}. (3) Given any word w it is intractably hard to compute dqferent messages M !jnd N such that E(M, w) = EN w). Now we can summarize how signatures can be generated and verified in this scheme. Suppose t: and B wish to conduct digitalized signed correspol\dence eve;’ an insecure channel. Each of them chooses L keys, x1, .. . . XL for A and y .. . . yL for B. Both sequences are kept secret. A computes (Y= CY~- . . . *