Cryptography After Prime Time:Protocols for Z2k and Groups of Unknown Order

Cryptographic protocols allow to solve problems between mutually distrusting parties<br/>such that the parties learn only what is absolutely necessary: With a zero-knowledge proof a prover can convince a verifier that a given statement is true without revealing anything<br/>else, and secure multiparty computation (MPC) allows for arbitrary computation on<br/>private data held by multiple parties. Many cryptographic constructions make extensive<br/>use of the properties of prime numbers, often in the form of finite prime fields and<br/>prime-order groups. In this thesis we explore different constructions that use rings Z2k<br/>and groups of unknown order instead.<br/><br/>Zero-knowledge proof systems are typically designed for the statements encoded as<br/>Boolean or arithmetic circuits over finite fields F2 or Fp . While the field properties<br/>are very useful for protocol design, actual computer programs and CPUs, however,<br/>usually work on 32- or 64-bit integers instead which can be modeled as rings Z2k for<br/>k ∈ {32, 64}. When such arithmetic is emulated in prime fields, the incurring overhead<br/>is significant. Designing efficient protocols that support Z2k natively is challenging<br/>due to the fact that Z2k is not a field (for k &gt; 1), but a ring with zero-divisors and<br/>many commonly used techniques no longer work in this setting. In the first part of<br/>this thesis we construct highly efficient and scalable interactive zero-knowledge proofs<br/>for Z2k with linear proof size and running time. These are based on ideas from recent<br/>constructions for finite fields using information-theoretic MACs and vector oblivious linear<br/>evaluation (VOLE). We design linearly homomorphic commitments for Z2k and show<br/>how to prove multiplicative relations to obtain zero-knowledge for general computation<br/>over Z2k . Moreover, we present the first actively secure protocol for VOLE over Z2k<br/>with sublinear communication which is needed to generate such commitments in large<br/>quantities and demonstrate the practicality of our constructions<br/><br/>With groups of prime order p everything in the exponent can be viewed as elements of<br/>the field Fp , but with groups of unknown order such as class groups, we have to treat<br/>exponents as integers instead. In the second part of this thesis we construct the first<br/>actively secure threshold version of the linearly homomorphic cryptosystem based on<br/>class groups from the so-called CL framework (Castagnos and Laguillaumie, 2015). For<br/>our distributed key generation and decryption protocols with static and adaptive security,<br/>we present new constructions for integer verifiable secret sharing schemes and (batched)<br/>zero-knowledge proofs in this setting. We use the statically secure variant of our threshold<br/>encryption scheme to construct general MPC with active security and guaranteed output<br/>delivery in the universal composability (UC) model while requiring only a transparent<br/>setup. Finally, the simplicity and low round complexity of our constructions compared to<br/>previous approaches allows us to adapt our protocols to the recent “You-Only-Speak-Once” (YOSO) setting for large-scale MPC.