Trellis is a mix-net based anonymous broadcast system with cryptographic security guarantees. Trellis can be used to anonymously publish documents or communicate with other users, all while assuming full network surveillance. In Trellis, users send messages through a set of servers in successive rounds. The servers mix and post the messages to a public bulletin board, hiding which users sent which messages. Trellis hides all network metadata, remains robust to changing network conditions,...

Random Allocation -the random assignment of the data to the parties- is a well-studied topic in the analysis of medical or judicial data, and the context of resource distribution. Random allocation reduces the chance of bias or corruption in the relevant applications, which makes the results more reliable. This is done by preventing a special or pre-planned assignment of the data to accommodate the assessment toward the desired results. This paper provides the first formal syntax and...

The re-encryption mix-net (RMN) is a basic cryptographic tool that is widely used in the privacy protection domain and requires anonymity support; for example, it is used in electronic voting, web browsing, and location systems. To protect information about the relationship between senders and messages, a number of mix servers in RMNs shuffle and forward a list of input ciphertexts in a cascading manner. The output of the last mix server is decrypted to yield the set of original messages....

Mix-nets are protocols that allow a set of senders to send messages anonymously. Faonio et al. (ASIACRYPT’19) showed how to instantiate mix-net protocols based on Public-Verifiable Re-randomizable Replayable CCA-secure (Rand-RCCA) PKE schemes. The bottleneck of their approach is that public-verifiable Rand-RCCA PKEs are less efficient than typical CPA-secure re-randomizable PKEs. In this paper, we revisit their mix-net protocol, showing how to get rid of the cumbersome public-verifiability...

Mix-networks were first proposed by Chaum in the late 1970s -- early 1980s as a general tool for building anonymous communication systems. Classical mix-net implementations rely on standard public key primitives (e.g. ElGamal encryption) that will become vulnerable when a sufficiently powerful quantum computer will be built. Thus, there is a need to develop quantum-resistant mix-nets. This paper focuses on the application case of electronic voting where the number of votes to be mixed may...

Efficient shuffle arguments are essential in mixnet-based e-voting solutions. Terelius and Wikström (TW) proposed a 5-round shuffle argument based on unique factorization in polynomial rings. Their argument is available as the Verificatum software solution for real-world developers, and has been used in real-world elections. It is also the fastest non-patented shuffle argument. We will use the same basic idea as TW but significantly optimize their approach. We generalize the...

The long term privacy of voting systems is of increasing concern as quantum computers come closer to reality. Everlasting privacy schemes offer the best way to manage these risks at present. While homomorphic tallying schemes with everlasting privacy are well developed, most national elections, using electronic voting, use mixnets. Currently the best candidate encryption scheme for making these kinds of elections everlastingly private is PPATC, but it has not been shown to work with any...

Verifiable mix nets, and specifically proofs of (correct) shuffle, are a fundamental building block in numerous applications: these zero-knowledge proofs allow the prover to produce a public transcript which can be perused by the verifier to confirm the purported shuffle. They are particularly vital to verifiable electronic voting, where they underpin almost all voting schemes with non-trivial tallying methods. These complicated pieces of cryptography are a prime location for critical...

Since David Chaum introduced the idea of mix nets 40 years ago, they have become widely used building blocks for privacy-preserving protocols. Several important applications, such as secure e-voting, require that the employed mix net be verifiable. In the literature, numerous techniques have been proposed to make mix nets verifiable. Some of them have also been employed in politically binding elections. Verifiable mix nets differ in many aspects, including their precise verifiability...

Mix nets are often used to provide privacy in modern security protocols, through shuffling. Some of the most important applications, such as secure electronic voting, require mix nets that are verifiable. In the literature, numerous techniques have been proposed to make mix nets verifiable. Some of them have also been employed for securing real political elections. With the looming possibility of quantum computers and their threat to cryptosystems based on classical hardness assumptions,...

A commitment scheme allows a committer to create a commitment to a secret value, and later may open and reveal the secret value in a verifiable manner. In the common reference string model, (equivocal) commitment schemes require a setup phase which is supposed to be done by a third trusted party. Recently, various news is reported about the subversion of $\textit{trusted}$ setup phase in mass-surveillance activities; strictly speaking about commitment schemes, recently it was discovered...

Re-randomizable RCCA-secure public key encryption (Rand-RCCA PKE) schemes reconcile the property of re-randomizability of the ciphertexts with the need of security against chosen-ciphertexts attacks. In this paper we give a new construction of a Rand-RCCA PKE scheme that is perfectly re-randomizable. Our construction is structure-preserving, can be instantiated over Type-3 pairing groups, and achieves better computation and communication efficiency than the state of the art perfectly...

Anonymous communication, that is secure end-to-end and unlinkable, plays a critical role in protecting user privacy by preventing service providers from using message metadata to discover communication links between any two users. Techniques, such as Mix-net, DC-net, time delay, cover traffic, Secure Multiparty Computation and Private Information Retrieval techniques, can be used to achieve anonymous communication. However, the existing solutions are very complex and difficult to implement...

Mixing Networks are protocols that allow a set of senders to send messages anonymously. Such protocols are fundamental building blocks to achieve privacy in a variety of applications, such as anonymous e-mail, anonymous payments, and electronic voting. Back in 2002, Golle et al. proposed a new concept of mixing network, called optimistic mixing, that allows for fast mixing when all the parties execute the protocol honestly. If, on the other hand, one or more mix-servers cheat, then the...

Email communication is amongst the most prominent online activities, and as such, can put sensitive information at risk. It is thus of high importance that internet email applications are designed in a privacy-aware manner and analyzed under a rigorous threat model. The Snowden revelations (2013) suggest that such a model should feature a global adversary, in light of the observational tools available. Furthermore, the fact that protecting metadata can be of equal importance as protecting...

Mix networks are a key technology to achieve network anonymity and private messaging, voting and database lookups. However, simple mix network designs are vulnerable to malicious mixes, which may drop or delay packets to facilitate traffic analysis attacks. Mix networks with provable robustness address this drawback through complex and expensive proofs of correct shuffling but come at a great cost and make limiting or unrealistic systems assumptions. We present Miranda, an efficient mix-net...

In this paper we present the first proof of a shuffle for lattice-based cryptography which can be used to build a universally verifiable mix-net capable of mixing votes encrypted with a post-quantum algorithm, thus achieving long-term privacy. Universal verifiability is achieved by means of the publication of a non-interactive zero knowledge proof of a shuffle generated by each mix-node which can be verified by any observer. This published data guarantees long-term privacy since its security...

We construct the most efficient known pairing-based NIZK shuffle argument. It consists of three subarguments that were carefully chosen to obtain optimal efficiency of the shuffle argument: * A same-message argument based on the linear subspace QANIZK argument of Kiltz and Wee, * A (simplified) permutation matrix argument of Fauzi, Lipmaa, and Zając, * A (simplified) consistency argument of Groth and Lu. We prove the knowledge-soundness of the first two subarguments in the generic...

We show that the simple and appealing unconditionally sound mix-net due to Abe (Asiacrypt'99) can be augmented to further guarantee anonymity against malicious verifiers. This additional guarantee implies, in particular, that when applying the Fiat-Shamir transform to the mix-net's underlying sub-protocols, anonymity is provably guaranteed for {\em any} hash function. As our main contribution, we demonstrate how anonymity can be attained, even if most sub-protocols of a mix-net are merely...

We propose a new random oracle-less NIZK shuffle argument. It has a simple structure, where the first verification equation ascertains that the prover has committed to a permutation matrix, the second verification equation ascertains that the same permutation was used to permute the ciphertexts, and the third verification equation ascertains that input ciphertexts were ``correctly'' formed. The new argument has $3.5$ times more efficient verification than the up-to-now most efficient shuffle...

A cryptographic contract and enforcement technology would guarantee release of a data decryption key to an authorized party if and only if predetermined contract requirements are satisfied. Threshold secret sharing can be used to eliminate the need for access to the hidden key under normal circumstances. It can also eliminate the liability and burden normally carried by device manufacturers or service providers when they store the decryption keys of their customers. Blockchain technology...

One way to guarantee security against malicious voting servers is to use NIZK shuffle arguments. Up to now, only two NIZK shuffle arguments in the CRS model have been proposed. Both arguments are relatively inefficient compared to known random oracle based arguments. We propose a new, more efficient, shuffle argument in the CRS model. Importantly, its online prover's computational complexity is dominated by only two $(n + 1)$-wide multi-exponentiations, where $n$ is the number of...

In this paper we present a novel, publicly verifiable mixing scheme which has everlasting privacy towards observers: all the information published on the bulletin board by the mixes (audit information etc) reveals no information about the identity of any of the messages published. The correctness of the mixing process is statistical: even if all authorities conspire, they cannot change the contents of any message without being detected with overwhelming probability. We accomplish this by...

In TCC 2007, Adida and Wikström proposed a novel approach to shuffle, called a public shuffle, in which a shuffler can perform shuffle publicly without needing information kept secret. Their scheme uses an encrypted permutation matrix to shuffle ciphertexts publicly. This approach significantly reduces the cost of constructing a mix-net to verifiable joint decryption. Though their method is successful in making shuffle to be a public operation, their scheme still requires that some trusted...

We study the heuristically secure mix-net proposed by Puiggalí and Guasch (EVOTE 2010). We present practical attacks on both correctness and privacy for some sets of parameters of the scheme. Although our attacks only allow us to replace a few inputs, or to break the privacy of a few voters, this shows that the scheme can not be proven secure.

We study mix-nets with randomized partial checking (RPC) as proposed by Jakobsson, Juels, and Rivest (2002). RPC is a technique to verify the correctness of an execution both for Chaumian and homomorphic mix-nets. The idea is to relax the correctness and privacy requirements to achieve a more efficient mix-net. We identify serious issues in the original description of mix-nets with RPC and show how to exploit these to break both correctness and privacy, both for Chaumian and homomorphic...

In order for a mix-net to be usable in practice (e.g. in electronic voting), efficient verification is a must. Despite many advances in the last decade, zero-knowledge proofs remain too computationally intense. Two alternative proof approaches have been suggested: optimistic mix-net verification and randomized partial checking. Puiggalí et al. proposed a verification method combining these two approaches. This paper investigates their mix-net and proposes a verification method which offers...

The contribution of this paper is twofold. First we present a new simple electronic voting scheme having standard re-encryption mix net back-end, which allows to cast a ballot and verify its correctness in a new way. Then we extend the proposed scheme to represent a new very efficient mix network construction. We called our mix network to be self-proving mix, because it is shown how mix process correctness can be verified without demanding from mix party a special proof. Our proposed mix...

The Jakobsson hybrid Mix-net proposed by Jakobsson and Juels, is a very practical and efficient scheme for long input messages. But this hybrid Mix-net does not have public verifiable property. In this paper a new attack to the Jakobsson hybrid Mix-net is introduced. This attack breaks the robustness of the hybrid Mix-net scheme, given that the corrupted first mix server and one of the senders collude with each other.

We introduce a pre-computation technique that drastically reduces the online computational complexity of mix-nets based on homomorphic cryptosystems. More precisely, we show that there is a permutation commitment scheme that allows a mix-server to: (1) commit to a permutation and efficiently prove knowledge of doing so correctly in the offline phase, and (2) shuffle its input and give an extremely efficient commitment-consistent proof of a shuffle in the online phase. We prove our result...

Consider an electronic election scheme implemented using a mix-net; a large number of voters submit their votes and then a smaller number of servers compute the result. The mix-net accepts an encrypted vote from each voter and outputs the set of votes in sorted order without revealing the permutation used. To ensure a fair election, the votes of corrupt voters should be independent of the votes of honest voters, i.e., some type of non-malleability or plaintext awareness is needed. However,...

We show how to public-key obfuscate two commonly used shuffles: decryption shuffles which permute and decrypt ciphertexts, and re-encryption shuffles which permute and re-encrypt ciphertexts. Given a trusted party that samples and obfuscates a shuffle \emph{before} any ciphertexts are received, this reduces the problem of constructing a mix-net to verifiable joint decryption. We construct a decryption shuffle from any additively homomorphic cryptosystem and show how it can be public-key...

We suggest an honest verifier zero-knowledge argument for the correctness of a shuffle of homomorphic encryptions. A shuffle consists of a rearrangement of the input ciphertexts and a re-encryption of them. One application of shuffles is to build mix-nets. Our scheme is more efficient than previous schemes in terms of both communication and computational complexity. Indeed, the HVZK argument has a size that is independent of the actual cryptosystem being used and will typically be smaller...

We propose a variant of the Paillier cryptosystem that improves efficiency in encryption, re-encryption and decryption while preserving the homomorphic property. We then use this variant to construct a new verifiable shuffle system and prove its security. We show that the new shuffle scheme has the least number of rounds and exponentiations compared to all known shuffle schemes. Finally, we show how to construct a publicly verifiable mix-net using the shuffle system.

We introduce the first El Gamal based mix-net in which each mix-server partially decrypts and permutes its input, i.e., no re-encryption is necessary. An interesting property of the construction is that a sender can verify non-interactively that its message is processed correctly. We call this sender verifiability. We prove the security of the mix-net in the UC-framework against static adversaries corrupting any minority of the mix-servers. The result holds under the decision Diffie-Hellman...

Mix-nets can be used to shuffle vectors of shared secrets. This operation can be an important building block for solving combinatorial problems where constraints depend on secrets of different participants. A main contribution of this paper is to show how participants in the mix-net can provide Zero-Knowledge proofs to convince each other that they do not tamper with the shuffled secrets, and that inverse permutations are correctly applied at unshuffling. The approach is related to the...

We propose a new technique for making mix nets robust, called randomized partial checking (RPC). The basic idea is that rather than providing a proof of completely correct operation, each server provides strong evidence of its correct operation by revealing a pseudo-randomly selected subset of its input/output relations. Randomized partial checking is exceptionally efficient compared to previous proposals for providing robustness; the evidence provided at each layer is shorter than the...