Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

A method for fast integer format preserving encryption for large integers

IP.com Disclosure Number: IPCOM000245153D
Publication Date: 2016-Feb-14
Document File: 3 page(s) / 60K

Publishing Venue

The IP.com Prior Art Database

Abstract

A method for using existing block cipher encryption for efficiently solving the problem of integer format preserving encryption. The idea behind this invention is to divide the problem of large integer format preserving encryption into two parts: (1) a regular block encryption problem, (2) an integer format preserving encryption (IFPE) of a small integer.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 53% of the total text.

Page 01 of 3

A method for fast integer format preserving encryption for large integers

Integer format preserving encryption (IFPE) is a cryptographic reversible function F: {0..n} ->
{0..n}, i.e., encrypts an integer i where

                                     for some , to integer j such using the same key for decryption would return i back.

IPFE can be used to encrypt any type of format such as telephone, credit card number, email, etc., by ranking each domain D to value [0..n], encrypting it and unranking back to the original domain. Thus an efficient solution to this problem opens up the wider field of format preserving encryption.

Essence of invention

A method for using existing block cipher encryption for efficiently solving the problem of integer format preserving encryption

Business value

Method can be used in any format preserving an encryption scheme.

The idea behind this invention is to divide the problem of large integer format preserving encryption into two parts: (1) a regular block encryption problem, (2) an integer format preserving encryption (IFPE) of a small integer.

Thus the block encryption problem can be solved by a proven and efficient algorithm such as AES, and then we are only left with a small IFPE problem. Small problem is easier and faster to solve than a large one. If the problem is small enough, i.e., involving a small domain, we can use FE1 above, do a pre-processing step to calculate values in advance, or by overlapping block which will show below.

Thus will address how to solve the more difficult of the problems, namely IPFE of large integers. A more in depth description is in the next section but in essence the solution entails :a. Represent max value in domain as bit arrayb. Break into blocks and encrypt using block cipher (AES for 128 bit block, TDES for 64 bit block, Skip32 for 32 bit blocks)c. Last block is a partial block,
i.e., it is a small IFPE problem, this can be solved by: i. Last block which is partial is encrypted as entire block with preceding complementing previously encrypted block (portion is encrypted twice), see depiction below. ii. IFPE algorithm such as FE1, small performance impact since it is a small integer iii. If integer is smaller than 2^32, we can run any permutation algorithm as preprocessing and save it in memory.

Overlap attributed to the last block above was chosen arbitrarily and for the sake of demonstration. This could have been attributed to any block, or even separated among many or all blocks.

1


Page 02 of 3

Our implementation needs four parameters.


1. Block cipher - A (i.e., AES/DES).

2. Block size - n (of the block cipher).


3. Domain size.

  4. Value (to ecrypt). Pseudocode of the algorithm:

Domain size bit-array MaxSize[l],

Bit-array out

For(

   i m; I < l; i++) toEnc[i] = 0 labal: bit-

     array out i mWhile there is at least n unencrypted bytes: out[i+ni…,i] A(toEnc[i+n,…,i])

out[1,…,n] A(toEnc[1,…,n])

if( out > Max...