Pairings are a powerful algebraic setting for realizing cryptographic functionalities. One challenge for cryptographers who design pairing systems is that the complexity of many systems in terms of the number of group elements and equations to verify has been steadily increasing over the past decade and is approaching the point of being unwieldy. To combat this challenge, multiple independent works have utilized computers to help with the system design. One common design task that researchers seek to automate is summarized as follows: given a description of a set of trusted elements T (e.g., a public key) and a set of untrusted elements U (e.g., a signature), automatically generate an algorithm that verifies U with respect to T using the pairing and group operations. To date, none of the prior automation works for this task have support for solutions with rational polynomials in the exponents despite many pairing constructions employing them (e.g., Boneh-Boyen signatures, Gentry's IBE, Dodis-Yampolskiy VRF). We demonstrate how to support this essential class of pairing systems for automated exploration. Specifically, we present a solution for automatically generating a verification algorithm with novel support for rational polynomials. The class of verification algorithms we consider in this work is called PPE Circuits (introduced in [HVW20]). Intuitively, a PPE Circuit is a circuit supporting pairing and group operations, which can test whether a set of elements U verifies with respect to a set of elements T. We provide a formalization of the problem, an algorithm for searching for a PPE Circuit supporting rational polynomials, a software implementation, and a detailed performance evaluation. Our implementation was tested on over three dozen schemes, including over ten test cases that our tool can handle, but prior tools could not. For all test cases where a PPE Circuit exists, the tool produced a solution in three minutes or less.

Pairing-based cryptography is widely used for its efficiency and functionality. When designing pairing-based schemes, one common task is to devise algorithms for verifying a set of untrusted group elements with respect to a set of trusted group elements. One might be searching for a verification algorithm for a signature scheme or a method for verifying an IBE/ABE private key with respect to the IBE/ABE public parameters. In ACM CCS 2019 Hohenberger Vusirikala, the AutoPPE software tool was introduced for automatically generating a set of pairing product equations (PPEs) that can verify the correctness of a set of pairing group elements with respect to a set of trusted group elements. This task is non-trivial. Some schemes (e.g., those based on dual system encryption) provably do not support any efficient algorithm for verifying the private keys with respect to the public parameters. Other schemes (e.g., the Boyen-Waters anonymous IBE) were left in a gray area by Hohenberger-Vusirikala (CCS 19) -- no conjunction of PPEs was known for testing them, but no proof of untestability either.

Using a set of pairing product equations (PPEs) to verify the correctness of an untrusted set of pairing elements with respect to another set of trusted elements has numerous cryptographic applications. These include the design of basic and structure-preserving signature schemes, building oblivious transfer schemes from "blind" IBE, finding new verifiable random functions and keeping the IBE/ABE authority "accountable" to the user.

Pairing-based cryptography has exploded over the last decade, as this algebraic setting offers good functionality and efficiency. However, there is a huge security gap between how schemes are usually analyzed in the academic literature and how they are typically implemented. The issue at play is that there exist multiple types of pairings: Type-I called "symmetric" is typically how schemes are presented and proven secure in the literature, because it is simpler and the complexity assumptions can be weaker; however, Type-III called "asymmetric" is typically the most efficient choice for an implementation in terms of bandwidth and computation time. There are two main complexities when moving from one pairing type to another. First, the change in algebraic setting invalidates the original security proof. Second, there are usually multiple (possibly thousands) of ways to translate from a Type-I to a Type-III scheme, and the "best" translation may depend on the application.

A secure ad-hoc survey scheme enables a survey authority to independently (without any interaction) select an ad-hoc group of registered users based only on their identities (e.g., their email addresses), and create a survey where only selected users can anonymously submit exactly one response. We present a formalization of secure ad-hoc surveys and a provably-secure implementation in the random oracle model, called ANONIZE. Our performance analysis shows that ANONIZE enables securely implementing million-person anonymous surveys using a single modern workstation. As far as we know, ANONIZE constitutes the first implementation of a large-scale secure computation protocol (of non-trivial functionalities) that scales to millions of users.

As devices everywhere increasingly communicate with each other, many security applications will require low-bandwidth signatures that can be processed quickly. Pairing-based signatures can be very short, but are often costly to verify. Fortunately, they also tend to have efficient batch verificatio n algorithms. Finding these batching algorithms by hand, however, can be tedious and error prone. We address this by presenting AutoBatch, an automated tool for generating batch verification code in either Python or C++ from a high level representation of a signature scheme. AutoBatch outputs both software and, for transparency, a LaTeX file describing the batching algorithm and arguing that it preserves the unforgeability of the original scheme. We tested AutoBatch on over a dozen pairing-based schemes to demonstrate that a computer could find competitive batching solutions in a reasonable amount of time. In particular, it found an algorithm that is faster than a batching algorithm from Eurocrypt 2010. Another novel contribution is that it handles cross-scheme batching, where it searches for a common algebraic structure between two distinct schemes and attempts to batch them together. In this work, we expand upon our paper on AutoBatch appearing in ACM CCS 2012 [in: Proceedings of the 2012 ACM Conference on Computer and Communications Security, CCS'12, ACM, New York, NY, USA, 2012, pp. 474–487] in a number of ways. We add a new loop-unrolling technique and show that it helps cut the batch verification cost of one scheme by roughly half. We describe our pruning and search algorithms in greater detail, including pseudocode and diagrams. All experiments were also re-run using the RELIC pairing library. We compare those results to our earlier results using the MIRACL library, and discuss why RELIC outperforms MIRACL in all but two cases. Automated proofs of several new batching algorithms are also included. AutoBatch is a useful tool for cryptographic designers and implementors, and to our knowledge, it is the first attempt to outsource to machines the design, proof writing and implementation of signature batch verification schemes.

Cryptographic design tasks are primarily performed by hand today. Shifting more of this burden to computers could make the design process faster, more accurate and less expensive. In this work, we investigate tools for programmatically altering existing cryptographic constructions to reflect particular design goals. Our techniques enhance both security and efficiency with the assistance of advanced tools including Satisfiability Modulo Theories (SMT) solvers.

As devices everywhere increasingly communicate with each other, many security applications will require low-bandwidth signatures that can be processed quickly. Pairing-based signatures can be very short, but are often costly to verify. Fortunately, they also tend to have efficient batch verification algorithms. Finding these batching algorithms by hand, however, can be tedious and error prone.

The use of privacy-enhancing cryptographic protocols, such as anonymous credentials and oblivious transfer, could have a detrimental effect on the ability of providers to effectively implement access controls on their content. In this article, we propose a stateful anonymous credential system that allows the provider to implement nontrivial, real-world access controls on oblivious protocols conducted with anonymous users. Our system models the behavior of users as a state machine and embeds that state within an anonymous credential to restrict access to resources based on the state information. The use of state machine models of user behavior allows the provider to restrict the users' actions according to a wide variety of access control models without learning anything about the users' identities or actions. Our system is secure in the standard model under basic assumptions and, after an initial setup phase, each transaction requires only constant time. As a concrete example, we show how to implement the Brewer--Nash (Chinese Wall) and Bell-La Padula (Multilevel Security) access control models within our credential system. Furthermore, we combine our credential system with an adaptive oblivious transfer scheme to create a privacy-friendly oblivious database with strong access controls.

An aggregate signature scheme is a digital signature scheme where anyone given n signatures on n messages from n users can aggregate all these signatures into a single short signature. Unfortunately, no "fully non-interactive" aggregate signature schemes are known outside of the random oracle heuristic; that is, signers must pass messages between themselves, sequentially or otherwise, to generate the signature. Interaction is too costly for some interesting applications.

In a proxy re-encryption (PRE) scheme, a proxy is given special information that allows it to translate a ciphertext under one key into a ciphertext of the same message under a different key. The proxy cannot, however, learn anything about the messages encrypted under either key. PRE schemes have many practical applications, including distributed storage, email, and DRM. Previously proposed re-encryption schemes achieved only semantic security; in contrast, applications often require security against chosen ciphertext attacks. We propose a definition of security against chosen ciphertext attacks for PRE schemes, and present a scheme that satisfies the definition. Our construction is efficient and based only on the Decisional Bilinear Diffie-Hellman assumption in the standard model. We also formally capture CCA security for PRE schemes via both a game-based definition and simulation-based definitions that guarantee universally composable security. We note that, simultaneously with our work, Green and Ateniese proposed a CCA-secure PRE, discussed herein.

We create a credential system that lets a user anonymously authenticate at most $n$ times in a single time period. A user withdraws a dispenser of n e-tokens. She shows an e-token to a verifier to authenticate herself; each e-token can be used only once, however, the dispenser automatically refreshes every time period. The only prior solution to this problem, due to Damgård et al. [29], uses protocols that are a factor of k slower for the user and verifier, where k is the security parameter. Damgård et al. also only support one authentication per time period, while we support n. Because our construction is based on e-cash, we can use existing techniques to identify a cheating user, trace all of her e-tokens, and revoke her dispensers. We also offer a new anonymity service: glitch protection for basically honest users who (occasionally) reuse e-tokens. The verifier can always recognize a reused e-token; however, we preserve the anonymity of users who do not reuse e-tokens too often.

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed an application called atomic proxy re-encryption , in which a semitrusted proxy converts a ciphertext for Alice into a ciphertext for Bob without seeing the underlying plaintext. We predict that fast and secure re-encryption will become increasingly popular as a method for managing encrypted file systems. Although efficiently computable, the wide-spread adoption of BBS re-encryption has been hindered by considerable security risks. Following recent work of Dodis and Ivan, we present new re-encryption schemes that realize a stronger notion of security and demonstrate the usefulness of proxy re-encryption as a method of adding access control to a secure file system. Performance measurements of our experimental file system demonstrate that proxy re-encryption can work effectively in practice.

In 1998, Blaze, Bleumer, and Strauss (BBS) proposed proxy re-signatures, in which a semi-trusted proxy acts as a translator between Alice and Bob. To translate, the proxy converts a signature from Alice into a signature from Bob on the same message. The proxy, however, does not learn any signing key and cannot sign arbitrary messages on behalf of either Alice or Bob. Since the BBS proposal, the proxy re-signature primitive has been largely ignored, but we show that it is a very useful tool for sharing web certificates, forming weak group signatures, and authenticating a network path.We begin our results by formalizing the definition of security for a proxy re-signature. We next substantiate the need for improved schemes by pointing out certain weaknesses of the original BBS proxy re-signature scheme which make it unfit for most practical applications. We then present two secure proxy re-signature schemes based on bilinear maps. Our first scheme relies on the Computational Diffie-Hellman (CDH) assumption; here the proxy can translate from Alice to Bob and vice-versa. Our second scheme relies on the CDH and 2-Discrete Logarithm (2-DL) assumptions and achieves a stronger security guarantee -- the proxy is only able to translate in one direction. Constructing such a scheme has been an open problem since proposed by BBS in 1998. Furthermore in this second scheme, even if the delegator and the proxy collude, they cannot sign on behalf of the delegatee. Both schemes are efficient and secure in the random oracle model.