Anonymous token schemes are cryptographic protocols for limiting the access to online resources to credible users. The resource provider issues a set of access tokens to the credible user that they can later redeem anonymously, i.e., without the provider being able to link their redemptions. When combined with credibility tests such as CAPTCHAs, anonymous token schemes can significantly increase user experience and provider security, without exposing user access patterns to providers.Current anonymous token schemes such as the Privacy Pass protocol by Davidson et al. rely on oblivious pseudorandom functions (OPRFs), which let server and user jointly compute randomly looking access tokens. For those protocols, token issuing costs are linear in the number of requested tokens.In this work, we propose a new approach for building anonymous token schemes. Instead of relying on two-party computation to realize a privacy-preserving pseudorandom function evaluation, we propose to offload token generation to the user by using group verifiable random functions (GVRFs). GVRFs are a new cryptographic primitive that allow users to produce verifiable pseudorandomness. Opposed to standard VRFs, verification is anonymous within the group of credible users. We give a construction of group VRFs from the Dodis-Yampolskiy VRF and EquivalenceClass Signatures, based on pairings and a new Diffie-Hellman inversion assumption that we analyze in the Generic Group Model. Our construction enjoys compact public keys and proofs, while evaluation and verification costs are only slightly increased compared to the Dodis-Yampolskiy VRF.By deploying a group VRF instead of a OPRF, we obtain an anonymous token scheme where communication as well as server-side computation during the issuing phase is constant and independent of the number of tokens a user requests. Moreover, by means of our new concept of updatable token policies, the number of unspent tokens in circulation can retrospectively (i.e., even after the credibility check) be decreased or increased in order to react to the current or expected network situation. Our tokens are further countable and publicly verifiable. This comes at the cost of higher computational efforts for token redemption and verification as well as somewhat weaker unlinkability guarantees compared to Privacy Pass.

SPDZ refers to a family of protocols for Secure Multi-Party Computation (MPC) that lie at the foundation of very popular software frameworks for MPC, such as SCALE-MAMBA and MP-SPDZ. SPDZ provides good efficiency while guaranteeing security even when all but one of the participants are corrupted. This seemingly optimal property comes at a price: the protocol only offers security with abort, meaning that even a single cheating participant can force the protocol to abort, leaving honest participants with no clue on what the correct output is, or who cheated. This is especially problematic since cheating participants are able to obtain the correct output of the computation, effectively `stealing' it. We propose a *hybrid secure* adaptation to SPDZ, which retains the existing security guarantees, but in case the number of cheating players is less than half of the total, we achieve *fairness*, meaning that either all players obtain the correct output of the computation, or no player does. The `less than half' threshold of corrupted players has been proven to be a tight bound to achieve fairness. Aside from the description of the protocol and its security proof, we also present a proof-of-concept implementation, and evaluate its practical performance, thereby demonstrating that our solution has negligible overhead compared to standard SPDZ in most application scenarios.

A pseudorandom correlation generator (PCG) is a recent tool for securely generating useful sources of correlated randomness, such as random oblivious transfers (OT) and vector oblivious linear evaluations (VOLE), with low communication cost. We introduce a simple new design for PCGs based on so-called expand-accumulate codes, which first apply a sparse random expander graph to replicate each message entry, and then accumulate the entries by computing the sum of each prefix. Our design offers the following advantages compared to state-of-the-art PCG constructions: Competitive concrete efficiency backed by provable security against relevant classes of attacks; An offline-online mode that combines near-optimal cache-friendliness with simple parallelization; Concretely efficient extensions to pseudorandom correlation functions , which enable incremental generation of new correlation instances on demand, and to new kinds of correlated randomness that include circuit-dependent correlations. To further improve the concrete computational cost, we propose a method for speeding up a full-domain evaluation of a puncturable pseudorandom function (PPRF). This is independently motivated by other cryptographic applications of PPRFs.

Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function Fk such that for a suitable joint key distribution ( k0, k1), the outputs (fk0(x), fk1(x)) are indistinguishable from instances of a given target correlation. An essential security requirement is that indistinguishability hold not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys. We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VDLPN). We also present several cryptographic applications that motivate our efficient PCF constructions. The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in depth-2 AC0[⊕] that can be conjectured to have subexponential security, matching the best known learning algorithms for this class. This is contrasted with the quasipolynomial security of previous (higher-depth) AC0[⊕] candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VDLPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.

We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base'' oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions: Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semi-honest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature. Malicious security. We provide security against malicious parties without additional interaction and with only a modest overhead; prior to our work, no similar protocols were known with any number of rounds. Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.