METHOD OF DESIGNING ONE-WAY COMPUTATIONAL SYSTEM IN QAP-BASED HOMOMORPHIC ENCRYPTION

Abstract

The present inventive concept discloses a method of designing a one-way computational system in QAP-based homomorphic encryption applied to the n-qubit encode operations of a k-qubit action M for public-key and semi-public-key schemes respectively, n≥k, wherein the method comprises: preparing a tensor-product operator =I.sub.2.sub.n-k.Math.M=.sub.1.sub.2 and decomposing it into two parts, wherein is composed of elementary gates, and let =.sub.1.sup.† and .sub.2=; providing a correction operator, =.sub.1.sub.2 for public-key and =I.sub.2.sub.k for semi-public-key, and an encoding operator, Q.sub.en.sup.†V.sup.†=W.sub.1W.sub.2 for public-key and Q.sub.p.sup.†=W.sub.1W.sub.2 for semi-public-key, both composed of elementary gates; providing appropriate permutations P, P.sub.0 and P.sub.1, while P.sub.0=P.sub.1 for semi-public-key, to obey the nilpotent condition PW.sub.1P.sub.0=I for the identity operator; through process of merging operators according to sets of identities of gates, including Id-GateELIM, Id-GateEx and Id-GateREP, there obtain the mixed encode for public-key scheme, U.sub.en=PQ.sub.en.sup.†V.sup.†=(P.sub.1.sup.†W.sub.1.sup.†.sub.2.sub.1W.sub.1P.sub.1)(P.sub.1.sup.†P.sub.0)(P.sub.0.sup.†.sub.2W.sub.1P.sub.0) (P.sub.0.sup.†W.sub.2), and that for semi-public key, U.sub.en=PMQ.sub.p.sup.†=(P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0)(P.sub.0.sup.†W.sub.2) with n=k, .sub.1=.sub.2=I.sub.2.sub.n and P.sub.0=P.sub.1.

Claims

1. A method of designing a one-way computational system in quotient algebra partition-based homomorphic encryption (QAPHE), which is based on the framework of quotient algebra partition (QAP) and the computation of homomorphic encryption (HE), wherein a fault tolerant encode of a k-qubit arithmetic operation, M, is constructed in a quantum code [n, k, C], wherein the method comprises: S1. decomposing a tensor-product operator, =I.sub.2.sub.n-k.Math.M=.sub.1.sub.2, into two parts, wherein the tensor-product operator is composed of elementary gates, and let =.sub.1.sup.† and .sub.2=; S2. providing a correction operator , wherein the correction operator is composed of elementary gates, wherein the elementary gates comprise a set of identities, and the set of identities includes Id-GateELIM, Id-GateEx and Id-GateREP; S3. decomposing a modified encoding into two operators, W.sub.1 and W.sub.2; S4. obtaining a modified operator by applying the operator W.sub.1 via the set of identities; S5. deriving a merging operator via the set of identities by choosing corresponding permutations, P, P.sub.0 and P.sub.1, wherein the merging operator satisfies the nilpotent condition; and a mixed modified operator is derived from the modified operator by the set of identities and the permutation; and S6. obtaining a one-way mixing encode by multiplying the merging operator and the mixed modified operator in the step of S5.

2. The method of claim 1, wherein the elementary gate comprises a spinor, a CNOT, a Toffoli Gate, a SWAP, a Controlled SWAP or a Multi-Controlled Gate.

3. The method of claim 2, wherein the correction operator according to the step of S2 is composed of the CNOT.

4. The method of claim 2, wherein the operator W.sub.1 in the step of S3 comprises the SWAP and the operator W.sub.2 is composed of the CNOT and the SWAP.

5. The method of claim 1, wherein the set of identities in the step of S4 is Id-GateREP.

6. The method of claim 1, wherein the one-way computational system designed by the method is applied to construct a public-key system in QAPHE.

7. The method of claim 6, wherein the step of S2 further comprises decomposing the correction operator into two components, which defines the correction operator =.sub.1.sub.2, wherein any component of the correction operator is composed of the CNOT.

8. The method of claim 7, wherein the merging operator .sub.2.sub.1 is obtained by the set of identities of elementary gates, and the set of identities includes Id-GateELIM and Id-GateEx.

9. The method of claim 6, according to the step of S3, wherein the modified encoding is defined as Q.sub.en.sup.†V.sup.†=W.sub.1W.sub.2.

10. The method of claim 6, according to the step of S4, wherein two modified operators are obtained by applying the operator W.sub.1 via the set of identities, wherein the two modified operators are W.sub.1.sup.†.sub.2.sub.1W.sub.1 and W.sub.1.sup.†.sub.2W.sub.1.

11. The method of claim 6, according to the step of S5, wherein the mixed modified operators are P.sub.1.sup.†W.sub.1.sup.†.sub.2.sub.1W.sub.1P.sub.1 and P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0, and the mixed modified operators are derived via the set of identities of elementary gate which is Id-GateREP.

12. The method of claim 6, according to the step of S5, wherein the merging operator is derived as PW.sub.1P.sub.1=I.sub.2.sub.n, P.sub.1.sup.†P.sub.0 or P.sub.0.sup.†W.sub.2 via Id-GateELIM, Id-GateEx and Id-GateREP.

13. The method of claim 6, according to the step of S6, wherein the one-way mixing encode is U.sub.en=(P.sub.1.sup.†W.sub.1.sup.†.sub.2.sub.1W.sub.1P.sub.1) (P.sub.1.sup.†P.sub.0)(P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0)(P.sub.0.sup.†W.sub.2)=PQ.sub.en.sup.†V.sup.†.

14. The method of claim 1, wherein the one-way computational system designed by the method is applied to construct a semi-public-key system in QAPHE.

15. The method of claim 14, wherein the correction operator is defined as =I.sub.2.sub.n.

16. The method of claim 14, according to the step of S3, wherein the encoding is defined as Q.sub.P=W.sub.1W.sub.2.

17. The method of claim 14, according to the step of S4, wherein a modified operator W.sub.1.sup.†.sub.2W.sub.1 is obtained by applying the operator W.sub.1 via the set of identities.

18. The method of claim 14, according to the step of S5, the mixed modified operator is P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0, and the mixed modified operator is derived via the set of identities of elementary gate which is Id-GateREP.

19. The method of claim 14, according to the step of S5, wherein the merging operator is derived as PW.sub.1P.sub.0=I.sub.2.sub.k or P.sub.0.sup.†W.sub.2 via Id-GateELIM, Id-GateEx and Id-GateREP.

20. The method of claim 14, according to the step of S6, wherein the one-way mixing encode is U.sub.en=(P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0) (P.sub.0.sup.†W.sub.2)=PQ.sub.p.sup.†.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

[0035] FIG. 1 is a flowchart of an embodiment of the method provided by the present inventive concept;

[0036] FIG. 2 is a library of elementary gates in QAPHE applied in the embodiment of the present inventive concept;

[0037] FIG. 3 is diagrammatic illustrations of different sets of identities among elementary gates of the present inventive concept;

[0038] FIG. 4A is an illustration of a QAPHE circuit without the one-way algorithm of the method provided by the present inventive concept; and

[0039] FIG. 4B is an illustration of a QAPHE circuit with the one-way algorithm of the method provided by the present inventive concept.

DETAILED DESCRIPTION

[0040] 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.

[0041] 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.

[0042] 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.

[0043] Another holy grail in the field of quantum information science is the realization of scalable fault tolerance quantum computation, which permits to protect quantum states from corruptions of errors due to computations or environments. The method of the present inventive concept is to construct fault tolerant encodes of every action in every error-correcting code. The success of this methodology is based on the framework Quotient Algebra Partition, QAP, whose partition structure is inherited by every stabilizer code. In the procedure of QAP-based Fault Tolerance Quantum Computation, QAPFTQC, a k-qubit state is encoded into an n-qubit codeword by an encoding in a QAP [n, k, C]. With an error appearing in the computation being represented by a spinor of a coset in [n, k, C], each corrupted state applied by a fault encode of this partition can be corrected by every member of the same coset. Meanwhile, it allows to design the dual process of QAPFTQC. That is, given a message state of k qubits, a k-qubit action M and a QAP [n, k, C], the encryption of message is conducted by an encoding and a random error, and the fault tolerant of M serves as the role of HE evaluation. Furthermore, the security is guaranteed by an exponential choices of errors in [n, k, C], which is post-quantum. The QAPHE is superior to current schemes of HE. In particular, since a computation is realized by rotations acting on the Hilbert space, each solution after an encoded computation is exact and requires small resources, achieving fully HE. In addition, the computation of QAPHE is blind and problem-dependently optimized because the rotations composing computation are all reversible and are admitted to mix up. Moreover, the quantum gates with one-way algorithm in the method of the present inventive concept make the scheme of QAPHE not only conductible on a quantum computer, but also achievable on a classical computer.

[0044] Please refer to FIG. 1 which is a library of elementary gates in QAPHE applied in the present inventive concept and FIG. 2 showing the diagrammatic illustrations of different sets of identities among elementary gates of the present inventive concept. The present inventive concept provides a method of designing a one-way computational system in quotient algebra partition-based homomorphic encryption (QAPHE), which is based on the framework of quotient algebra partition (QAP) and the computation of homomorphic encryption (HE), wherein a fault tolerant encode of a k-qubit arithmetic operation, M, is constructed in a quantum code [n, k, C]. The method comprises:

[0045] S1. decomposing a tensor-product operator, =I.sub.2.sub.n-k.Math.M=.sub.1.sub.2, into two parts, wherein the tensor-product operator is composed of elementary gates, and let =.sub.1.sup.† and .sub.2=;

[0046] S2. providing a correction operator , wherein the correction operator is composed of elementary gates, wherein the elementary gates comprise a set of identities, and the set of identities includes Id-GateELIM, Id-GateEx and Id-GateREP;

[0047] S3. decomposing a modified encoding into two operators, W.sub.1 and W.sub.2;

[0048] S4. obtaining a modified operator by applying the operator W.sub.1 via the set of identities;

[0049] S5. deriving a merging operator via the set of identities by choosing corresponding permutations, P, P.sub.0 and P.sub.1, wherein the merging operator satisfies the nilpotent condition; and a mixed modified operator is derived from the modified operator by the set of identities and the permutation; and

[0050] S6. obtaining a one-way mixing encode by multiplying the merging operator and the mixed modified operator in the step of S5.

[0051] Please refer to FIGS. 1 and 2. In an embodiment of the present inventive concept, the elementary gate may comprise a spinor, a CNOT, a Toffoli Gate, a SWAP, a Controlled SWAP or a Multi-Controlled Gate, but not limited to. In this embodiment, i, j, l in FIG. 2 may fulfill 1≤i,j,l≤n.

[0052] Please refer to FIGS. 1 and 3. According to an embodiment of the present inventive concept, the elementary gates may comprise a set of identities, and the set of identities may include Id-GateELIM, Id-GateEx and Id-GateREP, but not limited to. In this embodiment, i, j, l in FIG. 3 may fulfill 1≤i,j,l≤n.

[0053] In an embodiment of the present inventive concept, the correction operator according to the step of S2 may be composed of the CNOT.

[0054] In an embodiment of the present inventive concept, the operator W.sub.1 in the step of S3 may comprise the SWAP and the operator W.sub.2 may be composed of the CNOT and the SWAP.

[0055] In an embodiment of the present inventive concept, the set of identities in the step of S4 may be Id-GateREP.

[0056] In an embodiment of the present inventive concept, the one-way computational system designed by the method may be applied to construct a public-key system in QAPHE.

[0057] In an embodiment of the present inventive concept applied to construct a public-key system, the step of S2 may further comprise decomposing the correction operator into two components, which defines the correction operator =.sub.1.sub.2, wherein any component of the correction operator may be composed of the CNOT.

[0058] In a preferred embodiment of the present inventive concept, the merging operator .sub.2 .sub.1 may be obtained by the set of identities of elementary gates, and the set of identities may include Id-GateELIM and Id-GateEx.

[0059] In an embodiment of the present inventive concept applied to construct a public-key system, according to the step of S3, the modified encoding may be defined as Q.sub.en.sup.†V.sup.†=W.sub.1W.sub.2.

[0060] In an embodiment of the present inventive concept applied to construct a public-key system, according to the step of S4, wherein two modified operators may be obtained by applying the operator W.sub.1 via the set of identities, wherein the two modified operators may be W.sub.1.sup.†.sub.2 .sub.1W.sub.1 and W.sub.1.sup.†.sub.2 W.sub.1.

[0061] In an embodiment of the present inventive concept applied to construct a public-key system, according to the step of S5, the mixed modified operator may be P.sub.1.sup.†W.sub.1.sup.†.sub.2.sub.1W.sub.1P.sub.1 and P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0 via the set of identities of elementary gates, wherein the set of identities of elementary gates may be Id-GateREP.

[0062] In an embodiment of the present inventive concept applied to construct a public-key system, according to the step of S5, wherein the merging operator may be derived as PW.sub.1P.sub.1=I.sub.2.sub.n, P.sub.1.sup.†P.sub.0 or P.sub.0.sup.†W.sub.2 via Id-GateELIM, Id-GateEx and Id-GateREP.

[0063] In an embodiment of the present inventive concept applied to construct a public-key system, according to the step of S6, wherein the one-way mixing encode may be U.sub.en=(P.sub.1.sup.†W.sub.1.sup.†.sub.2.sub.1W.sub.1P.sub.1)(P.sub.1.sup.†P.sub.0)(P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0)(P.sub.0.sup.†W.sub.2)=PQ.sub.en.sup.†V.sup.†.

[0064] In an embodiment of the present inventive concept, the one-way computational system designed by the method may be applied to construct a semi-public-key system in QAPHE.

[0065] In an embodiment of the present inventive concept applied to construct a semi-public-key system, the correction operator may be defined as =I.sub.2.sub.n. In an embodiment of the present inventive concept applied to construct a semi-public-key system, according to the step of S3, wherein the modified encoding may be defined as Q.sub.p=W.sub.1W.sub.2.

[0066] In an embodiment of the present inventive concept applied to construct a semi-public-key system, according to the step of S4, wherein a modified operator W.sub.1.sup.†.sub.2W.sub.1 may be obtained by applying the operator W.sub.1 via the set of identities.

[0067] In an embodiment of the present inventive concept applied to construct a semi-public-key system, according to the step of S5, the mixed modified operator may be P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0 via the set of identities of elementary gates, wherein the set of identities of elementary gate may be Id-GateREP.

[0068] In an embodiment of the present inventive concept applied to construct a semi-public-key system, according to the step of S5, wherein the merging operator may be derived as PW.sub.1P.sub.0=I.sub.2.sub.k or P.sub.0.sup.†W.sub.2 via Id-GateELIM, Id-GateEx and Id-GateREP.

[0069] In an embodiment of the present inventive concept applied to construct a semi-public-key system, according to the step of S6, wherein the one-way mixing encode may be U.sub.en=(P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0) (P.sub.0.sup.†W.sub.2)=PMQ.sub.p.sup.†.

[0070] Please refer to FIGS. 4A and 4B. FIG. 4A is an illustration of a QAPHE circuit without the one-way algorithm of the method provided by the present inventive concept; and IG. 4B is an illustration of a QAPHE circuit with the one-way algorithm of the method provided by the present inventive concept. Compared to the circuit in FIG. 4A, the one in FIG. 4B reduces the computational depth and lowers the cost for fault tolerant computation as well. Specifically, by testing different computations, such as, but not limited to addition, subtraction, multiplication and division or comparison, the computational speed of the method with one-way algorithm provided by the present inventive concept are about 20% to 50% faster than that of the method of the prior art, which improves the HE computation performance.

[0071] According to the present inventive concept, a stabilizer code [n, k, C] with a stabilizer C⊂su(2.sup.n) is a quotient algebra partition {.sub.Q(C)}. The quotient algebra partition is generated by the k-th maximal bi-subalgebra C=.sup.[k] of a Cartan subalgebra in su(2.sup.n). Specifically, there exists an isomorphism between the stabilizer C of [n, k, C] under the multiplication and the k-th maximal bi-subalgebra .sup.[k], i.e. C=.sup.[k]. Therefore, the stabilizer code [n, k, C] inherits the partition structure from the QAP {.sub.Q(C)}. There is a duality between the n-qubit encrypted state in the Hilbert space and the partition structure [n, k, C] have duality, which verifies the orthogonality connecting spinors and the codewords. A significant concept of the coset spinor is illustrated in the QAP structure, which implies the n-s condition for the error-correctability in a QAP.

[0072] In the partition structure [n, k, C], an error set ε is correctable iff two arbitrary spinors of ε are either in different blocks or in a same coset of a block within this partition structure. Besides, there are two implications of the concept of the coset spinor, the correction equivalence and the code degeneracy. The former one indicates that an error may be corrected by any operator in the same coset and the latter one expresses that a correctable error set allows spinors in a same coset, thereby obtaining two immediate results. One is that if there is no spinor of the error set, ε, in the subspace, Γ.sub.0−C, [n, k, C] may detect the error set ε; and the other one is that if two errors exist in different cosets of the same block, then the two errors in [n, k, C] are not correctable. Consequently, the n−s condition for the error-correctability is affirmed.

[0073] The partition structure [n, k, C] is regarded as a quantum version of the classical Hamming code [n, k]. For every classical linear code, [n, k], there exists an only partition structure [n, k, C] determined by the code. For every partition structure [n, k, C], there exists an only symplectic linear code [2n, n+k] determined by the partition structure. In the partition structure [n, k, C], it requires an encoding built by the partition structure in the intrinsic coordinate to encode a k-qubit state into an n-qubit codeword.

[0074] In the partition structure [n, k, C], an encoding Q.sub.en∈SU(2.sup.n) is an n-qubit spinor-to-spinor mapping transforming [n, k, C] into an intrinsic coordinate [n, k, Ĉ] generated by the intrinsic bi-subalgebra Ĉ={S.sub.0.sup.ζ.Math.S.sub.0.sup.0: ζ∈Z.sub.2.sup.n-k}=Q.sub.en.sup.\CQ.sub.en. In the intrinsic coordinate, the partition structure [n, k, Ĉ] is generated by the intrinsic bi-subalgebra Ĉ={S.sub.0.sup.ζ.Math.s.sub.0.sup.0: ζ∈Z.sub.2.sup.n-k} that is the k-th maximal bi-subalgebra of the intrinsic Cartan subalgebra, .sub.[0]. In this partition structure, cosets of a block, =∪.sub.μ∈Z.sub.2.sub.2k, may be in the form of ={.Math.: ζ∈Z.sub.2.sup.n-k}. In fact, an encoding Q.sub.en is a QAP-preserving spinor-to-spinor transformation mapping the partition structure [n, k, C] into the intrinsic [n, k, Ĉ]. In the partition structure [n, k, C], each fault tolerant encode, U∈SU(2.sup.n), requires meeting two standards, the eigen-invariance of SU|ψ=U|ψ for each spinor S∈C and each codeword, |ψ and the error-correction against an error set ε wherein US.sub.β|ψ=Σ.sub.α∈Z.sub.2.sub.n-k.sub.−{0}S.sub.α,vU|ψ in each coset W.sub.α,v from each block, Γ.sub.α, v∈Z.sub.2.sup.2k and S.sub.β∈ε.

[0075] To correct an error set ε⊂su(2.sup.n) with an encoding Q.sub.en∈SU(2.sup.n) in the partition structure [n, k, C], a fault tolerant encode of the k-qubit operator M∈SU(2.sup.k) may be denoted as the form, U.sub.en=Q.sub.enQ.sub.en.sup.†, where is a tensor product of M and the (n−k)-qubit identity I.sub.2.sub.n-k, which may be expressed as =I.sub.2.sub.n-k.Math.M, where ∈SU(2.sup.n) is an operator of input coset associated with ε, ∈SU(2.sup.n) is an operation of an output coset and ∈SU(2.sup.n) is a transfer amplitude.

[0076] Quantum Circuit

[0077] Basic arithmetic, such as addition and multiplication, are illustrated in the following details of quantum circuit.

[0078] Every finite field F.sub.q=F.sub.p.sup.m is composed of elements q=p.sup.m for a prime number p and a positive integer m. The finite field is isomorphic to the quotient ring Z.sub.p[x]/ƒ(x) of a polynomial ring Z.sub.p [x] and an irreducible polynomial function ƒ(x) of degree m.

[0079] Currently, major post-quantum cryptosystems, such as lattice-based code system, code-based system and multivariate-based system, are described by polynomial rings, rather than linear operations. The QAP structure may be composed of operatees dual to states of a Hilbert space and allows applications of invertible linear transformations to these states inherently. This reveals essential differences between the solution of QAP-based HE and that based on a polynomial ring.

[0080] A quantum circuit exists to perform an addition Σ.sub.i=1.sup.Nm.sub.i of a number N of 1-bit message m.sub.i∈Z.sub.2.sup.l. For the addition of two 1-bit numbers, there is a more effective space-time implementation. For example, build a circuit with its linear size of O(l) in depth O(l) with O(l) ancilla qubit. Then, provide a circuit with its size of O(l) in logarithmic depth O(log l) with O(l/log l) ancilla qubit.

[0081] A quantum circuit exists to conduct a multiplication of two 1-bit numbers, which permits the circuit design of multiplying two numbers with lower cost. For example, the Karatsuba-based multiplication requires a circuit size O(l.sup.log.sup.2.sup.3) with its depth of O(l) without ancilla qubit. It is worth noting that every quantum gate applied to the addition or multiplication may be factorized into a composition of s-rotations.

[0082] Construction of Public-Key Scheme

[0083] The solution based on the QAPHE in a public key system is illustrated as follows.

[0084] The scheme of QAPHE is a dual process of QAP-based Fault Tolerance Quantum Computation, QAPFTQC. Assuming that a number of N of plaintexts, {x.sub.i∈Z.sub.2.sup.k.sup.i: 1≤i≤N}, are protected and proceeded in a cloud server, first, choose a partition structure [n, k, C] generated by the k-th maximal bi-subalgebra C of a Cartan subalgebra in su(2.sup.n) for the above purpose. Then, construct a fault tolerant encode in [n, k, C] according to the methodology of QAPFTQC to attain full homomorphism.

[0085] Three stages of a QAPHE over [n, k, C] are illustrated as follows, i.e., the encryption, the computation, and the decryption. In the stage of encryption, a message is going to be encoded by the public key. Every partition structure [n, k, C] makes the encrypted public key, Key.sub.pub, transform a k-qubit plaintext into n-qubit ciphertext. In the partition structure [n, k, C]. The cost of encryption via a public key Key.sub.pub has an upper bound O(n.sup.2). The complexity of breaking the encryption via the public key Key.sub.pub has a lower bound O(2.sup.L) and an upper bound O(2.sup.2n), where δ<L≤n−k, and δ is a postquantum security level.

[0086] A k-qubit encoded state |x is transformed to an n-qubit codeword |ψ.sub.en by a given public key Key.sub.pub in a partition structure, where |ψ.sub.en=ĒVQ.sub.en|0.Math.|x, x∈Z.sub.2.sup.k. The homomorphic computation of a k-qubit computation M|x with an action M is realized by the fault tolerant encode U.sub.en, where M∈SU(2.sup.k).

U.sub.en=PQ.sub.en.sup.†V.sup.†

=(PW.sub.1P.sub.1)(P.sub.1.sup.†W.sub.1.sup.†.sub.1W.sub.1P.sub.1)(P.sub.1.sup.†P.sub.0)(P.sub.0.sup.†W.sub.1.sup.†.sub.2W.sub.1P.sub.0)(P.sub.0.sup.†W.sub.2)  Eq. 1

[0087] In the above Eq. 1, =I.sub.2.sub.n-k.Math.M and I.sub.2.sub.n-k is an (n−k)-qubit identity. The correction operation =.sub.1.sub.2 is factorized into two operators .sub.1 and .sub.2∈SU(2.sup.n). Q.sub.en.sup.†V.sup.†, a product of two operators, W.sub.1 and W.sub.2∈SU(2.sup.n), may be written as Q.sub.en.sup.†V.sup.†=W.sub.1W.sub.2. The four operators , P, P.sub.1 and P.sub.0∈SU(2.sup.n) are chosen to mix up the encoded and PW.sub.1P.sub.1=I.sub.2.sup.n.

[0088] The practical application of U.sub.en is performed by the mixed composition of 2.sup.nd line of Eq. 1. Specifically, each of , P, P.sub.1 and P.sub.0 is a composition of spinor-to-spinor s-rotations. Initially, the correction operator =.sub.1.sub.2 is written as a product of two unitary actions, .sub.1 and .sub.2. The operator is chosen to mix up the composition .sub.1. By factorizing Q.sub.en.sup.†V.sup.† into two actions, W.sub.1 and W.sub.2, let the operator W.sub.1 be conducted as in the 2.sup.nd line of Eq. 1 and W.sub.2 stays. The two unitary actions P.sub.1 and P.sub.0 are inserted into the components of Eq. 1 to further mingle quantum gates. P.sub.0.sup.†W.sub.1.sup.†.sub.2 W.sub.1P.sub.0 is a modified action of .sub.2 by absorbing the spinor-to-spinor operation W.sub.1P.sub.0. Similarly, P.sub.1.sup.†W.sub.1.sup.†.sub.1W.sub.1P.sub.1 is a modified action of .sub.1 by absorbing the spinor-to-spinor operation W.sub.1P.sub.1.

[0089] It is worthy to note that the computation of U.sub.en admits optimized design according to the problem-dependent operation M.

[0090] The cost of encoding and the security of encryption will be shown as follows. In a partition structure [n, k, C], the cost of a homomorphic computation given by a public key has the upper bound O(n.sup.p) for an integer p∈N and the complexity of breaking the encryption via the public key Key.sub.pub has a lower bound O(2.sup.L).

[0091] The decryption of an encoded computation U.sub.en|ψ is accomplished by the operation of a private key. In the present inventive concept, a fault tolerant encode U.sub.en=PQ.sub.en.sup.†V.sup.†∈SU(2.sup.n) of a k-qubit arithmetic operation, M∈SU(2.sup.k), and an n-qubit state |ψ.sub.en=ĒVQ.sub.en|0.Math.|x encoded by the public key Key.sub.pub are given. =I.sub.2.sub.n-k.Math.M, the homomorphic computation U.sub.en|ψ.sub.ed is decrypted to M|x via the private key Key.sub.priv=.sup.\P.sup.\.

[0092] Notice that the scheme of public-key can be extended to the model of multi-party homomorphic encryption by appropriately increasing the numbers of data receivers, date providers, public keys, and computation providers.

[0093] Construction of Semi-Public-Key Scheme

[0094] The semi-public key scheme based on a QAPHE is illustrated in detail, which is almost the same as the public-key scheme except that a small resource of communication are allowed in the semi-public key scheme between the data receiver and data owner.

[0095] A k-qubit plaintext is encoded into a k-qubit cyphertext via the semi-public key Key.sub.s-pub. The cost of encoding a k-qubit state via the semi-public key Key.sub.s-pub is O(k). The encryption of a k-qubit plaintext through a semi-public key is more efficient than that of the same plaintext via a public key because it is not necessary to add a random error in the semi-public key scheme. The complexity of breaking the encryption by a semi-public key Key.sub.s-pub is identical to that of finding the encoding operation from the encrypted message of this operation. It allows a very high level of post-quantum security with the cryptosystem chosen for Q.sub.p, the semi-public-key scheme is more secure than the public-key scheme.

[0096] An encoding operator Q.sub.p∈SU(2.sup.k) generated by a k-qubit semi-public key Key.sub.s-pub. The homomorphic computation of a k-qubit evaluation conducted by an arithmetic operation M∈SU(2.sup.k) is realized by a fault tolerant encode U.sub.en.

U.sub.en=PMQ.sub.p.sup.\

=(P.sub.0.sup.\W.sub.1.sup.\MW.sub.1P.sub.0)(P.sub.0.sup.†W.sub.2)  Eq. 2

[0097] where Q.sub.p.sup.† is a product of two operators W.sub.1 and W.sub.2∈SU(2.sup.k) and can be written as Q.sub.p.sup.†=W.sub.1W.sub.2. The three operators , P and P.sub.0∈SU(2.sup.n) are used to mix up the encode and PW.sub.1P.sub.0=I.sub.2.sub.k. In the design of one-way function, the blindness of computation as of Eq. 2 is achievable, which is realized by merging and exchanging the given elementary gates. with n=k, .sub.1=.sub.2=I.sub.2.sub.n and P.sub.0=P.sub.1.

[0098] The cost of a homomorphic computation by a semi-public key of k qubits has the upper bound O(k.sup.t) for an integer t∈N. An overhead of error-correction is no need in the semi-public-key scheme, which implies a computational cost lower than that in the public-key setting. The complexity of breaking a homomorphic computation by a semi-public key of k qubits is limited by v(k)=(k.sup.e/(r−d)).sup.r-d+k.sup.2d, d, e and r∈N.

[0099] An encoded operation U.sub.en=PMQ.sub.p.sup.†∈SU(2.sup.n) of a k-qubit arithmetic operation M∈SU(2.sup.k) and n k-qubit state |ψ.sub.en=Q.sub.p|x encoded by a semi-public key Key.sub.s-pub are given. The homomorphic computation U.sub.en|ψ.sub.ed is decrypted to M|x by the private key Key.sub.priv=.sup.\P.sup.\.

[0100] Similar to the public-key scheme, the concept of multi-party is applicable to the semi-public-key by increasing the numbers of data receivers, data providers, and computation providers, where a single semi-public key is adopted to produce multiple encoding operators for multiple users.

Example of the Public Key Encryption

[0101] The following illustrates that the feature “every partition structure [n, k, C] makes the encrypted public key, Key.sub.pub, transform a k-qubit plaintext into n-qubit ciphertext. In the partition structure [n, k, C]” of the present inventive concept is feasible. Various types of designs of public-key encryptions are permitted in the framework of QAP according to distinct difficult problems. In the following, two designs of encryptions are demonstrated.

[0102] In a partition structure [n, k, C] with an encoding Q.sub.en, it allows a public key of encryption consisting of an operation VQ.sub.en and an error generator Gen(ε; J) associated with a set ε={E.sub.r=VE.sub.rV.sup.†: r=1, 2, . . . J} of J<n−k errors, where VQ.sub.en∈SU(2.sup.n) is a spinor-to-spinor transformation, spinors, V is a qubit permutation. The spinors E.sub.r∈su(2.sup.n) are selected from independent blocks in the partition structure, respectively. Gen(ε; J) can generate an error Ē=(E.sub.1).sup.ϵ.sup.1(E.sub.2).sup.ϵ.sup.2 . . . (Ē.sub.J).sup.ϵ.sup.J randomly from ε with (E.sub.r).sup.0=I.sub.2.sub.n and (E.sub.r).sup.1=E.sub.r, ϵ.sub.r∈Z.sub.2. The error Ē=(E.sub.1).sup.ϵ.sup.1(E.sub.2).sup.ϵ.sup.2 . . . (Ē.sub.J).sup.ϵ.sup.J may be a product by a certain number of spinors randomly chosen from ε. The public key can be written as Eq. 3 below.

Key.sub.pub.sup.(1)=(VQ.sub.en,Gen(ε;J))  Eq. 3

[0103] Supposed that a number of 1-qubit message x.sub.i∈Z.sub.2.sup.l is N, an l.sub.0-qubit blank state |x.sub.0 is expressed into a k-qubit basis state by k=l.sub.0+lN, which is |x=|x.sub.1.Math.|x.sub.2 . . . |x.sub.N.Math.|x. The form of the encoded state is |ψ.sub.en=ĒVQ.sub.en|0.Math.|x by writing the tensor product state |0.Math.|x for the n−k qubit basic state |0.

[0104] The cost of encoding a plaintext x to the ciphertext |ψ.sub.en equals |V∥Q.sub.en|+1, where |V|˜O(nk) and |Q.sub.en|˜O(n(n−k)) are the numbers of 1- and 2-qubit s-rotations, respectively, in V and Q.sub.en, and the number 1 is counted with the application of Ē.

[0105] The complexity of breaking the encryption by the public key Key.sub.pub.sup.(1) is the number of the steps to find the error Ē=(E.sub.1).sup.ϵ.sup.1 (E.sub.2).sup.ϵ.sup.2 . . . (Ē.sub.J).sup.ϵ.sup.J in the codeword |ψ.sub.en=ĒVQ.sub.en|0.Math.|x, where ϵ.sub.r∈Z.sub.2 and 1≤r≤J. A brute force attack leads to the upper bound 2.sup.J, hich is the number of all possibilities of the J-bits ϵ.sub.r. On the other hand, the cost of finding Ē is equivalent to that of the problem of searching the representation of Ē in terms of spinors in a subset S.sub.G={E.sub.r: 1≤r≤J} of a finite abelian group G=spanS.sub.G with its size 2.sup.J. It takes a complexity is larger than or equals to 2.sup.J/2+1 and has a lower bound O(2.sup.J/2).

[0106] In the known cryptosystem in code-based cryptography, the Muceliece cryptosystem, adopts a Goppa code [n, k] to corrects errors of weight

[00001]$t=.Math.\frac{n}{\log n}.Math..$

In this system, given a public key Ĝ∈Z.sub.2.sup.k×n,t, a message x∈Z.sub.2.sup.k is encrypted to a cyphertext c=xĜ+e by multiplying Ĝ and adding a randomly chosen error e of weight t. Through a generic attack called information-set decoding, the complexity of restoring x from c is approximately y.sup.n/log n, y=(1−k/n).sup.1-k/n.

[0107] In a partition structure [n, k, C] with an encoding Q.sub.en, a public key of encryption is allowed to be composed of the operation VQ.sub.en and an error generator Gen(R.sub.1, R.sub.2; J), where V∈SU(2.sup.n) is s spinor-to-spinor transformation. Gen(R.sub.1,R.sub.2;J) can generate an error Ē=S.sub.γ.sup.ξ∈su(2.sup.n) randomly that is a solution of two sets of relations R.sub.q=1,2={ξ.Math.ζ.sub.q,u.sub.q+α.sub.q,u.sub.q.Math.γ=0: 1≤u.sub.q≤2n−J.sub.q}, j.sub.g<n−k. Each set of R.sub.q is associated with a bi-subalgebra .sub.q⊂su(2.sup.n) sizing 2.sup.J.sup.q and comprising spinors from different blocks in the partition structure, respectively. The intersection =.sub.1∩.sub.2 forms a bi-subalgebra of size 2.sup.J, J<J.sub.q. The public key is written as Eq. 4.

Key.sub.pub.sup.(2)=(VQ.sub.en,Gen(R.sub.1,R.sub.2;J))  Eq. 4

[0108] The cost of encoding a plaintext x to the ciphertext |ψ.sub.en equals |V∥Q.sub.en|+1, where |V|˜O(nk) and |Q.sub.en|˜O(n(n−k)) are the numbers of 1- and 2-qubit s-rotations, respectively, in V and Q.sub.en, and the number 1 is counted with the application of Ē. The complexity of the security of this encryption is the number of the steps to solve the group intersection problem, which has a lower bound O(2.sup.j)/2) and an upper bound O(2.sup.J).

[0109] The present inventive concept illustrates a one-way algorithm based on QAPHE, which may rewrite the original form of the fault tolerant operation U.sub.en=PQ.sub.en.sup.†V.sup.† into a one-way mix form and be applied to the algorithm with the public-key scheme and the semi-public key scheme based on QAPHE. Briefly, because the computation may be constructed by well-designed and invertible elementary gates on the Hilbert Space, the computation provides the exact answer and naturally achieves fully HE according to the method provided by the present inventive concept. The ongoing computation can be hidden by the merge and exchange among the elementary gates, which enhances the security level of information processing and allows problem-dependent optimizations with modest overheads. Moreover, the quantum gates with one-way algorithm in the method of the present inventive concept make the scheme of QAPHE not only conductible on a quantum computer, but also achievable on a classical computer.

[0110] 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.