Recently, Kiayias, Zacharias and Zhang-proposed a new E2E verifiable e-voting system called 'DEMOS' that for the first time provides E2E verifiability without relying on external sources of randomness or the random oracle model; the main advantage of such system is in the fact that election auditors need only the election transcript and the feedback from the voters to pronounce the election process unequivocally valid. Unfortunately, DEMOS comes with a huge performance and storage penalty for the election authority (EA) compared to other e-voting systems such as Helios. The main reason is that due to the way the EA forms the proof of the tally result, it is required to {\em precompute} a number of ciphertexts for each voter and each possible choice of the voter. This approach clearly does not scale to elections that have a complex ballot and voters have an exponential number of ways to vote in the number of candidates. The performance penalty on the EA appears to be intrinsic to the approach: voters cannot compute an enciphered ballot themselves because there seems to be no way for them to prove that it is a valid ciphertext.

In contrast to the above, in this work, we construct a new e-voting system that retains the strong E2E characteristics of DEMOS (but against computational adversaries) while completely eliminating the performance and storage penalty of the EA. We achieve this via a new cryptographic construction that has the EA produce and prove, using voters' coins, the security of a common reference string (CRS) that voters subsequently can use to affix non-interactive zero-knowledge (NIZK) proofs to their ciphertexts. The EA itself uses the CRS to prove via a NIZK the tally correctness at the end. Our construction has similar performance to Helios and is practical. The privacy of our construction relies on the SXDH assumption over bilinear groups via complexity leveraging.