CSAIL Event Calendar

Thesis Defense:Pattern Matching Encryption, Strategic Equivalence of Range Voting and Approval Voting, and Statistical Robustness of Voting Rules

Thesis Defense: Pattern Matching Encryption, Strategic Equivalence of Range Voting and Approval Voting, and Statistical Robustness of Voting Rules

Abstract:
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
(substring search) queries, based on suffix trees. Encryption time
and ciphertext size are O(\lambda n), and querying time is O(\lambda m
+ k), where \lambda is the security parameter, n is the length of the
encrypted string, m is the length of the search string, and k is the
number of occurrences. Querying takes a small constant number of
rounds of communication. The construction is practical, as it is
based only on symmetric key primitives.

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. We show that
when using beta distributions, perhaps surprisingly, a strategic range
voter's best vote is not always a sincere one.

3. Statistical robustness of voting rules:
We introduce a new notion called "statistical robustness" for voting
rules, which says that 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.

See other events happening in January 2013