A hash is a one-way (hard to invert) function $H$ which can take an input of any size and produce a fixed-size output. Typical requirements for good hash functions are:
• Pre-image resistance: given $H(A)$, it is very difficult to find $A$.
• Second pre-image resistance: given $A$, it is very difficult to find $B\neq A$ such that $H(A)=H(B)$.
• Collision resistance: it is very difficult to find $A, B$, with $A\neq B$, such that $H(A) = H(B)$.
Alice wishes to vote in an upcoming election for which there are just two voting options. She can securely share a verification value with the voting authority in advance but will be voting over an untrustworthy channel.
Consider the following voting scheme based on a hash function $H$.
• Alice chooses two secret keys, $s_1$ and $s_2$.
• Alice generates the verification value $H(H(s_1)||H(s_2))$. This value is shared with the voting authority in advance of the election.
• If Alice wishes to vote ‘yes’ she sends $(s_1, H(s_2))$; if she wishes to vote ‘no’ she sends $(H(s_1), s_2)$.
Note that the symbol || is used to denote the concatenation of two values.
a. i) How does the authority determine how Alice voted?
ii) Why are the secret keys used in this voting scheme one-time use only?
iii) Justify why an adversary cannot change Alice’s vote.
b. Without increasing the number of secret keys nor increasing the size of the verification value, how can you generalise this scheme to voting for one of $8$ options? Justify why an adversary still cannot change Alice’s vote in your proposed scheme.
c. Discuss whether the property of second pre-image resistance is required in the choice of $H$ for this voting scheme.
Let $v = H(H(s_1) \| H(s_2))$ denote the verification value, and let $(c_1, c_2)$ be what Alice sends to the authority, i.e., $c_1 = s_1$ and $c_2 = H(s_2)$ if she intends to vote yes and $c_1 = H(s_1)$ and $c_2 = s_2$ if she intends to vote no.
(a)
(i) If Alice votes yes, then $v = H(H(c_1) \| c_2)$, otherwise $v \neq H(H(c_1) \| c_2)$. If Alice votes no, then $v = H(c_1 \| H(c_2))$, otherwise $v \neq H(c_1 \| H(c_2))$. By checking these equations ($v, c_1, c_2$ are given to the authority and $H$ is a public function), the authority can establish which of the two votes Alice intended, or whether she sent some random garbage values $c_1, c_2$ to the authority (if neither equation checks out).
(ii) As either $c_1 = s_1$ or $c_2 = s_2$, and $c_1, c_2$ are sent in the clear to the authority, the authority learns one of the two secret keys, which is not what you want for long-term secret keys... For instance, if you'd use the same $v, s_1, s_2$ for the next election, then the authority could forge Alice's vote by copying the $(c_1, c_2)$ she sent in the first election as her vote for the second election, so that if she voted yes in the first election, the authority can guarantee she also votes yes in the next election.
(iii) To change from yes to no say, he has to find $(c_1', c_2')$ such that $v = H(c_1'\|H(c_2')) = H(H(s_1) \| H(s_2))$, given $(c_1, c_2) = (s_1, H(s_2))$. By pre-image resistance, the adversary cannot find any other value $r$ such that $H(r) = v = H(c_1'\|H(c_2'))$ so he must find the intended preimage: $c_1' = H(s_1)$ and $H(c_2') = H(s_2)$. The adversary knows $c_1 = s_1$ so the first part is easy - he can find $c_1'$ by hashing $c_1$. But again, for the second part he must find a $c_2'$ such that $H(c_2') = H(s_2)$. Pre-image resistance again says that $c_2'$ must equal $s_2$, which is a value that the adversary does not know (he only knows $H(s_2)$). So the adversary cannot change the vote from yes to no (or vice versa), because computing $s_2$ from $H(s_2)$ breaks pre-image resistance.
(b)
Try $v = H(H(s_1) \| \dots \| H(s_8))$ and voting $(c_1, \dots, c_8)$ where $c_i = H(s_i)$ for $i \neq j$ and $c_j = s_j$ if the user wants to vote $j \in \{1, \dots, 8\}$.
(c)
At first sight I don't see how non-second-pre-image-resistance would help an adversary to cheat here, but I might be missing something.
By the way, this voting scheme lacks several other useful properties. If the votes and verification values are not public, the adversary can just deny having received Alice's vote, or publish something else as her vote. If they are public, then anyone can verify what Alice voted. If they are public but anonymous, then the scheme has to be adapted first to guarantee anonymity for the voters, and there is no way to tell whether the authority stuffed the ballot box.