Abstract. We present a key-policy attribute-based encryption (ABE) scheme for circuits based on the Learning with Errors (LWE) assumption, whose key size is independent of the circuit depth. Our result constitutes the first improvement for ABE for circuits from LWE in almost a decade, given by Gorbunov, Vaikuntanathan, and Wee ( Attribute-based encryption for circuits, 2013) and Boneh et al. ( Fully key-homomorphic encryption, arithmetic circuit ABE and compact garbled circuits, 2014): We reduce the key size in the latter from [Formula: see text] to [Formula: see text]. The starting point of our construction is a recent ABE scheme of Li, Lin, and Luo ( ABE for circuits with constant-size secret keys and adaptive security, 2022) which achieves [Formula: see text] key size but requires pairings and generic bilinear groups in addition to LWE; we introduce new lattice techniques to eliminate the additional requirements.

We present a key-policy attribute-based encryption (ABE) scheme for circuits based on the Learning With Errors (LWE) assumption whose key size is independent of the circuit depth. Our result constitutes the first improvement for ABE for circuits from LWE in almost a decade, given by Gorbunov, Vaikuntanathan, and Wee (STOC 2013) and Boneh, et al. (EUROCRYPT 2014) – we reduce the key size in the latter from poly(depth $,\lambda)$ to poly $(\lambda)$. The starting point of our construction is a recent ABE scheme of Li, Lin, and Luo (TCC 2022), which achieves poly $(\lambda)$ key size but requires pairings and generic bilinear groups in addition to LWE; we introduce new lattice techniques to eliminate the additional requirements.

Attribute-based encryption (ABE) enables fine-grained access control on encrypted data and has a large number of practical applications. This paper presents FABEO: faster pairing-based ciphertext-policy and key-policy ABE schemes that support expressive policies and put no restriction on policy type or attributes, and the first to achieve optimal, adaptive security with multiple challenge ciphertexts. We implement our schemes and demonstrate that they perform better than the state-of-the-art (Bethencourt et al. S&P 2007, Agrawal et al., CCS 2017 and Ambrona et al., CCS 2017) on all parameters of practical interest.

Vector commitments enable a user to commit to a sequence of values and provably reveal one or many values at specific posi- tions at a later time. In this work, we construct Pointproofs? a new vector commitment scheme that supports non-interactive aggregation of proofs across multiple commitments. Our construction enables any third party to aggregate a collection of proofs with respect to different, independently computed commitments into a single proof represented by an elliptic curve point of 48-bytes. In addition, our scheme is hiding: a commitment and proofs for some values reveal no information about the remaining values. We build Pointproofs and demonstrate how to apply them to blockchain smart contracts. In our example application, Pointproofs reduce bandwidth overheads for propagating a block of transactions by at least 60% compared to prior state- of-art vector commitments. Pointproofs are also efficient: on a single-thread, it takes 0.08 seconds to generate a proof for 8 values with respect to one commitment, 0.25 seconds to aggregate 4000 such proofs across multiple commitments into one proof, and 23 seconds (0.7 ms per value proven) to verify the aggregated proof.

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 xA, xBin which Alice learns the output f(xA, xB) 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 xA. 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(x1, ..., xN) 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.

Motivated by cryptographic applications such as predicate encryption, we consider the problem of representing an arbitrary predicate as the inner product predicate on two vectors. Concretely, fix a Boolean function P and some modulus q. We are interested in encoding x to x_vector and y to y_vector so that P(x,y) = 1 <=> = 0 mod q, where the vectors should be as short as possible. This problem can also be viewed as a generalization of matching vector families, which corresponds to the equality predicate. Matching vector families have been used in the constructions of Ramsey graphs, private information retrieval (PIR) protocols, and more recently, secret sharing. Our main result is a simple lower bound that allows us to show that known encodings for many predicates considered in the cryptographic literature such as greater than and threshold are essentially optimal for prime modulus q. Using this approach, we also prove lower bounds on encodings for composite q, and then show tight upper bounds for such predicates as greater than, index and disjointness.

Attribute-based encryption (ABE) is a cryptographic primitive which supports fine-grained access control on encrypted data, making it an appealing building block for many applications. In this paper, we propose, implement, and evaluate fully automated methods for proving security of ABE in the Generic Bilinear Group Model (Boneh, Boyen, and Goh, 2005, Boyen, 2008), an idealized model which admits simpler and more efficient constructions, and can also be used to find attacks. Our method is applicable to Rational-Fraction Induced ABE, a large class of ABE that contains most of the schemes from the literature, and relies on a Master Theorem, which reduces security in the GGM to a (new) notion of symbolic security, which is amenable to automated verification using constraint-based techniques. We relate our notion of symbolic security for Rational-Fraction Induced ABE to prior notions for Pair Encodings. Finally, we present several applications, including automated proofs for new schemes.

We present the OPTLS key-exchange protocol, its design, rationale and cryptographic analysis. OPTLS design has been motivated by the ongoing work in the TLS working group of the IETF for specifying TLS 1.3, the next-generation TLS protocol. The latter effort is intended to revamp the security of TLS that has been shown inadequate in many instances as well as to add new security and functional features. The main additions that influence the cryptographic design of TLS 1.3 (hence also of OPTLS) are a new "0-RTT requirement" (0-RTT stands for "zero round trip time") to allow clients that have previously retrieved or cached the public key of the server to send protected data already in the first flow of the protocol, making perfect forward secrecy (PFS) a mandatory requirement, and moving to elliptic curves as the main cryptographic basis for the protocol (for performance and security reasons). Accommodating these requirements calls for moving away from the RSA-centric design of TLS in favor of a protocol based on Diffie-Hellman techniques. OPTLS offers a simple design framework that supports all the above requirements from the protocol with a uniform and modular logic that helps in the specification, analysis, performance optimization, and future maintenance of the protocol. The current (draft) specification of TLS 1.3 builds upon the OPTLS framework as a basis for the cryptographic core of the handshake protocol adapting the different modes of OPTLS to the TLS 1.3 context.

We show how to securely obfuscate conjunctions, which are functions f(x1,...,xn) = ∧i∈I yi where I ⊆ [n] and each literal yi is either just xi or ¬ xi e.g., f(xi,...,x_n) = xi ⊆ ¬ x3 ⊆ ¬ x7 ... ⊆ x{n-1. Whereas prior work of Brakerski and Rothblum (CRYPTO 2013) showed how to achieve this using a non-standard object called cryptographic multilinear maps, our scheme is based on an "entropic" variant of the Ring Learning with Errors (Ring LWE) assumption. As our core tool, we prove that hardness assumptions on the recent multilinear map construction of Gentry, Gorbunov and Halevi (TCC 2015) can be established based on entropic Ring LWE. We view this as a first step towards proving the security of additional mutlilinear map based constructions, and in particular program obfuscators, under standard assumptions.

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an ℓ-bit public index ind and a message m , and a secret key is associated with a Boolean predicate P . The secret key allows decrypting the ciphertext and learning m if and only if P (ind) = 1. Moreover, the scheme should be secure against collusions of users, namely, given secret keys for polynomially many predicates, an adversary learns nothing about the message if none of the secret keys can individually decrypt the ciphertext. We present attribute-based encryption schemes for circuits of any arbitrary polynomial size, where the public parameters and the ciphertext grow linearly with the depth of the circuit. Our construction is secure under the standard learning with errors (LWE) assumption. Previous constructions of attribute-based encryption were for Boolean formulas, captured by the complexity class NC 1 . In the course of our construction, we present a new framework for constructing ABE schemes. As a by-product of our framework, we obtain ABE schemes for polynomial-size branching programs, corresponding to the complexity class LOGSPACE , under quantitatively better assumptions.

In an attribute-based encryption (ABE) scheme, a ciphertext is associated with an l-bit public index pind and a message m, and a secret key is associated with a Boolean predicate P. The secret key allows to decrypt the ciphertext and learn m iff P(pind) = 1. Moreover, the scheme should be secure against collusions of users, namely, given secret keys for polynomially many predicates, an adversary learns nothing about the message if none of the secret keys can individually decrypt the ciphertext.

We present round-efficient protocols for secure multi-party computation with a dishonest majority that rely on black-box access to the underlying primitives. Our main contributions are as follows: · a O(log* n)-round protocol that relies on black-box access to dense cryptosystems, homomorphic encryption schemes, or lossy encryption schemes. This improves upon the recent O(1)log* n-round protocol of Lin, Pass and Venkitasubramaniam (STOC 2009) that relies on non-black-box access to a smaller class of primitives. · a O(1)-round protocol requiring in addition, black-box access to a one-way function with sub-exponential hardness, improving upon the recent work of Pass and Wee (Eurocrypt 2010). These are the first black-box constructions for secure computation with sublinear round complexity. Our constructions build on and improve upon the work of Lin and Pass (STOC 2009) on nonmalleability amplification, as well as that of Ishai et al. (STOC 2006) on black-box secure computation. In addition to the results on secure computation, we also obtain a simple construction of a 0(log* n)-round non-malleable commitment scheme based on one-way functions, improving upon the recent O(1)log* n-round protocol of Lin and Pass (STOC 2009). Our construction uses a novel transformation for handling arbitrary man-in-the-middle scheduling strategies which improves upon a previous construction of Barak (FOCS 2002).

We put forth a new computational notion of entropy, which measures the (in)feasibility of sampling high entropy strings that are consistent with a given protocol. Specifically, we say that the i'th round of a protocol (A,B) has *accessible entropy* at most k, if no polynomial-time strategy A* can generate messages for A such that the entropy of its message in the i'th round has entropy greater than k when conditioned both on prior messages of the protocol and on prior coin tosses of A*. We say that the protocol has *inaccessible entropy* if the total accessible entropy (summed over the rounds) is noticeably smaller than the real entropy of A's messages, conditioned only on prior messages (but not the coin tosses of A). As applications of this notion, we -- Give a much simpler and more efficient construction of statistically hiding commitment schemes from arbitrary one-way functions. -- Prove that constant-round statistically hiding commitments are necessary for constructing constant-round zero-knowledge proof systems for NP that remain secure under parallel composition (assuming the existence of one-way functions).

We continue the study of noncommutative polynomial identity testing initiated by Raz and Shpilka and present efficient algorithms for the following problems in the noncommutative model: polynomial identity testing: The algorithm gets as an input an arithmetic circuit with the promise that the polynomial it computes has small degree (for instance, a circuit of logarithmic depth or an arithmetic formula) and determines whether or not the output of the circuit is identically zero (as a formal expression). Unlike the algorithm by Raz and Shpilka, our algorithm is black-box (but randomized with one-sided error) and evaluates the circuit over the ring of matrices. In addition, we present query complexity lower bounds for identity testing and explore the possibility of de-randomizing our algorithm. The analysis of our algorithm uses a noncommutative variant of the Schwartz-Zippel test. Minimizing algebraic branching programs: The algorithm gets as an input an algebraic branching program (ABP) and outputs a smallest equivalent ABP. The algorithm is based on Nisan's characterization of ABP complexity, and uses as a sub-routine an algorithm for computing linear dependencies amongst arithmetic formulas, a problem previously studied by the authors.

We investigate the possibility of obfuscating point functions in the framework of Barak et al. from Crypto '01. A point function is a Boolean function that assumes the value 1 at exactly one point. Our main results are as follows:We provide a simple construction of efficient obfuscators for point functions for a slightly relaxed notion of obfuscation, for which obfuscating general circuits is nonetheless impossible. Our construction relies on the existence of a very strong one-way permutation, and yields the first non-trivial obfuscator under general assumptions in the standard model. We also obtain obfuscators for point functions with multi-bit output and for prefix matching.Our assumption is that there is a one-way permutation wherein any polynomial-sized circuit inverts the permutation on at most a polynomial number of inputs. We show that a similar assumption is in fact necessary, and that our assumption holds relative to a random permutation oracle.Finally, we establish two impossibility results which indicate that the limitations on our construction, namely simulating only adversaries with single-bit output and using nonuniform advice in our simulator, are in some sense inherent.Previous work gave negative results for the general class of circuits (Barak et al., Crypto '01) and positive results in the random oracle model (Lynn et al., Eurocrypt '04) or under non-standard number-theoretic assumptions (Canetti, Crypto '97). This work represents the first effort to bridge the gap between the two for a natural class of functionalities.

A source is comprehensible if we can efficiently compute short descriptions of strings in the support and efficiently recover the strings from the descriptions. A source has high pseudo-entropy if it is computationally distinguishable from a source of high entropy. In this paper, we present a technique for proving lower bounds on compressibility in an oracle setting, which yields the following results: 1. We exhibit oracles relative to which there exists samplable sources over {0, 1}/sup n/ of low pseudoentropy (say n/2) that cannot be compressed to length less than n - /spl omega/(log n) by polynomial size circuits. This matches the upper bounds in (Goldberg and Sipser, 1991, Trevisan et al., 2004), and provides an oracle separation between compressibility and pseudoentropy, thereby partially addressing an open problem posed in (Impagliazzo, 1999). 2. We also provide a separation between 1/s-metric-type pseudoentropy and 1/s-Yao-type pseudoentropy - which are two computational analogues of entropy introduced in (Barak et al., 2003) - for the class of oracle circuits of sizes (s polynomially bounded). This is the first known separation result for metric-type and Yao-type pseudoentropy. 3. In the random oracle model, we show that there exists in compressible functions as defined in (Dwork et al., 1996) where any substantial compression of the output of the function must reveal something about the seed. This yields the first known practical realization of incompressible functions, under the assumption that random oracles may be realized using cryptographic hash functions. Finally, we show that computational assumptions are needed to separate compressibility and pseudoentropy for samplable sources. In particular, if one-way functions do not exist, then any samplable flat source of entropy k can be compressed by circuits to length k + 0(log n); furthermore, any such source has 1/2-Yao-type pseudoentropy k + 0(log n).

We analyze replication of resources by server nodes that act selfishly, using a game-theoretic approach. We refer to this as the selfish caching problem. In our model, nodes incur either cost for replicating resources or cost for access to a remote replica. We show the existence of pure strategy Nash equilibria and investigate the price of anarchy, which is the relative cost of the lack of coordination. The price of anarchy can be high due to undersupply problems, but with certain network topologies it has better bounds. With a payment scheme the game can always implement the social optimum in the best case by giving servers incentive to replicate.