The Future of Encrypted Computation Craig Gentry and Shai Halevi IARPA SPAR Final PI Meeting, Annapolis MD June 17, 2014 Encrypted Computation: Where are we now? Homomorphic Encryption Noisy somewhat HE, and bootstrapping Progress 2011-2014

Can handle poly-depth circuits rather than logdepth, but deep circuits are still very expensive Security from weaker assumptions (LWE/RLWE/NTRU) Ciphertext-packing: SIMD on encrypted arrays, manipulating encrypted data across plaintext slots Many other low-level optimizations Ring-switching, scale-invariant,

Using (F)HE in Applications Work barely started Some work on use cases (linear regression, PIR, ) Some benchmarking work Focus on apps that need very shallow circuits

Homomorphic evaluation of AES Our recent work on using HE as a primitive inside higher-level protocols Leverage interaction to reduce circuit depth MMAPs Mmaps: (sort of) like FHE Elements are encoded (vs. encrypted)

Plausible MMAP constructions: GGH13, CLT13 Cannot recover them in plaintext form But can test if an encoded element is zero By modifying HE constructions, enabling zerotest (In)security: Assumptions are new, unstudied (In)efficiency: Comparable to [Gen09] FHE

Obfuscation Hiding secrets in software Plaintext strutpatent.com AES encryption Ciphertext Obfuscation Hiding secrets in software

Plaintext @P=split//,".URRUU\c8R";@d=split//,"\ nrekcah xinU / lreP rehtona tsuJ";sub p{ @p{"r$p","u$p"}=(P,P);pipe"r$p","u$p"; ++$p;($q*=2)+=$f=! fork;map{$P=$P[$f^ord ($p{$_})&6]; $p{$_}=/ ^$P/ix?$P:close$_}keys %p}p;p;p;p;p;map{$p{$_}=~/^[P.]/&& close$_}%p;wait until$?;map{/^r/&&<$_>}%p; $_=$d[$q];sleep rand(2)if/\S/;print Ciphertext AES encryption Public-key encryption Obfuscation

Encrypting a computation, getting result in the clear Can be realized from FHE with conditional x decryption F(x) + Homomorph F ic Encryption F(x)

F Encrypted-result + eval transcript If describes homomorphic evaluation that takes x,F to , then useCondDec sk to decrypt Obfuscation

Encrypting a computation, getting result in the clear Can be realized from FHE with conditional decryption Plausible obfuscation constructions: GGHRSW13, (In)security: Use complicated assumptions over mmaps (In)efficiency: Can be used for upto ~10 gates Poor understanding: We still dont know what we can/cant achieve, or what we want to achieve. Garbled RAM

Garbled RAM: (sort of) like Yao garbled circuits, but with RAM complexity rather than circuit complexity Think binary search vs. linear scan One-time GRAM: from simple tools Reusable GRAM: Uses obfuscation (In)efficiency:

Goal is to get RAM efficiency (sub-linear time) But using obfuscation makes it impractical Verifiable Computation Offline: Client computes CRSf for a function f sends to server Online: Client sends x to server

Server computes f(x), together with a short proof that f(x) was computed correctly (using CRSf) Client verifies much faster than computing f(x) from scratch Verifiable Computation (cont.) Current schemes use bilinear maps

Leveled schemes: CRS size linear in |f| Server computation quasi-linear in |CRS| Bootstrapped schemes: Server aggregates proofs dynamically by proving that it has verified proofs Problem: Bilinear maps are slow Bootstrapped schemes are especially slow

Since pairing computations (needed for verifying proofs) are very expensive Functional Encryption [SW05, ,GGHRSW13] Public Parameters MSK Authority Functionality: yeilds ; remains hidden Collusion resistance: Knowing yields only CT: x

Key: f SKf CTx An Application: Facial Identification SK Status of Functional Encryption Pairing-based solutions for simple functions

Complexity exponential in circuit depth Practical for very simple functions Obfuscation-based solution for all functions Asymptotically efficient, practically not Encrypted Computation: On the Horizon Low-Hanging Fruit: Hardware Accelerators for Encrypted Computation

FHE/mmap computations embarrassingly parallel Parallel complexity of FHE/mmaps may even be better than Yao We still dont seem to have good parallelized implementations (ASIC, FPGA, GPU, ) Low-Hanging Fruit: More optimization for PIR/Batch-Keyword with SWHE 32 bit records, 5 Mbps network trivial PIR

Is worst 2 multiplications are best (dim=3) (batch=4620) (batch=6521) (batch=7992) Low-Hanging Fruit: More optimization for PIR/Batch-Keyword with SWHE We can probably do better Data insertion phase

Quick compression phase Multiply data into ciphertexts that batch-encrypt selector bits Data packed into new ciphertexts w/ only (1+) expansion) expansion Initial large ciphertexts are collapsed immediately (via addition) E.g., New ciphertexts may be 1/1000 size of initial data Telescoping phase

Applying selection recursively, total ciphertext size decreases geometrically Due to small size of compressed ciphertexts and geometric reduction in ciphertext size, the time of this phase is small Obfuscation Based on LWE? Goal: Base obfuscation on simple assumptions (LWE) This pursuit was very fruitful for FHE

Led to much more efficient schemes Also improved security Can this be repeated for MMAPs/obfuscation? Obfuscation From Rank Assumptions [GLW14, GLSW14] Subgroup-membership assumptions: Plaintext space has order (s are primes) Adversary gets encoded elements

The order of is Given a target encoded element , hard to decide if its order is or Boils down to computing rank in the exponent Each Hard to determine the rank of the matrix

Subgroup-Membership Obfuscation Based on LWE? LWE is also a rank assumption: Given , is close to a low-rank matrix? Can this analogy be pushed further?? Understanding Obfuscation

Our conceptual understanding is lacking What we really want is virtual blackbox (VBB) obfuscation We know that this is not achievable in general But the only negative examples are contrived It is plausible that all interesting natural functions can be VBB-obfuscated No idea how to formulate interesting

natural functions Understanding Obfuscation A weaker notion of indistinguishability obfuscation (iO) is not subject to impossibility results This notion is intuitively clearly not what we want Sufficient for many (but not all) applications

Somewhat unwieldy to work with, induces inefficiencies Intermediate notions also exist (e.g. diO) Some impossibility results are known for these Verifiable Computation from 2-MMAPs Recall: Best verifiable computation use pairings Can we replace pairings by 2-multilinear maps?

The [GGH13,CLT13] with 2-multilinearity Perhaps more efficient than pairings over ECs Bootstrapping must be faster for lattice-based MMAPs Verification of MMAPs much faster than pairing Uses multiplication and rounding, rather than EC pairing Use SWHE for Practical ORAM? Practical

encrypted RAM? Replace MUX logic by encrypted MUX Naively: n-bit address using degree-n MUX Better: use -batching to get degree- circuit Think Get efficient degree-2 function using affordable x256 blowup of the address

Image taken from Wikipedia Encrypted Computation: Over the Rainbow A Totally Different Approach to FHE? FHE without noise? Might also make (expensive) bootstrapping unnecessary How about FHE based on non-abelian groups?

Gentry: workshop presentation in Weizmann (dec 2013) Nuida: A Simple Framework for Noise-Free Construction of Fully Homomorphic Encryption from a Special Class of Non-commutative Groups, 2014/097 High-Level Idea: Set Representations We have a big set G, subset H

Each with many representations Procedures for choosing random representation of G,H Hard to tell G from H Public operations for union, intersection G represents 1, H represents 0 Union OR, intersection AND Can implement NOT by pushing it to the leaves

Perfect Group Pairs Perfect groups: Commutator subgroup Only interesting when G is non-abeliean G is perfect when G = [G,G] We need perfect groups (G, H) such that:

H is a proper, nontrivial, normal subgroup of G Efficient Group Operations Given two sets of generator , generating the groups (each either G or H): Re-Randomization: Given a group (G or H) represented by some generators, output n random elements that generate the same group

n is a parameter Hardness Assumption Subgroup Decision Assumption (for perfect group pairs): Given n elements that generate either G or H, hard to distinguish which Existence? Need perfect group pairs with hard distinguishing problem (and efficient operations and a trapdoor)

Example of perfect group pair with easy dist. problem: Direct product: G = H K, where H and K are perfect Failed Attempt Form of H elements Form of G

elements Linear algebra attack: Encryptions of 0 in proper subspace Is there a patch? Can we use non-abelian groups without fatally embedding them in a ring? (representation theory) Frontier Applications 101 uses of obfuscation Imagine that perfect obfuscation was possible, what could you do with it? Frontier Applications Encrypted analysis of network traffic: Have the AT&Ts, Verizons of the world publish all their network traffic in encrypted form Allow obfuscated analysis on this

encrypted data, yielding nothing but the result of the analysis Controlled by policy that says what analysis is permitted Frontier Applications Mobile agents: I want to send my software agent to roam the network, collect/process available information Hosts to grant it access to their data (or not) based on their own policies Agent

sees all/only permitted info Hosts do not get to learn what the agent knows Popular concept in the 90s But not much was known about how to do it Can be done in principle using obfuscation Frontier Applications Software antibodies: Code fragments embedded in systems, triggered on attacks, performs some

counter measure But specific trigger, action is obfuscated To protect against adversarial analysis Implement local command and control Frontier Applications Mobile brains What I see What I say

My brain Frontier Applications Mobile brains What I see @P=split//,".URRUU\c8R";@d=split//,"\ nrekcah xinU / lreP rehtona tsuJ";sub p{ @p{"r$p","u$p"}=(P,P);pipe"r$p","u$p"; ++$p;($q*=2)+=$f=! fork;map{$P=$P[$f^ord ($p{$_})&6]; $p{$_}=/ ^$P/ix?$P:close$_}keys %p}p;p;p;p;p;map{$p{$_}=~/^[P.]/&& close$_}%p;wait until$?;map{/^r/&&<$_>}%p; $_=$d[$q];sleep rand(2)if/\S/;print

What I say My brain made digital securely!!! Thank You! Questions? E M I T IRED P X E ?