[continued from previous message]

In this note, we study the interplay between the communication from a verifier in a general private-coin interactive protocol and the number of random bits it uses in the protocol. Under worst-case derandomization assumptions, we show that it is possible
to transform any $I$-round interactive protocol that uses $\rho$ random bits into another one for the same problem with the additional property that the verifier's communication is bounded by $O(I\cdot \rho)$. Importantly, this is done with a minor,
logarithmic, increase in the communication from the prover to the verifier and while preserving the randomness complexity. Along the way, we introduce a new compression game between computationally-bounded compressor and computationally-unbounded
decompressor and a new notion of conditioned efficient distributions that may be of independent interest. Our solutions are based on a combination of perfect hashing and pseudorandom generators.



## 2024/953

* Title: MixBuy: Contingent Payment in the Presence of Coin Mixers
* Authors: Diego Castejon-Molina, Dimitrios Vasilopoulos, Pedro Moreno-Sanchez * [Permalink](https://eprint.iacr.org/2024/953)
* [Download](https://eprint.iacr.org/2024/953.pdf)

### Abstract

A contingent payment protocol involves two mutually distrustful parties, a buyer and a seller, operating on the same blockchain, and a digital product, whose ownership is not tracked on a blockchain (e.g. a digital book, but not a NFT). The buyer holds
coins on the blockchain and transfers them to the seller in exchange for the product. However, if the blockchain does not hide transaction details, any observer can learn that a buyer purchased some product from a seller. In this work, we take contingent
payment a step further: we consider a buyer who wishes to buy a digital product from a seller routing the payment via an untrusted mixer. Crucially, we require that said payment is unlinkable, meaning that the mixer (or any other observer) does not learn
which buyer is paying which seller. We refer to such setting as unlinkable contingent payment (UCP).

We present MixBuy, a system that realizes UCP. Mixbuy relies on \emph{oracle-based unlinkable contingent payment} (O-UCP), a novel four-party cryptographic protocol where the mixer pays the seller and the seller provides the buyer with the product
only if a semi-trusted notary attests that the buyer has paid the mixer. More specifically, we require four security notions: (i) mixer security that guarantees that if the mixer pays the seller, the intermediary must get paid from the buyer; (ii) seller
security that guarantees that if the seller delivers the product to the buyer, the seller must get paid from the intermediary; (iii) buyer security that guarantees that if the buyer pays the intermediary, the buyer must obtain the product; and (iv)
unlinkability that guarantees that given a set of buyers and sellers, the intermediary should not learn which buyer paid which seller.

We present a provably secure and efficient cryptographic construction for O-UCP. Our construction can be readily used to realize UCP on most blockchains, as it has minimal functionality requirements (i.e., digital signatures and timelocks). To
demonstrate the practicality of our construction, we provide a proof of concept for O-UCP and our benchmarks in commodity hardware show that the communication overhead is small (a few kB per message) and the running time is below one second.



## 2024/954

* Title: Arithmetisation of computation via polynomial semantics for first-order logic
* Authors: Murdoch J. Gabbay
* [Permalink](https://eprint.iacr.org/2024/954)
* [Download](https://eprint.iacr.org/2024/954.pdf)

### Abstract

We propose a compositional shallow translation from a first-order logic with equality, into polynomials; that is, we arithmetise the semantics of first-order logic. Using this, we can translate specifications of mathematically structured programming
into polynomials, in a form amenable to succinct cryptographic verification.

We give worked example applications, and we propose a proof-of-concept succinct verification scheme based on inner product arguments.



## 2024/955

* Title: ElectionGuard: a Cryptographic Toolkit to Enable Verifiable Elections * Authors: Josh Benaloh, Michael Naehrig, Olivier Pereira, Dan S. Wallach
* [Permalink](https://eprint.iacr.org/2024/955)
* [Download](https://eprint.iacr.org/2024/955.pdf)

### Abstract

ElectionGuard is a flexible set of open-source tools that---when used with traditional election systems---can produce end-to-end verifiable elections whose integrity can be verified by observers, candidates, media, and even voters themselves.
ElectionGuard has been integrated into a variety of systems and used in actual public U.S. elections in Wisconsin, California, Idaho, Utah, and Maryland as well as in caucus elections in the U.S. Congress. It has also been used for civic voting in the
Paris suburb of Neuilly-sur-Seine and for an online election by a Switzerland/Denmark-based organization.

The principal innovation of ElectionGuard is the separation of the cryptographic tools from the core mechanics and user interfaces of voting systems. This separation allows the cryptography to be designed and built by security experts without having to
re-invent and replace the existing infrastructure. Indeed, in its preferred deployment, ElectionGuard does not replace the existing vote counting infrastructure but instead runs alongside and produces its own independently-verifiable tallies. Although
much of the cryptography in ElectionGuard is, by design, not novel, some significant innovations are introduced which greatly simplify the process of verification.

This paper describes the design of ElectionGuard, its innovations, and many of the learnings from its implementation and growing number of real-world deployments.



## 2024/956

* Title: SNARGs under LWE via Propositional Proofs
* Authors: Zhengzhong Jin, Yael Tauman Kalai, Alex Lombardi, Vinod Vaikuntanathan
* [Permalink](https://eprint.iacr.org/2024/956)
* [Download](https://eprint.iacr.org/2024/956.pdf)

### Abstract

We construct a succinct non-interactive argument (SNARG) system for every NP language $\mathcal{L}$ that has a propositional proof of non-membership for each $x\notin \mathcal{L}$. The soundness of our SNARG system relies on the hardness of the learning
with errors (LWE) problem. The common reference string (CRS) in our construction grows with the space required to verify the propositional proof, and the size of the proof grows poly-logarithmically in the length of the propositional proof.

Unlike most of the literature on SNARGs, our result implies SNARGs for languages $\mathcal L$ with proof length shorter than logarithmic in the deterministic time complexity of $\mathcal L$. Our SNARG improves over prior SNARGs for such ``hard'' NP
languages (Sahai and Waters, STOC 2014, Jain and Jin, FOCS 2022) in several ways:

- For languages with polynomial-length propositional proofs of non-membership, our SNARGs are based on a single, polynomial-time falsifiable assumption, namely LWE.
- Our construction handles propositional proofs of super-polynomial length, as long as they have bounded space, under the subexponential LWE assumption.
- Our SNARGs have a transparent setup, meaning that no private randomness is required to generate the CRS.

Moreover, our approach departs dramatically from these prior works: we show how to design SNARGs for hard languages without publishing a program (in the CRS) that has the power to verify $\mathsf{NP}$ witnesses.

The key new idea in our cryptographic construction is what we call a ``locally unsatisfiable extension'' of the $\mathsf{NP}$ verification circuit $\{C_x\}_x$. We say that an $\mathsf{NP}$ verifier has a locally unsatisfiable extension if for every $x\
not\in \mathcal L$, there exists an extension $E_x$ of $C_x$ that is not even locally satisfiable in the sense of a local assignment generator [Paneth-Rothblum, TCC 2017]. Crucially, we allow $E_x$ to be depend arbitrarily on $x$ rather than being
efficiently constructible.

In this work, we show -- via a ``hash-and-BARG'' for a hidden, encrypted computation -- how to build SNARGs for all languages with locally unsatisfiable extensions. We additionally show that propositional proofs of unsatisfiability generically imply the
existence of locally unsatisfiable extensions, which allows us to deduce our main results.

As an illustrative example, our results imply a SNARG for the decisional Diffie-Hellman (DDH) language under the LWE assumption.

--- SoupGate-Win32 v1.05
* Origin: fsxNet Usenet Gateway (21:1/5)