Browse Prior Art Database

Efficient, Parallelizable Methods for Data Encryption

IP.com Disclosure Number: IPCOM000115033D
Original Publication Date: 1995-Mar-01
Included in the Prior Art Database: 2005-Mar-30
Document File: 4 page(s) / 107K

Publishing Venue

IBM

Related People

Basturk, E: AUTHOR [+5]

Abstract

Let f sub a be a pseudorandom function mapping L bits to l bits. Let G be a generator outputting a sequence of L bit strings. The message x to be encrypted is regarded as a sequence of l bit blocks, x = x sub 1 x sub 2 ellipsis x sub n.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 42% of the total text.

Efficient, Parallelizable Methods for Data Encryption

      Let f sub a be a pseudorandom function mapping L bits to l
bits.  Let G be a generator outputting a sequence of L bit strings.
The message x to be encrypted is regarded as a sequence of l bit
blocks, x = x sub 1 x sub 2 ellipsis x sub n.

      The key K of the basic encryption scheme is taken to specify a
pair a , s hat consisting of a key a specifying the pseudorandom
function f sub a and a seed s hat for the generator.  The state of
the scheme is the current state d of the generator; the initial value
of this state is the empty string lambda.  The scheme ( E , D ) is
specified as follows.
  1.  To compute the encryption E(a, s hat, x, d) = (y, d bar) of
       message x=x sub 1 ellipsis x sub n, the sender does the
       following:
      a.  Set d sub 0 =d and compute the next n steps of the
generator,
           (s sub j, d sub j) = G(s hat, d sub <j-1>) for j=1,
           ellipsis, n.
      b.  Create a "pseudorandom pad" by applying the PRF f sub a to
           the sequence of outputs of the generator, p sub j = f sub
a
           (s sub j) for j=1, ellipsis, n.
      c.  XOR the message blocks with the pad blocks, y sub j = p sub
j
           cplus x sub j for j=1, ellipsis, n
      d.  Let y = y sub 1 ellipsis y sub n and output y as the
           encryption of x.
      e.  Update the state by d bar = d sub n.
  2.  To compute the decryption D(a, s hat, y, d)=(x, d bar) of
       ciphertext y, the receiver does the following:
      a.  Set d sub 0 = d and compute the next n steps of the
           generator, (s sub j, d sub j) = G(s hat, d sub <j-1>) for
           j=1, ellipsis, n.
      b.  Recreate the pseudorandom pad by p sub j = f sub a (s sub
j)
           for j=1, ellipsis, n.
      c.  XOR the ciphertext blocks with the pad blocks, x sub j = p
           sub j cplus y sub j for j=1, ellipsis, n
      d.  Output x=x sub 1 ellipsis x sub n as the recovered
plaintext
      e.  Update the state by d bar = d sub n.

      Give a memoryless (i.e., no need to preserve a state) variant
of the above.  The key K of the memoryless encryption scheme is a PRF
key a.  Some notation: lbracket k rbracket sub L denotes the L bit
binary representation of integer k.  The scheme (E',D') is specified
as below.
  1.  To compute the encryption E'(a,x) =r, y of message x=x sub 1
       ellipsis x sub n, the sender does the following:
      a.  Pick a random number r in the range 0, ellipsis, 2 sup L -
1
      b.  Create a pseudorandom pad by applying the PRF f sub a to
the
           consecutive sequence of points beginning with r; formally:
p
           sub j = f sub a (lbracket r+j ' mod ' 2 sup L rbracket sub
L)
           for j=1, ellip...