{'fraction_non_alphanumeric': 0.03235000712555223, 'fraction_numerical': 0.011614650135385492, 'mean_word_length': 4.250467639356528, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 2, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Post-Quantum Key Exchange Protocols

If an eavesdropper Eve is equipped with quantum computers, she can easily break the public key exchange protocols used today. In this paper we will discuss the post-quantum Diffie-Hellman key exchange and private key exchange protocols.


WHY POST-QUANTUM KEY EXCHANGE?
Diffie and Hellman proposed the first public-key agreement for key exchange in 1976. This protocol relies on the difficulty of computing discrete logarithms in a finite field. The most popular public key algorithm for encryption and digital signature is RSA. The security of RSA is based on the intractability of the integer factorization problem. There are a few other cryptographic schemes that are used in practice, for example, the Digital Signature Algorithm (DSA) and the Elliptic Curve Digital Signature Algorithm (ECDSA). The security of these schemes is based on the discrete logarithm problem in the multiplicative group of a prime field or in the group of points of an elliptic curve over a finite field.
But in 1994 Shor 1 showed that quantum computers can break all digital signatures that are used today. In 2001 Chuang et al 2 implemented Shor's algorithm on a 7 − qubit quantum computer. When quantum computers reach approximately 30 to 40 q − bits they will start to have the speed (parallelism) needed to attack the methods society uses to protect data and processes, including encryption, digital signatures, random number generators, key transmission, and other security algorithms.
We cannot predict exactly when this will happen because each advance in the number of q − bits has had radically different hardware architecture. We believe quantum computers will surpass the speed of "Moore's Law" computers in the next 15 years, break encryption in 25 years, and break the responding enhanced encryption (with much longer key lengths) in 30 to 50 years.
Most planners don't look 20 years into the future, and propose to defend against quantum computer attacks by lengthening the keys. However, we can also defend against quantum computer attacks by researching a way which is somewhat or wholly immune to quantum computer attacks. Many quantum public key exchange protocols have been studied, for example BB84 and B92 3 . We will look at two schemes that achieve key agreement protocol.
The heart of our key exchange protocol is to use a public satellite -continually broadcasting random bits at a rate so high that no one could store more than a small fraction of them. Parties that want to communicate in privacy share a relatively short key that they both use to select a sequence of random bits from the public broadcast; the selected bits serve as an encryption key for their messages. An eavesdropper cannot decrypt an intercepted message without a record of the random broadcasts, and cannot keep such a record because it would be too voluminous. How much randomness would the satellite have to broadcast? Rabin and Ding 4 mention a rate of 50 gigabits per second, which would fill up some 800, 000 CD-ROMs per day.
The general framework is shown in Figure 1: General Key Agreement Framework 1. Random source: a satellite sends random bit signals.
2. The two communicating parties Alice and Bob get these signals 3. They need to know when they should count the bits as the key.
5. They agree to flip one bit or more.
A geostationary satellite can be used as a data source generating a random bit stream. Two communicating parties, Alice and Bob with dish antennas, are able to receive the bit signal from the satellite. When they want to encrypt the message, they catch the random bits of the signal as a key. They make a public agreement on the key size, for example, 1024 bits. The key is never stored in the computer's memory, so they essentially vanish even as the message is being encrypted and decrypted.
In order for both Alice and Bob to count the same bits as the key from the satellite signals, three problems should be solved: 1. Due to the different distances between the satellite to Alice and to Bob, they will not count the same bits.
2. Alice and Bob should know the starting times that they can count the same number of bits as a key.
3. Alice and Bob should determine the time difference between their spatially separated clocks. For example, the determination of the difference should be better than 100 ns.
The first problem is easily solved by using Global Position Systems (GPS) to determine their positions and calculate the time delay due to the different distance from the satellite to the receivers. We propose to use the technology of quantum teleportation and quantum clock synchronization to solve the latter two problems.
The organization of the paper is as follows: In Section 2 and 3, we describe post-quantum Diffie-Hellman key, private key exchange and quantum random walk protocols. A conclusion is given in Section 4. We provide the fundamentals of random source, random number generator, quantum teleportation, quantum clock synchronization, and quantum random walk in the Appendix.

Diffie-Hellman Key Exchange
With a symmetric cryptosystem, it is necessary to transfer a secret key to both communicating parties before secure communication can begin. Diffie-Hellman key exchange protocol allows two parties that have no prior knowledge of each other, to jointly establish a shared secret key over an insecure communication channel. The first practical scheme, Diffie-Hellman Discrete Log (see A.1 for classes of candidate) key exchange protocol, begins with two users Alice and Bob who want to exchange two secret integers a and b. They agree on two public parameters, large prime p and base g. The protocol is specified as follows: Diffie-Hellman Key Exchange Protocols Public announcement: G = g p , g as generator and p is the order of the group G Common input: (p, g) Output: an element k ∈ G shared between Alice and Bob 1. Alice chooses random number a ∈ U ⊗ 1 and p, and send g a to Bob 2. Bob: Choose random number b between 1 and p, and send g b to Alice 3. Alice: compute (g b ) a 4. Bob: compute (g a ) b 5. By commutativity, Alice's k a = g ba = g ab = k b . Notice that an adversary Eve intercepts g, g a , g b public information and cannot break the scheme with non-negligible probability. However this scheme is vulnerable to man-in-the-middle attack.

Post-Quantum Public Key Exchange
Public key cryptosystems and related protocols have been constructed on the Turing machine model. The underlying theories are based on Church-Turing's thesis, which asserts that any reasonable computation can be efficiently simulated on a probabilistic Turing machine. New model of computing, quantum computation, has been investigated since 1980. Two most successful results are Shor's probabilistic polynomial time algorithms for integer factorization and discrete logarithm in the quantum Turing machine (QTM) model 1 and Grover's unstructured search method in √ N . 5 Although Shor's result demonstrates the power of QTMs, Bennett, Bernstein, Brassard, and Vazirani 6 show that relative to an oracle chosen uniformly at random, with probability 1, class N P cannot be solved on a QT M in time O(2 n/2 ). Many researchers consider that it is hard to find a probabilistic polynomial time algorithm to solve an N P -complete problem even in the QTM model.
Since Shor's result and Grover's search algorithm reduced many practical public-key cryptosystems (RSA, multiplicative group/elliptic curve versions of Diffie-Hellman and ElGamal schemes) to insecure status, we need a quantum public-key cryptosystem (QPKC). Many public key schemes such as BB84 and B92 were studied. In 2000, Okamoto, et al 7 proposed a theoretical paradigm of QPKC that consist of quantum public-key encryption (QPKE) and quantum digital signature (QDS). In our studies of quantum channel and satellite communication, we realize an extension of QPKC model and construct two practical schemes that achieve key agreement. We discuss the possible attack and countermeasure of our schemes.
If Eve has a quantum computer, she can easily break the logarithm and get a and b, then the secret key ((g b mod p) a mod p).
The protocol of the Post-quantum Diffie-Hellman Key Exchange is described below: Quantum Public Key Exchange Scheme 1. Alice and Bob use a quantum clock to synchronize their clocks.
2. When Alice sends the message to Bob, she publicly announces to Bob that they will start to count the bits at time t. (Due to the different distance, Bob knows when he will start to count the bits at time t 1 ). The key is g. They also agree on a prime number p. g and p are public.
3. Alice teleports a quantum particle state to Bob and informs Bob that she flips the n th bit of g. The position of the bit flipped depends on the quantum state teleported by Alice to Bob. So both Alice and Bob have the new key called g 1 .
4. Alice and Bob choose their secret keys a, and b, respectively. Alice sends Bob ((g 1 ) a (mod p)), and Bob sends Alice ((g 1 ) b (mod p)). Both Alice and Bob have arrived at the same value

The key vanishes after it is used on Alice and Bob's site.
Only p is public, Eve could intercept (g 1 ) a (mod p) and (g 1 ) b (mod p). All a, b and g 1 are secret. Eve could not figure out the key even she has a quantum computer or this would make it too hard for her to compute the secret key. See

Post-quantum Private Key Exchange Protocol
The Private Key Encryption uses the same key to encrypt and decrypt the message. Only Alice and Bob know the key. How do Alice and Bob make the agreement on the key? They must trust the security of some means of communications. Further, how do Alice and Bob secure the key on their site? The key may be stolen.
The protocol of the post-quantum private key exchange is described below: 1. First, Alice and Bob use a quantum clock to synchronize their clocks.
2. When Alice sends the message to Bob, she teleports a quantum particle state to Bob. Both of them understand they will start to count the bits at time t, (due to the different distance, Bob knows when he will start to count the bits at time t 1 ).
3. The key vanishes after it is used by Alice and Bob.
Eve could not get this entangled information, so she does not know when Alice and Bob start to count the bits. Even Eve is at the same site of Alice or Bob, she could not get the key since it disappears after it is used. The keys used in encoding and decoding are used once and are never stored.

QUANTUM RANDOM WALK PROTOCOL
In this section, we look at the quantum key distribution problem under a slightly different consideration. We assume both Alice and Bob have a simple quantum device, whereas Eve has a quantum computer. Since the seminar work of BB84 and B92, quantum key distribution (QKD) receives widespread attention because its security is guaranteed by the law of physics and is different from the classical counterparts. 8 Our scheme based on the experimental realization 9 and security proof 10-12 extends the KKKP scheme 13 in two ways.
The procedure for the proposed quantum protocol is as follows: Quantum Walk Agreement Protocol 1. Alice and Bob perform a random walk on the random bits. In order to get an agreement, they both must use the same operator.
2. Alice and Bob teleport or synchronize with a quantum clock to exchange the "operator" 3. Once they are in synchronization with the same operator, they apply the "operator" on random bits stream, i.e. tree-walk the graph.
4. Alice and Bob yield to the same key, i.e. the path of the operator-oriented walk on the graph.
Security of our scheme which minimizes the common problem of high transmission rate of errors and defeats man-in-the-middle attack is cleverly directed by quantum walk on one q − bit. Once quantum walk determines the q − bit, Alice and Bob can use the agreed operator to perform classical tree-walking on the random bits stream and determine the key efficiently. Our scheme can be applied to any quantum device that satisfies the above requirement.
In a similar vein, we formulate a quantum walk on a graph. Consider a spin−1/2 particle that shifts to left or right depending on its spin state. Let a set of orthonormal basis states correspond to vertices of the graph. If a particle is in the state |g , that corresponds to a vertice g. (Another name for this technique is commonly used by computational group theorists to carry argument through for Cayley-graphs of Abelian groups and infinite groups.) We will look at the possible attacks from Eve's perspective. Eve with a quantum computer can intercept all messages and perform a quantum walk search. 14,15 Our procedure modifies the discrete quantum random walk result 16 with a different quantum device. Our quantum walk U searches the graph G as follows: Quantum Walk Agreement Search Algorithm 1. Initialize the quantum system in the uniform superposition |Φ 0 .
2. Do T times: Apply the marked walk U ′ .
3. Measure the position register.
4. Check if the measured vertex is the marked item.
The physical attack is that Eve can place a beam splitter attack between the quantum channel and amplify the error rate. Another attack is by eavesdropping with phase shifters. Once Eve has an estimate on the state pulse of quantum state, she can perform probabilistic search of the key space N , i.e. the random bits stream, on a √ N × √ N grid in time O( √ N log N ) (See A.6 for definitions). Since the quantum walk search is restricted by initial condition and localization of the quantum walk search, Eve is not guaranteed to find the key in timely fashion for practical purpose.

CONCLUSION
We have shown that our schemes are secure against weak impersonation attack, and quantum eavesdropping attacks. For future research on quantum key agreement protocol, we like to consider the potential weakness of random source generation on the satellite and carry out experiment on the Elliptic pseudo random generation functions. One open question is whether it is possible to extend our schemes with the additional capability of entity authentication and signature? For example, currently we are looking at the challenge of designing quantum cryptographic voting protocols. 17 Another line of research undertaken by us investigates whether quantum computer based on topological quantum computation 18 with Anyons 19 and quantum knots is easier to build and perform faster. Current schemes of designing quantum computers use techniques to control interference of quantum system with the ambient environment and lower the error rates. As an alternative approach to the open problems of quantum circuit complexity, 20 what can we say about braiding operator 21 as the universal quantum gates?
On the quantum search problems, we are looking to extend the quantum random walk techniques to arbitrary graphs, i.e. independent of initial condition and localization problems and provide a better bound on time and space.

ACKNOWLEDGEMENTS
It is a pleasure to thank Professor Mark Hillery for a discussion on the quantum random walk subject.

A.1. Discrete Logarithm Problem
We let G = g n be a cyclic group generated by g. By repeated squaring method, it is easy to compute g n in O(log n) steps. Finding n from g and g n is a hard problem with exponential complexity. The degree of computational complexity depends on the representation of the group. More generally in group-theoretic setting, given an isomorphism of two finite group G 1 , and Z k for k ∈ N , finding the image of an element g n under the isomorphism map is equivalent to solving the discrete log problem. A large variety of groups are studied for use in the discrete logarithm problem.
1. Subgroups of Z P for some prime p.
2. Subgroups of F p n for prime p = 2 3. Cyclic subgroups of the group of an elliptic curve E a,b (F p ) over the finite field F p with 4. The natural generalizations of the group of an elliptic curve to the Jacobian of a hyperelliptic curve

Ideal class group of an algebraic number field
A rigorous and formal security analysis with syntactical and semantical consideration is in here. 8

A.2. Random Resource
Most computer programming languages could generate random numbers. In Lisp the expression (random 100) produces an integer in the range between 0 and 99, with each of the 100 possible values having equal probability. But these are pseudo-random numbers: They "look" random, but under the surface there is nothing unpredictable about them. 22 The only source of true randomness in a sequence of pseudo-random numbers is a "seed" value that gets the series started. If you supply identical seeds, you get identical sequences; different seeds produce different numbers. The crucial role of the seed was made clear in the 1980s by Blum. He pointed out that a pseudorandom generator does not actually generate any randomness; it stretches or dilutes whatever randomness is in the seed, spreading it out over a longer series of numbers like a drop of pigment mixed into a gallon of paint.
For most purposes, pseudo-random numbers serve perfectly well often better than true random numbers. Almost all Monte Carlo work is based on them. Nevertheless, true randomness is still in demand, if only to supply seeds for pseudo-random generators. Finding events that are totally patternless turns out to be quite difficult.
A obvious scheme for digitizing noise is to measure the signal at certain instants and emit a 1 if the voltage is positive or a 0 if it is negative. Another popular source of randomness is the radioactive decay of atomic nuclei, a quantum phenomenon that seems to be near the ultimate in unpredictability.
Next we show an algorithm 23 that achieves excellent uniform distribution on seed generation.

A.3. Random Number Generator and Elliptic-Zeta function
Random number generator is an important mathematical tool. Van Dam 24 shows that many known hard computational problems can be exploited and solved by quantum factoring method and quantum search algorithm, e.g Gauss Sums over finite rings. We have not seen work that reduces Elliptic-Zeta function to Gauss Sums estimation. We will reproduce definitions and theorems from the Anshel and Goldfeld paper 23 and describe three candidates of one-way functions F Kronecker , F Elliptic , and F Artin .

A.3.1. Pseudorandom Number Generator.
We adopt the notion of a pseudorandom generator suggested and developed by Blum and Micali and Yao. A pseudorandom number generator is a deterministic polynomial time algorithm that expands short seeds into longer bit sequences such that the output of the ensemble is polynomial-time indistinguishable from a target probability distribution. We shall present an algorithm for a cryptographically secure pseudorandom number generator that is based on the candidate one-way function for the class Z Elliptic , and Z Artin . We shall call this pseudorandom number generator PNG Elliptic . It has the property that it transforms a short seed into a long binary string of zeros and 1s with the target probability (1/3, 2/3) (i.e., the probability of zero appearing is 2/3 while the probability of a 1 is 1/3). The proofs of these assertions are based on Theorems below.
Definition. Let P be a set of primes having a certain property. We define the density of P to be lim x→∞ p∈P,p≤x 1/ p≤x 1, provided the limit exists. If the limit does not exist, then the density of P is not defined.
With this definition, we now propose the following theorems.
THEOREM 1. Let a, b determine an elliptic curve E : y 2 = x 3 + ax + b. Define d to be the degree of the field obtained by adjoining the roots of the cubic equation x 3 + ax + b = 0 to Q. If d =1,2, then c E (p) will be even for all except finite many rational primes p. If d= 3, then the density of primes for which c E (p) is even is 1/3 while if d=6, the density is 2/3. Then P H has density |H|/|G|, where |H|, |G| denote the cardinalities of H, G, respectively. THEOREM 3. Let E be an elliptic curve defined over Q. Let K denote the field obtained by adjoining the 2-torsion points of E to Q. Then there exists an entire Artin L-function for all except finitely many rational primes p.

A.3.2. Coin Flipping by Telephone.
Alice and Bob want to simulate a random coin toss over a telephone. The following algorithm provides a mechanism for accomplishing this task. The algorithm assumes that B → ∞ and m = (log B) k for some constant k > 2.
Step 1. Alice chooses integers a, b such that the roots of the equation x 3 + ax + b = 0 generate a field of degree 6 over Q, and the discriminant △ = 4a 3 + 27b 2 lies in the interval B ≤ △ ≤ 2B. Alice then computes the vector v of the first m coefficients v = {a(1), a(2), ..., a(m)} of the Zeta function associated to E : y 2 = x 3 + ax + b. Alice transmits v to Bob.
Step 2. Bob randomly chooses two prime numbers p < p ′ with p > m.
Step 4. Bob can verify the correctness of the coin flip when Alice announces the elliptic curve E. Otherwise it is not feasible for him to compute trial (p, p ′ ).

A.4. Quantum Teleportation
Quantum teleportation (QT) 18, 19, 21 is a particularly attractive paradigm. It involves the transfer of a quantum state over an arbitrary spatial distance by exploiting the prearranged entanglement (correlation) of "carrier" quantum systems in conjunction with the transmission of a minimal amount of classical information. This concept was first discussed by Aharonov and Albert 25 (AA) using the method of nonlocal measurements.
Over a decade later, Bennett, Brassard, Crepeau, Jozsa, Peres, and Wootters (BBCJPW) 26 developed a detailed alternate protocol for teleportation. It consists of three stages. First, an Einstein-Podolsky-Rosen (EPR) 27 source of entangled particles is prepared. Sender and receiver share each a particle from a pair emitted by that source. Second, a Bell-operator measurement is performed at the sender on his EPR 27 particle and the teleportation-target particle, whose quantum state is unknown. Third, the outcome of the Bell measurement is transmitted to the receiver via a classical channel. This is followed by an appropriate unitary operation on the receiver's EPR particle. To justify the name "teleportation", 26 notice that the unknown state of the transfertarget particle is destroyed at the sender site and instantaneously appears at the receiver site. Actually, the state of the EPR particle at the receiver site becomes its exact replica. The teleported state is never located between the two sites during the transfer.
The first laboratory implementation of QT was carried out in 1997 at the University of Innsbruck by a team led by Anton Zeilinger. 28 It involved the successful transfer of a polarization state from one photon to another.

A.5. Quantum Clock Synchronization
Clock synchronization 29,30 is an important problem with many practical and scientific applications. Alice and Bob, both have good local clocks that are stable and accurate, and wish to synchronize these clocks in their common rest frame. The basic problem is easily formulated: determine the time difference ∆ between two spatially separated clocks, using the minimum communication resources. 31 Generally, the accuracy to which ∆ can be determined is a function of the clock frequency stability, and the uncertainty in the delivery times for messages sent between the two clocks. Given the stability of present clocks, and assuming realistic bounded uncertainties in the delivery times, protocols have been developed which presently allow determination of ∆ to accuracies better than 100 ns (even for clock separations greater than 8000 km); it is also predicted that accuracies of 100 ps should be achievable in the near future.
A quantum bit (q-bit ) behaves naturally much like a small clock. For example, a nuclear spin in a magnetic field processes at a frequency given by its gyromagnetic ratio times the magnetic field strength. And an optical q-bit, represented by the presence or absence of a single photon in a given mode, oscillates at the frequency of the electromagnetic carrier. The relative phase between the |0 and |1 states of a q-bit thus keeps time, much like a clock, and ticks away during transit. Unlike a classical clock, however, this phase information is lost after measurement, since projection causes the q-bit to collapse onto either |0 or |1 , so repeated measurements and many q-bits are necessary to determine ∆. On the other hand, with present technology it is practical to communicate q-bits over long distances through fibers, 32,33 and even in free space. 34 Let t a and t b be the local times on Alice and Bob's respective clocks. We assume that their clocks operate at exactly the same frequency and are perfectly stable. The goal is to determine the difference ∆= t b -t a , which is initially unknown to either of them. Quantum synchronization [35][36][37] comes in many schemas. Chuang 31 accomplished this goal by using the Ticking qubit handshake (TQH ) protocol. He also established an upper bound on the number of q-bits which must be transmitted in order to determine ∆ to a given accuracy. Chuang found that only O(n) q-bits are needed to obtain n bits of ∆, if we have the freedom of sending q-bits which tick at different frequencies.

A.6. Quantum Random Walk
We provide the standard notation 38 and model on tree and graph for our discussion. Then we also briefly describe the connection between the coined quantum random walk and the graph representation of quantum state. We cite the main result of quantum random walk theorem 16 used in our arguments.
Let us look at an example of tree T (V, E) that consists of vertices and edges. Consider a 3 − bits binary tree T. T with depth of 3, has 2 3 = 8 (vertices) binary numbers represented at its leaves. The topmost level of T is denoted 'root ' and the bottom level of T is denoted leaf. The prefixes associated with subtrees are denoted in italics. In this example, we consider three leaves the 001 ,011 , and 110 vertice. The tree-walking algorithm, a recursive depth first algorithm, here first singulates the 001 leave. It does this by following the path that connects two vertices and the complexity is O(log n).
Formally, given an undirected graph G = (V, E) that each vertex v stores a variable a v ∈ {0, 1}, our goal is to find a vertex v for which a v = 1 (assuming such vertex exists). We will often call such vertices marked and vertices for which a v = 0 unmarked.
In one step, an algorithm can examine the current vertex or move to a neighboring vertex in the graph G. The goal is to find a marked vertex in as few steps as possible.
A quantum algorithm is a sequence of unitary transformations on a Hilbert space 14 . H i ⊗ H V . H V is a Hilbert space spanned by states |v corresponding to vertices of G. H i represents the algorithm's internal state and can be of arbitrary fixed dimension. A t-step quantum algorithm is a sequence U 1 , U 2 , . . ., U t where each U i is either a query or a local transformation. A query U i consists of two transformations (U 0 i , U 1 i ). U 0 i ⊗ I is applied to all H i ⊗ |v for which a v = 0 and U 1 i ⊗ I is applied to all H i ⊗ |v for which a v = 1. A local transformation can be defined in several ways. In this paper, we require them to be Z-local. A transformation U i is Z-local if, for any v ∈ V and |ψ ∈ H i , the state U i (|ψ ⊗ |v ) is contained in the subspace H i ⊗ H Γ(v) where H Γ(v) ⊂ H V is spanned by the state |v and the states |v ′ for all v ′ adjacent to v. Our results also apply if the local transformations are C-local.
The algorithm starts in a fixed starting state |ψ start and applies U 1 , . . ., U t . This results in a final state |ψ f inal = U t U t−1 . . . U 1 |ψ start . Then, we measure |ψ start . The algorithm succeeds if measuring the H V part of the final state gives |g such that a g = 1.
THEOREM 16 4. The associated quantum walk search algorithm takes O( √ N log N ) steps and the probability to measure the marked state is Ω(1/ log N ). This yields a local search algorithm running in time O( √ N log N ).