Aggregate signature schemes combine the digital signatures of multiple users on different messages into one single signature. The Boneh-Gentry-Lynn-Shacham (BGLS) aggregate signature scheme is one such scheme, based on pairings, where anyone can aggregate the signatures in any order. We suggest improvements to its current chosen-key security model. In particular, we argue that the scheme should be resistant to attackers that can adaptively choose their target users, and either replace other users' public keys or expose other users' private keys. We compare these new types of forgers to the original targeted-user forger, building up to the stronger replacement-and-exposure forger. Finally, we present a security reduction for a variant of the BGLS aggregate signature scheme with respect to this new notion of forgery. Recent attacks by Joux and others on the discrete logarithm problem in small-characteristic finite fields dramatically reduced the security of many type I pairings. Therefore, we explore security reductions for BGLS with type III rather than type I pairings. Although our reductions are specific to BGLS, we believe that other aggregate signature schemes could benefit from similar changes to their security models.

One attractive feature of lattice-based cryptosystems is the existence of security reductions relating the difficulty of breaking the cryptosystem to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based cryptosystems using the learning with errors (LWE) problem select parameters for which the reduction to the underlying lattice problem gives no meaningful assurance of concrete security. We analyze the runtime of the algorithm constructed in the reductions and select parameters for a cryptosystem under which the reductions give 128-bit security. While the resulting LWE-based cryptosystem is somewhat cumbersome, requiring a dimension of n = 1460, this is less than 2 times the dimension in the recently proposed Frodo cryptosystem (Bos et al., ACM CCS 2016), and could be implemented without catastrophic damage to communication times. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems. / Thesis / Master of Science (MSc) / The advent of quantum computing poses a serious threat to modern cryptography, as most cryptosystems in use today are vulnerable to attacks by quantum algorithms. Recently proposed cryptosystems based on lattices are conjectured to be resistant to attacks by quantum computers. These cryptosystems also have a conditional security guarantee: if the cryptosystem can be broken by an attack, then a reduction exists which uses that attack to solve variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As these problems have no known efficient solutions, breaking the cryptosystem should be hard. However this guarantee only holds if the cryptosystem is constructed using parameters which satisfy conditions given in the reduction. Current proposals do not do this, and so cannot claim even a conditional security guarantee. We analyze two reductions and select parameters for a cryptosystem which satisfy these conditions. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.