Bit-oriented quantum public-key encryption Chenmiao Wu 1,2,3, Li Yang1,2∗ 1.State Key Laboratory of Information Security, Institute of Information Engineering, 5 Chinese Academy of Sciences, Beijing 100093, China 1 0 2.Data Assurance and Communication Security Research Center,Chinese Academy of 2 Sciences, Beijing 100093, China 3.University of Chinese Academy of Sciences, Beijing, 100049, China n a J 9 2 ] Abstract h p We propose a bit-oriented quantum public-key scheme which uses Boolean - t n function as private-key and randomly changed pairs of quantum state and a classical string as public-keys. Contrast to the typical classical public-key u q scheme, one private-key in our scheme corresponds to an exponential number [ of public-keys. The goal of our scheme is to achieve information-theoretic 2 security, and the security analysis is also given. v 3 Keywords: 4 quantum cryptography, quantum public-key encryption, information 9 5 theoretic security 0 . 1 0 1. Introduction 5 1 Public-key encryption (PKE) isoneoftheimportant branches of cryptog- : v raphy, and has been widely applied into various fields. Classical public-key i X encryption is based on one-way function with the hardness of solving the r a computational difficult problem. Since the investigation to quantum Tur- ing machine was started and Shor’s algorithm as well as Grover’s algorithm were put forward, quantum public-key encryption (QPKE) emerged as times require. According to whether the encrypted messages and keys are in quantum states or not, we classify QPKE into four types. The first type is that ∗Corresponding author email: [email protected] messages and keys are both classical. The Knapsack-based scheme[1] pro- posed by Okamato uses classical key to encrypt and to decrypt classical messages, but the participants are all quantum probabilitic polynomial Tur- ing machine. The second type encrpts quantum messages with classical keys. The McEliece QPKE scheme proposed in [2] was belong to this type. This scheme was based on a classical NP-complete problem related with finding a code word of a given weight in a linear binary code. With this foudation, Yang et al. [3] gave the definition of induced trapdoor one-way quantum function. Fujita[4] also constructed McEliece QPKE relied on the difficulty of NPC problem. The third type refers to classical messages and quan- tum keys. Gottesman and Chuang [5] were the first to construct quantum states as public-keys. Kawachi[6, 7] investigated the cryptographic property ”computational indistinguishability” of two quantum states generated via fully flipped permutations and proposed a QPKE based on it. Nikolopou- los [8] constructed a QPKE from the perspective of single-qubit rotation and trapdoor one-way function. [9] also proposed a information-theoretic se- cure QPKE designed with conjugate coding single-photon string. The fourth is with quantum messages and quantum keys. Gottesman [10] proposed a QPKE based on teleportation with information-theoretic security. Liang et al. [11] combined the basic idea of [12] and quantum perfect encryption to construct an information-theoretically secure QPKE. Kawachi and Pormann [13] presented another kind of quantum message-oriented public-key encryp- tionprotocolwithquantumpublic-key, buttheyshowthisscheme isbounded information-theoretic secure. In this paper, we invetigate the way to construct bit-oriented public-key encryption scheme. Firstly, we overview some definition about information- theoretically security aboutQPKEandquantum perfect encryption. Second, we present a new bit-oriental public-key encryption scheme. Finally, we investigate the scheme’s security against attack to the key and attack to the encryption and prove that the scheme is information-theoretically secure. 2. Preliminaries 2.1. Information-theoretic security Goldreich[14]definedtheciphertext indistinguishability inclassical PKE: for every polynomial-size circuit family c , every positive polynomial p( ), all n · 2 sufficiently large n, and every x,y 0,1 ∗, satisfies: ∈ { } 1 Pr C (G(1n),E (x)) = 1 Pr C (G(1n),E (y)) = 1 < . (1) n G(1n) n G(1n) − p(n) (cid:12) (cid:12) (cid:2) (cid:3) (cid:2) (cid:3) (cid:12) (cid:12) S(cid:12)imilar to the ciphertext indistinguishability in classical context(cid:12), [15] extend the concept to QPKE and presented the definition of information-theoretic quantum ciphertext-indistinguishability for public-key encryption of classical messages: Definition 1. A quantum public-key encryption scheme of classical messages is information-theoretically ciphertext-indistinguishable, if for every quantum circuit family C , every positive polynomial p( ), all sufficiently large n, n { } · and any two bit-string x,y 0,1 ∗, satisfies: ∈ { } 1 Pr C (G(1n),E (x)) = 1 Pr C (G(1n),E (y)) = 1 < (2) n G(1n) n G(1n) − p(n) (cid:12) (cid:12) (cid:2) (cid:3) (cid:2) (cid:3) (cid:12) (cid:12) where G is key generation algorithm, E is a quantum encryption algorithm, (cid:12) (cid:12) and the ciphertext E(x), E(y) are quantum states. [15]alsoprovedthataquantumpublic-keyencryptionschemeisinformation- theoretically secure if the trace distance between any two cihpertexts is O( 1 ), and Eq. (1) holds. 2n Definition 2. Forall plaintextx and y, let the density operators of ciphertext E(x) and E(y) be ρ and ρ respectively. A quantum public-key encryption x y scheme is said to be information-theoretically secure, if for every positive polynomial p( ) and every sufficiently large n, satisfies: · 1 D(ρ ,ρ ) < (3) x y p(n) 2.2. Quantum perfect encryption Assume a set of oeprations U , each U is a 2n 2n unitary matrix. The k k × ciphertext state of n-qubit quantum message ρ is ρ . k refers to private-key, C each k is chosen with probability p . To encrypt, applying U to ρ: k k ρ = U ρU† (4) c k k The private-key owner can use U† to decrypt: k ρ = U†ρU (5) k k 3 As defined in [16]: for every input state ρ, the output state is an ultimately mixed state: I p U ρU+ = . (6) k k k 2 k X That is: p = 1 ,U = UαUβ,k = (α,β),α,β 0,1 n is a quantum perfect { k 22n k 1 2 ∈ { } } encryption, where U = UαUβ constitute a complete orthogonal basis. k 1 2 2.3. Simple description of QPKE in [12] The QPKE in [12] consists of three phases: key generation, encryption and decryption. SupposethatΩ = k Z W (k)isodd ,Π = k Z W (k)iseven . n 2n H n 2n H { ∈ | } { ∈ | } W denotes the hamming weight of k. In this scheme defined two n-qubit H states: 1 ρ0 = ( i + i k )( i + i k ) (7) k,i 2 | i | ⊕ i h | h ⊕ | and 1 ρ1 = ( i i k )( i i k ), (8) k,i 2 | i−| ⊕ i h |−h ⊕ | where i Z , k Ω . 2n n ∈ ∈ [Key Generation] 1. Bob randomly selects a Boolean Function as his private-key from the mapping set F : 0,1 m 0,1 n, and also chooses a bit string s, { } 7→ { } s Z ; 2m ∈ 2. Bob computes F(s) = k, and then prepares quantum state ρ0 accord- k,i ing to the string k Ω , i Z ; n 2n ∈ ∈ 3. Bob sends his public-key (s,ρ0 ) to the public register. k,i [encryption] 1. Ailce download Bob’s public-key from the public register; 4 2. if she wants to send message ”0”, she sends (s,ρ0 ) to Bob; if the k,i message is ”1”, she does Z⊗n on ρ0 to acquire ρ1 , then sends (s,ρ1 ) k,i k,i k,i to Bob. [decryption] 1. Receiving the message send from Alice, Bob uses his private-key F to compute F(S) = k; 2. Using a bit ”1” in k as controlled bit to do CONT operation to other bitsinthequantumstate, thenmeasuring thequantum statewithbasis + , to get the message. {| i |−i} 2.4. Attack method [9] presented an effective attack for the scheme descrpted in 2.4. The concrete steps are as follows: 1. whenanattackergetsuser’spublic-key(s,ρ0 ),hedoesrandomHadamard k,i transform to the quantum state ρ0 : k,i 1 1 H⊗n[ ( i + i k )] = (( 1)y·i y +( 1)y·(i⊕k) y ) √2 | i | ⊕ i √2n+1 − | i − | i y X 1 = ( 1)y·i(1+( 1)y·k) y (9) √2n+1 − − | i y X 2. Attacker measures y , and gets y . 0 | i y satisfies y k = 0. That is to say, it satisfies the equation y F(s) = 0. 0 0 0 · · The Boolean function is n-input and n-output, it can be expressed as: F(s) = (F(1)(s),...,F(n)(s)) (10) The minor term expression of every F(i)(s) is: F(j)(s) = (saj11 ... saj1n) ... (sajp(n)1 ... sajp(n)n) (11) 1 · · n ⊕ ⊕ 1 · · n Since that xa = xa a 1, we rewrite the Boolean function in linear expres- ⊕ ⊕ sion: p(n) n F(j)(s) = ( (s a +a +1)) (12) β jαβ jαβ α=1 β=1 M Y So the attacker gets the equation about F(s), he will be able to acquire information about user’s private-key F. 5 3. bit-oriented public-key encryption 3.1. preparition of quantum state Firstly, we take into account how to construct the quantum state used in this scheme. The quantum state is ρ0: k 1 ρ0 = ( 0 + k )( 0 + k ) (13) k 2 | i | i h | h | The concrete steps of preparing quantum state ρ0 is as follows: k 1. Prepare quantum state 0 0 and two quantum registers. Applying | i⊗| i Hadamard transform to the first register, the state of the whole system becomes: 0 + 1 (H I⊗n)( 0 0 ) = | i | i 0 (14) ⊗ | i⊗| i √2 ⊗| i 2. Definecontrolled-k operatorC as: C 0 0 = 0 0 ,C 1 0 = 1 k , k k k | i| i | i| i | i| i | i| i C can be realized via a group of CNOT operations. We get the state: k 1 ( 0 0 + 1 k ) (15) √2 | i| i | i| i 3. Use one of the non-zero bits in k to do CNOT to the first register, then obtain: 1 ( 0 0 + 0 k ) (16) √2 | i| i | i| i Finally, we get the state ρ0 . k,i ρ1 can be obtained by applying Z⊗n on ρ0 . k,i k,i Remark 1. There is another way to prepare ρ0 : k,i 1. prepare n-qubit quantum state 0 , and select the jth qubit ”0 ” which j | i at the same time satisfies k = 1 in 0 to do Hadamard transform: j | i 0 + 1 j j 0 ,...,0 (| i | i) 0 ,...,0 , 1 j−1 j+1 n | i √2 | i 6 2. use all the ”1” in k to do CNOT on the above quantum state, we acquire: 1 ( 0 + k ). √2 | i | i Compared with the previous one, this method is more efficient because of that the total number of CNOT operation decreased by two. 3.2. detail description of bit-oriented public-key encryption Letk Ω ,k = k ,...,k ,k = k ,...,k andk = k ,...,k 1 n 1 11 1n 2 21 2n 3 31 3n ∈ { } { } { } are bit strings, where each element is in 0,1 . We denote H⊗k = Hk1 { } ⊗ Hkn, where H0 = I, H1 = H. The definition is similar with Y⊗k ···⊗ [Key Generation] 1. Bob selects randomly two Boolean function F = (F ,F ,F ) from 1 2 3 F : 0,1 m 0,1 n as his private-key, and also chooses two string { } 7→ { } s = (s ,s ,s ) randomly from the set 0,1 m to do the computation 1 2 3 { } F (s ) = k , F (s ) = k , F (s ) = k to get k = (k ,k ,k ). If k / Ω , 1 1 1 2 2 2 3 3 3 1 2 3 1 n ∈ Bob selects s again until k Ω ; 1 1 n ∈ 2. Bob uses k to prepare quantum state ρ0 ,and then does Hadamard 1 k1 transform on ρ0 to get the quantum part of public-key according to k1 k : 2 1 ρ0 = Y⊗k3H⊗k2( 0 + k )( 0 + k )H⊗k2Y⊗k3 (17) F(s) 2 | i | 1i h | h 1| 3. Bob stores (s,ρ0 ) in the quantum registers as his public-key. F(s) [encryption] 1. Alice downloads Bob’s public-key from quantum registers; 2. if Alice wants to send message 0, she sends (s,ρ0 ) to Bob; if she F(s) sends 1, she does transform as bellow: ρ1 = Y⊗nρ0 (Y⊗n)† F(s) F(s) 1 = Y⊗nY⊗k3H⊗k2( 0 + k )( 0 + k )H⊗k2Y⊗k3Y⊗n 1 1 2 | i | i h | h | 1 = Y⊗k3H⊗k2( 1 +( 1)p(k1) k )( 1 +( 1)p(k1) k )H⊗k2Y⊗k3 1 1 2 | i − | i h | − h | 1 = Y⊗k3H⊗k2( 1 k )( 1 k )Y⊗k3H⊗k2, (18) 1 1 2 | i−| i h |−h | 7 where the length of n is even, 3. Alice sends (s,ρ1 ) to Bob; F(s) [Decryption] 1. Bobusess = (s ,s ,s )andF = (F ,F ,F )tocomputek = (k ,k ,k ); 1 2 3 1 2 3 1 2 3 2. Bob uses k ,k to remove transforms on the ciphertext state ρb : 2 3 F(s) ρb = (Y⊗k3H⊗k2)†ρb Y⊗k3H⊗k2 (19) k F(s) 3. Bob sums the 2th and nth qubit to the first component. If the trans- mitted message is 0, the quantum state becomes: 0 ,0 ,...,0 + 1 2 n | i 1 ,k ,...,k , and then he uses the first bit in the second component 1 2 n | i k as controlled bit to do CNOT operation to other bits in this state: 1 | i 0 ,0 ,...,0 + 1 ,0 ,...,0 . If the transmitted message is 1, the 1 2 n 1 2 n | i | i quantum state after operation is: 0 ,1 ,...,1 1 ,k ,...,k , and 1 2 n 1 2 n | i−| i takes the first bit in k as controlled bit to do CNOT operationto other 1 bits to get the state: 0 ,0 ,...,0 1 ,0 ,...,0 . Finally, Bob mea- 1 2 n 1 2 n | i−| i sures the quantum state with basis + , to get the message. {| i |−i} Remark 2. The Boolean function F can be generated efficiently. For the m-input, n-output F = (F(1)(s),...,F(n)(s)), each output F(i)(s) has p(n) terms. The minor term expression of every F(i)(s) is: F(j)(s) = (saj11 ... saj1n) ... (sajp(n)1 ... sajp(n)n). (20) 1 · · n ⊕ ⊕ 1 · · n Each term sajα1 ... sajαn can be determined by n times of coin tossing. If we 1 · · n toss the coin for np(n) times, p(n) components are determined. Therefore, the Boolean function F will be efficiently generated by n2p(n) times of coin tossing. 4. Security analysis The security of the bit-oriental quantum public-key encryption scheme proposed above is analyzed from two aspects: (1) the security of private-key; (2) the security of encryption. 8 4.1. security of private key The quantum part of public-key is ρ0 . Since the adversary has no F(s) idea of private-key F = (F ,F ,F ), the public-key state for him is ρ0 = 1 2 3 p ρ0 . The specific expression of ρ0 is: F F(s) F(s) F P 1 ρ0 = Y⊗k3H⊗k2 ( 0 + k )( 0 + k ) H⊗k2Y⊗k3. (21) F(S) 2 | i | 1i h | h 1| h i Thus, we have: ρ0 = p ρ0 F F(s) F X 1 1 = Y⊗k3H⊗k2 ( 0 + k )( 0 + k ) H⊗k2Y⊗k3 22n 2n | i | 1i h | h 1| kX2,k3 h Xk1 i 1 = Y⊗k3H⊗k2ρ(Y⊗k3H⊗k2)†, (22) 22n kX2,k3 where 1 ρ = ( 0 + k )( 0 + k ). (23) 2n | i | 1i h | h 1| Xk1 Since k 0,1 n, the possibilities of the value of k is 2n. The Boolean 1 1 ∈ { } function F (s ) has n-output, and each output has p(n) terms, so n2p(n) 1 1 times coin tossing will determine F (s ). n2p(n) times coin tossing has 2n2p(n) 1 1 possibilities. The possibilities of F (s ) is 2nnp(n)−n times of that of k . So the 1 1 1 output of private-key F (s ) iterates over all the possible value of k . (k ,F ) 1 1 1 2 2 and (k ,F ) is the same case as (k ,F ). 3 3 1 1 Before demonstrate the quantum state of ρ0 is an ultimately mixed state, we firstly prove: p = 1 ,U = YαHβ,k = (α,β),α,β 0,1 n is a { k 22n k ∈ { } } quantum perfect encryption. Proof. YαHβ,α,β 0,1 n is complete orthogonal basis, therefore any n- { ∈ { } } qubit state can be expressed as a linear combination of 2n unitary matrices: ρ = a YαHβ, (24) α,β α,β X 9 where 1 a = tr(ρHβYα), (25) α,β 2n 1 tr( a YαHβHδYγ) 2n α,β α,β X 1 = tr(a + ( 1)(δ⊕β)·γYα+γHβ+δ). (26) 2n α,β − γ6=α or δ6=β X In the above equation is either α = γ or β = δ, moreover, tr(Y) = 0, 6 6 tr(H) = 0, so tr ( 1)α2+γ2+(δ⊕β)·γYα+γHβ+δ = 0. − γ6=α or δ6=β (cid:0) P (cid:1) 1 1 tr( a YαHβHδYγ) = a (27) 2n α,β 2n α,β α,β X 1 p U ρU† = YγHδρHδYγ k k k 22n k γ,δ X X 1 = a YγHδYαHβHδYγ α,β 22n α,β γ,δ X X 1 = a ( 1)α·δYαYγHδ( 1)β·γHδYγHβ 22n α,β − − α,β γ,δ X X 1 = a ( 1)α·δ( 1)β·γYαHβ, (28) 22n α,β − − α,β γ,δ X X because of 1 ( 1)β·γ = δ , p U ρU† is as bellow: 2n − β,0 k k k γ∈{0,1}n k P P p U ρU† = a δ δ YαHβ k k k α,β α,0 β,0 t α,β X X = a I 00 tr(ρ) = I 2n I = (29) 2n 10