Encryptions
We introduced private-key encrytion earlier, but public-key encryption is deferred to this section. It is because the hardness assumption: private-key encryption and other primitives can be based on the existence of OWFs, but we need other assumptions to obtain PKE.
Definition: Public-key encryption.
is said to be a public-key encryption scheme if the following syntax, correctness, and security holds.
is a PPT algorithm, is a PPT algorithm, for all and all , is a deterministic algorithm, for all and , such that . Correctness: For all
, Security: For all NUPPT
, there exists a negligible function such that for all , , distinguishes between the following distributions with probability at most :
With this definitions, there are some immediate impossibility results:
- Perfect secrecy is impossible: given
, the adversary can try to encrypt all messages with all randomness. - Deterministic encryption is also impossible: the adversary can try to encrypt the same message and get the same ciphertext.
Also, IND-CPA security is implied directly. Yet another difference compared to secret-key encryptions is that, the security for long messages is implied directly.
Lemma:
If
is secure public-key encryption, then for any polynomial length , for all , the two distributions are indistinguishable:
where
denotes the -th bit of .
Similarly, the adversary may adaptively choose
Ref: [KL, 12.2]
Learning with Errors, LWE
In this section, we change the representation of
The modular arithmetic is the same. We also say that an element in
We consider matrix
The LWE problem considers the following variant:
where
For our purpose, it is easier to use the decision variant of LWE, formalized next.
Definition: Learning with Errors (LWE) Assumption
We say the decisional
problem is quantum-hard if for all quantum polynomial-time distinguisher there is a negligible function such that for all , where
are functions of , and is an efficiently samplable distribution over .
Discuss:
- Again, the hardness depend on the parameters
. For example, when is uniform over , the two distributions are identical (but useless). - Notice that the above definition also samples
from . - The two distributions differ in entropy:
consists of uniform elements from , but is sampled from uniform elements plus elements from .
An useful set of parameter:
, the smaller the harder LWE so that we can write an element in bits a distribution such that , outputs except with negligible probability (think as a uniform dist); the larger compared to the harder LWE
Ref: [KL, 14.3]
An Encryption Based on LWE
If we have the following decisional
Then, given
by a simple reduction that multiply the former indisintinguishability by
Construction: Secret Key Encryption from LWE
Parameters:
as a function of , a distribution over .
: output
: for binary message , sample and , output (where the arithmetic is in ).
: output
The correctness is direct. The (secret-key) CPA security can be proved by a reduction
Homomorphic Encryption
Definition: Homomorphic encryption.
A (public or secret key) encryption scheme
is said to be homomorphic if the scheme provides efficient operations that satisfies the syntax and correctness below.
Addition: For any messages
, Multiplication: For any messages
, Multiply by constant: For any messages
, Here, the message space and the arithmetic operations
are in , but one may define similarly for other algebra.
[Ref: Barak@Prinecton]
Discuss:
- The homomorphic operations are requiring correctness (not security).
- We sometimes relax the correctness to “except for negligible probability” due to technical construction
- The above definition requires only for “single hop” homomorphic operation, which means that
and work for ciphertexts freshly encrypted by - We may define
-hop operations so that or work also for ciphertexts that is output by -hop or - Ideally, we want unlimited-hop operations. Since
in implement logical (XOR, AND), that enables any boolean-circuit computation on ciphertexts. This is called Fully Homomorphic Encryption, FHE. - Less ideally, if a scheme achieves unlimited-hop
and multiply by constant, it is called additive homomorphic encryption (or linear homomorphic), which is still useful. - Notice that
and need no key, which is essential (otherwise, given key, it would be trivial to perform the operations) - It is trivial and cheating to output
as the output of (and resp.), which belows up the size of the ciphertext and leaves the actual arithmetic to . However, in the above 1-hop Add and Mul definition, we have no way to require it (because one may always pad with unused bits). For more-than-constant hops, we require the ciphertext size to be small even after homomorphic evaluations.
Alternatively, we define homomorphic encryption with respect to a class of circuits
Definition: Homomorphic encryption for class .
Let
be a class of circuits. We say the encryption scheme is homomorphic for if for any , for any where is the input size of , let be the encryption key, Moreover, we require the output size of
to be compact, that is, bounded by .
The above secret-key encryption based on LWE has a direct homomorphic addition. To see why, consider two ciphertexts that is encrypted using the same key
The homomorphic
where
Multiplicative homomorphism is more involved. We show an application of additive homomorphic encryption first.
Public-key Encryption from Additive Homomorphic Encryption
Theorem:
Let
be a secret-key homomorphic encryption scheme for the class of inner product between -bit binary vectors, where to be chosen later is a polynomial of the security parameter given to . Then, the following is a public-key encryption scheme.
: let , sample -bit string such that , compute . Output and public key
: sample -bit string uniformly at random subject to . Output where
is the inner product for any .
: it simply output .
The correctness follows because
Firstly, consider the hybrid scheme that in
, we encrypt instead of . By CPA security of , the hybrid is indistinguishable from the real . Secondly in the hybrid, the ciphertext
is an encryption of 0 of the scheme. It could be attemping to think we were finished, but unfortunately as written, depends on and then still depends on (indeed, different encryptions of 0 might reveal something). To be formal, the key is to observe that is short. Let be the output size of , and let . Then, the adversary is given and aims to find , where is independent of and denotes . Rewrite the computation as Notice that
is uniform, is subject to , and is -bits. Because the min-entropy of subject to any fixed and any fixed is at least , and because is a universal hash family, is statistically close to a uniform bit (by statistical difference ).
Ref: Rothblum, TCC 2011, Homomorphic Encryption: From Private-Key to Public-Key
Homomorphic Multiplication
Consider the encryption scheme for LWE. The ciphertext has format
and the decryption is to compute
so that the decryption works as
For multiplication, we would like to perform similarly,
This would give a correct decrytion when we compute
a quadratic function (degree 2 of
for , where is the -th coordinate of . for .
Since the encryptions (of the above values
- Compute
from and - In
, substitute with , which yields , a linear function of size .
The encryption of
Notice This relinearization is oversimplified. Actually, the
Ref:
- Brakerski and Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, FOCS 2011,
- Brakerski, Gentry, and Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping, ITCS 2012
- Barak @ Princeton
Fully Homomorphic using Bootstrapping
The above homomorphic addition and multiplication (over
The homomorphic addition incurs a small error: each
However, the homomorphic multiplication incurs a much higher error due to the relinearization. Since the error increases exponentially in the number of operations, the
To this end, Gentry (STOC 2009) introduced the idea of “bootstrapping.” That is, to view the high-error ciphertext as a constant string, the decryption algorithm plus the string as a circuit, and then the decryption key as the input of the circuit. That is, define
- Circuit
: it takes input and then run and ouput .
Then, we can encrypt the decryption key
.
The above
where the first equality holds if the error incurred by
- The circuit depth of
is bounded by small number - The
works correctly for circuit depth more than (because we want to perform at least one operation on )
The LWE-based encryption has a simple
With that, we can generate a chain of keys
Alternatively, let
Application: Private Information Retrieval
Definition: Private information retrieval (PIR)
A protocol
is a PIR if it satisfies the following syntax, correctness, and privacy. Let be the size of a database such that .
Correctness: for all
, all , Privacy: for all
, all , for all NUPPT , the following are indistinguishable: Moreover, we define the computation time and the communication to be the time and output size of
.
There are many settings of PIR, for example, the database