Willy Quach: Laconic Function Evaluation and Applications

Abstract:  We introduce a new cryptographic primitive called laconic function evaluation (LFE). Using LFE, Alice can compress a large circuit f into a small digest. Bob can encrypt some data x under this digest in a way that enables Alice to recover f(x) without learning anything else about Bob's data. For the scheme to be laconic, we require that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should all be small, much smaller than the circuit-size of f. We construct an LFE scheme for general circuits under the learning with errors (LWE) assumption, where the above parameters only grow polynomially with the depth but not the size of the circuit. We then use LFE to construct secure 2-party and multi-party computation (2PC, MPC) protocols with novel properties:

_ We construct a 2-round 2PC protocol between Alice and Bob with respective inputs x_A, x_B in which Alice  
learns the output f(x_A,x_B) in the second round.  This is the first such protocol which is ``Bob-optimized'', 
meaning that Alice does all the work while Bob's computation and the total  communication of the protocol are 
smaller than the size of the circuit f or even Alice's input x_A. In contrast, prior solutions based on fully 
homomorphic encryption are ``Alice-optimized''.

_ We construct an MPC protocol, which allows N parties to securely evaluate a function f(x_1,...,x_N) over 
their respective inputs, where the total amount of computation performed by the parties during the protocol 
execution is smaller than that of evaluating the function itself! Each party has to individually pre-process the 
circuit f before the protocol starts and post-process the protocol transcript to recover the output after the protocol 
ends, and the cost of these steps is larger than the circuit size. However, this gives the first MPC where the 
computation performed by each party during the actual protocol execution, from the time the first protocol 
message is sent until the last protocol message is received, is smaller than the circuit size. 

Joint work with Hoeteck Wee and Daniel Wichs.