Understanding Homomorphic Signatures and Fully Homomorphic Encryption

Slide Note

Explore the concepts of homomorphic signatures, fully homomorphic encryption, and their unified construction as they relate to security and authenticity in data processing. Learn about commitments, extractable commitments, and equivocal commitments in the context of encryption and signatures.

dberg Follow

Uploaded on Sep 17, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

E N D

Presentation Transcript

Homomorphic Signatures Daniel Wichs Daniel Wichs Northeastern University based on work with: based on work with: Sergey Gorbunov and Vinod Vaikuntanathan

Fully Homomorphic Encryption (FHE) [Rivest-Adleman-Dertouzos 78, Gentry 09, ] ??,?? ? = Enc??(?) ? = Eval(?,?) Alice Dec??? = ?(?)

Fully Homomorphic Signatures Median Household Size? large dataset Alice Bob ? ? ? = ?(?) Authenticity: how do we know ? is correct?

Fully Homomorphic Signatures ??,?? short ?? Alice Bob ? , ? ? ,? ? = ?(?) ? =Eval(?,?) Verify??(?,?,? ) = Sign??(?) Security : If ? = ?(?), then the cloud cannot convince Bob that result is ? ?

Theorem [Gorbunov, Vaikuntanathan, Wichs15]: A leveled fully homomorphic signature (HS) scheme for all circuits of some a-priori bounded depth d. Shortness: Size of certificate f,y is poly( , d) where is the security parameter and d is the circuit depth for f. Security: assuming hardness of LWE/SIS. Caveat: Need large public random string (public params) or random oracle model.

Unified Construction: Connects FHE and FHS Fully Homomorphic Encryption Fully Homomorphic Commitments Fully Homomorphic Signatures

Commitments ?? : public commitment key ?? : trapdoor ? = commit??(?,?) Alice Bob bit: ? , opening: ? ? {0,1} Hiding: Commitment ? hides ? Binding: Can only open ? to a single value ?.

Extractable Commitments encryption ?? : public commitment key ?? : trapdoor ? = commit??(?,?) Alice Bob bit: ? , opening: ? ? {0,1} Hiding: Commitment ? hides ? but given ?? can recover ? Binding: Can only open ? to a single value ?.

Equivocal Commitments signatures ?? : public commitment key ?? : trapdoor ? = commit??(?,?) Alice Bob bit: ? , opening: ? ? {0,1} Hiding: Commitment ? hides ? Binding: Can only open ? to a single value ?. but given ?? can open any ? to any ?

Fully Homomorphic Commitments Can evaluate a function ? over commitments and openings Commitments: ?1 = commit??(?1,?1) , ,?? = commit??(??,??) Bits/Openings: (?1,?1) , ,(??,??) Evalcom( ?,?1, ,?? ) =? Evalopen( ?,(?1,?1), ,(??,??) ) =? ? = commit??(?(?1, ,??), ? )

Recall the GSW FHE ? ?LWE matrix,sk= LWE secret pk = A ? Encryptpk(x) : C = AR + xG R 0,1? ? is random, small entries G ? ? ?is a public gadget matrix

GSW as a Commitment ? ? Commitment key pk = A ? Commitpk(x) : C = AR + xG Opening: (x, R) : R has small entries

Homomorphic Computation on Commitments and Openings Commitments: C1 = AR1 + x1G , C2 = AR2 + x2G, Openings: (x1, R1),(x2, R2), Evaluate f: Evalcom(f, C1, ,Cn) Cf Evalopen(f, (x1, R1), ,(xN, Rn)) ( f(x1, ,xn), Rf ) Might reveal extra info about x1, ,xn. (can remove this) Cf = ARf + f(x1, ,xn)G

Homomorphic Computation on Commitments and Openings Commitments: C1 = AR1 + x1G , C2 = AR2 + x2G Openings: (x1, R1)(x2, R2) Addition: Evalcom C+ = C1 + C2 Evalopen ( x1 + x2, R1 + R2) C+= ( AR1 + x1G ) + ( AR2 + x2G ) = A(R1+R2) + (x1+x2)G

Homomorphic Computation on Commitments and Openings Commitments: C1 = AR1 + x1G , C2 = AR2 + x2G Openings: (x1, R1)(x2, R2) Multiplication: Evalcom Cx = C1 G-1(C2) Evalopen (x1x2, R1 G-1(C2) + x1R2) Cx= (AR1 + x1G) G-1(C2) = (AR1 G-1(C2) + x1(AR2 + x2G) = A(R1 G-1(C2) + x1R2) + x1x2G

Homomorphic Computation on Commitments and Openings Commitments: C1 = AR1 + x1G , C2 = AR2 + x2G, Openings: (x1, R1),(x2, R2), Evaluate f: Evalcom(f, C1, ,Cn) Cf Evalopen(f, (x1, R1), ,(xN, Rn)) ( f(x1, ,xn), Rf ) Rf = [R1, ,Rn]H where H depends on {Ci , xi} and f.

Two Flavors of Commitments Commitpk(x) : C = AR + xG A is chosen as in GSW: computationally hiding (LWE). statistically binding. extractable using trapdoor. B A = b = sB+e A is chosen uniformly random: scheme is statistically hiding, commitments are uniformly random. computationally binding (LWE or SIS) equivocal using a trapdoor (next) A =

SIS Trapdoor [Ajtai99, ,MP12] Goal: choose a random A with a trapdoor such that for any V can find short R : AR = V. To open commitment C to a bit x, set V = C xG. R = TG-1(V) m/2 m/2 Trapdoor: T = -R* B A = BR* + G n I AT = G

SIS Trapdoor with Correct Distribution [GPV08, MP12, LW15] Stronger Goal: choose a random A with trapdoor td such that the following are statistically close. (V, R) : R ShortDist, V = AR (C, R) : R ShortDist, C = AR + xG (V, R) : V Uniform, R Opentd(V) (C, R) : C Uniform, R Equivocatetd(C,x) Can do this by carefully analyzing Gaussian distributions, or via rejection sampling.

Summary: Homomorphic Commitments C= Commitpk(x;R) is a commitment, (x,R) is opening. Can homomorphically evaluate any function on commitments and openings: Evalcom(f, C1, ,CN) Cf Evalopen(f, (x1, R1), ,(xN, RN)) ( f(x1, ,xN), Rf ) Two flavors: extractable, equivocal. Commitment key pk can be set to either, they are indistinguishable. In equivocal mode: A commitment to any bit is just a random value C Given a trapdoor for pk, can equivocate commitment C to any bit. Distributions match.

Recall: Fully Homomorphic Signatures ??,?? short ?? Alice Bob ? , ? ? ,? ? = ?(?) ? =Eval(?,?) Verify??(?,?,? ) = Sign??(?) Security : If ? = ?(?), then the cloud cannot convince Bob that result is ? ?

Constructing Fully Homomorphic Signatures Security Intuition: If adversary can forge a signature for incorrect ?1 $$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ random commitments Secret key: ?? (equivocation) ?? Public randomness: Public key: ?? ? ?(?) then can break binding of the commitment ? . ,? ? ,? ? ? = ?(?) Verifypk(?,?,? )=1 = Signsk(? = (?1, ??)) ? := Evalopen(?,(?1,?1), ,(??,??)) = (?1, ,??) s.t. commit??(?? ,??)=?? Compute ? = Evalcom(?,?1, ,??) Check Commitpk(?, ? ) = ?

Security Proof Selective security : data x is worst-case but indep of CRS. Sig security game: ?? $ , ?? Equivocatetd(Ci,xi) Adv(A, {Ci, Ri}) = (f, R*) Pr[ AR* +(1-f(x))G = ARf + f(x)G] = non-negligible Modified game: ?? SmallDist, ??=ARi + xG Adv(A, {Ci, Ri}) = (f, R*) Pr[ AR* +(1-f(x))G = ARf + f(x)G] = non-negligible Break binding: given A sample {Ri, Ci} as in modified game and run Adv(A, {Ci, Ri}) = (f,R*). Output (R*, Rf)

Extensions Full security (beyond selective): Homomorphic chameleon hash [KR00] = Homomorphic equivocal commitments. Multiple data sets: Use standard signature to sign a fresh verification key of homomorphic signature scheme for each data set. Context Hiding (certificate only reveals output of comp.) Can be done generically with NIZKs. Nice way to do this for our scheme using equivocation trapdoors.