In this dissertation we develop novel primitives and algorithms in quantum cryptography, specifically for quantum key distribution and random number generation. We show a device-independent quantum key distribution (DIQKD) algorithm that is based on the notion of synchronous correlations. Most algorithms in DIQKD literature rely on the well-known CHSH inequality which is neither symmetric nor synchronous. We propose a new synchronous Bell inequality that simplifies the QKD setting by being fully symmetric so that the roles of the two parties in the protocol, Alice and Bob, are completely interchangeable. This has implications for QKD hardware since an identical set of devices can be produced for both parties instead of separate devices for each. We also achieve key rates comparable to CHSH-based protocols.

This dissertation also focuses on closing the causality or locality loophole present in device-independent schemes. An assumption that is critical to device-independent protocols is that the two parties are acausally separated and cannot communicate with each other once they receive their inputs. This is typically referred to as the nonsignaling condition. If the condition of nonsignaling is violated, then an attacker may simulate the entire protocol classically. This erases any certificate of quantumness produced by the violation of a Bell inequality. We pose a new security assumption with respect to the adversary's uncertainty about the two parties' measurement bases. We derive a bound for this uncertainty and show that if the uncertainty grows any larger than the threshold, there is no strategy any adversary can use to cheat in the protocol. This closes the causality loophole and makes the protocol easier to implement for practical use.

A primitive widely used in QKD and other cryptographic protocols is a random bit generator. We define ideal and real models of random bit generators and show their efficiency and security in the Constructive Cryptography framework. We specifically look at random bit generators based on process tomography of one-qubit channels. We consider ideal quantum random bit generators, then introduce some state preparation and bit-flip errors to define real quantum random bit generators. We show that the ideal and real generators are close to each other in statistical distance.

The third part of this dissertation presents some initial ideas for quantum lattice sieving algorithms. Lattices are very important objects in the effort to construct cryptographic primitives that are secure against quantum attacks. A central problem in the study of lattices is that of finding the shortest non-zero vector in the lattice. Asymptotically, sieving is the best known technique for solving the shortest vector problem, however, sieving requires memory exponential in the dimension of the lattice. This work tries to provide better memory complexity while also improving runtime. Our ideas are inspired by classical heuristic sieving algorithms and make an attempt to quantize those algorithms.