For an electronic election to be fully democratic there is a need for security mechanisms that will assure the privacy of the voters. With receipt-free electronic voting, a voter neither obtains nor is able to construct a receipt proving the content of her vote. In this paper we first consider the minimal requirements for receipt-free elections, without untappable communication channels between the voter and the voting authorities. We then propose a solution, which satisfies these requirements. This solution is based on an encryption blackbox, which uses its own randomness. Finally we present an implementation with smartcards, suitable for Internet voting. Electronic democracy refers to the use of Information & Communication Technologies (ICT) for communication between the politicians and citizens. In a representative democratic system, electronic elections (e-voting) constitute an important tool, which, if designed carefully, will strengthen the democratic substance of e-government. For an electronic election to be fully democratic, there is a need for security mechanisms that will assure the privacy of the vote. In traditional elections, a voting booth does more than allow voters to keep their vote secret: it prevents vote-selling and coercion. Preventing such abuses in electronic voting schemes has been the subject of recent research. The notions of receipt-freeness and uncoercibility for electronic voting were introduced by Benaloh [1] . With the former the voters are convinced that their vote is counted without getting a receipt. With the latter the voters are not able to convince any other participant (e.g. a coercer) of the value of their vote. More specifically, in an 2 Emmanouil Magkos, Mike Burmester and Vassilis Chrissikopoulos uncoercible voting scheme a voter neither obtains nor is able to construct a receipt that proves the content of her vote. While the concept of uncoercibility is stronger than receipt-freeness, the term "receipt-freeness" has been used in the literature as the prevalent expression to denote the security resulted by both the receipt-freeness and uncoercibility criterions. Most electronic voting schemes sacrifice receipt-freeness at the cost of establishing correctness for the election results. In these schemes, voters get a receipt that will help them check the final tally. Note that this useful property, also known as atomic verifiability, is not met in current physical-based elections. An even more desirable property for electronic elections is universal verifiability (e.g. see [8] ), which not only permits the voter to verify that the vote has been counted correctly, but also gives voters the means to verify that the election tally actually represents the "sum" of the votes cast. Current research is focused on receipt-free schemes that also establish universal verifiability. All the receipt-free schemes [1] [2] [3] [4] [5] [6] [7] in the literature make some basic assumptions about the communication channel between the voter and the election authorities and about the voting process. These assumptions can be modelled by the following primitives: -An untappable channel, from the voter to the voting authority [5, 6] . This channel models a one-way physical apparatus by which the voter can send a message to the authority. This message will be perfectly secret to all other parties (including the coercer). -An untappable channel, from the voting authority to the voter [2, 3, 4] . This channel models a one-way physical apparatus, used by the voting authority to send a message to the voter. This message will be perfectly secret to all other parties (including the coercer). -A voting booth, in which the voter casts the vote [1, 7] . This models a physical booth and guarantees the secrecy of the communication between the voting authority and the voter. Several authors in the literature have pointed out the difficulty of implementing untappable channels. Hirst and Sako have recently stated that [4] , "untappable channels from the authorities to the voters are the weakest physical assumption for receipt-freeness". Such channels can also be quite cumbersome, particularly for large-scale voting with geographically distributed voters. For example, voters who abstain from elections because they find it inconvenient to go the polls, will find it equally inconvenient to cast their vote from a physically isolated voting booth in a dedicated computer network. Note that untappable channels will also force the voter to use specified voting locations. Contribution/Organization. In this paper, we consider receipt-freeness in the presence of a coercer that can tap communication lines. In Section 2 we first define the minimal requirements for receipt-freeness and show that it can be achieved only 3 if the voter does not use any secret information, other than the vote itself. In Section 3 we propose a solution which uses an encryption blackbox to encrypt the votes in a verifiable way. Receipt-freeness is based on the difficulty of tampering with the blackbox. In Section 4 we present an implementation with a tamper-resistant smartcard, where receipt-freeness is achieved by distributing the voting procedure between the voter and the smartcard. This implementation is based on the voting scheme of Cramer-Gennaro-Schoenmakers [8] , and is suitable for PCs and the Internet. Section 5 concludes the paper. Receipt-freeness in Large-scale Elections without Untappable Channels Below we define the minimal requirements for an election scheme to be receiptfree without any assumptions on the untappability of the communication channels between the voter and the voting authorities. It is clear that the vote should be encrypted, to achieve vote secrecy (private channel). Moreover, there should be an authenticated communication channel, which only the voter (and not the coercer) uses to submit the encrypted vote to the voting authorities. The control over this channel should at least involve a secret key that only the voter possesses. This could be for example a secret signature key or a biometric. If the secret decryption key is in the possession of the voter (as in [5, 6] ), then receipt-freeness is lost: the key together with the encrypted vote (which the coercer can get by tapping the communication line) is a receipt. So the voter must not know the secret decryption key.
A scheme by Magkos et al. relies on a tamper resistant smart card which collaborates with the voter to produce a valid encryption of her vote REF but requires significant voter participation.
Receipt-Freeness in Large-Scale Elections without Untappable Channels
I3E
Business Computer Science