In this work, we introduce and construct D-restricted Functional Encryption (FE) for any constant $$D \ge 3$$D≥3, based only on the SXDH assumption over bilinear groups. This generalizes the notion of 3-restricted FE recently introduced and constructed by Ananth et al. (ePrint 2018) in the generic bilinear group model.A $$D=(d+2)$$D=(d+2)-restricted FE scheme is a secret key FE scheme that allows an encryptor to efficiently encrypt a message of the form $$M=(\varvec{x},\varvec{y},\varvec{z})$$M=(x,y,z). Here, $$\varvec{x}\in \mathbb {F}_{\mathbf {p}}^{d\times n}$$x∈Fpd×n and $$\varvec{y},\varvec{z}\in \mathbb {F}_{\mathbf {p}}^n$$y,z∈Fpn. Function keys can be issued for a function $$f=\varSigma _{\varvec{I}= (i_1,..,i_d,j,k)}\ c_{\varvec{I}}\cdot \varvec{x}[1,i_1] \cdots \varvec{x}[d,i_d] \cdot \varvec{y}[j]\cdot \varvec{z}[k]$$f=ΣI=(i1,..,id,j,k)cI·x[1,i1]⋯x[d,id]·y[j]·z[k] where the coefficients $$c_{\varvec{I}}\in \mathbb {F}_{\mathbf {p}}$$cI∈Fp. Knowing the function key and the ciphertext, one can learn $$f(\varvec{x},\varvec{y},\varvec{z})$$f(x,y,z), if this value is bounded in absolute value by some polynomial in the security parameter and n. The security requirement is that the ciphertext hides $$\varvec{y}$$y and $$\varvec{z}$$z, although it is not required to hide $$\varvec{x}$$x. Thus $$\varvec{x}$$x can be seen as a public attribute.D-restricted FE allows for useful evaluation of constant-degree polynomials, while only requiring the SXDH assumption over bilinear groups. As such, it is a powerful tool for leveraging hardness that exists in constant-degree expanding families of polynomials over $$\mathbb {R}$$R. In particular, we build upon the work of Ananth et al. to show how to build indistinguishability obfuscation ($$i\mathcal {O}$$iO) assuming only SXDH over bilinear groups, LWE, and assumptions relating to weak pseudorandom properties of constant-degree expanding polynomials over $$\mathbb {R}$$R.

We construct efficient non-malleable codes (NMC) that are (computationally) secure against tampering by functions computable in any fixed polynomial time. Our construction is in the plain (no-CRS) model and requires the assumptions that (1) $$\mathbf {E}$$E is hard for $$\mathbf {NP}$$NP circuits of some exponential $$2^{\beta n}$$2βn ($$\beta >0$$β>0) size (widely used in the derandomization literature), (2) sub-exponential trapdoor permutations exist, and (3) $$\mathbf {P}$$P-certificates with sub-exponential soundness exist.While it is impossible to construct NMC secure against arbitrary polynomial-time tampering (Dziembowski, Pietrzak, Wichs, ICS ’10), the existence of NMC secure against $$O(n^c)$$O(nc)-time tampering functions (for any fixedc), was shown (Cheraghchi and Guruswami, ITCS ’14) via a probabilistic construction. An explicit construction was given (Faust, Mukherjee, Venturi, Wichs, Eurocrypt ’14) assuming an untamperable CRS with length longer than the runtime of the tampering function. In this work, we show that under computational assumptions, we can bypass these limitations. Specifically, under the assumptions listed above, we obtain non-malleable codes in the plain model against $$O(n^c)$$O(nc)-time tampering functions (for any fixed c), with codeword length independent of the tampering time bound.Our new construction of NMC draws a connection with non-interactive non-malleable commitments. In fact, we show that in the NMC setting, it suffices to have a much weaker notion called quasi non-malleable commitments—these are non-interactive, non-malleable commitments in the plain model, in which the adversary runs in $$O(n^c)$$O(nc)-time, whereas the honest parties may run in longer (polynomial) time. We then construct a 4-tag quasi non-malleable commitment from any sub-exponential OWF and the assumption that $$\mathbf {E}$$E is hard for some exponential size $$\mathbf {NP}$$NP-circuits, and use tag amplification techniques to support an exponential number of tags.

The existence of secure indistinguishability obfuscators ( $$i\mathcal {O}$$ ) has far-reaching implications, significantly expanding the scope of problems amenable to cryptographic study. All known approaches to constructing $$i\mathcal {O}$$ rely on d-linear maps. While secure bilinear maps are well established in cryptographic literature, the security of candidates for $$d>2$$ is poorly understood.We propose a new approach to constructing $$i\mathcal {O}$$ for general circuits. Unlike all previously known realizations of $$i\mathcal {O}$$ , we avoid the use of d-linear maps of degree $$d \ge 3$$ .At the heart of our approach is the assumption that a new weak pseudorandom object exists. We consider two related variants of these objects, which we call perturbation resilient generator ( $$\varDelta $$ RG) and pseudo flawed-smudging generator ( $$\mathrm {PFG}$$ ), respectively. At a high level, both objects are polynomially expanding functions whose outputs partially hide (or smudge) small noise vectors when added to them. We further require that they are computable by a family of degree-3 polynomials over $$\mathbb {Z}$$ . We show how they can be used to construct functional encryption schemes with weak security guarantees. Finally, we use novel amplification techniques to obtain full security.As a result, we obtain $$i\mathcal {O}$$ for general circuits assuming:Subexponentially secure LWEBilinear Maps $$\mathrm {poly}(\lambda )$$ -secure 3-block-local PRGs $$\varDelta $$ RGs or $$\mathrm {PFG}$$ s

We present the first two-round multiparty computation (MPC) protocols secure against malicious adaptive corruption in the common reference string (CRS) model, based on DDH, LWE, or QR. Prior two-round adaptively secure protocols were known only in the two-party setting against semi-honest adversaries, or in the general multiparty setting assuming the existence of indistinguishability obfuscation (iO).Our protocols are constructed in two steps. First, we construct two-round oblivious transfer (OT) protocols secure against malicious adaptive corruption in the CRS model based on DDH, LWE, or QR. We achieve this by generically transforming any two-round OT that is only secure against static corruption but has certain oblivious sampleability properties, into a two-round adaptively secure OT. Prior constructions were only secure against semi-honest adversaries or based on iO.Second, building upon recent constructions of two-round MPC from two-round OT in the weaker static corruption setting [Garg and Srinivasan, Benhamouda and Lin, Eurocrypt’18] and using equivocal garbled circuits from [Canetti, Poburinnaya and Venkitasubramaniam, STOC’17], we show how to construct two-round adaptively secure MPC from two-round adaptively secure OT and constant-round adaptively secure MPC, with respect to both malicious and semi-honest adversaries. As a corollary, we also obtain the first 2-round MPC secure against semi-honest adaptive corruption in the plain model based on augmented non-committing encryption (NCE), which can be based on a variety of assumptions, CDH, RSA, DDH, LWE, or factoring Blum integers. Finally, we mention that our OT and MPC protocols in the CRS model are, in fact, adaptively secure in the Universal Composability framework.

We introduce a new notion of one-message zero-knowledge (1ZK) arguments that satisfy a weak soundness guarantee—the number of false statements that a polynomial-time non-uniform adversary can convince the verifier to accept is not much larger than the size of its non-uniform advice. The zero-knowledge guarantee is given by a simulator that runs in (mildly) super-polynomial time. We construct such 1ZK arguments based on the notion of multi-collision-resistant keyless hash functions, recently introduced by Bitansky, Kalai, and Paneth (STOC 2018). Relying on the constructed 1ZK arguments, subexponentially-secure time-lock puzzles, and other standard assumptions, we construct one-message fully-concurrent non-malleable commitments. This is the first construction that is based on assumptions that do not already incorporate non-malleability, as well as the first based on (subexponentially) falsifiable assumptions.