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.

(Gen,Enc,Dec) is said to be a public-key encryption scheme if the following syntax, correctness, and security holds.

  1. Gen is a PPT algorithm, (pk,sk)Gen(1n)
  2. Enc is a PPT algorithm, for all pk and all m{0,1}, cEncpk(m)
  3. Dec is a deterministic algorithm, for all sk and c, mDecsk(c) such that m{0,1}.

Correctness: For all nN,m{0,1},

Pr[(pk,sk)Gen(1n):Decsk(Encpk(m))=m]=1.

Security: For all NUPPT D, there exists a negligible function ϵ() such that for all nN, m0,m1{0,1}, D distinguishes between the following distributions with probability at most ϵ(n):

  • {(pk,sk)Gen(1n):(pk,Encpk(m0))}n
  • {(pk,sk)Gen(1n):(pk,Encpk(m1))}n

With this definitions, there are some immediate impossibility results:

  • Perfect secrecy is impossible: given pk, 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 (Gen,Enc,Dec) is secure public-key encryption, then for any polynomial length (), for all m0,m1{0,1}(n), the two distributions are indistinguishable:

  • {(pk,sk)Gen(1n):(pk,Encpk(m0,1),,Encpk(m0,(n)))}n
  • {(pk,sk)Gen(1n):(pk,Encpk(m1,1),,Encpk(m1,(n)))}n

where mb,i denotes the i-th bit of mb.

Similarly, the adversary may adaptively choose (m0,i,m1,i) depending on the earlier ciphertexts Encpk(mb,i),i<i. That is called multi-message security and is also implied by single-message security.

Ref: [KL, 12.2]

Learning with Errors, LWE

In this section, we change the representation of Zq so that

Zq{q12,...,0,...,q2}.

The modular arithmetic is the same. We also say that an element in Zq is small if it is close to 0.

We consider matrix AZqm×n and vector sZqn such that mn. Let t:=AsZqm. Using standard linear algebra, it is efficient to solve Ax=t (when A is full rank).

The LWE problem considers the following variant: A and s are chosen as before, but an additional error vector eZqm is sampled such that e=iei2 is small; Then, the goal is to find x,y such that

Ax+y=t,

where t:=As+e, xZqn, and yZqm is small. The hardness of this problem, Learning with Errors, is parameterized by q,m,n, and the bound of small. When parameters are chosen appropriately, this problem is believed to be hard even for quantum algorithms (the belief is established by reductions from lattice problems which is beyond the scope).

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 LWEm,q,ψ problem is quantum-hard if for all quantum polynomial-time distinguisher D there is a negligible function ϵ such that for all nN,

Pr[AZqm×n;sψn;eψm:D(A,As+e)=1]Pr[AZm×n)q;tZqm:D(A,t)=1]ϵ(n),

where m,qN are functions of n, and ψ is an efficiently samplable distribution over Zq.

Discuss:

  • Again, the hardness depend on the parameters m,q,ψ. For example, when ψ is uniform over Zq, the two distributions are identical (but useless).
  • Notice that the above definition also samples s from ψ.
  • The two distributions differ in entropy: (A,t) consists of mn+m uniform elements from Zq, but (A,As+e) is sampled from mn uniform elements plus (m+n) elements from ψ.

An useful set of parameter:

  • m(n)=poly(n)n2, the smaller the harder LWE
  • q(n)=npoly(n) so that we can write an element in poly(n) bits
  • ψ a distribution such that B=poly(n), ψ outputs |a|B except with negligible probability (think ψ as a uniform dist); the larger B compared to q the harder LWE

Ref: [KL, 14.3]

An Encryption Based on LWE

If we have the following decisional LWEm,q,ψ:

{A,As+e}{A,t}

Then, given dN such that gcd(d,q)=1, we also have

{A,As+de}{A,t}

by a simple reduction that multiply the former indisintinguishability by d (because A and t are both uniform over Zq). Hence, we can construct a secret-key encryption.

Construction: Secret Key Encryption from LWE

Parameters: m,qN as a function of n, ψ a distribution over Zq.

Gen(1n): output k:=sψn

Enck(m): for binary message m{0,1}, sample aZqn and eϕ, output c:=(a,t=as+2e+m) (where the arithmetic is in Zq).

Deck(c): output

m:=(tasmod2)

The correctness is direct. The (secret-key) CPA security can be proved by a reduction R such that when ever the adversary A of the encryption asks for an encryption, R takes the next row from its LWE input and adds m. The details are skipped here.

Homomorphic Encryption

Definition: Homomorphic encryption.

A (public or secret key) encryption scheme (Gen,Enc,Dec) is said to be homomorphic if the scheme provides efficient (Add,Mul) operations that satisfies the syntax and correctness below.

  • Addition: For any messages m0,m1Z2,

    Prk[(ciEnck(mi))i{0,1};Deck(Add(c0,c1))=m0+m1]=1
  • Multiplication: For any messages m0,m1Z2,

    Prk[(ciEnck(mi))i{0,1};Deck(Mul(c0,c1))=m0m1]=1
  • Multiply by constant: For any messages m0,m1Z2,

    Prk[c0Enck(m0);Deck(Mul(c0,m1))=m0m1]=1

Here, the message space and the arithmetic operations (+,) are in Z2, 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 Add and Mul work for ciphertexts freshly encrypted by Enc
  • We may define t-hop operations so that Add or Mul work also for ciphertexts that is output by (t1)-hop Add or Mul
  • Ideally, we want unlimited-hop operations. Since (+,) in Z2 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 Add and multiply by constant, it is called additive homomorphic encryption (or linear homomorphic), which is still useful.
  • Notice that Add and Mul need no key, which is essential (otherwise, given key, it would be trivial to perform the operations)
  • It is trivial and cheating to output (add,c0,c1) as the output of Add (and Mul resp.), which belows up the size of the ciphertext and leaves the actual arithmetic to Dec. However, in the above 1-hop Add and Mul definition, we have no way to require it (because one may always pad c0 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 C.

Definition: Homomorphic encryption for class C.

Let C be a class of circuits. We say the encryption scheme (Gen,Enc,Dec,Eval) is homomorphic for C if for any CC, for any m1,,m{0,1} where is the input size of C, let kGen(1n) be the encryption key,

Prk[(ciEnck(mi))i[];Deck(Eval(C,c1,...,c))=C(m1,...,m)]=1.

Moreover, we require the output size of Eval to be compact, that is, bounded by |Enck(mi)|.

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 s,

c0:=(a0,a0s+2e0+m0),c1:=(a1,a1s+2e1+m1)

The homomorphic Add(c0,c1) is defined to be the coordinate-wise addition:

Add(c0,c1):=(a0+a1,(a0s+2e0+m0)+(a1s+2e1+m1))=(a,as+2e+(m0+m1))

where a=a0+a1 and e=e0+e1. The multiplication by constant is also coordinate-wise multiply by plaintext m1. Notice that the correctness holds as long as eq/4 before modulo q. Hence, we can perform O(q/B) operations (of addition or multiply by constant) and then still obtain the correct decrytion, where B,q are the LWE parameters.

Multiplicative homomorphism is more involved. We show an application of additive homomorphic encryption first.

Public-key Encryption from Additive Homomorphic Encryption

Theorem:

Let (G,E,D,Eval) be a secret-key homomorphic encryption scheme for the class of inner product between -bit binary vectors, where :=(n) to be chosen later is a polynomial of the security parameter n given to G. Then, the following (Gen,Enc,Dec) is a public-key encryption scheme.

  • Gen(1n): let sk=kG(1n), sample n-bit string r=(r1,,r){0,1} such that r0, compute R1Ek(r1),,REk(r). Output sk and public key

    pk=(r1,...,r,R1,...,R).
  • Encpk(m): sample -bit string u uniformly at random subject to ru=m. Output

    c:=Eval(fu,R1,...,R),

    where fu is the inner product fu(x):=ux for any x{0,1}.

  • Decsk(c): it simply output Dsk(c).

The correctness follows because r0n implies the existence of u and then by the correctness of Eval. The efficiency is also direct (just need to sample r and u with care). The security is sketched below.

Firstly, consider the hybrid scheme that in Gen, we encrypt RiEnck(0) instead of Enck(ri). By CPA security of (G,E,D), the hybrid is indistinguishable from the real (Gen,Enc,Dec).

Secondly in the hybrid, the ciphertext c is an encryption of 0 of the (G,E,D) scheme. It could be attemping to think we were finished, but unfortunately as written, c depends on u and then u still depends on m (indeed, different encryptions of 0 might reveal something). To be formal, the key is to observe that |c| is short. Let t:=|c| be the output size of Eval, and let :=4t. Then, the adversary is given (r,FR(u)) and aims to find m=ru, where R is independent of r and FR() denotes Eval(f(),R1,,Rn). Rewrite the computation as

Ext(r,u):=(r,FR(u),m=ru).

Notice that r is uniform, u is subject to m, and FR(u) is t-bits. Because the min-entropy of u subject to any fixed m and any fixed FR(u) is at least /2, and because hr(u)=ru is a universal hash family, ru is statistically close to a uniform bit (by statistical difference 2Ω(t)).

Ref: Rothblum, TCC 2011, Homomorphic Encryption: From Private-Key to Public-Key

Homomorphic Multiplication

Consider the encryption scheme for LWE. The ciphertext has format c=(a,b), and the decrytion is done by baTs, where s is the decryption key, and mod2 is skipped. We can view the decryption as a function,

fa,b(x):=baTx,

and the decryption is to compute fa,b(s). To obtain additive homomorphism, we are exactly performing

fa,b(x):=fa1,b1(x)+fa2,b2(x),

so that the decryption works as

fa,b(s)=fa1,b1(s)+fa2,b2(s).

For multiplication, we would like to perform similarly,

fa,b(x):=fa1,b1(x)fa2,b2(x).

This would give a correct decrytion when we compute fa,b(s). However, we begin with linear functions fa1,b1, but we end with

(b1a1Tx)(b2a2Tx)=b1b2(b1a2T+b2a1T)x+i,ja1,ia2,jxixj,

a quadratic function (degree 2 of x). Moreover, the ciphertext size goes from n+1 to ~n2. This is far from ideal, and there are many techniques to resolve this. One is known as “relinearization”, and the trick is to provide the encryptions of

  • si for i[n], where si is the i-th coordinate of s.
  • sisj for i,j[n].

Since the encryptions (of the above values sisj) are another linear function gci,j(y), the homomorphic multiplication can then

  1. Compute fa,b from fa1,b1 and fa2,b2
  2. In fa,b, substitute xixj with gci,j(y), which yields fa,b(y), a linear function of size n+1.

The encryption of sisj are given as public evaluation key in such constructions.

Notice This relinearization is oversimplified. Actually, the b1b2 term in fa,b(x) consists of products, such as a1Ts2e2. The naive representation of a1Ts is a large integer of order q, but that would incur huge error and incorrect decryption. A careful bitwise decomposition of b1 and b2 will reduce the error factor to poly(n,logq).

Ref:

Fully Homomorphic using Bootstrapping

The above homomorphic addition and multiplication (over Z2) are amazing because we can continue to perform the operations on the ciphertexts repeatedly even when the ciphertexts comes from the previous homomorphic operation. That correctness / functionality hold as long as the error term 2e is <q/4 before modulo q.

The homomorphic addition incurs a small error: each Add introduces a factor at most 2. Starting with B=poly(n) and q=npoly(n), we have the budget to perform many additions.

However, the homomorphic multiplication incurs a much higher error due to the relinearization. Since the error increases exponentially in the number of operations, the <q/4 bar is indeed a critical limitation.

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 fDec,c(x): it takes input x and then run and ouput Decx(c).

Then, we can encrypt the decryption key k1 using another key k2, and call the result as the evaluation key ek:=Enck2(k1). With that, we can homomorphically perform decryption on high-error c:

  • c2Eval(fDec,c,ek=Enck2(k1)).

The above c2 can be later decrypted by k2 as

Deck2(c)=fDec,c(k1)=Deck1(c),

where the first equality holds if the error incurred by fDec,c is smaller than O(q/B). Thus, we need a homomorhic encryption scheme such that

  • The circuit depth of Dec is bounded by small number d
  • The Eval works correctly for circuit depth more than d+1 (because we want to perform at least one operation on c2)

The LWE-based encryption has a simple Dec, which computes firstly a linear operation and secondly a modulo q division, which takes circuit depth poly(logq). This is why we want to minimize the error of homomorphic multiplication.

With that, we can generate a chain of keys k1,k2,,k such that each key encrypts the previous one, so that we can perform many operations. This is known as “leveled homomorphic encryption.”

Alternatively, let k1=k2=k, and thus ek=Enck(k), which is known as “bootstrapping.” Because ek is given to the evaluator (to perform Eval), ek is essentially public and known to any adversaries. That introduces a significant concern in security: we do not know how to prove or disprove that the encryption is still secure given such Enck(k), and this is called “circular security” and used as an additional assumption. Circular security gives a fully homomorphic encryption (and it is still the only known way).

Application: Private Information Retrieval

Definition: Private information retrieval (PIR)

A protocol (Query,Resp,Dec) is a PIR if it satisfies the following syntax, correctness, and privacy. Let N be the size of a database x such that |x|=N.

  • (q,st)Query(i)
  • aResp(x,q)
  • bDec(st,a)

Correctness: for all x, all i[N],

Pr[(q,st)Query(i),aResp(x,q):Dec(st,a)=xi]=1

Privacy: for all x, all i0,i1[N], for all NUPPT D, the following are indistinguishable:

{(q0,st0)Query(i0):q0}{(q1,st1)Query(i1):q1}

Moreover, we define the computation time and the communication to be the time and output size of Query,Resp,Dec.

There are many settings of PIR, for example, the database x and thus the query may be answered by multiple servers. We consider the simpler single server setting here. There is trivial solutions, but we want the protocol to be efficient. Using a somewhat homomorphic encryption, we can construct an efficient PIR with short communication and client time.

Ref: Lin, Mook, Wichs, Doubly Efficient Private Information Retrieval and Fully Homomorphic RAM Computation from Ring LWE. STOC 2023.