# Linkable membership proofs, some options

In all of the options below, the way that the protocol works is that voters solve an equation that is only solvable to people who have a secret key corresponding to one of the public keys in the census, and use this proof to sign a message. The message is not encrypted, and the content of the message is the voter's vote. (Domain-separation information such as chain id and process id can also go into the message, in order to provide replay protection.)

## DualDory

[DualDory: Logarithmic-verifier linkable ring signatures through preprocessing](https://dualdory.github.io)
This is an elliptic curve discrete log-based scheme, with pairings-based preprocessing. This scheme is very new, but a huge plus is that it is implementable and launchable today, with no future research needed.

<div class="c-row">
<div class="c-column">

#### Pros:
- Usable today
- Linkable out of the box
- No MPC trusted setup required
- No further research needed
- Assumptions : sXDH
- Tiny constants for proving and verification time, and signature size

</div>
<div class="c-column">

#### Cons:
- Signing time : O(n)
- Verification time : O(n) (preprocessing) + O(logn)
- Signature size : O(logn) (include constants)

</div>
</div>

## BBS signatures
[Short Group Signatures](https://www.iacr.org/archive/crypto2004/31520040/groupsigs.pdf)
This is a pairings based scheme, which has great asymptotics (the signature and proving and verification computations do not grow at all with the number of voters, which means it is great for scaling). This scheme is currently going through the [cfrg standardisation process](https://datatracker.ietf.org/doc/draft-irtf-cfrg-bbs-signatures/), as it is being used in companies that are trying to provide privacy preserving proof of identity solutions. This means it should be straightforward to implement well. However, it currently is linkable only to an authority, and it's still an open research question whether this authority could be easily distributed (or replaced with some publicly verifiable equations).

<div class="c-row">
<div class="c-column">

#### Pros:
- Signing time : O(1)
- Verification time : O(1)
- Signature size : O(1)
- Uses pairings-based assumptions (q-SDH, DLin)
</div>
<div class="c-column">

#### Cons:
- An option for the future
- Currently linkable only to an authority
- Needs research time to figure out whether it is possible to distribute the ability to verify whether people are double voting

</div>
</div>

## Au et al signatures
[Short linkable ring signatures revisited](https://dl.acm.org/doi/abs/10.1007/11774716_9)
This is a strong RSA and elliptic curve DDH based scheme, which again has great asymptotics (the signature and proving and verification computations do not grow at all with the number of voters, which means it is great for scaling). However, use of RSA assumptions means that this scheme would need a bespoke trusted setup, and the difficulty of distributing this work in a privacy-preserving way is an open research problem.

<div class="c-row">
<div class="c-column">

#### Pros:
- Signing time : O(1)
- Verification time : O(1)
- Signature size : O(1)
- Linkable out of the box
- Assumptions : strong RSA, DDH
</div>
<div class="c-column">

#### Cons:
- An option for the future
- Needs some research to make sure MPC of RSA parameter generation is possible
- Strong RSA assumption means that an MPC based setup of RSA parameters needs to be done

</div>
</div>

## Snark-based solutions

Vocdoni lives here!

A walk-through of some tradeoffs for some potential SNARK-based options can be found in Arnau's document [Anonymous voting in the Vochain without trusted-setup](https://hackmd.io/PkoDFcQyTkan4w9XIWzCDA).

<div class="c-row">
<div class="c-column">

#### Pros:
- Usable today
- Arbitrary functionality can be added by developers!
- Signature size : O(1)
- Verification time : O(circuit size) (preprocessing) + O(1)

</div>
<div class="c-column">

#### Cons:
- Proving time : O(polynomial in circuit size)
- Concretely has heavy proving and setup requirements -- not phone friendly
- May need MPC for trusted setup

</div>
</div>

<style>
.c-row{
background:#f0f0f0;
}
.c-row:after {
content: "";
display: table;
clear: both;
}
.c-column {
float: left;
width: 50%;
padding: 10px;
}

/* CSS hack to add section numbers to titles,
starting from h2.*/
/* Titles numbers */
.markdown-body h1 {counter-reset: h2}
.markdown-body h2 {counter-reset: h3}
.markdown-body h3 {counter-reset: h4}
.markdown-body h2:before {counter-increment: h2; content: counter(h2) ". "}
.markdown-body h3:before {counter-increment: h3; content: counter(h2) "." counter(h3) ". "}
.markdown-body h2.nocount:before, .markdown-body h3.nocount:before { markdown-body: ""; counter-increment: none }
.markdown-body h1:before, .markdown-body h2:before, .markdown-body h3:before {
color: #737373!important;
}

/* TOC numbers */
.toc ul li ul {
counter-reset: section;
list-style-type: none;
}
.toc ul li ul li::before {
color: #919191!important;
counter-increment: section;
content: counters(section, ".") " ";
}
</style>