International Association
for Cryptologic Research

Witness encryption (WE), first introduced by Garg, Gentry, Sahai and Waters in [GGSW13], is an encryption scheme where messages are encrypted with respect to instances of an NP relation, such that in order to decrypt one needs to know a valid witness for the instance that is associated with the ciphertext. Despite of significant efforts in the past decade to construct WE from standard assumptions, to the best of our knowledge all of the existing WE candidates either rely directly on iO or use techniques that also seem to imply iO in the same way that they seem to imply WE. \In this work we propose a new hardness assumption with regard to lattice trapdoors and show a ``simple'' witness encryption candidate which is secure under it. Contrary to previous WE candidates, our technique is trivially broken when one tries to convert it to iO, which suggests that the security relies on a different mechanism. We view the gap between WE and iO as an analogue to the gap between ABE and FE and thus potentially significant. \Intuitively, the assumption says that ``the best an attacker can do with a trapdoor sample is to use it semi-honestly'' -- i.e.\ that LWE with respect to a public matrix A, given as auxiliary information a trapdoor sample from A to B, is as hard as LWE with respect to the public matrix [A|B] and no auxiliary information. In order to formally state the assumption and use it in the security proof we define a notion of LWE challenges with general distributions of public matrices and auxiliary information. This model allows to bound the hardness of LWE with respect to one distribution as a function of the hardness of LWE with respect to another distribution. Repeated arguments of this flavor can be used as a sequence of hybrids in order to gradually change the challenge that an adversary is facing while keeping track on the security loss in each step of the proof. Typically security proofs of LWE-based systems implicitly make arguments of this flavor for distributions that are indistinguishable, while our model allows to make relaxed arguments that in some cases suffice for the proof requirements. Independently of lattice techniques, our WE candidate relies on branching programs that behave in a predicted manner when they are executed with inconsistent input sequences. This part of the work is information-theoretic in nature and can possibly be used in other environments as well.

We present a novel tree-based technique that can convert any designated-prover NIZK proof system (DP-NIZK) which maintains zero-knowledge only for single statement, into one that allows to prove an unlimited number of statements in ZK, while maintaining all parameters succinct. Our transformation requires leveled fully-homomorphic encryption. We note that single-statement DP-NIZK can be constructed from any one-way function. We also observe a two-way derivation between DP-NIZK and attribute-based signatures (ABS), and as a result derive now constructions of ABS and homomorphic signatures (HS). Our construction improves upon the prior construction of lattice-based DP-NIZK by Kim and Wu (Crypto 2018) since we only require leveled FHE as opposed to HS (which also translates to improved LWE parameters when instantiated). Alternatively, the recent construction of NIZK without preprocessing from either circular-secure FHE (Canetti et al., STOC 2019) or polynomial Learning with Errors (Peikert and Shiehian, Crypto 2019) could be used to obtain a similar final statement. Nevertheless, we note that our statement is formally incomparable to these works (since leveled FHE is not known to imply circular secure FHE or the hardness of LWE). We view this as evidence for the potential in our technique, which we hope can find additional applications in future works.

We show, via a non-interactive reduction, that the existence of a secure multi-party computation (MPC) protocol for degree-2 functions implies the existence of a protocol with the same round complexity for general functions. Thus showing that when considering the round complexity of MPC, it is sufficient to consider very simple functions.Our completeness theorem applies in various settings: information theoretic and computational, fully malicious and malicious with various types of aborts. In fact, we give a master theorem from which all individual settings follow as direct corollaries. Our basic transformation does not require any additional assumptions and incurs communication and computation blow-up which is polynomial in the number of players and in $$S,2^D$$S,2D, where S, D are the circuit size and depth of the function to be computed. Using one-way functions as an additional assumption, the exponential dependence on the depth can be removed.As a consequence, we are able to push the envelope on the state of the art in various settings of MPC, including the following cases. 3-round perfectly-secure protocol (with guaranteed output delivery) against an active adversary that corrupts less than 1/4 of the parties.2-round statistically-secure protocol that achieves security with “selective abort” against an active adversary that corrupts less than half of the parties.Assuming one-way functions, 2-round computationally-secure protocol that achieves security with (standard) abort against an active adversary that corrupts less than half of the parties. This gives a new and conceptually simpler proof to the recent result of Ananth et al. (Crypto 2018). Technically, our non-interactive reduction draws from the encoding method of Applebaum, Brakerski and Tsabary (TCC 2018). We extend these methods to ones that can be meaningfully analyzed even in the presence of malicious adversaries.

Attribute-based Encryption (ABE), first introduced by [SW05, GPSW06], is a public key encryption system that can support multiple users with varying decryption permissions. One of the main properties of such schemes is the supported function class of policies. While there are fully secure constructions from bilinear maps for a fairly large class of policies, the situation with lattice-based constructions is less satisfactory and many efforts were made to close this gap. Prior to this work the only known fully secure lattice construction was for the class of point functions (also known as IBE).In this work we construct for the first time a lattice-based (ciphertext-policy) ABE scheme for the function class t-CNF, which consists of CNF formulas where each clause depends on at most t bits of the input, for any constant t. This class includes NP-verification policies, bit-fixing policies and t-threshold policies. Towards this goal we also construct a fully secure single-key constrained PRF from OWF for the same function class, which might be of independent interest.

We show that any multi-party functionality can be evaluated using a two-round protocol with perfect correctness and perfect semi-honest security, provided that the majority of parties are honest. This settles the round complexity of information-theoretic semi-honest MPC, resolving a longstanding open question (cf. Ishai and Kushilevitz, FOCS 2000). The protocol is efficient for $${\mathrm {NC}}^1$$NC1 functionalities. Furthermore, given black-box access to a one-way function, the protocol can be made efficient for any polynomial functionality, at the cost of only guaranteeing computational security.Technically, we extend and relax the notion of randomized encoding to specifically address multi-party functionalities. The property of a multi-party randomized encoding (MPRE) is that if the functionality g is an encoding of the functionality f, then for any (permitted) coalition of players, their respective outputs and inputs in g allow them to simulate their respective inputs and outputs in f, without learning anything else, including the other outputs of f.