Parameters Generation

• Registration authority \(A\) generates the keys \(\text{Reg}sk = X\) and \(\text{Reg}pk = ([A\ B\ C\ 1], u)\) by running \(\text{SKeyGen}(1^\lambda)\) with \(u \xleftarrow{\$} \mathcal{R}_q\).

  It also generates a keypair for the blind signature scheme by running \((\text{RegS}sk, \text{RegS}pk) \leftarrow \text{BSGen}(1^\lambda)\).

• Couting authority \(C\) generates the keys \(\text{Count}sk\), \(\text{Count}pk\) by running \(\text{EKeyGen}(1^\lambda)\).
• Collection authority \(D\) generates the keys \(\text{Coll}sk\), \(\text{Coll}pk\) by running \(\text{EKeyGen}(1^\lambda)\).

User Registration

To register, a user with identity \(m \in \mathcal{U}\) first generates a vote token \(x \xleftarrow{\$} \mathcal{X}\). After interaction with the user, registration authority \(A\):

• signs user identity by running \((1, [S\ ;\ 0], 1) \leftarrow \text{Sign}(\text{Reg}sk, m)\)
• blindly signs their vote token by running \(st \leftarrow \text{BSSign}(\text{RegS}sk, x)\).

\(A\) sends back \((S, st)\) to user \(m\), and store identity \(m\) in memory.

User Vote

Assume some verified user with identity \(m \in \mathcal{U}\), signature \(S\) on \(m\), vote \(v\), and vote token \((x, st)\) wants to submit their vote.

The user first generates a one-time signature key pair \((sk, vk) \leftarrow \text{OTSGen}(1^\lambda)\). Then she commits to her identity by computing \(F = b^{-1}(C + mG + E)\).

By construction, we have:

\[\begin{aligned} \begin{bmatrix} A & B & F & 1 \end{bmatrix} \begin{bmatrix} S_1 \\ S_2 \\ bS_3 \\ -E S_3 \end{bmatrix} = u \mod q \end{aligned}\]

The user creates a relaxed NIZK proof \(\Pi_0\) of knowledge of a signature on the committed identity. The proof is made non-interactive with the usual Fiat-Shamir transform, while also using the one-time signature verification key \(vk\) in the hash.

By construction, we also have:

\[\begin{aligned} \begin{bmatrix} G^\T & F^\T & I_m \end{bmatrix} \begin{bmatrix} m \\ -b \\ E^\T \end{bmatrix} = -C^\T \end{aligned}\]

As in the group-signature scheme proposed by Boschini et al, the user uses the verifiable partial encryption scheme to encrypt witness \(w = (m, [-b; E^\T], 1)\) with \(x = ([G^\T\ F^\T\ \mathbb{I}_m], -C^\T)\) by running \(\text{Enc}(\text{Coll}_{pk}, x, w, v_k)\).

The user obtains a ciphertext \(t = (v_1, w_1, v_2, w_2)\) and proof \(\pi = (\Pi_1, \Pi_2)\).

At this point the user can prove that:

• she is verified and allowed to vote. (\(\Pi_0\))
• she has encrypted the identity she just committed to. (\(\Pi_1\), \(\Pi_2\))

Now we simply encrypt her vote using a generic lattice-based encryption scheme, giving us the ciphertext \(t' \leftarrow \text{Enc}'(\text{Count}_{pk}, v)\).

Then the user signs everything with the one-time signature scheme:

\[ots \leftarrow \text{OTSSign}(s_k, (A, B, F, u, \Pi_0, t, (\Pi_1, \Pi_2), t')\]

Finally, the user sends \((F, x, st, \Pi_0, t, (\Pi_1, \Pi_2), t', v_k, ots)\) to the filtering authority \(B\).

Vote Submission Check

Upon reception of \((F, \Pi_0, t, (\Pi_1, \Pi_2), t', v_k, ots)\) from a user, the filtering authority \(B\) goes through the following steps:

1. Check that the vote token \(x\) was never used and that \(st\) is a valid signature on \(x\):

   \[\text{BSVf}(\text{RegS}pk, st, x) = 1\]

2. Check that the one-time signature is indeed valid

   \[\text{OTSVf}(v_k, (A, B, F, u, \Pi_0, t, (\Pi_1, \Pi_2), t'), ots) = 1\]

3. Check the NIZK proof \(\Pi_0\) that the user is allowed to vote, and that \(v_k\) was used in the Fiat-Shamir transform (to make sure that the proof was generated for this submission only).

4. Check the identity encryption proof

   \[\text{EVerify}(\text{Coll}_{pk}, ([G^\T\ F^\T, \mathbb{I}_m], -C^\T), t, \pi, v_k) = 1\]

If all these checks succeed, then filtering authority sends the encrypted identity to the collection authority, and send the encrypted vote to the counting authority.

It stores in memory the vote token \(x\) to prevent users for submitting their vote multiple times.