How can AES + cycle walking be used as an FPE? I'm a bit confused after reading several articles that seem to provide conflicting information.  Basically I was wondering if AES by itself can be used as an FPE? And if so is this something computationally prohibitive, or something reasonable to do.  Furthermore how can we use AES by itself + cycle walking?  

According to this paper it says one of the methods for FPE is


  5.2 Cycle walking Method "The  cycle  walking  works  by  encrypting  the  plaintext  by repeatedly   applying   AES   or   3DES   until the
  cipher   text becomes in acceptable range. The duration for ciphering
  is not deterministic. "


If this is the case, what is the general construct for this (I.e. how to set up your AES encryptor, key, IV, mode etc)

In that paper they also have a table that summarizes the speed of this method compared to others. 


  


But in another article it is stated that it would be prohibitively expensive to use cyclewalking alone since it would take many iterations to get a value in the desired range.


  "So, why can't we just use cycle-walking? Because it only works well
  if the block size is approximately right—if the size of the valid set
  is a lot smaller than the block size of the cipher, then you have to
  do a lot of iterations in order to get an in-range result. So, you
  can't use a 64-bit block cipher in order to encrypt an SSN because you
  end up having to do a prohibitive number if iterations; you need to
  use L-R to construct a block cipher of approximately the right size
  and then use cycle-walking to shave off the last few values."


I'm not sure if the result 1500 milliseconds in the comparison table above is considered prohibitive or not for such an encryption scheme.
The general construction to encrypt (inputs of less than 128 bits) with cycle-walking is:

# IN, OUT are 128-bit unsigned integers in the range 0..MAX
OUT = AES(K, IN)
while OUT &gt; MAX do OUT = AES(K, OUT)
return OUT


AES is going to permute your 128-bit input into a seemingly-random 128-bit output. About $1/2$ of the time the top bit of the output will be 0.  About $1/4$ of the time the top 2 bits will both be 0.  About $1/(2^n)$ of the time the top n bits will all be zero.

The construction above keeps looping until your output is coincidentally in the desired range.  This is non-deterministic: it could happen on the first iteration, or on the billionth.  Statistically it is likely to happen, on average, around iteration $2^{128}/{MAX}$.

If your MAX is close to $2^{128}$ then cycle walking can produce an efficient FPE solution.  But if your MAX is small - say a 9 digit account number ($MAX = 10^9$, which is close to $2^{30}$) then you can expect $2^{98}$ iterations to perform one FPE encryption.  That's harder than brute-forcing 2-key TDES, and clearly in the territory of 'prohibitive'.