Method of Designing of Multi-Party System in QAP-Based Homomorphic Encryption

Abstract

A method of designing a multi-party 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 the method comprises: increasing single model provider A to multiple ones, wherein the number of the multiple model providers is L and let A.sub.1≤i≤L and L≥2; increasing single data provider B to multiple ones, wherein the number of the multiple data providers is R and let B.sub.1≤j≤R and R≥2; and encoding plaintexts, each of which is of k.sub.j qubits, from all data providers into ciphertexts respectively; aggregating the ciphertexts by a form of tensor product and generating an encoded state for computation; and preparing a model operation to conduct the encrypted computation via an encoded operator and the encoded state in a cloud. The method can improve the security of public-key/semi-public-key system and be applied to a threshold HE or a multi-key HE to solve actual problems.

Claims

1. A method of designing a multi-party 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 the method comprises: S1. increasing a single model provider A to multiple ones, wherein the number of the multiple model providers is L and let A.sub.1≤i≤L and L≥2; S2. increasing a single data provider B to multiple ones, wherein the number of the multiple data providers is R and let B.sub.1≤j≤R and R≥2; and for the k.sub.j-qubit plaintext from each of the data providers, encoding this plaintext into a ciphertext |ψ.sub.j; S3. aggregating the number R of ciphertexts by a form of tensor product and generating an encoded state $|{\psi }_{en}.Math.=\stackrel{\stackrel{j=1}{R}}{.Math.}|{\psi }_j.Math.$ for computation; and S4. preparing a model operation to conduct the computation, U.sub.en|ψ.sub.en, of an encoded operator U.sub.en and the encoded state |ψ.sub.en in a cloud.

2. The method of claim 1, wherein the multi-party system designed by the method executes its function by following a single public-key in QAPHE.

3. The method of claim 2, wherein the step of S1 of the method further comprises: choosing a partition [n.sub.i, k.sub.i, C.sub.i] by each of the model providers and one public-key Key.sub.pub,i and one private-key are generated by each of the partition.

4. The method of claim 3, wherein the public-key is composed of n.sub.i-qubit modified encoding and a random error generator.

5. The method of claim 2, wherein the step of S2 of the method further comprises: choosing a public-key Key.sub.pub,j by each of the data providers and each of the data providers encodes its own k.sub.j-qubit plaintext into a ciphertext |ψ.sub.j.

6. The method of claim 1, wherein the multi-party system designed by the method executes its function by following a single semi-public-key in QAPHE.

7. The method of claim 6, wherein the step of S1 of the method further comprises: generating the semi-public-key Key.sub.s-pub by all the A.sub.1≤i≤L together.

8. The method of claim 7, wherein the semi-public-key is composed of encoding generators.

9. The method of claim 6, wherein the step of S2 of the method further comprises: choosing an encoding Q.sub.P.sup.(j) by each of the data providers and each of the data providers encodes its own k.sub.j-qubit plaintext into a ciphertext |ψ.sub.j.

10. The method of claim 6, wherein $\stackrel{R}{\underset{j=1}{.Math.}}{k}_j\le k$ in the step of S2.

11. The method of claim 6, wherein after the step of S3, the method further comprises: sending encoded message En(ζ.sub.P.sup.(j)) to A.sub.σ(j) by the data providers, wherein σ(j) is a permutation.

12. The method of claim 1, wherein the cloud maintains single due to considering the parallel computation.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

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

[0027] FIG. 2A is a schematic diagram of a single public key in the QAPHE system of an embodiment of the present inventive concept;

[0028] FIG. 2B is a schematic diagram of extending a single public key in the QAPHE system to multi-party system by the method of the present inventive concept;

[0029] FIG. 3A is a schematic diagram of a single semi-public key in the QAPHE system of an embodiment of the present inventive concept;

[0030] FIG. 3B is a schematic diagram of extending a single semi-public key in the QAPHE system to multi-party system by the method of the present inventive concept.

DETAILED DESCRIPTION

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

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

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

[0034] Please refer to FIG. 1 which is a flowchart of an embodiment of the method provided by the present inventive concept. The present inventive concept provides a method of designing a multi-party 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 the method comprises:

[0035] S1. increasing a single model provider A to multiple ones, wherein the number of the multiple model providers is L and let A.sub.1≤i≤L and L≥2;

[0036] S2. increasing a single data provider B to multiple ones, wherein the number of the multiple data providers is R and let B.sub.1≤j≤R and R≥2; and for the k.sub.j-qubit plaintext from each of the data providers, encoding this plaintext into a ciphertext |ψ.sub.j;

[0037] S3. aggregating the number R of ciphertexts by a form of tensor product and generating an encoded state

[00003]$|{\psi }_{en}.Math.=\stackrel{\stackrel{j=1}{R}}{.Math.}|{\psi }_j.Math.$

for computation; and

[0038] S4. preparing a model operation to conduct the computation, U.sub.en|ψ.sub.en, of an encoded operator U.sub.en and the encoded state |ψ.sub.en in a cloud.

[0039] In an embodiment of the present inventive concept, the cloud maintains single due to considering the parallel computation.

[0040] Please refer to FIG. 2A which is a schematic diagram of one public key in the QAPHE system of an embodiment of the present inventive concept. Specifically, the single public key may be defined as Key.sub.pub=(VQ.sub.en, Gen.sub.ε); U.sub.en may be defined as PQ.sub.en.sup.†V.sup.†; and the private key may be defined as Key.sub.priv=.sup.+P.sup.+.

[0041] Please refer to FIG. 2B which is a schematic diagram of extending a single public key in the QAPHE system to multi-party system by the method of the present inventive concept. In an embodiment of the present inventive concept, the multi-party system designed by the method executes its function by following a single public-key in QAPHE shown in FIG. 2A.

[0042] According to the present inventive concept, as shown in FIG. 2B, the model provider may be part of Alice and the data provider may be part of Bob.

[0043] In an embodiment of the present inventive concept, the step of S1 of the method may further comprise: choosing a partition [n.sub.i, k.sub.i, C.sup.i] by each of the model providers and one public-key Key.sub.pub,i and one private-key may be generated by each of the partition.

[0044] In an embodiment of the present inventive concept, the public-key may be composed of n.sub.i-qubit modified encoding and a random error generator. The modified encoding may be represented as V.sup.(j)Q.sub.en.sup.(j) and the random error generator may be represented as Gen.sub.ε.sub.i.sub.°

[0045] In an embodiment of the present inventive concept, the step of S2 of the method may further comprise: choosing a public-key Key.sub.pub,j by each of the data providers and each of the data providers may encode its own k.sub.j-qubit plaintext into a ciphertext |ψ.sub.j. In this embodiment, the ciphertext may be denoted as |ψ.sub.j=Ē.sup.(j)V.sup.(j)Q.sub.en.sup.(j)|0.Math.|x.sub.j.

[0046] According to the present inventive concept, as shown in FIG. 2B, the public key may be defined as Key.sub.pub,i=(V.sup.(j)Q.sub.en.sup.(j), Gen.sub.ε.sub.i); U.sub.en may be defined as PQ.sub.en.sup.†V.sup.†; Q.sub.en.sup.†V.sup.† may be defined as

[00004]$\underset{j=1}{\stackrel{R}{.Math.}}{\left(V^{\left(j\right)}{Q}_{en}^{\left(j\right)}\right)}^{+};$

may be defined as

[00005]$\underset{j=1}{\stackrel{R}{.Math.}}{ℬ}^{\left(j\right)};$

may be defined as

[00006]$I_{2^{n-k}}.Math.\left\{\underset{j=1}{\stackrel{R}{.Math.}}{M}_j\right\};$

and the private key may be defined as Key.sub.priv=.sup.+P.sup.+.

[0047] Please refer to FIG. 3A which is a schematic diagram of a single semi-public key in the QAPHE system of an embodiment of the present inventive concept. Specifically, the single semi-public key may be defined as Key.sub.s-pub=Gen.sub.Q; U.sub.en may be defined as PQ.sub.p.sup.†; and the private key may be defined as Key.sub.priv=.sup.+P.sup.+.

[0048] Please refer to FIG. 3B which is a schematic diagram of extending a single semi-public key in the QAPHE system to multi-party system by the method of the present inventive concept. according to an embodiment of the present inventive concept, the multi-party system designed by the method may execute its function by following a single semi-public-key in QAPHE shown in FIG. 3A.

[0049] According to the present inventive concept, as shown in FIG. 3B, the model provider may be part of Alice and the data provider may be part of Bob.

[0050] In an embodiment of the present inventive concept, the step of S1 of the method may further comprise: generating the semi-public-key Key.sub.s-pub by all the A.sub.1≤i≤L together.

[0051] In an embodiment of the present inventive concept, the semi-public-key may be composed of encoding generators. The encoding generators may be, for example, but not limited to k-qubit permutations.

[0052] In an embodiment of the present inventive concept, the step of S2 of the method may further comprise: choosing an encoding Q.sub.P.sup.(j) by each of the data providers and each of the data providers encodes its own k.sub.j-qubit plaintext into a ciphertext |ψ.sub.j. In this embodiment, the ciphertext may be denoted as |ψ.sub.j=Q.sub.p.sup.(j)|x.sub.j.

[0053] In an embodiment of the present inventive concept,

[00007]$\stackrel{R}{\underset{j=1}{.Math.}}{k}_j\le k$

in the step of S2.

[0054] In an embodiment of the present inventive concept, after the step of S3, the method may further comprise: sending encoded message En(ζ.sub.P.sup.(j)) to A.sub.σ(j) by the data providers, wherein σ(j) is a permutation.

[0055] According to the present inventive concept, as shown in FIG. 3B, the semi-public key maybe defined as Key.sub.s-pub=Gen.sub.Q; U.sub.en may be defined as PQ.sup.†; Q.sup.† may be defined as

[00008]$\underset{j=1}{\stackrel{R}{.Math.}}{\left(Q_p^{\left(j\right)}\right)}^{+};$

may be defined as

[00009]$\underset{j=1}{\stackrel{R}{.Math.}}{M}_j;$

and the private key may be defined as Key.sub.priv=.sup.+P.sup.+.

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

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

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

[0059] 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 from each block, Γ.sub.α, v∈Z.sub.2.sup.2k and S.sub.β∈ε.

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

[0061] Quantum Circuit

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

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

[0064] 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 operates 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.

[0065] A quantum circuit exists to perform an addition Σ.sub.i=1.sup.Nm.sub.i of a number N of l-bit message m.sub.i∈Z.sub.2.sup.l. For the addition of two l-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.

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

[0067] Construction of Public-Key Scheme

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

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

[0070] 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 an 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.

[0071] 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

[0072] 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.sub.n.

[0073] 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 . 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.2W.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.

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

[0075] 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).

[0076] 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.†.

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

[0078] Construction of Semi-Public-Key Scheme

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

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

[0081] 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

[0082] where Q.sub.p.sup.† is a product of two operators W.sub.1 and W.sub.2W1 and W2∈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.

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

[0084] An encoded operation U.sub.en=PQ.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.†.

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

[0086] Example of the Public Key Encryption

[0087] 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 an 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.

[0088] 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

[0089] Supposed that a number of l-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.

[0090] 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 Ē.

[0091] 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, which 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).

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

[00010]$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.

[0093] 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.q<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

[0094] 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).

[0095] The present inventive concept provides a method of designing of multi-party system in QAP-based homomorphic encryption. This method is able to improve the security of public-key/semi-public-key system; under proper conditions, the common designs of multi-party HE, such as threshold HE or multi-key HE, may be included to be immediately applied to actual problems.

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