Multi-input Laconic Function Evaluation

Bo Pang, Long Chen, Xiong Fan, Qiang Tang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Recently, Quach, Wee and Wichs (FOCS 2018) proposed a new powerful cryptographic primitive called laconic function evaluation (LFE). Using an LFE scheme, 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. The laconic property requires that the size of the digest, the run-time of the encryption algorithm and the size of the ciphertext should be much smaller than the circuit-size of f. This new tool is motivated by an interesting application of “Bob-optimized” two-round secure two-party computation (2PC). In such a 2PC, Alice will get the final result thus the workload of Bob will be minimized. In this paper, we consider a “client-optimized” two-round secure multiparty computation, in which multiple clients provide inputs and enable a server to obtain final outputs while protecting privacy of each individual input. More importantly, we would also minimize the cost of each client. For this purpose, we propose multi-input laconic function evaluation (MI-LFE), and give a systematic study of it. It turns out that MI-LFE for general circuit is not easy. Specifically, we first show that the directly generalized version, i.e., the public-key MI-LFE implies virtual black-box obfuscation. Hence the public-key MI-LFE (for general circuits) is infeasible. This forces us to turn to secret key version of MI-LFE, in which encryption now needs to take a secret key. Next we show that secret-key MI-LFE also implies heavy cryptographic primitives including witness encryption for NP language and the indistinguishability obfuscation. On the positive side, we show that the secret-key MI-LFE can be constructed assuming indistinguishability obfuscation and learning with errors assumption. Our theoretical results suggest that we may have to explore relaxed versions of MI-LFE for meaningful new applications of “client-optimized” MPC and others.

Original languageEnglish (US)
Title of host publicationInformation Security and Privacy - 25th Australasian Conference, ACISP 2020, Proceedings
EditorsJoseph K. Liu, Hui Cui
PublisherSpringer
Pages369-388
Number of pages20
ISBN (Print)9783030553036
DOIs
StatePublished - 2020
Event25th Australasian Conference on Information Security and Privacy, ACISP 2020 - Perth, Australia
Duration: Nov 30 2020Dec 2 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12248 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference25th Australasian Conference on Information Security and Privacy, ACISP 2020
CountryAustralia
CityPerth
Period11/30/2012/2/20

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Keywords

  • Indistinguishability obfuscation
  • Laconic function evaluation
  • Multi-party computation

Fingerprint Dive into the research topics of 'Multi-input Laconic Function Evaluation'. Together they form a unique fingerprint.

Cite this