As the outputs of generative AI (GenAl) techniques improve in quality, it becomes increasingly challenging to distinguish them from human-created content. Watermarking schemes are a promising approach to address the problem of distinguishing between AI and human-generated content. These schemes embed hidden signals within AI -generated content to enable reliable detection. While watermarking is not a silver bullet for addressing all risks associated with GenAl, it can play a crucial role in enhancing AI safety and trustworthiness by combating misinformation and deception. This paper presents a comprehensive overview of water-marking techniques for GenAl, beginning with the need for watermarking from historical and regulatory perspectives. We formalize the definitions and desired properties of watermarking schemes and examine the key objectives and threat models for existing approaches. Practical evaluation strategies are also explored, providing insights into the development of robust watermarking techniques capable of resisting various attacks. Additionally, we review recent representative works, highlight open challenges, and discuss potential directions for this emerging field. By offering a thorough understanding of watermarking in GenAl, this work aims to guide researchers in advancing watermarking methods and applications, and support policymakers in addressing the broader implications of GenAl.

We propose hinTS — a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features:A silent setup process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys.Support for dynamic choice of thresholds and signers, after the silent setup, without further interaction.Support for general access policies; in particular, native support for weighted thresholds with zero additional overhead over standard threshold setting.Strong security guarantees, including proactive security and forward security.We prove the security of hinTS in the algebraic group model, and also provide an open-source implementation. Our scheme outperforms all prior proposals that avoid distributed key generation in terms of aggregation time, signature size, and verification time (as well as other qualitative measures). As an example, the aggregation time in hinTS for 1000 signers is under 0.5 seconds, while both signing and verification are constant time algorithms, taking 1 ms and 17.5 ms, respectively.The key technical contribution of our work involves the design of special-purpose succinct proofs to efficiently prove the well-formedness of aggregated public keys. Our solution uses public "hints" released by the signers as part of their public keys (hence the name hinTS).

We propose SublonK --- a new succinct non-interactive argument of knowledge (SNARK). SublonK is the first SNARK that achieves both a constant proof size and prover runtime that grows only with the size of the ``active part'' of the executed circuit (i.e., *sub-linear* in the size of the entire circuit) while being *black-box in cryptography*. For instance, consider circuits encoding conditional execution, where only a fraction of the circuit is exercised by the input. For such circuits, the prover runtime in SublonK grows only with the exercised execution path. Our new construction builds on PlonK [Gabizon-Williamson-Ciobotaru, EPRINT'19], a popular state-of-the-art practical zkSNARK, and preserves all its great features --- constant size proofs, constant time proof verification, a circuit-independent universal setup, and support for custom gates and lookup gates. Our techniques are useful for a wide range of applications that involve a circuit executing k steps, where at each step, a (possibly different) s-sized segment is executed from a choice of n segments. Our prover cost for such circuits is O(ks(log (ks) + log(n))). Finally, we show that our improvements are not purely asymptotic. Specifically, we demonstrate the concrete efficiency of SublonK using zkRollups as an example application. Based on our implementation, for parameter choices derived from rollup contracts on Ethereum, n =8, k = 128, s= 2^{16}, the SublonK prover is approximately 4.8x faster than the PlonK prover, and proofs in SublonK are 2.4KB and can be verified in under 50ms.

How can a model owner prove they trained their model according to the correct specification? More importantly, how can they do so while preserving the privacy of the underlying dataset and the final model? We study this problem and formulate the notion of zero-knowledge proof of training (zkPoT), which formalizes rigorous security guarantees that should be achieved by a privacy-preserving proof of training. While it is theoretically possible to design zkPoT for any model using generic zero-knowledge proof systems, this approach results in extremely unpractical proof generation times. Towards designing a practical solution, we propose the idea of combining techniques from MPC-in-the-head and zkSNARKs literature to strike an appropriate trade-off between proof size and proof computation time. We instantiate this idea and propose a concretely efficient, novel zkPoT protocol for logistic regression.

We introduce a new notion of multiverse threshold signatures (MTS). In an MTS scheme, multiple universes – each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold – can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe.We construct an MTS scheme building on BLS signatures. Our scheme is practical, and can be used to reduce bandwidth complexity and computational costs in decentralized oracle networks. As an example data point, consider a multiverse containing 2000 nodes and 100 universes (parameters inspired by Chainlink’s use in the wild), each of which contains arbitrarily large subsets of nodes and arbitrary thresholds. Each node computes and outputs 1 group element as its partial signature; the aggregator performs under 0.7 seconds of work for each aggregate signature, and the final signature of size 192 bytes takes 6.4 ms (or 198K EVM gas units) to verify. For this setting, prior approaches, when used to construct MTS, yield schemes that have one of the following drawbacks: (i) partial signatures that are 48× larger, (ii) have aggregation times 311× worse, or (iii) have signature size 39× and verification gas costs 3.38× larger. We also provide an open-source implementation and a detailed evaluation.

Abstract We propose a new approach to construct general-purpose indistinguishability obfuscation (iO). Our construction is obtained via a new intermediate primitive that we call split fully homomorphic encryption (split FHE), which we show to be sufficient for constructing iO. Specifically, split FHE is FHE where decryption takes the following two-step syntactic form: (i) a secret decryption step that uses the secret key and produces a hint which is (asymptotically) shorter than the length of the encrypted message, and (ii) a public decryption step that only requires the ciphertext and the previously generated hint (and not the entire secret key) and recovers the encrypted message. In terms of security, the hints for a set of ciphertexts should not allow one to violate semantic security for any other ciphertexts. Next, we show a generic candidate construction of split FHE based on three building blocks: (i) A standard FHE scheme with linear decrypt-and-multiply (which can be instantiated with essentially all LWE-based constructions), (ii) a linearly homomorphic encryption scheme with short decryption hints (such as the Damgård-Jurik encryption scheme, based on the DCR problem), and (iii) a cryptographic hash function (which can be based on a variety of standard assumptions). Our approach is heuristic in the sense that our construction is not provably secure and makes implicit assumptions about the interplay between these underlying primitives. We show evidence that this construction is secure by providing an argument in an appropriately defined oracle model. We view our construction as a big departure from the state-of-the-art constructions, and it is in fact quite simple.

We study the problem of constructing succinct zero knowledge proof systems for floating point computations. The standard approach to handle floating point computations requires conversion to binary circuits, following the IEEE-754 floating point standard. This approach incurs a poly(w) overhead in prover efficiency for computations with w-bit precision, resulting in very high prover runtimes -- already the key bottleneck in the design of succinct arguments. We make the following contributions: -We propose a new model for verifying floating point computations that guarantees approximate correctness w.r.t. a relative error bound. This model is inspired by numerical analysis, and is very meaningful for applications such as machine learning and scientific computing. -Using this model, we present a general method for constructing succinct zero-knowledge proofs for floating point computations starting from existing public-coin "commit-and-prove'' systems. For computations with w-bit precision, our approach incurs only a log(w) overhead in prover running time. Our compiler nearly preserves (up to a factor of 2) the communication complexity of the underlying protocol, and requires sub-linear verification time. The resulting proof can be made non-interactive in the random oracle model. Concretely, our scheme is ~57x faster than the method following IEEE standard exactly [35] for 32-bit floating point computations. Central to our main result, and of independent interest, is a new batch range proof system in standard prime order groups that does not rely on bit decomposition.

We construct indistinguishability obfuscation (iO) solely under circular-security properties of encryption schemes based on the Learning with Errors (LWE) problem. Circular-security assumptions were used before to construct (non-leveled) fully-homomorphic encryption (FHE), but our assumption is stronger and requires circular randomness-leakage-resilience. In contrast with prior works, this assumption can be conjectured to be post-quantum secure; yielding the first provably secure iO construction that is (plausibly) post-quantum secure. Our work follows the high-level outline of the recent work of Gay and Pass [STOC 2021], who showed a way to remove the heuristic step from the homomorphic-encryption based iO approach of Brakerski, Döttling, Garg, and Malavolta [EUROCRYPT 2020]. They thus obtain a construction proved secure under circular security assumption of natural homomorphic encryption schemes - specifically, they use homomorphic encryption schemes based on LWE and DCR, respectively. In this work we show how to remove the DCR assumption and remain with a scheme based on the circular security of LWE alone. Along the way we relax some of the requirements in the Gay-Pass blueprint and thus obtain a scheme that is secure under a different assumption. Specifically, we do not require security in the presence of a key-cycle, but rather only in the presence of a key-randomness cycle. An additional contribution of our work is to point out a problem in one of the building blocks used by many iO candidates, including all existing provable post-quantum candidates. Namely, in the transformation from exponentially-efficient iO (XiO) from Lin, Pass, Seth and Telang [PKC 2016]. We show why their transformation inherently falls short of achieving the desired goal, and then rectify this situation by showing that shallow XiO (i.e. one where the obfuscator is depth-bounded) does translate to iO using LWE.

Overparameterized models with millions of parameters have been hugely successful. In this work, we ask: can the need for large models be, at least in part, due to the \emph{computational} limitations of the learner? Additionally, we ask, is this situation exacerbated for \emph{robust} learning? We show that this indeed could be the case. We show learning tasks for which computationally bounded learners need \emph{significantly more} model parameters than what information-theoretic learners need. Furthermore, we show that even more model parameters could be necessary for robust learning. In particular, for computationally bounded learners, we extend the recent result of Bubeck and Sellke [NeurIPS'2021] which shows that robust models might need more parameters, to the computational regime and show that bounded learners could provably need an even larger number of parameters. Then, we address the following related question: can we hope to remedy the situation for robust computationally bounded learning by restricting \emph{adversaries} to also be computationally bounded for sake of obtaining models with fewer parameters? Here again, we show that this could be possible. Specifically, building on the work of Garg, Jha, Mahloujifar, and Mahmoody [ALT'2020], we demonstrate a learning task that can be learned efficiently and robustly against a computationally bounded attacker, while to be robust against an information-theoretic attacker requires the learner to utilize significantly more parameters.

We provide new two-round multiparty secure computation (MPC) protocols in the dishonest majority setting assuming the minimal assumption that two-round oblivious transfer (OT) exists. If the assumed two-round OT protocol is secure against semi-honest adversaries (in the plain model) then so is our two-round MPC protocol. Similarly, if the assumed two-round OT protocol is secure against malicious adversaries (in the common random/reference string model) then so is our two-round MPC protocol. Previously, two-round MPC protocols were only known under relatively stronger computational assumptions.

Privacy attacks on machine learning models aim to identify the data that is used to train such models. Such attacks, traditionally, are studied on static models that are trained once and are accessible by the adversary. Motivated to meet new legal requirements, many machine learning methods are recently extended to support machine unlearning, i.e., updating models as if certain examples are removed from their training sets, and meet new legal requirements. However, privacy attacks could potentially become more devastating in this new setting, since an attacker could now access both the original model before deletion and the new model after the deletion. In fact, the very act of deletion might make the deleted record more vulnerable to privacy attacks. Inspired by cryptographic definitions and the differential privacy framework, we formally study privacy implications of machine unlearning. We formalize (various forms of) deletion inference and deletion reconstruction attacks, in which the adversary aims to either identify which record is deleted or to reconstruct (perhaps part of) the deleted records. We then present successful deletion inference and reconstruction attacks for a variety of machine learning models and tasks such as classification, regression, and language models. Finally, we show that our attacks would provably be precluded if the schemes satisfy (variants of) deletion compliance (Garg, Goldwasser, and Vasudevan, Eurocrypt’20).

Poisoning attacks have emerged as a significant security threat to machine learning algorithms. It has been demonstrated that adversaries who make small changes to the training set, such as adding specially crafted data points, can hurt the performance of the output model. Most of these attacks require the full knowledge of training data. This leaves open the possibility of achieving the same attack results using poisoning attacks that do not have the full knowledge of the clean training set.In this work, we initiate a theoretical study of the problem above. Specifically, for the case of feature selection with LASSO, we show that \emph{full information} adversaries (that craft poisoning examples based on the rest of the training data) are provably much more devastating compared to the optimal attacker that is \emph{oblivious} to the training set yet has access to the distribution of the data. Our separation result shows that the two settings of data-aware and data-oblivious are fundamentally different and we cannot hope to achieve the same attack or defense results in these scenarios.

A private machine learning algorithm hides as much as possible about its training data while still preserving accuracy. In this work, we study whether a non-private learning algorithm can be made private by relying on an instance-encoding mechanism that modifies the training inputs before feeding them to a normal learner. We formalize both the notion of instance encoding and its privacy by providing two attack models. We first prove impossibility results for achieving a (stronger) model. Next, we demonstrate practical attacks in the second (weaker) attack model on InstaHide, a recent proposal by Huang, Song, Li and Arora [ICML’20] that aims to use instance encoding for privacy.

We provide the first constructions of identity-based encryption and hierarchical identity-based encryption based on the hardness of the (Computational) Diffie-Hellman Problem (without use of groups with pairings) or Factoring. Our construction achieves the standard notion of identity-based encryption as considered by Boneh and Franklin [CRYPTO 2001]. We bypass known impossibility results using garbled circuits that make a non-black-box use of the underlying cryptographic primitives.

Over recent years, devising classification algorithms that are robust to adversarial perturbations has emerged as a challenging problem. In particular, deep neural nets (DNNs) seem to be susceptible to small imperceptible changes over test instances. However, the line of work in provable robustness, so far, has been focused on information theoretic robustness, ruling out even the existence of any adversarial examples. In this work, we study whether there is a hope to benefit from algorithmic nature of an attacker that searches for adversarial examples, and ask whether there is any learning task for which it is possible to design classifiers that are only robust against polynomial-time adversaries. Indeed, numerous cryptographic tasks (e.g. encryption of long messages) can only be secure against computationally bounded adversaries, and are indeed impossible for computationally unbounded attackers. Thus, it is natural to ask if the same strategy could help robust learning. We show that computational limitation of attackers can indeed be useful in robust learning by demonstrating the possibility of a classifier for some learning task for which computational and information theoretic adversaries of bounded perturbations have very different power. Namely, while computationally unbounded adversaries can attack successfully and find adversarial examples with small perturbation, polynomial time adversaries are unable to do so unless they can break standard cryptographic hardness assumptions. Our results, therefore, indicate that perhaps a similar approach to cryptography (relying on computational hardness) holds promise for achieving computationally robust machine learning. On the reverse directions, we also show that the existence of such learning task in which computational robustness beats information theoretic robustness requires computational hardness by implying (average-case) hardness of NP.

Consider sources that supply sensitive data to an aggregator. Standard encryption only hides the data from eavesdroppers, but using specialized encryption one can hope to hide the data (to the extent possible) from the aggregator itself. For flexibility and security, we envision schemes that allow sources to supply encrypted data, such that at any point a dynamically-chosen subset of sources can allow an agreed-upon joint function of their data to be computed by the aggregator. A primitive called multi-input functional encryption (MIFE), due to Goldwasser et al. (EUROCRYPT 2014), comes close, but has two main limitations: - it requires trust in a third party, who is able to decrypt all the data, and - it requires function arity to be fixed at setup time and to be equal to the number of parties. To drop these limitations, we introduce a new notion of ad hoc MIFE. In our setting, each source generates its own public key and issues individual, function-specific secret keys to an aggregator. For successful decryption, an aggregator must obtain a separate key from each source whose ciphertext is being computed upon. The aggregator could obtain multiple such secret-keys from a user corresponding to functions of varying arity. For this primitive, we obtain the following results: - We show that standard MIFE for general functions can be bootstrapped to ad hoc MIFE for free, i.e. without making any additional assumption. - We provide a direct construction of ad hoc MIFE for the inner product functionality based on the Learning with Errors (LWE) assumption. This yields the first construction of this natural primitive based on a standard assumption. At a technical level, our results are obtained by combining standard MIFE schemes and two-round secure multiparty computation (MPC) protocols in novel ways highlighting an interesting interplay between MIFE and two-round MPC.

We consider the question of minimizing the round complexity of protocols for secure multiparty computation (MPC) with security against an arbitrary number of semi-honest parties. Very recently, Garg and Srinivasan (Eurocrypt 2018) and Benhamouda and Lin (Eurocrypt 2018) constructed such 2-round MPC protocols from minimal assumptions. This was done by showing a round preserving reduction to the task of secure 2-party computation of the oblivious transfer functionality (OT). These constructions made a novel non-black-box use of the underlying OT protocol. The question remained whether this can be done by only making black-box use of 2-round OT. This is of theoretical and potentially also practical value as black-box use of primitives tends to lead to more efficient constructions. Our main result proves that such a black-box construction is impossible, namely that non-black-box use of OT is necessary. As a corollary, a similar separation holds when starting with any 2-party functionality other than OT. As a secondary contribution, we prove several additional results that further clarify the landscape of black-box MPC with minimal interaction. In particular, we complement the separation from 2-party functionalities by presenting a complete 4-party functionality, give evidence for the difficulty of ruling out a complete 3-party functionality and for the difficulty of ruling out black-box constructions of 3-round MPC from 2-round OT, and separate a relaxed "non-compact" variant of 2-party homomorphic secret sharing from 2-round OT.

In a Conditional Disclosure of Secrets (CDS) a verifier V wants to reveal a message m to a prover P conditioned on the fact that x is an accepting instance of some NP-language L. An honest prover (holding the corresponding witness w) always obtains the message m at the end of the interaction. On the other hand, if x ∉ L we require that no PPT P* can learn the message m. We introduce laconic CDS, a two round CDS protocol with optimal computational cost for the verifier V and optimal communication cost. More specifically, the verifier's computation and overall communication grows with poly(|x|; λ; log(T)), where λ is the security parameter and T is the verification time for checking that x ϵ L (given w). We obtain constructions of laconic CDS under standard assumptions, such as CDH or LWE. Laconic CDS serves as a powerful tool for maliciousifying semi-honest protocols while preserving their computational and communication complexities. To substantiate this claim, we consider the setting of non-interactive secure computation: Alice wants to publish a short digest corresponding to a private large input x on her web page such that (possibly many) Bob, with a private input y, can send a short message to Alice allowing her to learn C(x; y) (where C is a public circuit). The protocol must be reusable in the sense that Bob can engage in arbitrarily many executions on the same digest. In this context we obtain the following new implications. 1) UC Secure Bob-optimized 2PC: We obtain a UC secure protocol where Bob's computational cost and the communication cost of the protocol grows with poly(|x|; |y|; λ; d), where d is the depth of the computed circuit C. 2) Malicious Laconic Function Evaluation: Next, we move on to the setting where Alice's input x is large. For this case, UC secure protocols must have communication cost growing with |x|. Thus, with the goal of achieving better efficiency, we consider a weaker notion of malicious security. For this setting, we obtain a protocol for which Bob's computational cost and the communication cost of the protocol grows with poly(|y|; λ; d), where d is the depth of the computed circuit C.

We show how to construct indistinguishability obfuscation (\bf iO) for RAM programs with bounded space, assuming \bf iO for circuits and one-way functions, both with subexponential security. That is, given a RAM program whose computation requires space $s(n)$ in the worst case for inputs of length at most $n$, we generate an obfuscated RAM program that, for inputs of size at most $n$, runs in roughly the same time as the original program, using space roughly $s(n)$. The obfuscation process is quasi-linear in the description length of the input program and $s(n)$. At the heart of our construction are succinct randomized encodings for RAM programs. We present two very different constructions of such encodings, each with its own unique properties. Beyond their use as a tool in obfuscation for RAM programs, we show that succinct randomized encodings are interesting objects in their own right. We demonstrate the power of succinct randomized encodings in applications such as publicly verifiable delegation, functional encryption for RAMs, and key-dependent security amplification.

In this paper, we initiate the study of garbled protocols - a generalization of Yao's garbled circuits construction to distributed protocols. More specifically, in a garbled protocol construction, each party can independently generate a garbled protocol component along with pairs of input labels. Additionally, it generates an encoding of its input. The evaluation procedure takes as input the set of all garbled protocol components and the labels corresponding to the input encodings of all parties and outputs the entire transcript of the distributed protocol. We provide constructions for garbling arbitrary protocols based on standard computational assumptions on bilinear maps (in the common random string model). Next, using garbled protocols we obtain a general compiler that compresses any arbitrary round multiparty secure computation protocol into a two-round UC secure protocol. Previously, two-round multiparty secure computation protocols were only known assuming witness encryption or learning-with errors. Benefiting from our generic approach we also obtain protocols (i) for the setting of random access machines (RAM programs) while keeping communication and computational costs proportional to running times, while (ii) making only a black-box use of the underlying group, eliminating the need for any expensive non-black-box group operations. Our results are obtained by a simple but powerful extension of the non-interactive zero-knowledge proof system of Groth, Ostrovsky and Sahai [Journal of ACM, 2012].

Annihilation attacks, introduced in the work of Miles, Sahai, and Zhandry (CRYPTO 2016), are a class of polynomial-time attacks against several candidate indistinguishability obfuscation (IO) schemes, built from Garg, Gentry, and Halevi (EUROCRYPT 2013) multilinear maps. In this work, we provide a general efficiently-testable property for two single-input branching programs, called partial inequivalence, which we show is sufficient for our variant of annihilation attacks on several obfuscation constructions based on GGH13 multilinear maps. We give examples of pairs of natural NC1 circuits, which - when processed via Barrington's Theorem - yield pairs of branching programs that are partially inequivalent. As a consequence we are also able to show examples of "bootstrapping circuits,'' (albeit somewhat artificially crafted) used to obtain obfuscations for all circuits (given an obfuscator for NC1 circuits), in certain settings also yield partially inequivalent branching programs. Prior to our work, no attacks on any obfuscation constructions for these settings were known.

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits $C_0$ and $C_1$ of similar size, the obfuscations of $C_0$ and $C_1$ should be computationally indistinguishable. In functional encryption, ciphertexts encrypt inputs $x$ and keys are issued for circuits $C$. Using the key $\mathrm{SK}_C$ to decrypt a ciphertext $\mathrm{CT}_x={\sf Enc}(x)$ yields the value $C(x)$ but does not reveal anything else about $x$. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: (1) We describe a candidate construction for indistinguishability obfuscation for $\mathbf{NC}^1$ circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call multilinear jigsaw puzzles. (2) We show how to use indistinguishability obfuscation for $\mathbf{NC}^1$ together with fully homomorphic encryption (with decryption in $\mathbf{NC}^1$) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and noninteractive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct ciphertexts, which enables several other applications.

Garbled RAM, introduced by Lu and Ostrovsky, enables the task of garbling a RAM (Random Access Machine) program directly, there by avoiding the inefficient process of first converting it into a circuit. Garbled RAM can be seen as a RAM analogue of Yao's garbled circuit construction, except that known realizations of Garbled RAM make non-black-box use of the underlying cryptographic primitives. In this paper we remove this limitation and provide the first black-box construction of Garbled RAM with polylogarithmic overhead. Our scheme allows for garbling multiple RAM programs being executed on a persistent database and its security is based only on the existence of one-way functions. We also obtain the first secure RAM computation protocol that is both constant round and makes only black-box use of one-way functions in the Oblivious Transfer hybrid model.

A randomized encoding allows to express a "complex" computation, given by a function f and input x, by a "simple to compute" randomized representation f(x) whose distribution encodes f(x), while revealing nothing else regarding f and x. Existing randomized encodings, geared mostly to allow encoding with low parallel-complexity, have proven instrumental in various strong applications such as multiparty computation and parallel cryptography. This work focuses on another natural complexity measure: the time required to encode. We construct succinct randomized encodings where the time to encode a computation, given by a program Π and input x, is essentially independent of Π's time complexity, and only depends on its space complexity, as well as the size of its input, output, and description. The scheme guarantees computational privacy of (Π,x), and is based on indistinguishability obfuscation for a relatively simple circuit class, for which there exist instantiations based on polynomial hardness assumptions on multi-linear maps.

Yao's garbled circuit construction is a very fundamental result in cryptography and recent efficiency optimizations have brought it much closer to practice. However these constructions work only for circuits and garbling a RAM program involves the inefficient process of first converting it into a circuit. Towards the goal of avoiding this inefficiency, Lu and Ostrovsky (Eurocrypt 2013) introduced the notion of "garbled RAM" as a method to garble RAM programs directly. It can be seen as a RAM analogue of Yao's garbled circuits such that, the size of the garbled program and the time it takes to create and evaluate it, is proportional only to the running time on the RAM program rather than its circuit size. Known realizations of this primitive, either need to rely on strong computational assumptions or do not achieve the aforementioned efficiency (Gentry, Halevi, Lu, Ostrovsky, Raykova and Wichs, EUROCRYPT 2014). In this paper we provide the first construction with strictly poly-logarithmic overhead in both space and time based only on the minimal assumption that one-way functions exist. Our scheme allows for garbling multiple programs being executed on a persistent database, and has the additional feature that the program garbling is decoupled from the database garbling. This allows a client to provide multiple garbled programs to the server as part of a pre-processing phase and then later determine the order and the inputs on which these programs are to be executed, doing work independent of the running times of the programs itself.

In this work, we study indistinguishability obfuscation and functional encryption for general circuits: Indistinguishability obfuscation requires that given any two equivalent circuits C0and C1of similar size, the obfuscations of C0and C1should be computationally indistinguishable. In functional encryption, cipher texts encrypt inputs x and keys are issued for circuits C. Using the key SKCto decrypt a cipher text CTx= Enc(x), yields the value C(x) but does not reveal anything else about x. Furthermore, no collusion of secret key holders should be able to learn anything more than the union of what they can each learn individually. We give constructions for indistinguishability obfuscation and functional encryption that supports all polynomial-size circuits. We accomplish this goal in three steps: - (1) We describe a candidate construction for indistinguishability obfuscation for NC1circuits. The security of this construction is based on a new algebraic hardness assumption. The candidate and assumption use a simplified variant of multilinear maps, which we call Multilinear Jigsaw Puzzles. (2) We show how to use indistinguishability obfuscation for NC1together with Fully Homomorphic Encryption (with decryption in NC1) to achieve indistinguishability obfuscation for all circuits. (3) Finally, we show how to use indistinguishability obfuscation for circuits, public-key encryption, and non-interactive zero knowledge to achieve functional encryption for all circuits. The functional encryption scheme we construct also enjoys succinct cipher texts, which enables several other applications.

We put forth the concept of witness encryption. A witness encryption scheme is defined for an NP language L (with corresponding witness relation R). In such a scheme, a user can encrypt a message M to a particular problem instance x to produce a ciphertext. A recipient of a ciphertext is able to decrypt the message if x is in the language and the recipient knows a witness w where R(x,w) holds. However, if x is not in the language, then no polynomial-time attacker can distinguish between encryptions of any two equal length messages. We emphasize that the encrypter himself may have no idea whether $x$ is actually in the language. Our contributions in this paper are threefold. First, we introduce and formally define witness encryption. Second, we show how to build several cryptographic primitives from witness encryption. Finally, we give a candidate construction based on the NP-complete Exact Cover problem and Garg, Gentry, and Halevi's recent construction of "approximate" multilinear maps.

In [8,9] Boneh et al. presented the first fully collusion-resistant traitor tracing and trace & revoke schemes. These schemes are based on composite order bilinear groups and their security depends on the hardness of the subgroup decision assumption.

It is easier to detect a DDoS attack near the victim but it is of little use to do so. Many researchers believe that it would be best to handle DDoS attacks closer to the computers which host these attacks and have propounded various strategies for packet filtering at edge-routers. This paper makes three contributions over earlier work. First, we propose that it is best to track illegitimate packets suspected to cause a DDoS at the source computer itself. Secondly, we come up with a secure and efficient implementation (ADVOS: Anti-DDoS Virtualized Operating System) for packet filtering at the source computer itself. Security dependency on the integrity of the source operating system is removed by using virtualization to isolate the modules providing the protection capabilities. Different models of traffic characterization could possibly be used in curtailing malicious traffic, we justify the effectiveness of symmetry based model at source computers. Thirdly, we demonstrate that such an anti-DDoS operating system using virtualization can be implemented practically and efficiently. In our prototype over native Linux system 2.4% overhead was observed in the attained network throughput. Less than 1% of the total attack traffic generated was allowed to pass through on attack. Finally, we discuss the scalability and deployment issues for ADVOS.