International Association
for Cryptologic Research

<p> We investigate proof systems where security holds against rational parties instead of malicious ones. Our starting point is the notion of rational arguments, a variant of rational proofs (Azar and Micali, STOC 2012) where security holds against rational adversaries that are also computationally bounded.</p><p>Rational arguments are an interesting primitive because they generally allow for very efficient protocols, and in particular sublinear verification (i.e. where the Verifier does not have to read the entire input). In this paper we aim at narrowing the gap between literature on rational schemes and real world applications. Our contribution is two-fold.</p><p>We provide the first construction of rational arguments for the class of polynomial computations that is practical (i.e., it can be applied to real-world computations on reasonably common hardware) and with logarithmic communication. Techniques-wise, we obtain this result through a compiler from information-theoretic protocols and rational proofs for polynomial evaluation. The latter could be of independent interest.</p><p>As a second contribution, we propose a new notion of extractability for rational arguments. Through this notion we can obtain arguments where knowledge of a witness is incentivized (rather than incentivizing mere soundness). We show how our aforementioned compiler can also be applied to obtain efficient extractable rational arguments for $\mathsf{NP}$. </p>

Vector Commitments allow one to (concisely) commit to a vector of messages so that one can later (concisely) open the commitment at selected locations. In the state of the art of vector commitments, {\em algebraic} constructions have emerged as a particularly useful class, as they enable advanced properties, such as stateless updates, subvector openings and aggregation, that are for example unknown in Merkle-tree-based schemes. In spite of their popularity, algebraic vector commitments remain poorly understood objects. In particular, no construction in standard prime order groups (without pairing) is known. In this paper, we shed light on this state of affairs by showing that a large class of concise algebraic vector commitments in pairing-free, prime order groups are impossible to realize. Our results also preclude any cryptographic primitive that implies the algebraic vector commitments we rule out, as special cases. This means that we also show the impossibility, for instance, of succinct polynomial commitments and functional commitments (for all classes of functions including linear forms) in pairing-free groups of prime order.

Exposure Notification is a system designed by Google and Apple for notifying individuals when they have been exposed to SARS-CoV-2 by coming in contact with someone who has tested positive for the virus. Within GAEN, no user-identifying data is ever uploaded to the central server; users establish their proximity exclusively peer-to-peer and anonymously, with the sole purpose of knowing whether they have been in contact with an individual who may later be deemed to have been infected. The design choices of the protocols in question, which makes them robust against data collection attacks, unfortunately also make them particularly susceptible to data injection by malicious parties. In particular, these protocols allow for a determined attacker to generate false exposure notifications on a mass scale in an undetectable and unpreventable manner. In this paper we highlight how these data injections attacks can be used to implement voter suppression in political elections and to compromise the integrity of the democratic process.

We develop a general approach to adding a threshold functionality to a large class of (non-threshold) cryptographic schemes. A threshold functionality enables a secret key to be split into a number of shares, so that only a threshold of parties can use the key, without reconstructing the key. We begin by constructing a threshold fully-homomorphic encryption scheme (ThFHE) from the learning with errors (LWE) problem. We next introduce a new concept, called a universal thresholdizer, from which many threshold systems are possible. We show how to construct a universal thresholdizer from our ThFHE. A universal thresholdizer can be used to add threshold functionality to many systems, such as CCA-secure public-key encryption (PKE), signature schemes, pseudorandom functions, and others primitives. In particular, by applying this paradigm to a (non-threshold) lattice signature system, we obtain the first single-round threshold signature scheme from LWE.

This paper initiates a study of Fine Grained Secure Computation: i.e. the construction of secure computation primitives against “moderately complex” adversaries. We present definitions and constructions for compact Fully Homomorphic Encryption and Verifiable Computation secure against (non-uniform) $$\mathsf {NC}^1$$ adversaries. Our results do not require the existence of one-way functions and hold under a widely believed separation assumption, namely $$\mathsf {NC}^{1}\subsetneq \oplus \mathsf {L}/ {\mathsf {poly}}$$ . We also present two application scenarios for our model: (i) hardware chips that prove their own correctness, and (ii) protocols against rational adversaries potentially relevant to the Verifier’s Dilemma in smart-contracts transactions such as Ethereum.