Key Agreement Against Quantum Adversaries

Key agreement is a cryptographic scenario between two legitimate parties, who need to establish a common secret key over a public authenticated channel, and an eavesdropper who intercepts all their messages in order to learn the secret. We consider query complexity in which we count only the number of evaluations (queries) of a given black-box function, and classical communication channels. Ralph Merkle provided the first unclassified scheme for secure communications over insecure channels. When legitimate parties are willing to ask O(N) queries for some parameter N, any classical eavesdropper needs Omega(N^2) queries before being able to learn their secret, which is is optimal. However, a quantum eavesdropper can break this scheme in O(N) queries. Furthermore, it was conjectured that any scheme, in which legitimate parties are classical, could be broken in O(N) quantum queries. In this thesis, we introduce protocols à la Merkle that fall into two categories. When legitimate parties are restricted to use classical computers, we offer the first secure classical scheme. It requires Omega(N^{13/12}) queries of a quantum eavesdropper to learn the secret. We give another protocol having security of Omega(N^{7/6}) queries. Furthermore, for any k>= 2, we introduce a classical protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1/2+k/{k+1}}) queries, approaching Theta(N^{3/2}) when k increases. When legitimate parties are provided with quantum computers, we present two quantum protocols improving on the best known scheme before this work. Furthermore, for any k>= 2, we give a quantum protocol in which legitimate parties establish a secret in O(N) queries while the optimal quantum eavesdropping strategy requires Theta(N^{1+{k}/{k+1}})} queries, approaching Theta(N^{2}) when k increases.

Agendas in legislative decision-making

Despite the wide range of agendas used in legislative decision-making, the literature has focused almost exclusively on two stylized formats, the so-called Euro-Latin and Anglo-American agendas. As emphasized by Ordeshook and Schwartz [1987], this focus leaves a sizable gap in our understanding of the legislative process. To help address the deficiency, I first define a very broad class of agendas (called simple agendas) whose features are common among agendas used in legislative settings. I then characterize the sophisticated (Farquharson [1969]) voting outcomes implemented by agendas in this class. By establishing a clear connection between the structure of simple agendas and the outcomes associated with them, the characterization extends our understanding of legislative decision-making well beyond the very limited scope of Euro-Latin and Anglo-American agendas.