Fully Homomorphic Encryption
HGI » UbiCrypt » Projects

Fully Ho­mo­mor­phic En­cryp­ti­on

1st ad­vi­sor: May, 2nd ad­vi­sor: Simon, 3rd ad­vi­sor: Schwenk

Fully ho­mo­mor­phic en­cryp­ti­on al­lows to eva­lua­te an ar­bi­tra­ry cir­cuit C (or a pro­gram) on an input x1, ... , xn alt­hough one only re­cei­ves an en­cryp­ted input Enc(C, x1, ... , xn). The eva­lua­ti­on yields the en­cryp­ti­on of C on input x1, ... , xn, i.e., c' = Enc(C(x1, ..., x_n)), where the size of c' does not de­pend on the size of the cir­cuit C.

De­pen­ding on C, fully ho­mo­mor­phic en­cryp­ti­on al­lows to rea­li­ze dif­fe­rent func­tio­na­li­ties like mul­ti­par­ty com­pu­ta­ti­on, pri­va­te in­for­ma­ti­on re­trie­val, se­arch on en­cryp­ted data, web ser­vices and ob­fu­s­ca­ti­on. These func­tio­na­li­ties are use­ful in ubi­qui­tous com­pu­ta­ti­on sce­na­ri­os where data from dif­fe­rent sour­ces like sen­sors, mo­bi­le de­vices or PCs are pro­ces­sed on non-trusted ser­vers in the cloud. Fully ho­mo­mor­phic en­cryp­ti­on the­re­by en­su­res pri­va­te pro­ces­sing of the data, which is often man­d­ato­ry, e.g., for me­di­cal data.

In 2009, Gen­try in­tro­du­ced the first rea­liza­t­i­on of a fully ho­mo­mor­phic pu­blic-key cryp­to sys­tem. Na­tu­ral­ly, a sche­me as power­ful as fully ho­mo­mor­phic en­cryp­ti­on re­qui­res strong com­ple­xi­ty as­sump­ti­ons. For rea­li­zing the full func­tio­na­li­ty, Gen­try had to as­su­me the exis­tence of cir­cu­lar en­cryp­ti­on, where a secret key can se­cu­re­ly be en­cryp­ted under its own pu­blic key, and the hard­ness of a very low weight sub­set sum pro­blem, which al­lo­wed for the so-cal­led squa­shing of the de­cryp­ti­on cir­cuit.

The main re­se­arch chal­len­ges are now to find the mi­ni­mal re­qui­re­ments under which fully ho­mo­mor­phic en­cryp­ti­on sche­mes can be rea­li­zed, which in turn would ma­xi­mi­ze the ef­fi­ci­en­cy of the sche­mes. For in­stan­ce, it is not clear whe­ther cir­cu­lar en­cryp­ti­on fol­lows from stan­dard no­ti­ons as CPA se­cu­ri­ty, or whe­ther there exist (pa­tho­lo­gi­cal) crypto­sys­tems that are CPA se­cu­re, but do not offer cir­cu­lar se­cu­ri­ty.

Mo­re­over, is the com­ple­xi­ty as­sump­ti­on on low weight sub­set sum re­al­ly ne­cessa­ry? Or on the cryp­t­ana­ly­tic side, do their exist ef­fi­ci­ent ways to solve sub­set sums of very low weight?

Prof. Alexander May

Prof. Alexander May