|
|
| Line 144: |
Line 144: |
| ===Trapdoor Functions=== | | ===Trapdoor Functions=== |
|
| |
|
| ===Quantum Capable Homomorphic Encryption===
| |
| ====Homomorphic Encryption====
| |
| A homomorphic encryption scheme HE is a scheme to carry out classical computation from the Server while hiding the inputs, outputs and computation. It can be divided into following four stages.
| |
| * ''Key Generation.'' The algorithm (pk,evk,sk) ← HE.Keygen(1λ) takes a λ, a security parameter as input and outputs a public key encryption key pk, a public evaluation key evk and a secret decryption key sk.
| |
| * ''Encryption.'' The algorithm c ← HE.Encpk(µ) takes the public key pk and a single bit message µ ∈ {0,1} and outputs a ciphertext c. The notation HE.Encpk(µ;r) is be used to represent the encryption of a bit µ using randomness r.
| |
| * ''Decryption''. The algorithm µ∗ ← HE.Decsk(c) takes the secret key sk and a ciphertext c and outputs a message µ∗ ∈ {0,1}.
| |
| * ''Homomorphic Evaluation'' The algorithm cf ← HE.Evalevk(f,c1,...,cl) takes the evaluation key evk, a function f : {0,1}l → {0,1} and a set of l ciphertexts c1,...,cl, and outputs a ciphertext cf. It must be the case that:
| |
| HE.Decsk(cf) = f(HE.Decsk(c1),...,HE.Decsk(cl)) (1)
| |
| with all but negligible probability in λ. This means classical HE decrypts ciphertext bit by bit.
| |
| HE scheme is compact if HE.Eval is independent of any inputs or computation. It is fully homomorphic if it can compute any boolean computation.
| |
| ====Quantum Capable====
| |
| ''A classical HE is quantum capable if it can be used to evaluate quantum circuits.''
| |
| Any HE scheme to be quantum capable requires the following two properties.
| |
| *''invariance of ciphertext:''
| |
| *''natural XOR operation:''
| |
| ==Gadget Construction (to correct phase errors)== | | ==Gadget Construction (to correct phase errors)== |