Willy Quach: Laconic Function Evaluation and Applications
Speaker
Willy Quach, Northeastern
Host
Vinod Vaikuntanathan
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.
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.