Patent Publication Number: US-7221756-B2

Title: Constructions of variable input length cryptographic primitives for high efficiency and high security

Description:
FIELD OF THE INVENTION 
   The present invention relates generally to cryptography, and more particularly, to constructions of variable input length cryptographic primitives for high efficiency and high security. 
   BACKGROUND OF THE INVENTION 
   A cryptographic primitive that operates on an input of fixed size is called a Fixed Input Length (FIL) primitive. For example, all block ciphers, which are common FIL primitives, operate on messages of fixed size. Informally, a block cipher is a type of encryption algorithm that transforms a block of unencrypted text (commonly called “plaintext”) into a block of encrypted text (commonly called “ciphertext”). The plaintext and ciphertext have the same length when transformed through a block cipher. This transformation takes place under the action of a secret key. Decryption is performed by applying a reverse transformation to the ciphertext block using the same secret key. The length of a block is called the block size, and, for many block ciphers, the block size is 64 or 128 bits. 
   However, in practice, one is faced with the situation of applying a cryptographic primitive on data of varying lengths. This situation calls for the development of cryptographic primitives called Variable Input Length (VIL) primitives. One particular situation is the need for an encryption algorithm which deals with messages of varying sizes but at the same time preserves the property that the length of the ciphertext equals the length of the plaintext. This situation is very common in Internet applications, where traffic consists of “packets” of varying sizes. If a block cipher is being used for encryption, then the blocks that need to be encrypted could be of varying lengths. 
   Wireless applications also vary packet sizes. This is due to the fact that the frames of data that are sent to each user may be different lengths from user to user because of the difference in the channel conditions of the users relative to the base station. 
   One problem associated with constructions made of VIL primitives is that encryption and decryption can take a relatively long time. A second problem associated with these constructions is that certain constructions have relatively inferior security. 
   A need therefore exists for techniques that provide constructions made of VIL primitives that are efficient and that provide relatively high security. 
   SUMMARY OF THE INVENTION 
   Broadly, techniques are presented for the construction of Variable Input Length (VIL) cryptographic primitives that are efficient and provide relatively high security. These techniques are used to encode a message to create an encrypted resultant message and to decode the encrypted resultant message to recreate the original message. One encryption and its corresponding decryption technique is more efficient than a comparable conventional encryption and decryption technique, while a second encryption and its corresponding decryption technique has relatively high security. These constructions may be implemented in any number of ways, such as through hardware devices or computer systems. 
   In a first aspect of the invention, a technique is used to encrypt a VIL input. This technique is faster than comparable conventional techniques. The technique of the first aspect uses a hash function that is applied to a prefix of the input. The output of the hash function is added to a suffix of the input. A block cipher is applied to results of the addition. An encryption function that uses a random number is performed on the prefix. In one embodiment, the encryption function is a parsimonious encryption function, such as a counter-mode encryption or a cipher block chaining encryption. Additionally, it is preferred, in some embodiments, that the random number be the output of the block cipher. The encrypted output is then the output of the encryption function and the output of the block cipher. The combination of the hash function and a single block cipher is fast compared to comparable conventional encryption techniques on VIL inputs. Thus, the total encryption time is reduced as compared with comparable conventional encryption techniques on VIL inputs. 
   In a second aspect of the invention, the encrypted output from the encryption technique of the first aspect is decrypted. 
   In a third aspect of the invention, a second encryption technique on VIL inputs is provided. This technique has a relatively high level of security yet also allows VIL inputs to be used. In this aspect, a hash function is applied to an input, and the output of the hash function has first and second portions, where the first and second portions can be of different sizes. A first function is applied to the second portion, and the output of the first function has a size smaller than the second portion, and preferably the same size as the first portion. In one embodiment, the first function is a block cipher using a first key. The output of the first function is preferably, in some embodiments, added to the first portion, and a second function is applied to the result of this first addition. The second function, in an embodiment, comprises a number of independently keyed block ciphers. The output of the second function is added, through a second addition, to the second portion. An inverse hash function is then applied to the output of the first and second additions, thereby creating an encrypted output. 
   In a fourth aspect of the invention, the encrypted output from the encryption technique of the third aspect is decrypted. 
   A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  illustrates a block diagram of an exemplary system implementing cryptographic constructions in accordance with a preferred embodiment of the invention; 
       FIG. 2  illustrates a block diagram of a block cipher construction in accordance with a preferred embodiment of the invention; 
       FIG. 3  is a flowchart of a method of decrypting the output of the block cipher construction of  FIG. 2 ; 
       FIG. 4  illustrates a block diagram of a block cipher construction in accordance with another preferred embodiment of the invention; and 
       FIG. 5  is a flowchart of a method of decrypting the output of the block cipher construction of  FIG. 4 . 
   

   DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS 
   The following detailed description is divided into several sections in order to facilitate an organized description of the embodiments of the present invention. In Section 1, an overview of the embodiments of the present invention is given. Section 2 contains a variety of definitions that are used in subsequent sections. Section 3 describes techniques for encrypting and decrypting data using Variable Input Length (VIL) PseudoRandom Permutations (PRP). To simplify understanding, these techniques are presented by showing how conventional techniques may be converted to techniques of the present invention. The VIL PRP encryption and decryption techniques of the present invention are described mathematically and in relation to  FIGS. 2 and 3 . Section 4 describes techniques for encrypting and decrypting VIL data using Strong-PRP. Basically, PRP is secure against plaintext attacks, while Strong-PRP is secure from both plaintext and ciphertext attacks. Again, these VIL Strong-PRP techniques are presented by showing how conventional techniques may be converted to the techniques of the present invention. Encryption and decryption techniques of the present invention are described mathematically and in relation to  FIGS. 4 and 5 . 
   1. Overview 
   Broadly, techniques of the present invention allow Variable Input Length (VIL) inputs to be encrypted. There are basically two classes of VIL techniques, “variable but fixed” and “variable in and variable out.” In the former, an input having one length is converted to an output having the same length. For instance, an input of 1024 bits is converted to an output having 1024 bits. In “variable in and variable out,” an input having one length is converted to an output having a different length. For example, an input of 1024 bits is converted to an output having 512 bits. The techniques of the present invention are “variable but fixed” VIL cryptographic techniques. The techniques of the present invention are variable because the size of the input is allowed to vary, as opposed to a fixed input length cryptographic technique where the input must be a particular size or perhaps an integer factor of the particular size. In other words, fixed input length cryptographic techniques can have an input of 1024 bits, for instance, or perhaps 2048 or 4086 bits, while the techniques of the present invention can be designed to operate on 517 bits or 1045, or some other suitable number of bits. 
   The inputs will be described below as having a size of n+b, where n and b are usually expressed as bits. Generally, b≧n, such as having b be 896 bits and n be 128 bits. However, it is possible for n&gt;b, although this can cause reduced security. The techniques of the present invention use VIL cryptographic primitives to encrypt input messages and decrypt encrypted messages. Input messages are referred to herein as plaintext, whereas encrypted versions of the input messages are referred to herein as ciphertext. The encryption techniques of the present invention are presented herein as constructions of cryptographic primitives, and the decryption techniques are presented as methods. This is solely for convenience, as it is quite easy for those skilled in the art to determine a construction from a method and vice versa. 
   Referring now to  FIG. 1 , an exemplary cryptographic system  100  is shown implementing cryptographic constructions and methods in accordance with preferred embodiments of the present invention. Cryptographic system  100  is shown interoperating with a network and a Digital Versatile Disk (DVD)  180 . Cryptographic system  100  comprises a processor  110 , a memory  120 , a media interface  130 , and a network interface  140 . Memory  120  comprises encryption construction  155 , decryption construction  160 , plaintext  165 , and ciphertext  170 . 
   Encryption construction  155  is a construction using VIL cryptographic primitives to encrypt plaintext  165  into ciphertext  170 . Encryption construction  155  may be the construction shown in  FIG. 2  or the construction shown in  FIG. 4 . Additionally, the encryption construction  155  can support both constructions. The former encrypts and decrypts at a higher speed compared to a conventional construction, while the latter has a higher amount of security than conventional constructions and provides VIL cryptography. 
   Decryption construction  160  is a construction using VIL cryptographic primitives to decrypt ciphertext  170  back into plaintext  165 . Decryption construction  160  may be the construction shown in  FIG. 3  as method  300 , if the encryption construction of  FIG. 2  is used. Alternatively, the decryption construction  160  may be the construction shown in  FIG. 5  as method  500 , if the encryption construction shown in  FIG. 4  is used. Additionally, the decryption construction  160  can support both constructions. 
   Although shown separately, the encryption construction  155  and the decryption construction  160  can be part of the same software package, such as an Application Programming Interface (API). These constructions may be added to other software packages, such as packages that support the Internet Protocol (IP) for instance. Moreover, these constructions may be implemented in integrated circuit form, for example, as part of an integrated circuit that performs encryption and decryption for cellular phone data or other wireless data. 
   Network interface  140  allows the cryptographic system  100  to communicate with a wired, optical, or wireless network. Media interface  130  allows the cryptographic system  100  to receive instructions via a computer-readable medium, such as a hard-drive or DVD  180 . As is known in the art, the methods and apparatus discussed herein may be distributed as an article of manufacture that itself comprises a computer-readable medium having computer-readable code means embodied thereon. The computer-readable code means is operable, in conjunction with a device such as cryptographic system  100 , to carry out all or some of the steps to perform the methods or create the apparatus discussed herein. The computer-readable medium may be a recordable medium (e.g., floppy disks, hard-drives, memory cards, or optical disks, such as DVD  180 ) or may be a transmission medium (e.g., a network comprising fiber-optics, the world-wide web, cables, or a wireless channel using time-division multiple access, code-division multiple access, or other radio-frequency channel). Any medium known or developed that can store information suitable for use with a computer system may be used. The computer-readable code means is any mechanism for allowing a computer system to read instructions and data, such as magnetic variations on a magnetic medium or height variations on the surface of a compact disk, such as DVD  180 . 
   Memory  120  configures its processor  110  to implement the methods, steps, and functions disclosed herein. Memory  120  could be distributed or local and the processor  110  could be distributed or singular. Each memory could be implemented as an electrical, magnetic or optical memory, or any combination of these or other types of storage devices. Moreover, the term “memory” should be construed broadly enough to encompass any information able to be read from or written to an address in the addressable space accessed by processor  110 . With this definition, information on a network (e.g., a wired network or a wireless network) is still within a memory, such as memory  120 , because the processor, such as processor  110 , can retrieve the information from the network. It should be noted that each processor that makes up a distributed processor generally contains its own addressable memory space. It should also be noted that some or all of cryptographic system  100 , as discussed above, can be incorporated into an application-specific or general-use integrated circuit. 
   Before proceeding with a discussion of the constructions of  FIGS. 2 through 5 , it is helpful to set out some definitions. 
   2. Definitions 
   In this section, pseudorandom functions, pseudorandom permutations, and other definitions are presented. Although these primitives are traditionally asymptotic, there is a need to model them in a concrete security framework. This treatment is necessary since fixed input length primitives are handled. Fixed input length primitives are finite objects, and as a result, meaningful security results cannot be captured by a traditional asymptotic treatment. As noted below, some portions of the definitions in this section are also presented in Bellare, Canetti and Krawczyk, “Pseudorandom Functions Revisited: The Cascade Construction and its Concrete Security,” 37th Ann. Symp. on Foundations of Comp. Sci., IEEE, 514–523 (1996); and Bellare, Kilian and Rogaway, “The Security of Cipher Block Chaining,” Advances in Cryptology, volume 839 of Lecture Notes in Comp. Sci., 341–358 (Yvo G. Desmedt ed.) (1994), the disclosures of which are hereby incorporated by reference. 
   Notation. If x is a string of bits, then its length is denoted by |x|. If a and b are integers greater than 0, and a&lt;b, then the substring of x starting at bit position a and ending at bit position b (counting from the left) is denoted x[a, . . . ,b]. Let S be a probability space, then the process of picking an element from S according to the underlying probability distribution is denoted 
           x   ⁢     ←   R     ⁢     S   .           
The term I n  is synonymous with {0,1} n  (the set of bit strings of length n). The set of all functions mapping I n  to I m  is denoted F n,m , and set of permutations on I n  is denoted P n .
 
   Computational Model. The convention in Bellare, Kilian and Rogaway, incorporated by reference above, is followed here and an adversary A is modeled as a program for a Random Access Machine. This adversary will have access to an oracle for computing a specified function ƒ; it can make black-box queries to this oracle, and it is assumed that it will receive a correct response in unit time. The symbol A ƒ  is used to denote an adversary with access to an oracle for computing function ƒ. Following the convention in Bellare, Kilian and Rogaway, incorporated by reference above, the running time of the adversary is defined to be its execution time plus the length of its description. The query complexity of A is defined as the number of queries it makes to its oracle. 
   Finite Function Families. A finite function family, F, is a collection of functions, all of which have domain Dom(F) and range Range(F). The present focus is on function families in which each function in the family can be formally specified by (at least one) “key.” Typically, the key for a function family will be a pre-defined fixed length bit string. For a function family F, and a key k, let F k  denote the function associated with the given key, and it is assumed that computing F k  at any given point of Dom(F) is easy given the key k. 
   Examples. Perhaps the simplest example is the set of all functions with domain I k  and range I l , under the uniform distribution. This family is denoted by Rand k→l . A function in this family can be represented by k2 l  bits—hence an appropriate key space is I k2     l   . Another simple example is the set of all permutations on I l . This family is denoted by Perm l . Any block cipher constitutes a keyed family of permutations. For example, DES has key space I 56 , with domain and range I 64 . DES is described in National Bureau of Standards, Federal Information Processing Standards Publication 46 (1977), the disclosure of which is hereby incorporated by reference. 
   Distinguishability. The concept of distinguishability helps capture the idea of a “computational distance” between two function families. The concept of distinguishability is described in more detail in Goldreich et al., “How to Construct Random Functions,” J. of the ACM 33(4), 792–807, October (1984), the disclosure of which is hereby incorporated by reference. This notion will be useful when pseudorandom functions and permutations are discussed. Suppose that F 0  and F 1  are two function families that have both identical domains and identical ranges. An adversary A will get oracle access to either a function sampled from F 0 , or a function sampled from F 1 . The adversary will not, however, be told whether the oracle really sampled from F 0  or F 1 . The adversary&#39;s goal is to determine which function family was actually sampled. Informally, distinguishability corresponds directly to the adversary&#39;s success rate in making this determination. In particular, let 
                 Adv   A     ⁡     (       F   0     ,     F   1       )       =       Pr   ⁡     [       f   ⁢     ←   R     ⁢       F   0     ⁢     :     ⁢     A   f         =   1     ]       -     Pr   ⁡     [       f   ⁢     ←   R     ⁢       F   1     ⁢     :     ⁢     A   f         =   1     ]           ,         
where the probabilities are taken over the choice of ƒ and A&#39;s internal coin tosses. Now, it can be said that A(t,q,n,∈)-distinguishes F 0  from F 1 , if A runs for time at most t, makes at most q queries to its oracle each length at most n, and Adv A (F 0 ,F 1 )≧∈.
 
   Pseudorandom Functions and Permutations. Pseudorandomness captures the distance between Rand k→l , and another function family F with domain I k  and range I l . That is, it captures the extent to which an adversary can tell apart a function chosen from F with a function chosen at random from the family of all possible functions that have the same domain and range as F. 
   Definition 1. Let F be a keyed function family with domain I k  and range I l . Let A be an adversary that is equipped with an oracle. Then, 
               Adv   F   prf     ⁡     (   A   )       =       Pr   ⁡     [       f   ⁢     ←   R     ⁢     F   :     A   f         =   1     ]       -       Pr   ⁡     [       f   ⁢     ←   R     ⁢       Rand     k   →   l       :     A   f         =   1     ]       .             
For any integers q,t≧0, an insecurity function, Adv ƒ   prƒ (q,t), is defined as:
 
               Adv   F   prf     ⁡     (     q   ,   t     )       =       max   A     ⁢       {       Adv   F   prf     ⁡     (   A   )       }     .             
The above maximum is taken over choices of adversary A that are restricted to running time at most t, and q oracle queries.
 
   The convention of Bellare, Kilian and Rogaway, incorporated by reference above, is used here and the amount of time it takes to perform the sampling operation 
           f   ⁢     ←   R     ⁢   F         
is incorporated into the running time of A as mentioned in the above definition.
 
   The concept of a PseudoRandom Permutation (PRP) family is now considered. This concept was originally defined by Luby et al., “How to Construct Pseudorandom Permutations from Pseudorandom Functions,” SIAM J. of Computing 17(2), 373–386 (1988), the disclosure of which is hereby incorporated by reference herein. The original notion considered the computational indistinguishability between a given family of permutations and the family of all functions. Following the treatment of Bellare, Kilian and Rogaway, incorporated by reference above, the pseudorandomness of a permutation family on I l  is measured in terms of its indistinguishability from Perm l . 
   Definition 2. Let F be a keyed function family with domain and range I l . Let A be an adversary that is equipped with an oracle. Then, 
               Adv   F   prp     ⁡     (   A   )       =       Pr   ⁡     [       f   ⁢     ←   R     ⁢     F   :     A   f         =   1     ]       -       Pr   ⁡     [       f   ⁢     ←   R     ⁢       Perm   l     :     A   f         =   1     ]       .             
For any integers q,t&gt;0, an insecurity function, Adv F   prp (q,t), is defined as:
 
               Adv   F   prp     ⁡     (     q   ,   t     )       =       max   A     ⁢       {       Adv   F   prp     ⁡     (   A   )       }     .             
The above maximum is taken over choices of adversary A that are restricted to running time at most t, and q oracle queries.
 
   Luby, incorporated by reference above, also considered the notion of a strong pseudorandom permutation. In this setting, the adversary is given access to both an oracle that computes the permutation for a given element, and an oracle that computes the inverse of the permutation. 
   Definition 3. Let F be a keyed function family with domain and range I l . Let A be an adversary that is given access to an oracle. Then, 
               Adv   F   prp     ⁡     (   A   )       =       Pr   ⁡     [       f   ⁢     ←   R     ⁢     F   :     A     f   ,     f     -   1               =   1     ]       -       Pr   ⁡     [       f   ⁢     ←   R     ⁢       Perm   l     :     A     f   ,     f     -   1               =   1     ]       .             
For any integers q,t≧0, an insecurity function, Adv F   prp (q,t), is defined as:
 
               Adv   F   prp     ⁡     (     q   ,   t     )       =       max   A     ⁢       {       Adv   F   prp     ⁡     (   A   )       }     .             
The above maximum is taken over choices of adversary A that are restricted to running time at most t, and q oracle queries.
 
   The security of a block cipher against chosen plaintext attacks can be understood by examining the block cipher as a pseudorandom permutation, whereas the security against chosen plaintext and ciphertext attacks can be understood by examining the block cipher as a strong pseudorandom permutation. 
   Universal Hash Functions. Let H be a family of functions with domain D and range S. Also, H comes equipped with an induced distribution (typically uniform). Functions can then be sampled from H according to this distribution. Let ∈ be a “small” constant such that 1/|S|≦∈≦1. 
   Definition 4 (a). H is a universal family of hash functions if for all x,y∈D with x≠y, Pr h∈H [h(x)=h(y)]≦1/|S|. 
   Definition 4 (b). H is an ∈-almost universal family of hash functions if Pr h∈H [h(x)=h(y)]≦∈. An example is the linear congruential hash h(x)=ax+b mod p. 
   Definition 5 (a). H is a Δ-universal-family of hash functions if for all x,y∈D with x≠y, and all δ∈S, Pr h∈H [h(x)−h(y)=δ]≦1/|S|. 
   Definition 5 (b). H is called ∈-almost-Δ-universal if Pr h∈H [h(x)−h(y)=δ]≦∈. An example is the linear hash h a (x)=ax mod p with a≠0. 
   Definition 6 (a). H is a strongly universal family of hash functions if for all x,y∈D with x≠y and all a,b∈S, Pr h∈H [h(x)=a,h(y)=b]≦1/|S| 2 . 
   Definition 6 (b). H is called ∈-almost-strongly-universal family of hash functions if Pr h∈H [h(x)=a,h(y)=b]≦∈/|S|. An example is the linear congruential hash h(x)=ax+b mod p where a is non-zero and p is a prime. 
   A remark can be made that, in Definition 6, if H consists only of permutations, then it will be said that H is a strongly universal family of permutations. Another remark can be made that, in Definition 6, if h is drawn from a Δ-universal family of hash functions then is will be said that h is a Δ-universal hash function. Similarly for the other types of hash function families defined above, it will be said that h is a hash function of the corresponding type. 
   3. FIL PRP to VIL PRP 
   In this section, VIL encoding and decoding techniques are presented that are faster than comparable conventional techniques and that are secure against plaintext attacks. The problem of constructing a variable input length mode of encryption for block ciphers was considered by Bellare and Rogaway, “On the Construction of Variable-Input-Length Ciphers,” Proc. of Fast Software Encryption, Lecture Notes in Comp. Sci. 1636 (1999), the disclosure of which is hereby incorporated by reference. In Bellare and Rogaway, a generic approach is given for solving this problem, and then a specific construction is instantiated. The generic approach involves utilizing a parsimonious pseudorandom function together with a parsimonious encryption scheme. Both CBC-mode encryption and counter-mode encryption (with a random initial counter) serve as examples of parsimonious encryption schemes. In this section, an efficient construction is given for taking an existing fixed input length pseudorandom permutation, and building a variable input length parsimonious pseudorandom function. The techniques of Bellare and Rogaway will be reviewed first in this section, then the techniques of the present invention will be discussed, beginning with the “VIL Parsimonious PRF” section below. 
   Parsimonious PRF. Let F be a keyed function family with domain I k  and range I n , where k≧n. Then F is called a parsimonious family if, for any key a∈Keys(F), and any input x∈I k , the last n bits of x are uniquely determined by the remaining bits of x, the key a, and F a (x). 
   Parsimonious Encryption. A parsimonious encryption scheme may be defined via three algorithms S=(K,E,D). The algorithm K is a key-generation algorithm, and returns a random key k to be used for the encryption. The algorithm E takes this key k and the message M, picks a random, fixed length IV, and then encrypts M to get a ciphertext C=(IV;C*), where C* and M have the same length. 
   General Scheme for VIL Block Ciphers. Given a parsimonious PRF and encryption scheme, it is possible to construct a general VIL scheme F as follows. Let G be the parsimonious PRF whose domain is the message space and whose range is I n . Let Recover denote G&#39;s corresponding recovery algorithm that obtains the last n bits of the message M given the key to G, the first |M|−n bits of M, and the output of G. Let S=(K,E,D) be a parsimonious encryption scheme. Let K prf  and K enc  be the secret keys for the parsimonious PRF and encryption schemes respectively. Let M pref  be the first |M|−n bits of M. The encryption and decryption algorithms are shown below. 
   Algorithm Encrypt K prf ; K enc  (M) 
   
     
       
         
           σ 
           = 
           
             
               G 
               
                 K 
                 prf 
               
             
             ⁡ 
             
               ( 
               M 
               ) 
             
           
         
       
     
     
       
         
           
             C 
             pref 
           
           = 
           
             
               
                 E 
                 K 
               
               enc 
             
             ⁡ 
             
               ( 
               
                 
                   M 
                   pref 
                 
                 ; 
                 σ 
               
               ) 
             
           
         
       
     
     
       
         
           
             return 
             ⁢ 
             
                 
             
             ⁢ 
             C 
           
           = 
           
             ( 
             
               σ 
               ⁢ 
               
                   
               
               ; 
               
                 C 
                 pref 
               
             
             ) 
           
         
       
     
   
   Algorithm Decrypt K prf , K enc  (C) 
   
     
       
         
           
             Let 
             ⁢ 
             
                 
             
             ⁢ 
             σ 
             ⁢ 
             
                 
             
             ⁢ 
             be 
             ⁢ 
             
                 
             
             ⁢ 
             first 
             ⁢ 
             
                 
             
             ⁢ 
             n 
             ⁢ 
             
                 
             
             ⁢ 
             bits 
             ⁢ 
             
                 
             
             ⁢ 
             of 
             ⁢ 
             
                 
             
             ⁢ 
             
               C 
               . 
               
                 
 
               
               ⁢ 
               
                 M 
                 pref 
               
             
           
           = 
           
             
               D 
               
                 K 
                 enc 
               
             
             ⁡ 
             
               ( 
               C 
               ) 
             
           
         
       
     
     
       
         
           
             M 
             suff 
           
           = 
           
             Recover 
             ⁢ 
             
                 
             
             ⁢ 
             
               
                 K 
                 prf 
               
               ⁡ 
               
                 ( 
                 
                   
                     M 
                     
                       pref 
                       , 
                     
                   
                   ⁢ 
                   σ 
                 
                 ) 
               
             
           
         
       
     
     
       
         
           
             return 
             ⁢ 
             
                 
             
             ⁢ 
             M 
           
           = 
           
             ( 
             
               
                 m 
                 pref 
               
               ; 
               
                 M 
                 suff 
               
             
             ) 
           
         
       
     
   
   Security for VIL Mode Encryption. Before giving any security analysis for general VIL Mode block cipher encryption, security is discussed for parsimonious encryption. The security for a parsimonious encryption scheme is defined by the adversary&#39;s inability to distinguish the encryption of a message from the encryption of a randomly chosen string of equal length. More formally, if S=(K,E,D) is a parsimonious encryption scheme, and A is a distinguishing adversary, then 
               Adv   A   priv     ⁡     (   S   )       =       Pr   ⁡     [       K   ←     K   :     A     ɛ     K     (           )               =   1     ]       -     P   ⁢           ⁢       r   ⁡     [       K   ←     K   :     A     ɛ     K     (     $   ||     )               =   1     ]       .               
In the first experiment, the oracle returns a random encryption of the message under the given key K, and in the second, a random encryption of a random string of the same length as the message (under the key K) is returned. Define Adv S   priv (t,q,μ) as max A {Adv S   priv (A)}. Here the maximum is taken over all adversaries A who are restricted to time t, and make at most q oracle queries whose total length is no more than μ bits.
 
   Bellare and Rogaway, incorporated by reference above, proved the following relating the security of their general VIL mode block cipher construction in terms of its constituent parsimonious PRF and encryption scheme: Suppose B is VIL block cipher constructed from the parsimonious PRF family F and the parsimonious encryption scheme S. Moreover, suppose that the functions in F have range I n . Then the following is true: 
                 Adv   B   prp     ⁡     (     t   ,   q   ,   μ     )       ≤         Adv   F   prf     ⁡     (       t   ′     ,   q   ,   μ     )       +       Adv   S   priv     ⁡     (       t   ′     ,   q   ,   μ     )       +       q   2       2   n           ,         
where t′=t+O(qn+μ).
 
   VIL Parsimonious PRF. It is now shown, in accordance with a preferred embodiment of the present invention, how to efficiently construct a parsimonious PRF that can handle variable input lengths. As pointed out before, the present construction is the most efficient known parsimonious PRF construction. Combining this parsimonious PRF with an existing parsimonious encryption scheme, a very efficient scheme for VIL block cipher encryption is developed. For now, it is assumed that there is a PRP over I n  (any block cipher will work). It is now shown how to construct a parsimonious PRF family with domain I n+b  and range I n , where n≦b. 
   Construction  1 . Let P be any pseudorandom permutation family on I n , and let H be an ∈-almost Δ-universal family of hash functions with domain I b  and range I n . A parsimonious PRF ParG is constructed with domain I n+b  and range I n  as follows: 
   A key of a function sampled from ParG is a pair  h,g  where h is sampled from H and g is sampled from P. For every input x∈I n+b , the value of ParG h,g  is defined as
 
 ParG   h,g ( x )= g ( h ( x[ 1 . . .  b] )⊕ x[b+ 1 . . .  n+b] ).
 
   Although an eXclusive-OR (XOR, or “⊕”) function is used above and throughout this detailed description, this function may be replaced by an addition operation in a quasigroup. As is known in the art, a quasigroup is a set with a binary operation “+” with the property that, for a,b∈Q, there are unique solutions to the equations a+x=b and y+a=b. 
   A remark can be made that, if a VIL parsimonious PRF is needed to be constructed for which b&lt;n, a fixed padding may be appended to the input x, to achieve total length 2n. The security bounds proven below remain the same, and almost the exact same security proof will go through. Before security is proved, it is observed that ParG is parsimonious: given the output of σ of ParG, its key, and the value x[1 . . . b], it is not difficult to see that x[b+1 . . . n+b]=g −1 (σ)⊕h(x[1 . . . b]). 
   A diagram of a construction that implements Construction  1  above is shown in  FIG. 2 . Referring now to this figure, a construction  200  is shown accepting an input  205  and producing an output  240 . Construction  200  comprises block  210  (denoted as “G ” in the figure), an intermediate result  230 , and an encryption function  235 . Block  210  comprises a hash function  215 , an XOR function  220 , and a block cipher  225 . Block  210  accepts the prefix of the input  205  (shown in the figure as message M) and produces an output of σ. The prefix, M pref , has b bits, while the output σ has n bits. Thus, block  210  reduces the size of the prefix M pref  in this example. Block  210  is the ParG as described above. 
   The hash function  215 , as described above, is preferably a Δ-universal hash function, which converts the b bits of the prefix M pref  to n bits of output. The output of the hash function  215  is added to the suffix, M suff , by XOR  220 . The output of the XOR  220  is then operated on by block cipher g 1 , which uses a key, k 1  (the key is not shown). Intermediate result  230  comprises the prefix M pref  and σ. 
   Encryption function  235  is a parsimonious encryption function, as described above. The output of the encryption function  235  is C pref , where C pref =E K     enc   (M pref ;σ). While other random numbers may be used in the encryption block  235 , the number σ is preferably used. There are a variety of parsimonious encryption that may be used as encryption function  235 . In particular, two suitable parsimonious encryptions, as stated above, are counter-mode encryption and Cipher Block Chaining (CBC) encryption. 
   In counter-mode encryption, the encryption is as follows: (1) perform a block cipher using a second key on σ (i.e., g 2 (σ)); (2) XOR the result of the block cipher with a first block of M pref  to create a first block of C pref ; (3) perform g 2 (σ+1); (4) XOR the result of the g 2 (σ+1) with a second block of M pref  to create a second block of C pref ; (5) continue this process until all blocks of M pref  have been processed. 
   In CBC, the encryption is as follows: (1) take σ and XOR with a first block of M pref , then encrypt the output of this addition with a block cipher using a second key, and call the output O 1 ; (2) XOR O 1  with a second block of M pref , then encrypt the output of this addition with the block cipher, and call the output O 2 ; (3) XOR O 2  with a third block of M pref , then encrypt the output of this addition with the block cipher, and call the output O 3 ; continue this process until all blocks of M pref  have been processed. At the end of this process, C pref  has been computed. 
   The construction  200  produces an output  240 , which comprises σ and C pref  and which is n+b bits in size. Thus, construction  210  takes an input message of n+b bits in size and produces an encrypted output that is n+b bits in size. A benefit to construction  200  is increased speed over comparable conventional constructions. The construction  210  of the present invention is about twice as fast as the VIL mode of disclosed in Bellare and Rogaway. 
   A method for decryption of output  240  is shown in  FIG. 3 . Turning now to  FIG. 3 , method  300  outlines the basic steps involved in decrypting the output of Construction  1 . In step  305 , an encrypted message (or cyphertext) of σ and C pref  is received. In step  310 , the prefix M pref  is determined by decrypting C pref . As explained above, there are multiple possible encryption and corresponding decryption schemes. For example, in counter-mode decryption, the decryption is as follows: (1) perform a block cipher using a second key on σ (i.e., g 2 (σ)); (2) XOR the result of the block cipher with a first block of C pref  to create a first block of M pref ; (3) perform g 2 (σ+1); (4) XOR the result of the g 2 (σ+1) with a second block of C pref ; (5) continue this process until all blocks of C pref  have been processed. The output is then M pref , which is the output of each XOR. 
   It should be noted that a benefit to using σ as the random number input to the encryption/decryption function is that σ is available at the decryption location. Consequently, efforts to synchronize the random number input between encryption and decryption locations need not be made. 
   After step  310 , M pref  and σ are known, but M suff  has yet to be determined. In step  315 , an inverse block cipher of σ is performed (i.e., g 1   −1 (σ)). It is known that σ=g 1 (h(M pref )⊕M suff ); therefore, g 1   −1 (σ)=h(M pref )⊕M suff . Consequently, M suff  may be determined through h(M pref )⊕g 1   −1 (σ)=M suff . In step  320 , a hash function is applied to M pref , and, in step  325 , the XOR between h(M pref ) and g 1   −1 (σ) is performed. After step  325 , both M pref  and M suff  have been determined. 
   The security of this aspect of the present invention may be proved as follows. Define ParG as in Construction  1 . Let ∈ 1  be the parameter associated with the Δ-universal family of hash functions in the construction, and suppose that the underlying pseudorandom permutation family P utilized by ParG is (t,q,n,∈ 2 )-secure. Then, for any adversary A restricted to t time steps, and q oracle queries of length at most n+b: 
   
     
       
         
           
             
               
                 
                   
                     Adv 
                     ParG 
                     prf 
                   
                   ⁡ 
                   
                     ( 
                     A 
                     ) 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     Pr 
                     ⁡ 
                     
                       [ 
                       
                         
                           g 
                           ⁢ 
                           
                             ← 
                             R 
                           
                           ⁢ 
                           
                             G 
                             : 
                             
                               A 
                               g 
                             
                           
                         
                         = 
                         1 
                       
                       ] 
                     
                   
                   - 
                   
                     Pr 
                     ⁡ 
                     
                       [ 
                       
                         
                           g 
                           ⁢ 
                           
                             ← 
                             R 
                           
                           ⁢ 
                           
                             
                               Rand 
                               
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     n 
                                     + 
                                     b 
                                   
                                   -&gt; 
                                   n 
                                 
                               
                             
                             : 
                             
                               A 
                               g 
                             
                           
                         
                         = 
                         1 
                       
                       ] 
                     
                   
                 
               
             
           
           
             
               
                 ≤ 
                   
                 ⁢ 
                 
                   
                     ( 
                     
                       
                         ( 
                         
                           
                             
                               q 
                             
                           
                           
                             
                               2 
                             
                           
                         
                         ) 
                       
                       · 
                       
                         ε 
                         1 
                       
                     
                     ) 
                   
                   + 
                   
                     
                       ε 
                       2 
                     
                     . 
                   
                 
               
             
           
         
       
     
   
   First, denote by G the function family obtained if Construction  1  is implemented, but where the pseudorandom permutation family P is replaced with the truly random function family Rand n→n . Then, the proof of the security of this aspect of the present invention will follow immediately if the following inequality is established: 
   
     
       
         
           
             
               
                 
                   
                     Adv 
                     ParG 
                     prf 
                   
                   ⁡ 
                   
                     ( 
                     A 
                     ) 
                   
                 
                 = 
                   
                 ⁢ 
                 
                   
                     Pr 
                     ⁡ 
                     
                       [ 
                       
                         
                           g 
                           ⁢ 
                           
                             ← 
                             R 
                           
                           ⁢ 
                           
                             G 
                             : 
                             
                               A 
                               g 
                             
                           
                         
                         = 
                         1 
                       
                       ] 
                     
                   
                   - 
                   
                     Pr 
                     ⁡ 
                     
                       [ 
                       
                         
                           g 
                           ⁢ 
                           
                             ← 
                             R 
                           
                           ⁢ 
                           
                             
                               Rand 
                               
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     n 
                                     + 
                                     b 
                                   
                                   -&gt; 
                                   n 
                                 
                               
                             
                             : 
                             
                               A 
                               g 
                             
                           
                         
                         = 
                         1 
                       
                       ] 
                     
                   
                 
               
             
           
           
             
               
                 ≤ 
                   
                 ⁢ 
                 
                   
                     ( 
                     
                       
                         
                           q 
                         
                       
                       
                         
                           2 
                         
                       
                     
                     ) 
                   
                   · 
                   
                     
                       ε 
                       1 
                     
                     . 
                   
                 
               
             
           
         
       
     
   
   In order to establish this inequality, first let Φ denote the oracle (either a function from G or Rand n+b→n ) that A accesses. If A makes the query x, then it is asking to obtain the value Φ(x). The query-answer pair for the i th  query that A makes is defined as:  x i ,y i   , where x t ∈I n+b  and y i ∈I n . It is assumed that A makes exactly q queries, and the sequence  x i ,y i   , . . . , x q ,y q    is called the transcript of A. The standard assumption is made that A is also deterministic (or assume that it is provided with the random tape that maximizes its advantage). Under this assumption, the i th  query made by A can be determined from the first i−1 query-answer pairs in A&#39;s transcript. 
   Definition 7. Let C A [{ x i ,y i   , . . . , x i−1 ,y i−1   }] denote the i th  query A makes as a function of the first i−1 query-answer pairs in A&#39;s transcript. Let C A [{ x i ,y i   , . . . , x q ,y q   }] denote the output A gives as a function of its transcript. 
   Definition 8. The random variables T G , T Rand     n+b→n    denote the transcript seen by A when its queries are answered by functions drawn from G, Rand n+b→n , respectively. 
   Observe that according to the above definitions and assumptions, A G  and C A  (G) denote the same random variable as do A Rand     n+b→n    and C A (T Rand     n+b→n   ). 
   A bound is now obtained on the advantage A will have in distinguishing between T G  and T Rand     n+b→n   . It turns out that T G  and T Rand     n+b→n    are identically distributed unless some rare event depending upon the choice of hash function h in G occurs. This event is called “BAD” herein and a bound is obtained on the probability that it actually occurs. Before proceeding, a convention is stated as follows: 
   For any possible transcript σ={ x i ,y i   , . . . ,  x q ,y q   } produced by A, it is assumed from now on that if i≠j then x i ≠x j . This formalizes the concept that A never repeats a query if it can determine the answer from a previous query-answer pair. 
   Definition 9. For every specific choice of ∈-universal hash function h define BAD(h) to be set of all possible transcripts σ={ x 1 ,y 1   , . . . , x q ,y q   } produced by A satisfying the following: there exists 1≦i&lt;j≦m such that h(x i [1 . . . b])+x i [b+1 . . . n+b]=h(x j [1 . . . b])+x j [b+1 . . . n+b]. 
   The probability that this bad event occurs is now bounded through the following argument. Let h∈H be an ∈ 1 -almost-Δ-universal hash function. Then, for any possible transcript σ={ x 1 ,y 1   , . . . , x q ,y q   } produced by A, it is true that Pr h [σ∈BAD(h)]≦( 2   q )∈ 1 . 
   A proof of the statement in the previous paragraph is as follows. For a fixed i,j with 1≠j, then it is known by statements given above that x i ≠x j . Thus, if x i [1 . . . b]=x j [1 . . . b] it must be that x i [b+1 . . . n+b]≠x j [b+1 . . . n+b], from which it follows that h(x i [1 . . . b])+x i [b+1 . . . n+b]≠h(x j [1 . . . b])+x j [b+1 . . . n+b]. If x i [1 . . . b]≠x j [1 . . . b] then by definition of h, it follows that Pr h [h(x i [1 . . . b])+x i [b+1 . . . n+b]=h(x j [1 . . . b])+x j [b+1 . . . n+]]≦∈ 1 . If a union bound is applied, and the sum is taken over all possible pairs i,j, then the statement made above immediately follows. 
   An important observation for proving the correctness of Construction  1  is the following. Let σ={ x 1 ,y 1   , . . . ,  x q ,y q   } be a possible transcript produced by M. Then: 
                 Pr   G     [       T   G     =     σ   |     σ   ∉     Bad   ⁡     (   h   )             ]     =       Pr     Rand             ⁢       n   +   b     -&gt;   n           [       T     Rand             ⁢       n   +   b     -&gt;   n           =   σ     ]       ,         
where h is part of the key for G.
 
   A proof of the statements of the previous paragraph is as follows. Since Rand n+b→n  represents a truly random function, and the inputs x i  to Rand n+b→n  are distinct, it follows that Pr Rand     n+b→n    [T Rand     n+b→n=σ]=   2 −nq  Now, if σ∉BAD(h), it follows that h(x i [1, . . . ,b])+x i [b+1, . . . ,n+b]≠h(x j [1, . . . ,b])+x j [b+1, . . . ,n+b] for all 1≦i&lt;j≦q. Thus, if the key for G is  h,g , then all the inputs to g will be distinct. Therefore the output values will be independently and identically distributed. It can finally be determined that Pr G [T G =σ|σ∉BAD(h)]=2 −nq , and the lemma follows. 
   The main security theorem may now be proven as follows. 
   Let T 1  be the set of all transcripts that A can produce for which C A (σ)=1 and let T 2  be the set of all transcripts that A can produce for which C A (σ)=0. Let T=T 1 ∪T 2 . Note that T denotes the set of all possible transcripts that A could produce. The advantage that A will have in distinguishing between G and Rand n+b→n  may be bounded as follows: 
   
     
       
         
           
             
               
                 
                   
                      
                     
                       
                         Pr 
                         ⁡ 
                         
                           [ 
                           
                             
                               g 
                               ⁢ 
                               
                                 ← 
                                 R 
                               
                               ⁢ 
                               
                                 
                                   Rand 
                                   
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                                 : 
                                 
                                   A 
                                   
                                     Rand 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                               
                             
                             = 
                             1 
                           
                           ] 
                         
                       
                       - 
                       
                         Pr 
                         ⁡ 
                         
                           [ 
                           
                             
                               g 
                               ⁢ 
                               
                                 ← 
                                 R 
                               
                               ⁢ 
                               
                                 G 
                                 : 
                                 
                                   A 
                                   g 
                                 
                               
                             
                             = 
                             1 
                           
                           ] 
                         
                       
                     
                      
                   
                   = 
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 ( 
                 1 
                 ) 
               
             
           
           
             
               
                 
                     
                 
                 ⁢ 
                 
                   
                      
                     
                       
                         
                           Pr 
                           
                             Rand 
                             
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   n 
                                   + 
                                   b 
                                 
                                 -&gt; 
                                 n 
                               
                             
                           
                         
                         [ 
                         
                           
                             
                               C 
                               A 
                             
                             ⁡ 
                             
                               ( 
                               
                                 T 
                                 
                                   Rand 
                                   
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                               
                               ) 
                             
                           
                           = 
                           1 
                         
                         ] 
                       
                       - 
                       
                         
                           Pr 
                           G 
                         
                         ⁡ 
                         
                           [ 
                           
                             
                               
                                 C 
                                 A 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   T 
                                   G 
                                 
                                 ) 
                               
                             
                             = 
                             1 
                           
                           ] 
                         
                       
                     
                      
                   
                   = 
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 ( 
                 2 
                 ) 
               
             
           
           
             
               
                 
                     
                 
                 ⁢ 
                 
                    
                   
                     
                       
                         ∑ 
                         
                           σ 
                           ∈ 
                           T 
                         
                       
                       ⁢ 
                       
                         
                           
                             Pr 
                             R 
                           
                           [ 
                           
                             
                               
                                 C 
                                 A 
                               
                               ⁡ 
                               
                                 ( 
                                 σ 
                                 ) 
                               
                             
                             = 
                             
                               
                                 1 
                                 | 
                                 
                                   T 
                                   
                                     Rand 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                               
                               = 
                               σ 
                             
                           
                           ] 
                         
                         · 
                         
                           
                             Pr 
                             
                               Rand 
                               
                                 
                                   n 
                                   + 
                                   b 
                                 
                                 -&gt; 
                                 n 
                               
                             
                           
                           [ 
                           
                             
                               T 
                               
                                 Rand 
                                 
                                   
                                     n 
                                     + 
                                     b 
                                   
                                   -&gt; 
                                   n 
                                 
                               
                             
                             = 
                             σ 
                           
                           ] 
                         
                       
                     
                     - 
                   
                 
               
             
             
               
                 ( 
                 3 
                 ) 
               
             
           
           
             
               
                 
                   
                     
                       ∑ 
                       
                         σ 
                         ∈ 
                         T 
                       
                     
                     ⁢ 
                     
                       
                         
                           Pr 
                           G 
                         
                         [ 
                         
                           
                             
                               C 
                               A 
                             
                             ⁡ 
                             
                               ( 
                               σ 
                               ) 
                             
                           
                           = 
                           
                             
                               1 
                               | 
                               
                                 T 
                                 G 
                               
                             
                             = 
                             σ 
                           
                         
                         ] 
                       
                       · 
                       
                         
                           Pr 
                           
                             Rand 
                             
                               
                                 n 
                                 + 
                                 b 
                               
                               -&gt; 
                               n 
                             
                           
                         
                         [ 
                         
                           
                             T 
                             G 
                           
                           = 
                           σ 
                         
                         ] 
                       
                     
                   
                    
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 ( 
                 4 
                 ) 
               
             
           
         
       
     
   
   Now, if σ∈T 1 , then Pr[C A (σ)=1]=1, and if σ∈T 2 , then Pr[C A (σ)=1]=0. Expressions (3) and (4) may be simplified to the following: 
   
     
       
         
           
             
               
                 
                    
                   
                     
                       ∑ 
                       
                         σ 
                         ∈ 
                         
                           T 
                           1 
                         
                       
                     
                     ⁢ 
                     
                       ( 
                       
                         
                           
                             Pr 
                             
                               Rand 
                               
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     n 
                                     + 
                                     b 
                                   
                                   -&gt; 
                                   n 
                                 
                               
                             
                           
                           [ 
                           
                             
                               T 
                               
                                 Rand 
                                 
                                   
                                       
                                   
                                   ⁢ 
                                   
                                     
                                       n 
                                       + 
                                       b 
                                     
                                     -&gt; 
                                     n 
                                   
                                 
                               
                             
                             = 
                             σ 
                           
                           ] 
                         
                         - 
                         
                           
                             Pr 
                             G 
                           
                           ⁡ 
                           
                             [ 
                             
                               
                                 T 
                                 G 
                               
                               = 
                               σ 
                             
                             ] 
                           
                         
                       
                       ) 
                     
                   
                    
                 
                 ≤ 
               
             
             
               
                 ( 
                 5 
                 ) 
               
             
           
           
             
               
                 
                   
                     
                        
                       
                         ( 
                         
                           
                             
                               Pr 
                               
                                 Rand 
                                 
                                   
                                     n 
                                     + 
                                     b 
                                   
                                   -&gt; 
                                   n 
                                 
                               
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   T 
                                   
                                     Rand 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                                 = 
                                 σ 
                               
                               ] 
                             
                           
                           - 
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             
                               
                                 Pr 
                                 G 
                               
                               ⁡ 
                               
                                 [ 
                                 
                                   
                                     T 
                                     G 
                                   
                                   = 
                                   
                                     σ 
                                     | 
                                     
                                       σ 
                                       ∉ 
                                       
                                         Bad 
                                         ⁡ 
                                         
                                           ( 
                                           h 
                                           ) 
                                         
                                       
                                     
                                   
                                 
                                 ] 
                               
                             
                             ) 
                           
                           · 
                           
                             
                               Pr 
                               G 
                             
                             ⁡ 
                             
                               [ 
                               
                                 σ 
                                 ∉ 
                                 
                                   Bad 
                                   ⁡ 
                                   
                                     ( 
                                     h 
                                     ) 
                                   
                                 
                               
                               ] 
                             
                           
                         
                          
                       
                       + 
                     
                   
                 
               
             
             
               
                 ( 
                 6 
                 ) 
               
             
           
           
             
               
                 
                   
                     
                        
                       
                         
                           ∑ 
                           
                             σ 
                             ∈ 
                             
                               T 
                               1 
                             
                           
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               
                                 Pr 
                                 
                                   Rand 
                                   
                                     
                                       n 
                                       + 
                                       b 
                                     
                                     -&gt; 
                                     n 
                                   
                                 
                               
                               [ 
                               
                                 
                                   T 
                                   
                                     Rand 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                                 = 
                                 σ 
                               
                               ] 
                             
                             - 
                           
                           ⁢ 
                           
                               
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             
                               Pr 
                               G 
                             
                             [ 
                             
                               
                                 T 
                                 G 
                               
                               = 
                               
                                 σ 
                                 | 
                                 
                                   σ 
                                   ∈ 
                                   
                                     Bad 
                                     ⁡ 
                                     
                                       ( 
                                       h 
                                       ) 
                                     
                                   
                                 
                               
                             
                             ] 
                           
                           ) 
                         
                         · 
                         
                           
                             Pr 
                             G 
                           
                           [ 
                           
                             σ 
                             ∈ 
                             
                               Bad 
                               ⁡ 
                               
                                 ( 
                                 h 
                                 ) 
                               
                             
                           
                           ] 
                         
                       
                        
                     
                   
                 
               
             
             
               
                 ( 
                 7 
                 ) 
               
             
           
         
       
     
   
   Now, observe that, from the observation for proving the correctness of Construction  1  described above, it follows that expression (6) is equal to 0. The proof of may be completed as follows: 
   
     
       
         
           
             
               
                 
                   
                     
                        
                       
                         
                           ∑ 
                           
                             σ 
                             ∈ 
                             
                               T 
                               1 
                             
                           
                         
                         ⁢ 
                         
                           ( 
                           
                             
                               
                                 Pr 
                                 
                                   Rand 
                                   
                                     
                                       n 
                                       + 
                                       b 
                                     
                                     -&gt; 
                                     n 
                                   
                                 
                               
                               [ 
                               
                                 
                                   T 
                                   
                                     Rand 
                                     
                                       
                                         n 
                                         + 
                                         b 
                                       
                                       -&gt; 
                                       n 
                                     
                                   
                                 
                                 = 
                                 σ 
                               
                               ] 
                             
                             - 
                           
                         
                       
                     
                   
                 
                 
                   
                     
                       
                         
                           
                             
                               
                                 Pr 
                                 G 
                               
                               [ 
                               
                                 
                                   T 
                                   G 
                                 
                                 = 
                                 
                                   σ 
                                   | 
                                   
                                     σ 
                                     ∉ 
                                     
                                       Bad 
                                       ⁡ 
                                       
                                         ( 
                                         h 
                                         ) 
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                             ) 
                           
                           · 
                           
                             
                               Pr 
                               G 
                             
                             [ 
                             
                               σ 
                               ∉ 
                               
                                 Bad 
                                 ⁡ 
                                 
                                   ( 
                                   h 
                                   ) 
                                 
                               
                             
                             ] 
                           
                         
                          
                       
                       ≤ 
                     
                   
                 
               
             
             
               
                 ( 
                 8 
                 ) 
               
             
           
           
             
               
                 
                   
                     max 
                     σ 
                   
                   ⁢ 
                   
                     
                       Pr 
                       G 
                     
                     ⁡ 
                     
                       [ 
                       
                         σ 
                         ∈ 
                         
                           Bad 
                           ⁡ 
                           
                             ( 
                             h 
                             ) 
                           
                         
                       
                       ] 
                     
                   
                 
                 ≤ 
               
             
             
               
                 ( 
                 9 
                 ) 
               
             
           
           
             
               
                 
                   ( 
                   
                     
                       
                         q 
                       
                     
                     
                       
                         2 
                       
                     
                   
                   ) 
                 
                 ⁢ 
                 
                   
                     ε 
                     1 
                   
                   . 
                 
               
             
             
               
                 ( 
                 10 
                 ) 
               
             
           
         
       
     
   
   Equation (9) follows from (8) by observing that for any positive values a,b, it holds that |a−b|≦max{a,b}. Moreover, the quantities being dealt with are probabilities, so they sum to at most 1. The last equation follows from the previous by applying the fact, proven above, that, for any possible transcript σ={ x 1 ,y 1   , . . . , x q ,y q   } produced by A, it is true that Pr h [σ∈BAD(h)]≦( 2   q )∈ 1 . 
   4. FIL PRP to VIL Strong-PRP 
   This section provides techniques for VIL encryption and decryption that are secure from both chosen plaintext and chosen ciphertext attacks. Now it is shown how to convert a fixed input length block cipher, which is secure against either chosen plaintext attacks or chosen ciphertext attacks, to a VIL block cipher, which is secure against both chosen plaintext and ciphertext attacks. The idea is to first treat the original PRP as pseudorandom function and create two different variable input length pseudorandom functions of specific lengths from it. Finally, these functions are used in an unbalanced Feistel network together with universal hash functions in the right places to yield the desired result. The construction of the present invention and outlined in this section works when it is desirable to convert a block cipher on I n  to a cipher on I n+b  where b≧n. These ideas can be extended to work for the case when b&lt;n, but there is a loss in security. 
   Construction  2 . In this aspect of the invention, let P be any pseudorandom permutation family on I n , let H be a family of pairwise independent permutations (i.e., strongly universal hash permutations) on I n+b , and let H′ be a universal family of hash functions with domain I b  and range I n . Define ƒ 1  and ƒ 2  as follows:
 
 ƒ   1 ( x )= P   k     0   ( h   1 ′( x )),
 
 ƒ   2 ( S )=( P   k     1   ( S ), p   k     2   ( S ), . . . , P   k     r   ( S ))[1, . . . , b], 
 
where
 
           r   =     ⌈     b   n     ⌉           
and P k     0   , P k     1   , . . . ,P k     r    are independently keyed permutations drawn from P, and h 1 ′ is drawn from H′. The notation [1, . . . ,b] means that ƒ 2 (S) operates on b bits. Now, define a new permutation family P′ which maps input X∈i n+b  to
 
           h   2     -   1           
(S,T) where:
 y=h(x),   S=y[ 1, . . . , n]⊕ƒ   1 ( y[n+ 1, . . . , n+b] ), and   T=y[n+ 1, . . . , n+b]⊕ƒ   2 ( S ). 
   A diagram of a construction that implements Construction  2  above is shown in  FIG. 4 . Referring now to this figure, a construction  400  is shown accepting an input  405  and producing an output  455 . Construction  400  comprises a first hash function  410 , a number of intermediate values  415 ,  430 , and  445 , two functions  420  and  435 , two XOR operators  425  and  440 , and an inverse of a second hash function  450 . 
   The hash function  410  operates on the input, x,  405  to produce an output, y,  415 . The output  415  is into two portions, one with n bits (y[1 . . . n]) and one with b bits (y[(n+1) . . . (n+b)]). The first function  420  operates on the b bits of Y and produces an output having n bits. Generally, b≧n, although this is not strictly required. The first function  420  is preferably a block cipher, which uses a first key, and that operates on an output of a universal hash function. Mathematically, first function  420  preferably is 
                 f   1     ⁡     (   x   )       =       p     k   0       ⁡     (       h   1   ′     ⁡     (   x   )       )         ,         
as described above.
 
   The output of the first function  420  is XORed by XOR  425  with the n bits of y (i.e., y[1 . . . n]). The result is S, stored in intermediate value  430 , and operated on by a second function  435 . Second function  435  accepts n bits as input and outputs b bits. The second function  435  is preferably ƒ 2 (S)=(P k     1   (S), p k     2   (S), . . . , p k     r   (S))[1, . . . ,b], as described above. The output of function  435  is XORed by XOR  440  with the b bits of y[(n+1) . . . (n+b)]. The output of the XOR  440  is T. The output  455  (of h 2   −1 (S,T)) is determined by performing an inverse hash function on the intermediate value  445 . 
   A benefit to the construction  400  is high security (strong-PRP) and variable input. A conventional construction only support input lengths of k and integer multiples (such as 2k and 3k) thereof. With construction  400 , there is no such limitation, and the input can be of any length. 
     FIG. 5  shows a method for decrypting output  455  of  FIG. 4 . Turning now to  FIG. 5 , method  500  starts when an encrypted message h 2   −1 (S,T) is received. A hash function is performed to determine S and T in step  510 . Mathematically, this step performs h 2 (S,T). It should be noted that (S,T)=h 2 (h 2   −1 (S,T)). It is known that T=y[n+1, . . . ,n+b]⊕ƒ 2 (S). Therefore, T⊕ƒ 2 (S)=y[n+1, . . . ,n+b]. In step  515 , ƒ 2 (S) is determined and this result is XORed with T to determine y[n+1, . . . ,n+b]. 
   It is also known that S=y[1, . . . ,n]⊕ƒ 1 (y[n+1, . . . ,n+b]). Therefore, S⊕ƒ 1 (y[n+1, . . . ,n+b])=y[1, . . . ,n]. Consequently, in step  520 , ƒ 1 (y[n+1, . . . ,n+b]) is determined and this result is XORed with S to determine y[1, . . . ,b]. In step  525 , an inverse of the first hash function is taken to determine the input message, x. Mathematically, this step performs x=h 1   −1 (y). 
   The following may be proven. Let P be a 
             (     t   ,       (     1   +     ⌈     b   n     ⌉       )     ⁢   q     ,   n   ,     ∈   1       )     -   secure         
pseudorandom permutation family on I n , let H be a family of pairwise independent permutations on I n+b , let H′ be an ∈ 2  universal family of hash functions with domain I b  and range I n , and let P′ be the permutation family defined above. Then P′ is (t,q,n+b,epsilon′) secure where:
 ∈′=( 2   q )(½ n +½ b +½ n+b−1 +∈ 2 )∈ 1 . 
   The proof follows by first utilizing the framework of Naor and Reingold&#39;s (discussed in Naor and Reingold, already incorporated by reference above) which can be used to analyze unbalanced Feistel networks, when the underlying round functions are truly random. The security of Construction  2  may be analyzed by several applications of the triangle inequality in a hybrid argument in which the truly random functions are replaced with ƒ 1  and ƒ 2  as above. 
   It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention.