BACKGROUND OF THE INVENTION

L Field of the Invention The present invention relates to cryptographic systems. More particularly, the invention generates, by public discussion, a cryptographic key that is unconditionally secure. 2. Discussion of the Related Art An Achilles heel of classical cryptographic systems is that secret communication can only take place after a key is communicated in secret over a totally secure communication channel. Lomonaco [4,5] describes the matter as the "Catch 22" of cryptography, as follows:

"Catch 22. Before Alice and Bob can communicate in secret, they must first communicate in secret."

Lomonaco goes on to describe further difficulties involving the public key cryptographic systems that are currently in use. For a discussion on several other disadvantages of the Public Key Infrastructure (PKI) see U.S. General Accounting Office Report [6] and Schneier [9]. Let Λ: be a common key that has been created for Alice and Bob. That is, Λ; is a binary vector of length n. Then x can be used as a one-time pad as follows. Let m be a message that Alice wishes to transmit to Bob: m is some binary vector also of length n. Alice encodes m as m Θ x where θ denotes bitwise addition, i.e., exclusive OR. Thus m ® x, not m, is broadcast over the public channel. Bob then decodes in exactly the same way. Thus Bob decodes the message (m θ x) ® x, which is m, because of the properties of bitwise addition. Alternatively, the key Λ: can be used in a standard symmetric key cryptosystem such as that of AES [8] or Data Encryption Standard (DES) [9]. The idea now is to encode m as fx(m) where fx denotes the AES permutation with the parameter x. Then, to get the message, Bob decodes by gx\fx(m)] = m where gx is the inverse of/t Brown [11] chapter 5 gives an example of a financial encryption system depending on RSA keys of 512-bit, namely the CREST system introduced in 1997 by the Bank of England. He quotes the noted cryptographer A. Lenstra concerning such codes as follows: "Keys of 512 bits might even be within the reach of cypherpunks. In principle they could crack such numbers overnight". An approach to obtaining independently generated but correlated raw random keys is to employ a commonly known to the communicating parties probabilistic array and agreed upon generation procedure comprising swapping.

SUMMARY OF THE INVENTION

The present invention provides an efficient, practical system and method for a key agreement protocol based on a probabilistic generation method comprising swapping that has the strongest possible security, namely, unconditional security, and that does not require any additional hardware. The present invention provides a protocol secret-key agreement by public discussion between a first and second party. At the outset, a first and second raw string is obtained in a pre¬ determined manner by the corresponding first and second party, a Key Distillation Protocol (KDP) divides each of the first and second string into at least one corresponding small block, and on each of the at least one corresponding small block searches for at least one error by comparing a parity of the at least one corresponding small block of the first party, with the corresponding parity of the at least one small block of the second party. A probabilistic generation method is a mathematical way of generating raw strings between a first party and a second party. A raw string generated by the probabilistic generation method has some information that is not shared by the first party with the second party. For example, the positions on which the raw string bit values agree (or disagree) with the bit values of a pre-determined, commonly known vector S (head-tail or HT-indicator) are only known by the owner of the raw string originally.

The present invention is a new KDP, termed a Swapping PARK KDP (SPARK KDP), that incorporates this information into the KDP process such that the distilled string not only depends on the bit value of the raw string, but also depends on the positions of the bits in the raw string. In a preferred embodiment, A and B employ a protocol comprising four phases, see FIG. 1: raw string generation, advantage distillation, information reconciliation, and information privacy amplification.

PHASE 1 -Alice and Bob employ the probabilistic generation method to construct a raw random string 101

At the outset of Phase 1, Alice and Bob begin by obtaining parameters for block sizes, which may include the process to calculate and agree upon all block sizes used during the step of extracting their reconciled strings; shuffle sizes and permutation functions, which may be used when applying permutations, wherein a permutation is a mathematical mapping of a set to itself; and operation rules, which may be used in performing operation and permutations on selected bits. Alice and Bob employ a pre-determined probabilistic string P to independently generate random raw strings XA and XB. The string P is either shared between Alice and Bob or generated by using a shared nonce to seed a pre-determined pseudo random number generator. To generate XA and Xg, Alice and Bob independently generate real-number strings r^ and rB, respectively, where 0 < rA[ϊ], rB[ϊ] ≤ 1 for all i (1 < i ≤ length of XΛ and Xg)- For position i, the bit Xγ[i] is set to 1 if strings rγ[i] ≤ P[i]; otherwise, Xγ[i] is set to 0, where Y = A or B. Alice and Bob also derive a binary string S, called HT-indicator string, as below: for each i, if P[J] > 0.5 set S[J] = 1; otherwise, set set S[J] = 0. Then Alice and Bob associate a pair of numbers (σ, r) with bit i of XA and XB, respectively, where o = r = i, i.e., the bit position of bit i in string XA or XB. Finally, each bit is marked by X according to whether or not the ith bit of XA or Xj? does not match the relevant bit of the HT-indicator string S.

PHASE 2- Alice and Bob employ these raw strings in a KDP with swapping to generate a reconciled string 102

Alice and Bob systematically partition their respective random raw strings, ZA and XB, into sub-blocks of a predetermined fixed length Z. For each sub-block they perform a process of compute, exchange, compare parities, and keep the sub-block, if the parities agree. Otherwise, they divide the disagreed upon block and repeat the process on each sub-block until the two blocks are of length I = 2. At this point, if the parities disagree, the disagreed upon block is discarded. If the parities agree, they keep the first bit and discard the second bit except when the second bit is marked by X and the first bit is not marked by X they keep the second bit and discard the first bit. The remaining bit's r is set to the r of the first bit of the block. At each step, Alice and Bob concatenate the retained blocks in their original order and obtain respective retained strings. Then, if their respective retained strings are not empty, Alice and Bob shuffle their respective retained strings using a previously agreed upon procedure and repeat Phase 2 until a stopping condition 103 and a verification procedure (checking hash) 104 have both been passed successfully. If the retained strings are empty the procedure starts over at Phase 1.

PHASE 3 - Alice and Bob Flip, XOR and Shuffle the Reconciled String to Create a Distilled String KA and KR 105

Alice and Bob flip each bit of their retained strings independently if the pre-determined flipping conditions are met, XOR the unmarked bits according to pre-determined rules and shuffle their flipped and XORed bits, according to a pre-determined process, to arrive at a new distilled KA and KB.

PHASE 4- Alice and Bob Create An Unconditionally Secure Key From Their Common Distilled String 106

^lice and Bob perform privacy amplification to eliminate any partial information that an savesdropper, Eve, might have using a pre-determined hash function to produce a final unconditionally secure key of a pre-determined length from their common distilled string resulting from Phase 3.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates an overview flow diagram of the SPARK KDP according to the present invention. FIG. 2 illustrates a flow chart of a raw string generation according to the probabilistic generation method. FIG. 3 illustrates adjusting bits using the present invention to increase the correlation between the reconciled strings of the communicating parties while decreasing the correlation between the reconciled strings of the communicating parties and a possible eavesdropper. FIG. 4 illustrates creating a distilled string from a reconciled string and creating an unconditionally secure key therefrom, according to the present invention.

DETAILED DESCRIPTION OF THE INVENTION

In a preferred embodiment, the key agreement scheme of the present invention comprises four phases. The first phase is raw string generation using the probabilistic generation method for construction of a permuted remnant bit string wherein two communicating parties, Alice and Bob, both know a probabilistic string P of real numbers and generate strings based on this string. Some of the bits may still be different after the initial bit string construction, so Alice and Bob then participate in a second phase called Information Reconciliation in which KDP with swapping is performed with respect to their strings by Alice and Bob until a stopping condition and a verification procedure are passed. The second phase results in Alice and Bob holding exactly the same key.

However, Eve may have partial knowledge of the reconciled strings, in the form of Shannon bits. Therefore, in a third phase Alice and Bob flip, XOR and shuffle their respective strings KA and KB to obtain a distilled KA and KB string, respectively, therefrom. In a final phase called Privacy Amplification, Alice and Bob perform a hash to eliminate any partial information collected by Eve.

PHASE I - Alice and Bob each know a random probabilistic array P. They independently proceed to generate raw random strings XA and XB- Referring now to FIG. 2, Alice and Bob perform the following steps: (i) Obtain parameters at step 201 to determine KDP block size, shuffle sizes, XORing rules, etc, i.e., for all the pre-determined items such as sub-block starting length /, rules, procedures, block size, etc. identified in the disclosure of the present invention. (ii) Generate and exchange nonces, at step 202. A nonce is a parameter that varies with time. It is a string of characters invented and used only in a given context, i.e., for the immediate occasion. Herein, the occasion is to secure communication between two parties. Alice and Bob do the following separately and simultaneously, (only Alice's steps for XA are shown but Bob performs similar steps for XB): (iii) At step 203, generate P, a probability string of length n, and S an HT-indicator string using the nonces. Alice and Bob do the following separately, (only Alice's steps for XA are shown but Bob performs similar steps for XB). (iv) At step 204, generate string XA = [XA [1], - - -, XA [»]} by P, for example, for each i, generate a random number r[i] and set XA U] = 1 if r[i] < P[z] and zero otherwise. (v) For every i ( 1 < i < ή), mark the bit XA [i] by X if XA [/] ≠ S [i] at step 205. (vi) At step 206, for every i (1 < i < n), assign a pair of numbers (o, r) to the bit XA [Ϊ\. Initially, o = i, r = i, and the number o will be fixed through out all the following processes, while the number r will be updated during the following processes.

PHASE π - Alice and Bob have their respective binary arrays XA and XB. Referring now o FIG. 3, they both simultaneously perform the following steps: Shuffle (vii) At step 301 Alice and Bob apply a permutation to XA and XB , obtain KA and KB , respectively. Parity exchange and bisective search (viii) At steps 302 and 303, Alice and Bob partition their shuffled raw string into sub- blocks of fixed length I. Initially, / is set to 2. When repeating this step, / can be increased to 4, 8, ... . When this step is repeated for the kth time, the block length / can be 2k. For each of these blocks, Alice and Bob compare the corresponding blocks parities as follows: 1 = 2: If the parities disagree, then Alice and Bob both discard the block. Otherwise, Alice and Bob keep the first bit and discard the second bit, except when the second bit is marked by X and the first bit is not marked by X, in which case, keep the second bit and discard the first bit. Alice and Bob update the remaining bit's r as below:

r = r of the first bit:

/ > 2: If the parities agree, then Alice and Bob both keep the block. Otherwise, Alice and Bob perform a divide-compare process on this block as follows: Divide-compare process Alice and Bob divide the block into two blocks, and compare the parity of their first blocks. If the parities disagree, then Alice and Bob repeat the divide- compare process on this block. Otherwise, Alice and Bob repeat the divide- compare process on their second blocks. Alice and Bob continue the divide- compare process until the block size is 4. Then Alice and Bob divide their blocks of size 4 into two blocks of size 2 and compare the parity of their first blocks. If the parities agree, they apply the procedures for / = 2 to this block and discard their second block. If the parities disagree, then they discard this block and apply the procedure for / = 2 to their second blocks. Estimate Correlation (ix) At step 304, from the current length of KA and KB , Alice and Bob calculate the estimated bit correlation x between KA and KB [4]. Stopping Condition (x) At step 305 Alice and Bob determine if a pre-determined stopping condition is satisfied. Examples of a stopping conditions include: a. 1. jc > 1 - δ, where x is the current estimated correlation, and δ is a positive small number (smaller than 1). b. the current string length t and correlation x the inequality /(1-ΛΓ) < ε must be satisfied where ε is a pre-determined positive number; c. the number of repeated KDP rounds > r, where r is a pre-determined positive integer. If the stopping condition is not satisfied then Phase II is repeated beginning at step (vii) using the final KA and KB of the divide-compare process. However, it may happen that the final KA and KB are empty, in which case both Alice and Bob start over the entire process at Phase I step 101. Verification Procedure (xi) At step 306 a checking hash is performed as a verification procedure. If the verification criterion is not satisfied Alice and Bob repeat Phase II beginning at step (vii). At this stage Alice and Bob have confirmed that they now share the same key. Once confirmed, the final remnant raw string as transformed by Phase II is re-named the "reconciled string" and Phase III, distillation, is performed.

PHASE HI - At this stage Alice and Bob now have a common reconciled string. In certain cases it is possible that the string is only partially secret to eavesdropper, Eve, in the sense that Eve may have some information on the reconciled string in the form of Shannon bits. Referring now to FIG. 4, Alice and Bob begin the process of generating a distilled string from their common reconciled string by transforming their reconciled strings using agreed upon flipping 401 , XORing 402 and shuffling 403 transformations: Flipping (xii) If a string K is obtained after PHASE II, then for each bit K[i\ in this string, compare its o and r. If o ≠ r, then compare X[o] = K[i] with X[f\. If K[i] = X[r], then flip K[i] (i.e., set K[i] = 1 - K[i\), and mark it by F. XORing (xiii) For all those r's that satisfy r ≠ o and X[r] = X[o], collect all those X[r]s and use them to XOR some (or all if there are enough X[r]s) of the bits in K that are not marked (neither by X nor by F). The XOR follows some agreed upon rules between the two parties. For example, both the X[r]s and the unmarked bits could be sorted in their original order and let rif be the number of all X [r]s, let nlt be the number of the unmarked bits, and let rs be the residue of «/ divided by nu. Now put the first rs unmarked bits at the end, and XOR the corresponding bits of this string with the bits of the sorted X[r) string Shuffling (xiv) Partition the bits of the string K into four parts: {K[ϊ\ I K[i] is marked by F, 1 < i < length(K)} {K[ϊ\ I K[i] is marked by X, but not by F, 1 < i < length{K)} {K[ϊ\ I K[i] is XORed, 1 < i < length(K)} {K[ι\ I K[i] is neither marked nor XORed, 1 < / < length(K)}

Shuffle the four parts separately, then shuffle the first two parts together, shuffle the last two parts together, and then shuffle the four parts all together. If all those bits that are not marked have been XORed, then the last part is empty, and the shuffle would be: shuffle the three parts separately, then shuffle the first part and the second part together, then shuffle the three parts all together. PHASE IV Privacy Amplification - Alice and Bob now begin the process of Privacy Amplification at step 404, that is, the extraction of a final secret key from a partially secret one (see [1] and [2]). A well-known result of Bennett, Brassard and Robert (see [1O]) shows that Eve's average information about the final secret key is less than 2~s/ln 2 Shannon bits (see Shannon [7]). The system and method of the present invention provide an unconditionally secure key agreement scheme as follows. In PHASE I, Alice and Bob generate raw strings using the probabilistic generation method. In PHASE It, the string from PHASE I undergoes a pre-agreed to shuffling process and then the treatment of Lomonaco [5] is applied. That is, in PHASE II Alice and Bob partition the remnant raw string into blocks of length /. In PHASE π, for each of these blocks, Alice and Bob publicly compare parity checks and each time an parity check does not agree, Alice and Bob initiate a binary search for the error, i.e., bisecting the mismatched block into two sub-blocks, publicly comparing the parities for each of these sub-blocks. They continue their bisective search on the sub-block for which their parities are not in agreement. This bisective search continues until the erroneous block is located and discarded. The bits of the kept block of length 2 are possibly swapped and the lower bit is discarded. They then proceed to the next /-block. PHASE π is then repeated, i.e., a suitable shuffling is chosen and applied to obtain the permuted remnant raw string. The shuffled remnant raw string is partitioned into blocks of length /, parities are compared, etc. The probability that corresponding bits agree in the arrays KA , KB is known as the bit correlation probability or, simply, as the bit correlation. The final secret key can now be used for a one-time pad to create perfect secrecy or can be used as a key for a symmetric key cryptosystem such as AES [8] or Triple DES [10].

The system and method of the present invention provides secure transmission over wireless and wire media and networks as set forth below; a. wireless 1. radio transmission 2. radio frequency 3. satellite 4. microwave 5. infrared 6. acoustic 7. electro-magnetic spectrum 8. spread spectrum 9. laser b. wired 1. optical 2. fiber optics 3. electrical 4. Ethernet 5. quantum communication c. networks 1. intranet 2. Internet 3. extranet 4. Public Switched Telephone Network (PSTN) 5. Local Area Network (LAN) 6. Wireless Local Area Network (WLAN) 7. Wireless Fidelity (WIFI) 8. Wireless Local Area Network (WiLAN) 9. IEEE 802.il, 802.11a, 802.11b 10. Personal Area Network (PAN) 11. Bluetooth 12. Code Division Multiple Access (CDMA) 13. Global System for Mobile (GSM) Communication 14. 3rd Generation Mobile Network (3G) 15. Asynchronous Transfer Mode (ATM) 16. Digital Subscriber Line (DSL) 17. Frame Relay

It will be understood by those skilled in the art, that the above-described embodiments are but examples from which it is possible to deviate without departing from the scope of the invention as defined in the appended claims. REFERENCE AND BIBLIOGRAPHY

Each of the following references are hereby incorporated by reference as if fully set forth herein.

[1] Charles Bennett, Franςois Bessette, Gilles Brassard, Louis Salvail, and John Smolin, Experimental quantum cryptography, EUROPCRYPT '90 (Arhus, Denmark), 1990, pp. 253-265.

[2] Charles H. Bennett, Gilles Brassard, and Jean-Marc Robert, Privacy Amplification by Public Discussion, Siam J. of Computing, 17, no.2 (1988), pp. 210-229.

[3] Aiden Bruen and David Wehlau, A Note On Bit-Reconciliation Algorithms, Non- Elephant Encryption Systems Technical Note 01.12 NE2, 2001.

[4] Samuel J. Lomonaco, A quick glance at quantum cryptography, Cryptologia 23 (1999), no. l, pp. 1-41.

[5] , A Rosetta Stone for Quantum Mechanics With An Introduction to Quantum Computation, quant-ph/0007045 (2000).

[6] United States General Accounting Office, Advances and Remaining Challenges to Adoption of Public Key Infrastructure Technology, GAO 01-227 Report, February 2001, Report to the Chairman, Subcommittee on Government Efficiency, Financial Management and Intergovernmental Relations, Committee on Government Reform, House of Representatives.

[7] Claude E. Shannon, Communication Theory of Secrecy Systems, Bell System Technical Journal 28(1949), 656-715. [8] Joan Daemon and Vincent Rijnmeien, The Rijndael Block Cypher, June 1998, http://csrc.nist.gov/encryption/aes/rijndael/rijndael.pdf [9] Bruce Schneier, Applied Cryptography, 2nd Edition, John Wiley & Sons, New York, 1996, Chapter 12. [10] Douglas R. Stinson, Cryptography: Theory and Practice, CRC Press, 1995. [11] Julian R. Brown, The Quest for the Quantum Computer, Simon & Schuster, New York, 2001.