An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

End-to-end verifiable election systems (E2E systems) provide a provably correct tally while maintaining the secrecy of each voter's ballot, even if the voter is complicit in demonstrating how they voted. Providing voter incoercibility is one of the main challenges of designing E2E systems, particularly in the case of internet voting. A second challenge is building deployable, human-voteable E2E systems that conform to election laws and conventions. This dissertation examines deployability, coercion-resistance, and their intersection in election systems. In the course of this study, we introduce three new election systems, (Scantegrity, Eperio, and Selections), report on two real-world elections using E2E systems (Punchscan and Scantegrity), and study incoercibility issues in one deployed system (Punchscan). In addition, we propose and study new practical primitives for random beacons, secret printing, and panic passwords. These are tools that can be used in an election to, respectively, generate publicly verifiable random numbers, distribute the printing of secrets between non-colluding printers, and to covertly signal duress during authentication. While developed to solve specific problems in deployable and incoercible E2E systems, these techniques may be of independent interest.

One of the most fascinating recent developments in research has been how different disciplines have become more and more interconnected. So much so that fields as disparate as information theory and fundamental physics have combined to produce ideas for the next generation of computing and secure information technologies, both of which have far reaching consequences. For more than fifty years Moore's law, which describes the trend of the transistor's size shrinking by half every two years, has proven to be uncannily accurate. However, the computing industry is now approaching a fundamental barrier as the size of a transistor approaches that of an individual atom and the laws of physics and quantum mechanics take over. Rather then look at this as the end, quantum information science has emerged to ask the question of what additional power and functionality might be realized by harnessing some of these quantum effects. This thesis presents work on the sub-field of quantum cryptography which seeks to use quantum means in order to assure the security of ones communications. The beauty of quantum cryptographic methods are that they can be proven secure, now and indefinitely into the future, relying solely on the validity of the laws of physics for their proofs of security. This is something which is impossible for nearly all current classical cryptographic methods to claim. The thesis begins by examining the first implementation of an entangled quantum key distribution system over two free-space optical links. This system represents the first test-bed of its kind in the world and while its practical importance in terrestrial applications is limited to a smaller university or corporate campus, the system mimics the setup for an entangled satellite system aiding in the study of distributing entangled photons from an orbiting satellite to two earthbound receivers. Having completed the construction of a second free-space link and the automation of the alignment system, I securely distribute keys to Alice and Bob in two distant locations separated by 1,575 m with no direct line-of-sight between them. I examine all of the assumptions necessary for my claims of security, something which is particularly important for moving these systems out of the lab and into commercial industry. I then go on to describe the free-space channel over which the photons are sent and the implementation of each of the major system components. I close with a discussion of the experiment which saw raw detected entangled photon rates of 565 s^{-1} and a quantum bit error rate (QBER) of 4.92% resulting in a final secure key rate of 85 bits/s. Over the six hour night time experiment I was able to generate 1,612,239 bits of secure key. With a successful QKD experiment completed, this thesis then turns to the problem of improving the technology to make it more practical by increasing the key rate of the system and thus the speed at which it can securely encrypt information. It does so in three different ways, involving each of the major disciplines comprising the system: measurement hardware, source technology, and software post-processing. First, I experimentally investigate a theoretical proposal for biasing the measurement bases in the QKD system showing a 79% improvement in the secret key generated from the same raw key rates. Next, I construct a second generation entangled photon source with rates two orders of magnitude higher than the previous source using the idea of a Sagnac interferometer. More importantly, the new source has a QBER as low as 0.93% which is not only important for the security of the QKD system but will be required for the implementation of a new cryptographic primitive later. Lastly, I study the free-space link transmission statistics and the use of a signal-to-noise ratio (SNR) filter to improve the key rate by 25.2% from the same amount of raw key. The link statistics have particular relevance for a current project with the Canadian Space Agency to exchange a quantum key with an orbiting satellite - a project which I have participated in two feasibility studies for. Wanting to study the usefulness of more recent ideas in quantum cryptography this thesis then looks at the first experimental implementation of a new cryptographic primitive called oblivious transfer (OT) in the noisy storage model. This primitive has obvious important applications as it can be used to implement a secure identification scheme provably secure in a quantum scenario. Such a scheme could one day be used, for example, to authenticate a user over short distances, such as at ATM machines, which have proven to be particularly vulnerable to hacking and fraud. Over a four hour experiment, Alice and Bob measure 405,642,088 entangled photon pairs with an average QBER of 0.93% allowing them to create a secure OT key of 8,939,150 bits. As a first implementer, I examine many of the pressing issues currently preventing the scheme from being more widely adopted such as the need to relax the dependance of the OT rate on the loss of the system and the need to extend the security proof to cover a wider range of quantum communication channels and memories. It is important to note that OT is fundamentally different than QKD for security as the information is never physically exchanged over the communication line but rather the joint equality function f(x) = f(y) is evaluated. Thus, security in QKD does not imply security for OT. Finally, this thesis concludes with the construction and initial alignment of a second generation free-space quantum receiver, useful for increasing the QKD key rates, but designed for a fundamental test of quantum theory namely a Svetlichny inequality violation. Svetlichny's inequality is a generalization of Bell's inequality to three particles where any two of the three particles maybe be non-locally correlated. Even so, a violation of Svetlichny's inequality shows that certain quantum mechanical states are incompatible with this restricted class of non-local yet realistic theories. Svetlichny's inequality is particularly important because while there has been an overwhelming number of Bell experiments performed testing two-body correlations, experiments on many-body systems have been few and far between. Experiments of this type are particularly valuable to explore since we live in a many-body world. The new receiver incorporates an active polarization analyzer capable of switching between measurement bases on a microsecond time-scale through the use of a Pockels cell while maintaining measurements of a high fidelity. Some of the initial alignment and analysis results are detailed including the final measured contrasts of 1:25.2 and 1:22.6 in the rectilinear and diagonal bases respectively.

Wireless networks are becoming more and more popular. In current wireless network environments, mobile users can use multiple wireless network interfaces built in their mobile devices to roam around the mobile networks. They can scan the wireless spectrums and utilize the network resources extremely, and they can roam into nearby wireless networks due to the mobility capabilities of the powerful mobile devices. Before connecting to an access point, an authentication process is necessary. There are many interactive wireless authentication protocols which have been proposed in the literature. Under the wireless networks, handover is an important property for a mobile user to change her/his position. However, the existing interactive wireless authentication protocols may cause unstable connection. This is because that a mobile user may perform failed authentications with some nearby invalid access points and thus she/he cannot finish handover in time. Hence, we would like to design a mechanism for a mobile user to determine the validity of access points before the interactive authentication, and the mobile user can choose a valid one when making handover. In our proposed scheme, the mobile user can just scan and receive authentication messages from access points without interactions with them while she/he can determine which one of them is valid. We call this cognitive authentication. Besides, we also propose cooperative defense which allows mobile users to exchange their received authentication messages for detecting illegal access points. Finally, we provide security proofs for our proposed scheme.

In an anonymous credential system, when a credential has been shown for verification, none can identify the owner of the credential and link the relationship between any two credentials. The unlinkability is the crucial feature for any anonymous credential system. In 2002, Jan Camenisch and Anna Lysyanskaya proposed a signature scheme (CL signature) which allows users to demonstrate their credentials without revealing their identity information. However, CL signature is compounded of a lot of zero-knowledge proof technologies which cause inefficiency for CL signatures. Such heavy computation requirements may limit the scope which CL signatures can be applied to. In this thesis, we propose a new blind signature scheme based on ElGamal signatures and design an anonymous verification procedure which is more efficient than the CL signature scheme. Finally, we also implement our proposed protocols.

Digital watermarking is one of the most popular technologies for protecting the ownerships of digital contents or products. By embedding digital watermarks into digital contents, the owners of the contents can convince the judge or the trusted third party of their ownership of the contents. However, some attacks, such as the binding attacks and the men-in-the-middle attacks, are threatening the security of the watermarking mechanisms. Moreover, that the privacy of content buyers is not fully protected or the dispute between the buyers and the sellers cannot be fairly resolved also reduce the quality of the services. Although several buyer-seller watermarking protocols have been introduced in the literature, none can cope with all of the above problems. In this thesis, we will propose a novel buyer-seller watermarking protocol that can resolve the dispute between the buyers and the sellers fairly. Furthermore, not only is the proposed protocol immune to all of the known attacks, but it is truly buyer anonymous as well.

The entire thesis text is included in the research.pdf file; the official abstract appears in the short.pdf file; a non-technical public abstract appears in the public.pdf file. Title from PDF of title page (University of Missouri--Columbia, viewed on December 30, 2009). Thesis advisor: Dr. William Banks. Includes bibliographical references.

Thesis (Ph. D.)--Florida State University, 2004. / Advisor: Dr. Yvo Desmedt, Florida State University, College of Arts and Sciences, Dept. of Computer Science. Title and description from dissertation home page (June 18, 2004). Includes bibliographical references.

Thesis (M.S.)--Worcester Polytechnic Institute. / Keywords: self-powered; universal hashing; ultra-low-power; message authentication codes; provable security. Includes bibliographical references (p. 55-61).

Thesis (M.S.)--Worcester Polytechnic Institute. / Includes bibliographical references (leaves 50-54).