QUANTUM PERFECT PRIVATE PRIVACY

Michael A. Bickel
Email: AWAREAI@aol.com
Telephone: 1-281-339-1452


Description of Invention

Quantum Perfect Private Privacy (QPPP) is an encryption method for regular ASCII text that ensures absolute privacy. QPPP is a bisymmetric secret key method using a "random" permutation (perm64K) of the integers 0 through 65535(=64K-1), and the inverse permutation (invrs64K). [1] Subroutine BILDPERM creates perm64K and stores it on two diskettes; one diskette for the sender and one diskette for the receiver. Without this permutation it is not possible to decrypt the encrypted messages. The permutation diskette must be securely delivered to your receiver and the information must be kept secret.

Subroutine CONVERTM converts the message string of regular ASCII characters into a vector of corresponding numeric ASCII codes and stores this vector in tempmsg. These numeric codes range from 0 to 127 for regular ASCII characters and from 128 to 255 for extended ASCII characters. In other words, regular ASCII codes are 8 bit bytes where the most significant bit is 0 and extended ASCII codes are 8 bit bytes where the most significant bit is 1. Extended ASCII characters are not allowed in the message; thus tempmsg begins as a vector of integers between 0 through 127. Let length denote the length of the message in one byte words and two byte words, depending upon the context.

Encryption

QPPP repeatedly transforms tempmsg numerically, two bytes at a time, producing a new vector, that overwrites the old vector in tempmsg; new tempmsg = ENCODEB(ENCODEF(old tempmsg)). ENCODEF encodes tempmsg Forward (L=1 to length) and ENCODEB encodes tempmsg Backwards (L=length to 1). After ROUND rounds of ENCODEB(ENCODEF()), the final vector in tempmsg is the encrypted message and is copied to encryptd. (refer to QPPP drawing #1)

Both ENCODEF and ENCODEB "smear" tempmsg onto itself with a running sum reduced modulo 64K (sequentially reversible), and then they map these reduced values using perm64K (reversible). For example, the ASCII string "abcxyz", converts to the vector (97,98,99,120,121,122), since ASCII "a" is 97, ASCII "b" is 98, ..., and ASCII "z" is 122. In two byte words, this vector equals (97*256+98, 99*256+120, 121*256+122) = (24930, 25464, 31098) and smears forward to (24930, 50394, 15956). Since the last term of the running sum, 81492, exceeds 64K, it is reduced modulo 64K to 15956. This vector, (24930, 50394, 15956), is mapped using perm64K and the result, (perm64K(24930), perm64K(50394), perm64K(15956)), is stored in tempmsg. Notice that ENCODEF may simultaneously smear and map each element of the vector tempmsg or ENCODEF may smear all elements of tempmsg and only then map all elements of tempmsg; both ways produce the same result. This is true for ENCODEB, DECODEB, and DECODEF. Also, all four functions are sequentially reversible; this means that consecutive values in tempmsg are required for encryption and decryption.

ENCODEF pseudocode : (ENCODEB uses L = length TO 1) smear = 0 FOR L = 1 TO length smear = (smear + tempmsg(L)) MOD 64K map = perm64K(smear) tempmsg(L) = map NEXT L


Decryption

QPPP moves the encrypted message into tempmsg and then repeats the composition DECODEF(DECODEB()), until tempmsg contains only values between 0 and 127, with no values between 128 and 255; new tempmsg = DECODEF(DECODEFB(old tempmsg)). When this condition (0 to 127) is satisfied, tempmsg is the decrypted message and is copied to decryptd.

DECODEB pseudocode : (DECODEF uses 1 to length
) lag = 0
FOR L = length TO 1 STEP -1
unmap = invrs64K(tempmsg(L)) unsmear = (unmap - lag) MOD 64K tempmsg(L) = unsmear lag = unmap NEXT L

EXTASCII pseudocode: (word=byte)
extasc$="SOME" FOR L = 1 TO length IF (tempmsg(L) > 127) THEN RETURN NEXT L extasc$="NONE" RETURN

Sketch of QPPP Demonstration Code

The QPPP demonstration code is written in Qbasic; this permits changing messages and parameters interactively. This code listing may be scanned and OCR'd and should execute. The demo creates a perm256 instead of a perm64K; i.e., a permutation of 0 through 255. This QPPP demo operates on single bytes of tempmsg, as opposed to perm64K which operates on two bytes at a time. False alarms may be explored since this demo uses no padding. Experiment with different messages (msg$); delete the REMark preceeding the examples or type your own message. Try msg$="a" or msg$="abc" since QPPP only exhibits false alarms with short messages, never with long messages. (refer to listing of QPPPdemo.bas)

QPPP Permutation Keys

There are (64K)! (64K factorial) different permutations of 0 through 65535; this number is approximately 1 followed by 300,000 zeroes. More precisely, express ln(n!) as a sum of logarithms in base e, then approximate this sum with the integral of ln(x) from 1 to n. This gives ln(n!)==nln(n)-n or n!==n^n/e^n. In base 2 logarithms, log2(64K!)==64K*log2(64K)-64K*log2(e)==64K*16-64K*(1.44), since log2(e)==1.44. Thus, log2(64K!)==64K*(16-1.44)==954,204. The number of permutations of 64K distinct objects is nearly a million bits long and any "random" perm64K makes a good encryption key. Notice that the run time for QPPP depends on the length of the message but not on the length of perm64K, the key. A 64K permutation using 2 byte words requires 128K bytes of storage and easily fits on a small 1.44M diskette. Creating a "random" permutation of the integers from 0 to 64K-1 may require a minute of computer time; however, the key is generated once and then used many times. [1]

QPPP Run Time Estimates

The preferred embodiments of QPPP are assembly language, machine code, microcode or silicon. The run time will be estimated using Pentium assembly language opcodes. Unsigned 16 bit integers are used so that reduction modulo 64K is automatic with 16 bit overflow/underflow. Suppose the Pentium runs at 200MHz, so that each clock cycle is 5 nanoseconds. Suppose also that the raw message is one megabyte (M) of regular ASCII characters; encoding uses 2 byte words, so that length = M/2. QPPP loads the message (converted to numeric codes), perm64K, and invrs64K into distinct data segments in memory and then initializes three 16 bit offset registers: mov ax,[si] -- variable offset address for tempmsg : mov bx,[pi] -- constant offset address for perm64K : similarly for invrs offset.

Assembly language pseudocode for ENCODEF inner loop:
start Load tempmsg(1) into register ax Load perm64K(ax) into tempmsg(1) Load length-1 = M/2-1 into loop register cx

innerloop: -control with cx counter:loop length-1 times -- 0 cycles add si,2 -- address for next value in tempmsg -- 1cycle mov dx,[si] -- move tempmsg value into dx -- 1 cycle add ax,dx -- compute running sum, accumulate in ax --1 cycle mov dx,[bx+ax] -- move perm64K value into dx -- 1 cycle mov [si],dx -- store value in current tempmsg slot --1 cycle loop innerloop total = 5 cycles

Square brackets, [ ], refer to memory addresses. Disregarding the cycles for initialize and start, it follows that ENCODEF requires length*(5 cycles) = M/2*(5 cycles). ENCODEB also requires length*(5 cycles). Hence a single QPPP encryption round, ENCODEB(ENCODEF()), requires 2 * M/2 * 5 cycles = M * 25 nanoseconds = 25 milliseconds. Thus 20 encryption rounds of QPPP takes approximately 20 * 25 ms = 0.5 second.

Similarly, 20 rounds of QPPP decryption (DECODEB and DECODEF) take approximately 20 * 30 ms = 0.6 second, since EXTASCII time is negligible except for the last round.

QPPP Cryptanalytic Attacks

There are no simple cryptanalytic attacks based upon the frequency of occurrence of the numbers (0 to 255) in the encrypted message. After two rounds of QPPP encryption, the 256 bin histogram of the one byte values in tempmsg appears almost uniform. After 20 rounds of encryption, there information remaining with which to design an attack. The 64K bin histogram of two byte values in tempmsg is also uniform and more sparse.

Assuming a raw message and the cipher text and the number of encryption rounds are known, how much time would a brute force search of every possible 64K permutation take? The goal is to recover perm64K. This is a search of approximately 2^954,204 permutations. Assume that every person in the world (8 billion) has a PC and that they are all networked for this search. Assume further that each PC can search 1 million permutations per second and that there are four million seconds per year. These are very generous estimates; this network can search 32*10^21 or approximately 2^75 permutations per year. It follows that this search will require only 2^(954,204-75) years. Our universe may be 16 billion years old; this is 2^34 years. Thus this permutation search takes way, way longer than the age of the universe. Since a search of this magnitude is impossible, QPPP is not breakable with a brute force method and should remain that way for a long while.

Suppose a cryptanalytic attack exploiting some weakness in QPPP could be programmed on a quantum computer. Independent of the existence of such a quantum program and machine, it must be possible to express and extract the answer; i.e., the permutation perm64K. This means the quantum computer must have a register equivalent to 954,204 qubits! A coherent quantum register this large is not feasible; in fact, an ordinary nonquantum register this size is not even feasible. Using multiple smaller quantum registers would disrupt the coherency needed for quantum superposition. Thus, QPPP is also secure against a quantum attack.

Differential cryptanalysis uses pairs of messages constructed with particular differences and follows these differences through encryption. The number of pairs needed for this analysis is a function of the key bit length; 954,204. Suppose this log function is 10%, so that 2^95,420 pairs are needed. This number exceeds the storage capacity of the world. Thus, QPPP is secure against a differential attack.

If perm64K is used only once and discarded, then QPPP is similar to a One Time Pad (OTP) encryption method; OTP methods are provably unbreakable. However, QPPP may use the same perm64K for many encryptions without jeopardizing security; thus QPPP is a Many Time Pad (MTP). Obviously, if the security of perm64K is compromised, the permutation should be replaced. In any case, perm64K should be changed on a regular basis.

QPPP Heuristics and False Alarms

Notice that smearing forward in ENCODEF has no diffusion to the left; i.e., the first element of tempmsg is unchanged before the perm64K mapping. However, the last element of tempmsg has long diffusion since it is a function of every element in tempmsg. Conversely, smearing backward in ENCODEB has no diffusion to the right; the last element of tempmsg is unchanged. However, the first element of tempmsg has long diffusion since it is a function of every element in tempmsg. Thus, the composition ENCODEB(ENCODEF()) displays long diffusion to the right and left; for this reason, QPPP runs ENCODE in both directions, forward and backward. Similarly, the composition DECODEF(DECODEB()) displays long diffusion to both the right and left.

To minimize false alarms and thwart cryptanalytic attacks, QPPP pads the raw message with a prefix and a suffix before converting to numeric ASCII codes. This prefix and suffix are random regular ASCII character strings at least 100 characters long. Their lengths are chosen so that the padded message is at least 1000 characters. This thwarts attacks where the message is short or all one character and also prevents false alarms.

What are the QPPP false alarms? False alarms occur only when EXTASCII returns extasc$="NONE" and the decrypted text is not the original message. In this case, the decrypted message must be all regular ASCII characters and yet not the original message. What is the probability of this inadvertent occurrence?

Let N denote the length of the message in bytes, including the prefix and suffix, and consider the N dimensional cube, X = [0,256) ^ N, where [0,256) is the real closed-open interval from 0 to 256 (the interval [0,256) contains 0 but not 256). Denote by P, the points of X having all integral coordinates. These points correspond numerically to all possible regular and extended ASCII character strings having length N. Let C = [0,127) ^ N, be an N dimensional cube contained in X. Denote by Q, the points of C having all integral coordinates. These points correspond numerically to all possible strings of regular ASCII characters having length N with no extended ASCII characters. The first vector in tempmsg, converted from the original message, is a point in Q. However, after each round of encryption, tempmsg corresponds to a point in P. Consider the orbit of tempmsg during many rounds of encryption. This orbit begins in Q, but after each round the next point in the orbit is a point in P and probably not a point in Q. After a few rounds of encoding, the values in tempmsg are all equally likely to be any number from 0 to 255. Thus the probability that any point in this orbit inadvertantly reenters Q is (1/2)^N = (128/256)^N. Since N is at least one thousand, this is no more than .00...001, where about 300 zeroes precede the 1. Thus, these false alarms are very, very rare.

According to statistical mechanics, there is a small nonzero probability that every molecule in a closed room will move to the left half of the room. This is analogous to the QPPP orbit inadvertantly moving from P into the smaller cube, Q. If there is only one molecule in the room (one character in the message), then this probability is 50-50 or 1/2. But with 1000 molecules in the room (1000 characters in the message), the probability is (1/2)^1000. Because of the minimum padding this probability is negligible and so are the false alarms. For example in three dimensions, when the message is three characters long, all three molecules would have to be less than halfway to the ceiling and in the front half of the room, in addition to being in the left half of the room.

QPPP and Ergodicity

QPPP is defined for points of P, but not for nonintegral points in X. The running sums in smear are well defined for all points in X; however, the mapping using perm64K is not well defined. Extend the definition of perm64K(x)for nonintegral values of x to be perm64K([x])+ fract(x), where [x] denotes greatest integer and fract(x)=x-[x] denotes the fractional part of x. This extension of QPPP to X agrees with the definition of QPPP on P, the integral points in X. It is not difficult to show that QPPP: X --> X is a measure preserving transformation; it is more difficult to show that QPPP: X --> X is ergodic (nonperiodic for almost every point in X). [3] The proof is similar to Dirichlet's and Kronecker's theorems. [4] Ergodic means that the extended QPPP encryption transformation, QPPP:X-->X, is very "mixing". The restriction QPPP:P-->P cannot be ergodic, since the lattice P is finite, and hence the orbit of any point must be periodic. However, the ergodicity of QPPP on X, implies that the periods (orbits) of QPPP restricted to P are very, very long. Maybe this should be called pseudoergodic; it is certainly "mixing". Each bit in the original message is mixed with all of the bits in the encrypted message. To verify this, change any bit in the encrypted message, then QPPP decryption will enter an infinite loop and never find the original unencrypted message.

QPPP Variations and Symmetries


As should be obvious to those skilled in the art, every embodiment of QPPP encryption possesses many equivalent symmetries:

1) exchange perm64K with invrs64K 2) exchange forward with backward 3) exchange the running sum with running difference 4) map first with perm64K and then smear 5) add a constant (0 < k < 64K) to smear: smear = smear + tempmsg + k 6) include an odd multiplier in smear: smear = smear + odd*tempmsg + k 7) define a new perm64K = (old perm64K)^p for any power p 8) reduce modulo 2^m for any power of 2 (not necessarily 2^16) 9) many other less obvious variations


Each of these symmetries and variations to smearing and mapping in QPPP encryption produce sequentially reversible functions. [2] The corresponding modifications to QPPP decryption are easily derived. All of these variations of QPPP encryption and decryption are fundamentally equivalent.

It should be obvious that the pseudocode, the assembly code, and the democode merely illustrate the logic that may be used to implement the present invention, and does not limit the concept nor implementation. Other variations, symmetries and modifications will, of course, become apparent from a consideration of the structures and techniques described. Accordingly, it should be clearly understood that the present invention is not intended to be limited by the particular features and structures hereinbefore described and depicted.

QPPP PROVISIONAL PATENT CLAIM

It should be clear to those skilled in the art, that these symmetries and variations to QPPP also may be embodied in assembly language, computer machine code, microcode, or silicon. This provisional patent seeks to protect the intellectual property of QPPP for all variations and symmetries that would be obvious to those skilled in the art. The scope of this intellectual property includes the composition of any sequentially reversible transformation with a reversible mapping using a permutation perm(2^m), for any power m. Since m may be arbitrary, it follows that the original message need not be restricted to all regular ASCII characters.
What is provisionally claimed:

A method and apparatus for encrypting a sequence of natural numbers between 0 and (2^(m-1))-1, where m is arbitrary, but then fixed. Said method and apparatus implementing the composition of any sequentially reversible transformation with a reversible mapping using a permutation perm(2^(m*k)). Said composition repeatedly applied to said sequence of natural numbers; new sequence = composition(old sequence). Said sequentially reversible transformation, having domain 0 to (2^(m-1))-1 and range 0 to 2^(m*k)-1, and acting upon consecutive contiguous subsequences of said sequence of natural numbers; new value = transformation(consecutive subsequences of values). Said reversible permutation mapping, having both range and domain 0 to 2^(m*k)-1, and mapping values of said transformation; new value = perm(2^(m*k))(old value).

References

1) Donald E. Knuth, "The Art of Computer Programming", Volume 2, chapter 3, Addison-Wesley 1981
2) Charles H. Bennett, "Notes on the history of reversible computation", IBM J. RES. DEVELOP. Vol.32 No. 1 Jan 1988
3) P. R. Halmos, "Lectures on Ergodic Theory", The Mathematical Society of Japan, 1956
4) G. H. Hardy and E. M. Wright, "An Introduction to the Theory of Numbers", chapter 23, Oxford Clarendon Press 1960

Michael A. Bickel
Email: AWAREAI@aol.com
Telephone: 1-281-339-1452