Method of constructing a semi-public key system in QAP-based homomorphic encryption

Abstract

The method of constructing QAP-based Homomorphic Encryption (HE) in the semi-public setting is introduced, which comprises: encryption, computation, and decryption. The data receiver produces a semi-public key Key.sub.s-pub. The data provider can encode his k-qubit plaintext |x to a k-qubit ciphertext |ψ.sub.en=Q.sub.P|x via a k-qubit invertible operator Q.sub.P randomly generated by Key.sub.s-pub. From the provider, the message En(ζ.sub.p) of Q.sub.P encoded by a cryptosystem G.sub.crypt in Key.sub.s-pub is transmitted to the receiver through a small-resource communication channel and the ciphertext |ψ.sub.en is conveyed to the cloud. The receiver creates the instruction of encoded computation U.sub.en=PMQ.sub.P and transports to the cloud, where M is the required k-qubit arithmetic operation, P a k-qubit permutation, and a k-qubit operator to mingle with M. According the instruction, the cloud performs the encrypted evaluation U.sub.en|ψ.sub.en and transfer to the receiver. The decryption Key.sub.priv U.sub.en|ψ.sub.en is conducted by the receiver via the private key Key.sub.priv=.sup.†P.sup.†, a complex-transpose of the product P, to obtain the final result M|x.

Claims

1. A method of constructing a semi-public key system in Quotient Algebra Partition (QAP)-based homomorphic encryption (HE), by an algebraic structure, QAP, and an arithmetic operation of homomorphic encryption, wherein the method comprises: S1: encryption: comprising key generation and encoding; S11: key generation: a data receiver generates a semi-public key, Key.sub.s-pub and a private key, Key.sub.priv; wherein the semi-public key Key.sub.s-pub, randomly generates an arbitrary k-qubit operation from a gigantic number of invertible gates of the same qubits; the private key, Key.sub.priv, for decryption is represented by Key.sub.priv=.sup.†P.sup.†, which is a product of two k-qubit operators, .sup.† and P.sup.†; wherein the semi-public key, Key.sub.s-pub is published in public space to transforming a plaintext to a ciphertext by anyone; and the private key, Key.sub.priv, is retained by the data receiver to decrypt the encrypted ciphertext; S12: encoding: a data provider provides a k-qubit plaintext, |x, a k-qubit operation Q.sub.p generated by the semi-public key, Key.sub.s-pub; an encoded state of ciphertext |ψ.sub.en=Q.sub.p|x with the same qubit length is obtained; the semi-public key, Key.sub.s-pub, encodes a binary string ζ.sub.p, which is 1-to-1 correspondence to Q.sub.p according to a given code system G.sub.crypt, into an encrypted message En(ζ.sub.p) and sends it to the data receiver through a communication channel of small resource; and the data provider sends the ciphertext |ψ.sub.en to a computation provider; S2: Computation: S21: a k-qubit arithmetic operation M is given to be operated and output a homomorphic encryption operation U.sub.en enable to be conducted on the encrypted state |ψ.sub.en; after receiving the encrypted message En(ζ.sub.p) from the data provider and obtaining the corresponding k-qubit operation Q.sub.p by the decryption process in G.sub.crypt, the data receiver produces a computational instructions of the homomorphic encryption operation U.sub.en with a form: $\begin{array}{c}{U}_{en}=P𝒜{\mathrm{MQ}}_p^{†}\\ =\left(P_1^{†}{W}_1^{†}𝒜ℳW_1{P}_1\right)\left(P_1^{†}{P}_0\right)\left(P_0^{†}{W}_2\right)\end{array}$ where Q.sub.P.sup.†=W.sub.1W.sub.2 is a product of a qubit permutation W.sub.1 and an operation W.sub.2 comprising of elementary gates (CNOTs, SWAPs, Toffolis, CSWAPs), P.sub.j=0,1 and P are qubit permutations following the nilpotent condition PW.sub.1P.sub.1=I.sub.2.sub.n, and then sends U.sub.en to the computation provider; S22: the computation provider receives the computational instructions to computes U.sub.en|ψ.sub.en and an encrypted evaluation is obtained; S3: Decryption: the computation provider conducts homomorphic encryption computation U.sub.en|ψ.sub.en and sends the encrypted evaluation to the data receiver; the data receiver decrypts the evaluation by applying the private key Key.sub.priv=.sup.†P.sup.† to the state U.sub.en|ψ.sub.en, which is written as .sup.†P.sup.†U.sub.en|ψ.sub.en=M|x, and then obtains the unencoded result M|x.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flow chart of actual operation for encryption, computation and decryption according to the present inventive concept; and

(2) FIG. 2 is a schematic diagram of the elementary gates used in the algorithm according to the present inventive concept.

DETAILED DESCRIPTION

(3) The present inventive concept is described by the following specific embodiments. Those with ordinary skills in the arts can readily understand other advantages and functions of the present inventive concept after reading the disclosure of this specification. Any changes or adjustments made to their relative relationships, without modifying the substantial technical contents, are also to be construed as within the range implementable by the present inventive concept.

(4) Moreover, the word “exemplary” or “embodiment” is used herein to mean serving as an example, instance, or illustration. Any aspect or design described herein as exemplary or an embodiment is not necessarily to be construed as preferred or advantageous over other aspects or designs. Rather, use of the word “exemplary” or “embodiment” is intended to present concepts and techniques in a concrete fashion.

(5) As used in this application, the term “or” is intended to mean an inclusive “or” rather than an exclusive “or.” That is, unless specified otherwise or clear from context, “X employs A or B” is intended to mean any of the natural inclusive permutations. That is, if X employs A; X employs B; or X employs both A and B, then “X employs A or B” is satisfied under any of the foregoing instances. In addition, the articles “a” and “an” as used in this application and the appended claims should generally be construed to mean “one or more,” unless specified otherwise or clear from context to be directed to a singular form.

(6) Please refer to FIG. 1. The present inventive concept provides a method of constructing a semi-public key system in Quotient Algebra Partition (QAP)-based homomorphic encryption (HE), by an algebraic structure, QAP, and an arithmetic operation of homomorphic encryption. The Encryption, computation and decryption are computed in the framework of QAP by QAP-based fault tolerance quantum computation in an algebraic structure of QAP.

(7) The method of the present inventive concept comprises:

(8) S1. encryption: comprising S11. key generation and S12. encoding by a data receiver (Alice). In step S11. key generation, Alice generates a semi-public key, Key.sub.s-pub (3) for encryption and a private key, Key.sub.priv (4) for decryption, wherein the semi-public key Key.sub.priv, may randomly generate an arbitrary k-qubit operation chosen from a gigantic number of invertible gates of the same qubits. For instance, the private key Key.sub.priv can be chosen as a key to randomly provide an arbitrary element from a number k!=1×2× . . . ×k of k-qubit permutations. The private key, Key.sub.priv, for decryption may be represented by Key.sub.priv=.sup.†P.sup.†, which is a product of two n-qubit operators, .sup.† and P.sup.†. The semi-public key, Key.sub.s-pub, may be published in public space to transforming a plaintext to a ciphertext by anyone; and the private key, Key.sub.priv, is retained by Alice to decrypt the encrypted ciphertext. In the Step S12 encoding, a data provider (Bob) provides k-qubit plaintext, |x, for the homomorphic encryption computation by the k-qubit qubit permutation generated by the semi-public key, Key.sub.priv, and an encoded state of ciphertext |ψ.sub.en=Q.sub.p|x with the same qubit length is obtained, which means a ciphertext with the same length as the plaintext would be obtained, rather than a longer length ciphertext, as shown in {circle around (2)} in FIG. 1. Because error-corrections are not necessary, and thereby the encryption time is shorter, the security is higher based on the same security level and same plaintext. The semi-public key, Key.sub.s-pub (3) encodes a binary string ζ.sub.p which is 1-to-1 correspondence to Q.sub.p according to a given code system, G.sub.crypt (for example, any post-quantum code system may be given) into an encrypted message En(ζ.sub.p) and sends it to Alice (1) (please refer to {circle around (3)} in FIG. 1). Bob (2) sends the cipher |ψ.sub.en to a computation provider (Cloud) (6) (please refer to {circle around (4)} in FIG. 1). This step allows a small resource of communication between Bob (2) and Alice (1), which means the semi-public key, Key.sub.s-pub (3) is enable to send any qubit permutation Q.sub.p and its encoded encrypted message En(ζ.sub.p) (5) to Alice (1) at the same time.

(9) According to an embodiment of the present inventive concept, the method may comprise step S2. Computation. A k-qubit arithmetic operation M is given to be operated and output a homomorphic encryption operation U.sub.en enable to be conducted on the encrypted state |ψ.sub.en; after receiving the encrypted message En(ζ.sub.p) corresponding to the qubit permutation Q.sub.p, from Bob, Alice (1) may produce a computational instructions of the homomorphic encryption operation U.sub.en with a form:
U.sub.en=PMQ.sub.p.sup.†=(P.sub.1.sup.†W.sub.1.sup.†W.sub.1P.sub.1)(P.sub.1.sup.†P.sub.0)(P.sub.0.sup.†W.sub.2),

(10) where Q.sub.P.sup.†=W.sub.1W.sub.2, which is a product of a qubit permutation W.sub.1 and an operation W.sub.2 comprising elementary gates (Spinors, CNOTs, Toffolis, SWAPs, Controlled SWAP, Multi-Control Gate), and P.sub.j=0,1 and P are qubit permutations and follow PW.sub.1P.sub.1=I.sub.2.sub.n.

(11) In an embodiment of the present inventive concept, Alice (1) may decrypt and recover the encrypted message En(ζ.sub.p) to the original Q.sub.p and encodes Q.sub.p into the computational instruction U.sub.en and sends to the Cloud (6) (please refer to {circle around (5)} in FIG. 1). The Cloud (6) may further receive a computational instructions to computes U.sub.en|ψ.sub.en.

(12) According to an embodiment of the present inventive concept, the method may comprise step S3. Decryption. The Cloud (6) conducts the homomorphic encryption computation U.sub.en|ψ.sub.en and sends the encrypted results to Alice (1) (please refer to {circle around (6)} in FIG. 1). Alice (1) decrypts the results by applying the private key, Key.sub.priv=.sup.†P.sup.† to the state U.sub.en|ψ.sub.en, which is written as .sup.†P.sup.†U.sub.en|ψ.sub.en =M|x, and then obtains the result M|x.

(13) Please refer to FIG. 2 which is a schematic diagram of the elementary gates used in the algorithm according to the present inventive concept. According to the present inventive concept, the spinor (7) is an n-qubit spinor .sub.a.sup.ζ=.sub.a.sub.1.sup.ε.sup.1.Math..sub.a.sub.2.sup.ε.sup.2.Math. . . . .Math..sub.a.sub.n.sup.ε.sup.n, which is composed of a tensor product of n spinors, with ζ, α∈ Z.sub.2.sup.n and ε.sub.j, a.sub.j ∈Z.sub.2. Each of the spinors .sub.a.sub.j.sup.ε.sup.j, 1≤j≤n, may be represented as a 2×2 matrix. The spinor .sub.a.sub.j.sup.ε.sup.j may transform a single-bit string b.sub.j into b.sub.j⊕a.sub.j, where ⊕ means a logical XOR operation, i.e. 0⊕0=0=1⊕1, 0⊕1=1=1⊕0.

(14) According to the present inventive concept, CNOT (8) is a binary logic gate operation. A binary string, a.sub.ia.sub.j, is given, where a.sub.i is a control bit and a.sub.j is a target bit. a.sub.i remain the same and a.sub.j is transformed into a.sub.j⊕a.sub.i for the CNOT operation performing on a.sub.ia.sub.j.

(15) According to the present inventive concept, Toffoli gate (9) is a trinary logic gate operation. A trinary string, a.sub.ia.sub.ja.sub.l, is given, where a.sub.i and a.sub.j are control bits and a.sub.l is a target bit. a.sub.i and a.sub.j remain the same and a.sub.l is transformed into=a.sub.l⊕(a.sub.i∧a.sub.j) for the Toffoli gate operation performing on a.sub.ia.sub.ja.sub.l, where ∧ means a logical AND operation.

(16) According to the present inventive concept, SWAP (10) is a binary logic gate operation. A binary string, a.sub.ia.sub.j, is given. The SWAP gate swaps the qubits, a.sub.i and a.sub.j, to generate a string a.sub.ja.sub.i.

(17) According to the present inventive concept, CSWAP (Controlled SWAP) (11) is a trinary logic gate operation. A trinary string, a.sub.ia.sub.ja.sub.l is given, where a.sub.i is a control bit and a.sub.j and a.sub.l is target bits. a.sub.i remains the same and a.sub.j is transformed into (a.sub.j∧ā.sub.i)⊕(a.sub.j∧a.sub.i), a.sub.l is transformed into (a.sub.l∧ā.sub.i)⊕(a.sub.l∧a.sub.i) for the CSWAP operation on a.sub.ia.sub.ja.sub.l, where ā.sub.i is a negation of the original bit a.sub.i, e.g. 0=1, 1=0.

(18) According to the present inventive concept, Multi-Control gate (12) is a n-nary logical gate operation. A n-bit string, a.sub.1a.sub.2 . . . a.sub.pa.sub.p+1 . . . a.sub.n, is given. Performing a multi-control p-gate ∧.sub.n-p.sup.12 . . . p(.sub.ω.sup.π), if the first p-bit a.sub.1=a.sub.2= . . . =a.sub.p=1, the last (n-p)-bits are effected by the spinor .sub.ω.sup.π; otherwise the n-bit string remains the same.

(19) According to the present inventive concept, the method of constructing a semi-public key system in QAP-based homomorphic encryption of the present inventive concept is a method of fault tolerance quantum computation in QAP by an algebraic structure, QAP, and an arithmetic operation of homomorphic encryption. The fully homomorphic encryption is naturally achieved in either scheme through delicately-designed invertible gates, acting on the Hilbert space and thereby the present inventive concept may provide an exact solutions rather than approximated ones. It conducts encoded arithmetic operation and the operators are fully blind operators and allows problem-dependent optimizations. The present inventive concept allows a communication channel to be built between the data receiver and the data provider with low cost, to improve the encryption efficiency and security and lower the computation cost. Besides, the ciphertext has the same length during the encryption, so an overhead of error-correction is not necessary in homomorphic encryption computation and thereby it may lower the computational cost.

(20) In summary, the method of constructing a semi-public key system in QAP-based homomorphic encryption of the present inventive concept allows so-called Homomorphic Encryption to be conducted with a small resource of communication between the data provider and the data receiver during encryption without secret disclosures. The encrypted ciphertext has the same length without errors. Thereby the encryption time is shorter, the security is higher based on the same security level and same plaintext and the method allows problem-dependent optimizations with modest overheads.

(21) The foregoing descriptions of the detailed embodiments are only illustrated to disclose the features and functions of the present inventive concept and not restrictive of the scope of the present inventive concept. It should be understood to those in the art that all modifications and variations according to the spirit and principle in the disclosure of the present inventive concept should fall within the scope of the appended claims.