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

Abstract

A public-key scheme of Homomorphic Encryption (HE) in the framework Quotient Algebra Partition (QAP) comprises: encryption, computation and decryption. With the data receiver choosing a partition or a QAP, [n, k, C], a public key Key.sub.pub=(VQ.sub.en, Gen.sub.ε) and a private key Key.sub.priv=.sup.†P.sup.† are produced, where VQ.sub.en is the product of an n-qubit permutation V and an n-qubit encoding operator Q.sub.en, Gen.sub.ε an error generator randomly provides a dressed operator Ē=V.sup.†EV spinor error E of [n, k, C]. Then, by Key.sub.pub, the sender can encode his k-qubit plaintext Ix) into an n-qubit ciphertext |ψ.sub.en, which is transmitted to the cloud. The receiver prepares the instruction of encoded computation U.sub.en=PV.sup.†Q.sub.en.sup.† for a given k-qubit action M and sends to cloud, where is the error-correction operator of [n, k, C], =I.sub.2.sub.n−k.Math.M the tensor product of the (n−k)-qubit identity I.sub.2.sub.n−k and M , and V.sup.†Q.sup.†.sub.en and P the complex-transposes of VQ.sub.en and .sup.†P.sup.† respectively. The cloud executes the homomorphic encryption computation U.sub.en|ψ.sub.en) and conveys the encrypted result to receiver. The receiver performs the decryption Key.sub.privU.sub.en|ψ.sub.en and obtains the final result M|x.

Claims

1. A method of constructing a 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: a quantum code [n, k, C], which is structurally a QAP and wherein n>k, is chosen by a data receiver at first; S11: key generation: the data receiver generates a public key, Key.sub.pub, to encrypt data and a private key, Key.sub.priv, to decrypt data; wherein the public key is represented by
Key.sub.pub=(VQ.sub.en, Gen.sub.ε),  where Q.sub.en is an n-qubit encoding in [n, k, C], V is an n-qubit permutation, Gen.sub.ε is an error generator allowing to randomly provide an error from a modified error set ε composed of a gigantic number of dressed operators Ē=VEV.sup.† of errors E in [n, k, C]; and wherein the private key for decryption is represented by Key.sub.priv=.sup.†P.sup.†, which is a product of two n-qubit operators, .sup.† and P.sup.†; wherein the public key of encryption, Key.sub.pub, is published in public space to transform 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 k-qubit plaintext, |x, preparing a blank state |0 and |x to cast into a product state |0.Math.|x of n qubits; an error generator Gen.sub.ε of Key.sub.pub randomly generates an error Ē from ε; the data provider encodes the product state |0.Math.|x into the n-qubit encoded state |ψ.sub.en=ĒVQ.sub.en|0.Math.|x, which means when the data provider encrypts a k-qubit basis state sensitive data (which is plaintext), |x, by writing the product state |0.Math.|x of n qubits (which is plaintext) from the plaintext |x for the basis state |0 of n−k qubits; by a modified encoding VQ.sub.en provided by the public key Key.sub.pub and a modified error Ē generated randomly from Gen.sub.ε of Key.sub.pub, acquiring a encoded state ciphertext |ψ.sub.en by |ψ.sub.en=ĒVQ.sub.en|0.Math.|x; and the data provider sends |ψ.sub.en to a computation provider; S2: Computation: S21: a k-qubit arithmetic operation M is given to be operated on the encrypted state |.sub.en; the k-qubit arithmetic operation M is written as n-qubit operation =I.sub.2.sub.n−k.Math.M, which is a tensor product of an (n−k)-qubit operation of identity operator I.sub.2.sub.n−k and a k-qubit operation M; the data receiver produces a computational instructions of a homomorphic encryption (HE) operation U.sub.en with a form:
U.sub.en PQ.sup.†.sub.enV.sup.†=(PW.sub.1P.sub.1)(P.sup.†.sub.1W.sup.†.sub.1.sub.1W.sub.1P.sub.1)(P.sup.†.sub.1P.sub.0)(P.sup.†.sub.0W.sup.†.sub.1.sub.2W.sub.1P.sub.0)(P.sup.†.sub.0W.sub.2), where Q.sup.†.sub.enV.sup.†=W.sub.1W.sub.2 with a qubit permutation W.sub.1 and an operator W.sub.2 comprising Spinor, CNOTs, Toffolis, SWAPs, Controlled SWAPs, Multi-Control Gate, 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 the correction operation =.sub.1.sub.2 is written as a product of two operators .sub.1 and .sub.2, which are consisting of Spinor, CNOTs, Toffolis, SWAPs, Controlled SWAPs, Multi-Controlled Gate; the data provider sends the encoded computational instructions U.sub.en to the computation provider and the computation provider receives the computational instructions to computes U.sub.en|ψ.sub.en; S3: Decryption: the computation provider conducts homomorphic encryption computation U.sub.en|ψ.sub.en and sends the encrypted results to the data receiver; the data receiver 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=|λ.Math.M|x; with an (n−k)-qubit syndrome state |λ, and then obtains the result M|x.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a schematic flow diagrams according to the present inventive concept;

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

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

DETAILED DESCRIPTION

(4) 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.

(5) 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.

(6) 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.

(7) Please refer to FIG. 1 first. The present inventive concept provides a method of constructing a public key system in QAP-based homomorphic encryption. by an algebraic structure, QAP, and an arithmetic operation of homomorphic encryption. The Encryption, computation and decryption are computed after the schemes of homomorphic encryption are constructed and computed in the framework of QAP by QAP-based fault tolerance quantum computation in an algebraic structure of QAP. In the computation, a k-qubit state, i.e. |x (1), in a quantum computation could be provided, which is represented as a k-qubit binary string in this code system and as a plaintext. This plaintext is represent as an element in an additive group Z.sup.k.sub.2, and considered as a vector having 2.sup.k dimensions. For example, k=3 qubit , the plaintext |x=|100 is an element in the additive group Z.sup.3.sub.2={000, 001, 010, 011, 100, 101, 110, 111}, which is considered to be a vector having 2.sup.3 dimensions.

(8) According to the present inventive concept, the encryption in the method to obtain a ciphertext, i.e. |ψ.sub.en, with longer codes comprises the steps of key generation and encoding. In the step of key generation, a public key, Key.sub.pub, to encrypt data and a private key, Key.sub.priv, to decrypt data would be generated. In this code system, the public key may be represented by Key.sub.pub=(VQ.sub.en, Gen.sub.ε), which is k-qubit state. Wherein |x (1), which is a plaintext may be transform into a ciphertext, |ψ.sub.en), by the public key for encryption, where Q.sub.en is an n-qubit encoding in [n, k, C], V is an n-qubit permutation, each of which may be represented as a 2.sup.n×2.sup.n matrix or composed by elementary gates (please further refer to FIG. 3). Gen.sub.ε is an error generator allowing to randomly provide an error from a modified error set Ē composed of a gigantic number of dressed operators Ē=VEV.sup.† of errors E in [n, k, C]; the error is a spinor, which may be represented as a 2.sup.n×2.sup.n matrix or composed by elementary gates.

(9) When the encoded state |ψ.sub.en=|0.Math.|x (3) may be obtained in the encryption, the vector |ψ.sub.en means a encoded state, namely a ciphertext, and ĒVQ.sub.en is a product by three operations. An n-qubit string |0.Math.|x is a tensor product of an (n−k)-qubit basic state and a k-qubit basic state |x. For example, n=5, k=3, |x=|111, |0.Math.|x=|00.Math.|111=|00111.

(10) In the step of computation, a k-qubit computation M |x is realized by an equivalent homomorphic encryption computation, that is, an encoded operation U.sub.en on the encrypted state of |ψ.sub.en. Because U.sub.en is an operation of homomorphic encryption, which is an encoding of the k-qubit operation M (represented as a 2.sup.k×2.sup.k matrix or composed of elementary gates), which may be represented as a 2.sup.n×2.sup.n matrix or composed of elementary gates; U.sub.en|ψ.sub.en means the operation U.sub.en is conducted on the ciphertext |ψ.sub.en, which results an n-qubit state and achieves U.sub.en|ψ.sub.en (4).

(11) Finally, in the step of decryption, U.sub.en|ψ.sub.en (4) is decrypted. The decryption is conducted by the Key.sub.priv=.sup.†P.sup.† which is generated by the step of the key generation at the beginning, which is written as .sup.†P.sup.†U.sub.en|ψ.sub.en=|λ.Math.M|x (5), with an (n−k)-qubit syndrome state |λ, and then obtains the result M|x. Wherein .sup.†P.sup.† represents the private key of the code system, which is a product of the operations alt and Pt (each of the two operations may be represented as a 2.sup.n×2.sup.n matrix or composed of elementary gates, respectively), |λ is an (n−k)-qubit string and M|x is a k-qubit string (which is an original computation without encryption).

(12) Please refer to FIG. 2 which is a flow chart of actual operation for encryption, computation and decryption according to the present inventive concept. According to an embodiment of the present inventive concept, the steps of the method may be as follows. Step S1. Encryption. a quantum code [n, k, C], which is structurally a QAP and wherein n>k, is chosen by a data receiver (Alice) (6) at first. The step of encryption may include key generation and encoding. Step S11. key generation. Alice generates a public key, Key.sub.pub, to encrypt data (8) (please refer to {circle around (1)} in FIG. 2) and a private key, Key.sub.priv, to decrypt data (9). wherein the public key (8) provides a modified encoding VQ.sub.en and a modified error Ē randomly generated, which may be represent by Key.sub.pub=(VQ.sub.en,Gen.sub.ε) and sent to a data provider (Bob) (7) (please refer to {circle around (2)} in FIG. 2), where Q.sub.en is an n-qubit encoding in [n, k, C], V is an n-qubit permutation, Gen.sub.ε is an error generator allowing the public key to randomly provide an error from a modified error set E composed of a gigantic number of dressed operators Ē=VEV.sup.† of errors E in [n, k, C]. The private key Key.sub.priv (9) used 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.†; wherein the public key of encryption, Key.sub.pub (8), may be published in public space to transform a plaintext to a ciphertext by anyone; and the private key, Key.sub.priv (9), is retained by Alice to decrypt the encrypted ciphertext. In the step S12 encoding: Bob provides k-qubit plaintext, |x, to conduct a computation of homomorphic encryption. A blank state |0 and |x are prepared to cast into a product state |0.Math.|x of n qubits; an error generator Gen.sub.ε of Key.sub.pub randomly generates an error Ē from ε; Bob (7) encodes the product state |0.Math.|x into the n-qubit encoded state |ψ.sub.en=ĒVQ.sub.en|0.Math.|x, which means when Bob encrypts a k-qubit basis state sensitive data (which is plaintext), |x, by writing the product state |0 .Math.|x of n qubits (which is plaintext) from the plaintext |x for the basis state |0 of n−k qubits; by a modified encoding VQ.sub.en provided by the public key Key.sub.pub and a modified error Ē generated randomly from Gen.sub.ε of Key.sub.pub, acquiring a encoded state ciphertext |ψ.sub.en by |ψ.sub.en=ĒVQ.sub.en|0; and Bob (7) sends the ciphertext |ψ.sub.en to a computation provider (cloud) (please refer to {circle around (3)} in FIG. 2).

(13) 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 on the encrypted state |ψ.sub.en; the k-qubit arithmetic operation M is written as n-qubit operation =I.sub.2.sub.n−k.Math.M, which is a tensor product of an (n−k)-qubit operation of identity I.sub.2.sub.n−k and a k-qubit operation M; Alice (6) may produce a computational instructions of a homomorphic encryption (HE) operation U.sub.en with a form:
U.sub.en=PQ.sup.†.sub.enV.sup.†=(PW.sub.1P.sub.1)(P.sup.†.sub.1W.sup.†.sub.1.sub.1W.sub.1P.sub.1)(P.sup.†.sub.1P.sub.0)(P.sup.†.sub.0W.sup.†.sub.1.sub.2W.sub.1P.sub.0)(P.sup.†.sub.0W.sub.2),

(14) where Q.sup.†.sub.enV.sup.†=W.sub.1W.sub.2 with a qubit permutation W.sub.1 and an operator W.sub.2 comprising elementary gates, such as Spinor, CNOTs, Toffolis, SWAPs, Controlled SWAPs, Multi-Control Gate. P.sub.J=0,1 and P are qubit permutations following PW.sub.1P.sub.1=I.sub.2.sub.n, and the correction operation =.sub.1.sub.2 is written as a product of two operators, .sub.1 and .sub.2, each of which are consisting of elementary gates, such as Spinor, CNOTs, Toffolis, SWAPs, Controlled SWAPs, Multi-Control Gate.

(15) Then, Alice sends the encoded computational instructions U.sub.en to cloud (10) (please refer to {circle around (4)} in FIG. 2) and cloud (10) receives the computational instructions to computes U.sub.en|ψ.sub.en.

(16) According to an embodiment of the present inventive concept, the method may comprise Step S3. Decryption. Cloud conducts homomorphic encryption computation U.sub.en|ψ.sub.en and sends the encrypted results to Alice (6) (please refer to {circle around (5)} in FIG. 2); Alice (6) may decrypt the encrypted 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=|λ.Math.M|x;

(17) with an (n−k)-qubit syndrome state |λ, and then obtains the result M|x.

(18) Please refer to FIG. 3 which is a schematic diagram of the elementary gate used in the algorithm according to the present inventive concept. According to the present inventive concept, the spinor (11) is an n-qubit spinor .sup.ζ.sub.a=.sub.a.sub.1.sup.ε.sup.1.Math..sub.a.sub.2.sup.ε.sup.2.Math. . . . .Math..sup.ε.sup.n.sub.a.sub.n, composed of a tensor product of n spinors, with ζ, a∈Z.sup.n.sub.2 and ε.sub.j, a.sub.j∈Z.sub.2. Each of the spinors .sup.ε.sup.j.sub.a.sub.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.

(19) According to the present inventive concept, CNOT (12) 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.

(20) According to the present inventive concept, Toffoli gate (13) 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.

(21) According to the present inventive concept, SWAP (14) 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.

(22) According to the present inventive concept, CSWAP (Controlled SWAP) ((15) 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.

(23) According to the present inventive concept, Multi-Control gate (16) 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 ∧.sup.12 . . . p.sub.n−p(.sup.π.sub.107 ), 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 .sup.π.sub.ω,; otherwise the n-bit string remains the same.

(24) In summary, the method of constructing a public key system in QAP-based homomorphic encryption of the present inventive concept allows so-called Homomorphic Encryption to be conducted without communication between the data receiver and the data provider during encryption. The method of the present inventive concept may conduct blind evaluations without secret disclosures, and allow problem-dependent optimizations with modest overheads.

(25) 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.