Pattern matching encryption, strategic equivalence of range voting and approval voting, and statistical robustness of voting rules

We present new results in the areas of cryptography and voting systems. 1. Pattern matching encryption: We present new, general definitions for queryable encryption schemes - encryption schemes that allow evaluation of private queries on encrypted data without performing full decryption. We construct an efficient queryable encryption scheme supporting pattern matching queries, based on suffix trees. Storage and communication complexity are comparable to those for (unencrypted) suffix trees. The construction is based only on symmetric-key primitives, so it is practical. 2. Strategic equivalence of range voting and approval voting: We study strategic voting in the context of range voting in a formal model. We show that under general conditions, as the number of voters becomes large, strategic range-voting becomes equivalent to approval voting. We propose beta distributions as a new and interesting way to model voter's subjective information about other votes. 3. Statistical robustness of voting rules: We introduce a new notion called "statistical robustness" for voting rules: a voting rule is statistically robust if, for any profile of votes, the most likely winner of a sample of the profile is the winner of the complete profile. We show that plurality is the only interesting voting rule that is statistically robust; approval voting (perhaps surprisingly) and other common voting rules are not statistically robust.

Department dc:contributor.department

Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2013

Author dc:creator

• Shen, Emily (Emily Huei-Yi)

Advisor dc:contributor.advisor

• Ronald L. Rivest.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/79224

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/79224