Abstract
In state-of-the-art e-voting systems, a bulletin board (BB) is a critical component for preserving election integrity and availability. We introduce a framework for the formal security analysis of the BB functionality modeled as a distributed system. Our framework treats a secure BB as a robust public transaction ledger, defined by Garay et al. [Eurocrypt 2015], that additionally supports the generation of receipts for successful posting. Namely, in our model, a secure BB system achieves Persistence and Liveness that can be confirmable, in the sense that any malicious behavior can be detected via a verification mechanism.
As a case study for our framework, we analyze security guarantees and weaknesses of the BB system of [CSF 2014]. We demonstrate an attack revealing that the said system does not achieve Confirmable Liveness in our framework, even against covert adversaries. In addition, we show that special care should be taken for the choice of the underlying cryptographic primitives, so that the claimed fault tolerance threshold of N/3 out-of N corrupted IC peers is preserved.
Next, based on our analysis, we introduce a new BB protocol that upgrades the [CSF 2014] protocol. We prove that it tolerates any number less than N/3 out-of N corrupted IC peers both for Persistence and Confirmable Liveness, against a computationally bounded general Byzantine adversary. Furthermore, Persistence can also be Confirmable, if we distribute the AB (originally a centralized entity in [CSF 2014]) as a replicated service with honest majority.
This work was supported by the European Union’s Horizon 2020 research and innovation programme under grant agreements No. 653497 (project PANORAMIX) and No. 780477 (project PRIViLEDGE). Lipmaa and Siim were also supported by the Estonian Research Council grant (PRG49). Siim has been supported by European Regional Development Fund under the grant no. EU48684.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
E.g., if \(s_U\) is a signing key, then \(\mathsf {cr}_U\) could be a valid signature under \(s_U\); if \(s_U\) is a password, then \(\mathsf {cr}_U\) can be the pair \((U,s_U)\).
- 2.
Observe that it is safe for \(P_i\) to mark \(P_k\) as a malicious, since an honest \(P_k\) would neither send two non-\(\bot \) views for \(P_j\), nor accept an invalid signature from \(P_j\).
- 3.
The security of \(\mathsf {DS}\) ascertains \(P_i\) that with \(1-\mathsf {negl}(\kappa )\) probability, only if \(P_j\) is malicious, two non-equal records can be valid under \(P_j\)’s verification key. Thus, in case (C.2), \(P_i\) can safely fix the bit \(b_{i,j}\) to 0.
- 4.
Since there are \(N_c-t_c\ge t_c+1\) honest peers, \(P_i\) will obtain at least \(t_c+1\) all matching non-\(\bot \) views for every honest’ peers record (including its own). Thus, in case (R.3), \(P_i\) can safely fix \(b_{i,j}\) to 0 if it receives inconsistent non-\(\bot \) views or less than \(t_c+1\) matching non-\(\bot \) views for \(P_j\).
- 5.
In case (F.2), removal is a safe action for \(P_i\), as every honestly posted item for which a receipt has been generated, is stored in the records of at least \(N_c-2t_c\ge t_c+1\) honest peers during the Posting protocol. Thus, \(N_{i,p}(x)< t_c+1\) implies that either (i) (p, x) was maliciously posted, or (ii) a receipt for (p, x) was not generated.
References
Adida, B.: Helios: web-based open-audit voting. In: USENIX (2008)
Aumann, Y., Lindell, Y.: Security against covert adversaries: efficient protocols for realistic adversaries. J. Cryptol. 23(2), 281–343 (2010)
Benaloh, J.: Verifiable secret-ballot elections. Ph.D. thesis. Yale University (1987)
Benaloh, J., et al.: STAR-Vote: a secure, transparent, auditable, and reliable voting system. In: EVT/WOTE 2013 (2013)
Burton, C., et al.: Using Prêt à voter in Victoria state elections. In: EVT/WOTE (2012)
Burton, C., Culnane, C., Schneider, S.: vVote: verifiable electronic voting in practice. IEEE Secur. Priv. 14(4), 64–73 (2016)
Chaum, D.: SureVote: technical overview. In: WOTE (2001)
Chaum, D., et al.: Scantegrity: end-to-end voter-verifiable optical-scan voting. IEEE Secur. Priv. 6(3), 40–46 (2008)
Chaum, D., Ryan, P.Y.A., Schneider, S.: A practical voter-verifiable election scheme. In: di Vimercati, S.C., Syverson, P., Gollmann, D. (eds.) ESORICS 2005. LNCS, vol. 3679, pp. 118–139. Springer, Heidelberg (2005). https://doi.org/10.1007/11555827_8
Chondros, N., et al.: D-DEMOS: a distributed, end-to-end verifiable, internet voting system. In: ICDCS (2016)
Cramer, R., Gennaro, R., Schoenmakers, B.: A secure and optimally efficient multi-authority election scheme. In: EUROCRYPT, pp. 103–118 (1997)
Culnane, C., Ryan, P.Y.A., Schneider, S.A., Teague, V.: vVote: a verifiable voting system. ACM Trans. Inf. Syst. Secur. 18(1), 3:1–3:30 (2015)
Culnane, C., Schneider, S.: A peered bulletin board for robust use in verifiable voting systems. CoRR abs/1401.4151 (2014)
Culnane, C., Schneider, S.A.: A peered bulletin board for robust use in verifiable voting systems. In: CSF (2014)
Dini, G.: A secure and available electronic voting service for a large-scale distributed system. Future Gener. Comput. Syst. 19(1), 69–85 (2003)
Dwork, C., Lynch, N., Stockmeyer, L.: Consensus in the presence of partial synchrony. J. ACM 35(2), 288–323 (1988)
Fujioka, A., Okamoto, T., Ohta, K.: A practical secret voting scheme for large scale elections. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 244–251. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-57220-1_66
Garay, J., Kiayias, A., Leonardos, N.: The bitcoin backbone protocol: analysis and applications. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 281–310. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_10
Gennaro, R., Jarecki, S., Krawczyk, H., Rabin, T.: Robust and efficient sharing of RSA functions. In: Koblitz, N. (ed.) CRYPTO 1996. LNCS, vol. 1109, pp. 157–172. Springer, Heidelberg (1996). https://doi.org/10.1007/3-540-68697-5_13
Hauser, S., Haenni, R.: A generic interface for the public bulletin board used in UniVote. In: CeDEM (2016)
Heather, J., Lundin, D.: The append-only web bulletin board. In: Degano, P., Guttman, J., Martinelli, F. (eds.) FAST 2008. LNCS, vol. 5491, pp. 242–256. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-01465-9_16
Heiberg, S., Willemson, J.: Verifiable internet voting in Estonia. In: EVOTE (2014)
Juels, A., Catalano, D., Jakobsson, M.: Coercion-resistant electronic elections. In: WPES (2005)
Kiayias, A., Kuldmaa, A., Lipmaa, H., Siim, J., Zacharias, T.: On the security properties of e-voting bulletin boards. Cryptology ePrint Archive, Report 2018/567 (2018)
Kiayias, A., Zacharias, T., Zhang, B.: End-to-end verifiable elections in the standard model. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 468–498. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_16
Krummenacher, R.: Implementation of a web bulletin board for e-voting applications. Institute for Internet Technologies and Applications (2010)
Lynch, N.A.: Distributed Algorithms. Morgan Kaufmann, Burlington (1996)
Peters, R.A.: A secure bulletin board. Master’s thesis. Eindhoven UT (2005)
Reiter, M.K.: The Rampart toolkit for building high-integrity services. In: Birman, K.P., Mattern, F., Schiper, A. (eds.) Theory and Practice in Distributed Systems. LNCS, vol. 938, pp. 99–110. Springer, Heidelberg (1995). https://doi.org/10.1007/3-540-60042-6_7
Sandler, D., Wallach, D.S.: Casting votes in the auditorium. In: EVT (2007)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Kiayias, A., Kuldmaa, A., Lipmaa, H., Siim, J., Zacharias, T. (2018). On the Security Properties of e-Voting Bulletin Boards. In: Catalano, D., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2018. Lecture Notes in Computer Science(), vol 11035. Springer, Cham. https://doi.org/10.1007/978-3-319-98113-0_27
Download citation
DOI: https://doi.org/10.1007/978-3-319-98113-0_27
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-98112-3
Online ISBN: 978-3-319-98113-0
eBook Packages: Computer ScienceComputer Science (R0)