Trapdoor Privacy in Asymmetric Searchable Encryption Schemes

in Progress in Cryptology -- AFRICACRYPT 2014, Marrakesh 28-30 May 2014 (2014)

Asymmetric searchable encryption allows searches to be carried over ciphertexts, through delegation, and by means of trapdoors issued by the owner of the data. Public Key Encryption with Keyword Search ... [more ▼]

Asymmetric searchable encryption allows searches to be carried over ciphertexts, through delegation, and by means of trapdoors issued by the owner of the data. Public Key Encryption with Keyword Search (PEKS) is a primitive with such functionality that provides delegation of exact-match searches. As it is important that ciphertexts preserve data privacy, it is also important that trapdoors do not expose the user’s search criteria. The difficulty of formalizing a security model for trapdoor privacy lies in the verification functionality, which gives the adversary the power of verifying if a trapdoor encodes a particular keyword. In this paper, we provide a broader view on what can be achieved regarding trapdoor privacy in asymmetric searchable encryption schemes, and bridge the gap between previous definitions, which give limited privacy guarantees in practice against search patterns. We propose the notion of Strong Search Pattern Privacy for PEKS and construct a scheme that achieves this security notion. [less ▲]

Privacy and Security in an Age of Surveillance

in Dagstuhl Reports (2014), 4(9), 106-123

The Snowden revelations have demonstrated that the US and other nations are amassing data about people's lives at an unprecedented scale. Furthermore, these revelations have shown that intelligence ... [more ▼]

The Snowden revelations have demonstrated that the US and other nations are amassing data about people's lives at an unprecedented scale. Furthermore, these revelations have shown that intelligence agencies are not only pursuing passive surveillance over the world's communication systems, but are also seeking to facilitate such surveillance by undermining the security of the internet and communications technologies. Thus the activities of these agencies threatens not only the rights of individual citizens but also the fabric of democratic society. Intelligence services do have a useful role to play in protecting society and for this need the capabilities and authority to perform targeted surveillance. But the scope of such surveillance must be strictly limited by an understanding of its costs as well as benefits, and it should not impinge on the privacy rights of citizens any more than necessary. Here we report on a recent Dagstuhl Perspectives Workshop addressing these issues - a four-day gathering of experts from multiple disciplines connected with privacy and security. The meeting explored the scope of mass-surveillance and the deliberate undermining of the security of the internet, defined basic principles that should underlie needed reforms, and discussed the potential for technical, legal and regulatory means to help restore the security of the internet and stem infringement of human-rights by ubiquitous electronic surveillance. [less ▲]

DoubleMod and SingleMod: Simple Randomized Secret-Key Encryption with Bounded Homomorphicity

in IACR Cryptology ePrint Archive (2014)

An encryption relation f Z Z with decryption function f 􀀀1 is “group-homomorphic” if, for any suitable plaintexts x1 and x2, x1+x2 = f 􀀀1( f (x1)+f (x2)). It is “ring-homomorphic” if furthermore x1x2 ... [more ▼]

An encryption relation f Z Z with decryption function f 􀀀1 is “group-homomorphic” if, for any suitable plaintexts x1 and x2, x1+x2 = f 􀀀1( f (x1)+f (x2)). It is “ring-homomorphic” if furthermore x1x2 = f 􀀀1( f (x1) f (x2)); it is “field-homomorphic” if furthermore 1=x1 = f 􀀀1( f (1=x1)). Such relations would support oblivious processing of encrypted data. We propose a simple randomized encryption relation f over the integers, called DoubleMod, which is “bounded ring-homomorphic” or what some call ”somewhat homomorphic.” Here, “bounded” means that the number of additions and multiplications that can be performed, while not allowing the encrypted values to go out of range, is limited (any pre-specified bound on the operation-count can be accommodated). Let R be any large integer. For any plaintext x 2 ZR, DoubleMod encrypts x as f (x) = x + au + bv, where a and b are randomly chosen integers in some appropriate interval, while (u; v) is the secret key. Here u > R2 is a large prime and the smallest prime factor of v exceeds u. With knowledge of the key, but not of a and b, the receiver decrypts the ciphertext by computing f 􀀀1(y) = (y mod v) mod u. DoubleMod generalizes an independent idea of van Dijk et al. 2010. We present and refine a new CCA1 chosen-ciphertext attack that finds the secret key of both systems (ours and van Dijk et al.’s) in linear time in the bit length of the security parameter. Under a known-plaintext attack, breaking DoubleMod is at most as hard as solving the Approximate GCD (AGCD) problem. The complexity of AGCD is not known. We also introduce the SingleMod field-homomorphic cryptosystems. The simplest SingleMod system based on the integers can be broken trivially. We had hoped, that if SingleMod is implemented inside non-Euclidean quadratic or higher-order fields with large discriminants, where GCD computations appear di cult, it may be feasible to achieve a desired level of security. We show, however, that a variation of our chosen-ciphertext attack works against SingleMod even in non-Euclidean fields. [less ▲]

Proving Prêt à Voter Receipt Free Using Computational Security Models

in USENIX Journal of Election Technology and Systems (2013), 1(1), 62-81

Pret a Voter is a supervised, end-to-end verifiable voting scheme. Informal analyses indicate that, subject to certain assumptions, Pret a Voter is receipt free, i.e. a voter has no way to construct a ... [more ▼]

Pret a Voter is a supervised, end-to-end verifiable voting scheme. Informal analyses indicate that, subject to certain assumptions, Pret a Voter is receipt free, i.e. a voter has no way to construct a proof to a coercer of how she voted. In this paper we propose a variant of Pret a Voter and prove receipt freeness of this scheme using computational methods. Our proof shows that if there exists an adversary that breaks receipt freeness of the scheme then there exists an adversary that breaks the IND-CCA2 security of the Naor-Yung encryption scheme. We propose a security model that defines receipt freeness based on the indistinguishability of receipts. We show that in order to simulate the game we require an IND-CCA2 encryption scheme to create the ballots and receipts. We show that, within our model, a non-malleable onion is sufficient to guarantee receipt freeness. Most of the existing Pret a Voter schemes do not employ IND-CCA2 encryption in the construction of the ballots, but they avoid such attacks by various additional mechanisms such as pre-commitment of ballot material to the bulletin board, digitally signed ballots etc. Our use of the Naor-Yung transformation provides the IND-CCA2 security required. [less ▲]

Enhancements to prepare-and-measure based QKD protocols

in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (2013)

We propose some simple changes to a class of Quantum Key Distribution protocols. The first enhancement ensures early detection of any attempted Man-in-the-Middle attack and results in less leakage of key ... [more ▼]

We propose some simple changes to a class of Quantum Key Distribution protocols. The first enhancement ensures early detection of any attempted Man-in-the-Middle attack and results in less leakage of key material to any eavesdropping attacker. We argue that this version is at least as secure as the original BB'84 scheme, but ensures a closer binding of the key establishment and authentication components of the protocol. Further proposed enhancements lead to a doubling of the key rate, but the security arguments become more delicate. We also touch on the need to enhance the models used to analyze both the classical and quantum aspects of QKD protocols. This is prompted by the observation that existing analyses treat the quantum (key-establishment) and classical (authentication etc) phases separately and then combine them in a simple-minded fashion. [less ▲]

Verifiable postal voting

in Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (2013)

This proposal aims to combine the best properties of paper-based and end-to-end verifiable remote voting systems. Ballots are delivered electronically to voters, who return their votes on paper together ... [more ▼]

This proposal aims to combine the best properties of paper-based and end-to-end verifiable remote voting systems. Ballots are delivered electronically to voters, who return their votes on paper together with some cryptographic information that allows them to verify later that their votes were correctly included and counted. We emphasise the ease of the voter's experience, which is not much harder than basic electronic delivery and postal returns. A typical voter needs only to perform a simple check that the human-readable printout reflects the intended vote. The only extra work is adding some cryptographic information into the same envelope as the human-readable vote. The proposed scheme is not strictly end-to-end verifiable, because it depends on procedural assumptions at the point where the ballots are received. These procedures should be public and could be enforced by a group of observers, but are not publicly verifiable afterwards by observers who were absent at the time. [less ▲]

Verifiable Voting Systems

in Computer and Information Security Handbook (2013)

The introduction of technology into voting systems can bring a number of benefits, such as improving accessibility, remote voting, and efficient, accurate processing of votes. A voting system that uses ... [more ▼]

The introduction of technology into voting systems can bring a number of benefits, such as improving accessibility, remote voting, and efficient, accurate processing of votes. A voting system that uses electronic technology in any part of processing the votes, from vote capture and transfer through to vote tallying, is known as an e-voting system. In addition to the undoubted benefits, the introduction of such technology introduces particular security challenges, some of which are unique to voting systems because of their specific nature and requirements. The key role that voting systems play in democratic elections means that such systems must not only be secure and trustworthy, but must be seen by the electorate to be secure and trustworthy. This chapter emphasizes the challenge to reconcile the secrecy of the ballot, with demonstrable correctness of the result. © 2013 Copyright © 2013 Elsevier Inc. All rights reserved. [less ▲]

Faster print on demand for Prêt à Voter

in USENIX Journal of Election Technology and Systems (JETS) (2013), 2(1),

Printing Pret a Voter ballots on demand is desirable both for convenience and security. It allows a polling station to serve numerous different ballots, and it avoids many problems associated with the ... [more ▼]

Printing Pret a Voter ballots on demand is desirable both for convenience and security. It allows a polling station to serve numerous different ballots, and it avoids many problems associated with the custody of the printouts. This paper describes a new proposal for printing Pret a Voter ballots on demand. The emphasis is on computational efficiency suitable for real elections, and on very general ballot types. [less ▲]

Testing Voters' Understanding of a Security Mechanism Used in Verifiable Voting

in 53 USENIX Journal of Election Technology and Systems (JETS) (2013), 1(1), 53-61

Proposals for a secure voting technology can involve new mechanisms or procedures designed to provide greater ballot secrecy or verifiability. These mechanisms may be justified on the technical level, but ... [more ▼]

Proposals for a secure voting technology can involve new mechanisms or procedures designed to provide greater ballot secrecy or verifiability. These mechanisms may be justified on the technical level, but researchers and voting officials must also consider how voters will understand these technical details, and how understanding may affect interaction with the voting systems. In the context of verifiable voting, there is an additional impetus for this consideration as voters are provided with an additional choice; whether or not to verify their ballot. It is possible that differences in voter understanding of the voting technology or verification mechanism may drive differences in voter behaviour; particularly at the point of verification. In the event that voter understanding partially explains voter decisions to verify their ballot, then variance in voter understanding will lead to predictable differences in the way voters interact with the voting technology. This paper describes an experiment designed to test voters’ understanding of the ‘split ballot’, a particular mechanism at the heart of the secure voting system Prˆet `a Voter, used to provide both vote secrecy and voter verifiability. We used a controlled laboratory experiment in which voter behaviour in the experiment is dependent on their understanding of the secrecy mechanism for ballots. We found that a two-thirds majority of the participants expressed a confident comprehension of the secrecy of their ballot; indicating an appropriate level of understanding. Among the remaining third of participants, most exhibited a behaviour indicating a comprehension of the security mechanism, but were less confident in their understanding. A small number did not comprehend the system. We discuss the implications of this finding for the deployment of such voting systems. [less ▲]

A Fair and Robust Voting System by Broadcast

in Lecture Notes in Informatics (2012)

Hao, Ryan, and Zieliński (2010) propose a two-round decentralized voting protocol that is efficient in terms of rounds, computation, and bandwidth. However, the protocol has two drawbacks. First, if some ... [more ▼]

Hao, Ryan, and Zieliński (2010) propose a two-round decentralized voting protocol that is efficient in terms of rounds, computation, and bandwidth. However, the protocol has two drawbacks. First, if some voters abort then the election result cannot be announced, that is, the protocol is not robust. Secondly, the last voter can learn the election result before voting, that is, the protocol is not fair. Both drawbacks are typical of other decentralized e-voting protocols. This paper proposes a recovery round to enable the election result to be announced if voters abort, and we add a commitment round to ensure fairness. In addition, we provide a computational security proof of ballot secrecy. [less ▲]