Whitepapers

Get the facts:

66 pages of detailed review of the new Concordium Network. Background, market research, design philosophy, business- and technical review. Meet our science team, executive team, and advisory board. Detailed project- and delivery plan. Discover the future of blockchains for mainstream business and public sector applications.

Download Whitepaper

Get the science:

Study these white papers to get an idea of the cryptography we are basing Concordium network protocols and privacy management on. Our Concordium Science Team members are marked in bold red and their contributing colleagues in black italics. You can download these white papers directly. We will be posting more as we go along –– next up is papers on the Concordium Protocol, Finalization Layer and Privacy Cloaking. Sign up for email updates to get notified when they are ready.

  • SPDZ2k: Efficient MPC mod 2^k for Dishonest Majority

    Ronald Cramer and Ivan Damgård and Daniel Escudero and Peter Scholl and Chaoping Xing

    Abstract: Most multi-party computation protocols allow secure computation of arithmetic circuits over a finite field, such as the integers modulo a prime. In the more natural setting of integer computations modulo 2k2k, which are useful for simplifying implementations and applications, no solutions with active security are known unless the majority of the participants are honest. We present a new scheme for information-theoretic MACs that are homomorphic modulo 2k2k, and are as efficient as the well-known standard solutions that are homomorphic over fields. We apply this to construct an MPC protocol for dishonest majority in the preprocessing model that has efficiency comparable to the well-known SPDZ protocol (Damgård et al., CRYPTO 2012), with operations modulo 2k2k instead of over a field. We also construct a matching preprocessing protocol based on oblivious transfer, which is in the style of the MASCOT protocol (Keller et al., CCS 2016) and almost as efficient.

    Download
  • Compact Zero-Knowledge Proofs of Small Hamming Weight

    Ivan Damgård, Ji Luo, Sabine Oechsner, Peter Schol, and Mark Simkin

    Abstract. We introduce a new technique that allows to give a zeroknowledge proof that a committed vector has Hamming weight bounded by a given constant. The proof has unconditional soundness and is very compact: It has size independent of the length of the committed string, and for large fields, it has size corresponding to a constant number of commitments. We show five applications of the technique that play on a common theme, namely that our proof allows us to get malicious security at small overhead compared to semi-honest security: 1) actively secure k-out-of-n OT from black-box use of 1-out-of-2 OT, 2) separable accountable ring signatures, 3) more efficient preprocessing for the TinyTable secure two-party computation protocol, 4) mixing with public verifiability, and 5) PIR with security against a malicious client.

    Download
  • Proofs of Replicated Storage Without Timing Assumptions

    Ivan Damgård, Chaya Ganesh, and Claudio Orlandi .

    Abstract: In this paper we provide a formal treatment of proof of replicated storage, a novel cryptographic primitive recently proposed in the context of a novel cryptocurrency, namely Filecoin. In a nutshell, proofs of replicated storage is a solution to the following problem: A user stores a file m on n different servers to ensure that the file will be available even if some of the servers fail. Using proof of retrievability, the user could check that every server is indeed storing the file. However, what if the servers collude and, in order to save on resources, decide to only store one copy of the file? A proof of replicated storage guarantees that, unless the server is indeed storing n copies of the file, the user will not accept the proof. While some candidate proofs of replicated storage have already been proposed, their soundness relies on timing assumptions i.e., the user must reject the proof if the prover does not reply within a certain time-bound. In this paper we provide the first construction of a proof of replication which does not rely on any timing assumptions.

    Download
  • Bounded Tamper Resilience: How to go beyond the Algebraic Barrier

    Ivan Damgaard and Sebastian Faust and Pratyay Mukherjee and Daniele Venturi

    Abstract: Related key attacks (RKAs) are powerful cryptanalytic attacks where an adversary can change the secret key and observe the effect of such changes at the output. The state of the art in RKA security protects against an a-priori unbounded number of certain algebraic induced key relations, e.g., affine functions or polynomials of bounded degree. In this work, we show that it is possible to go beyond the algebraic barrier and achieve security against arbitrary key relations, by restricting the number of tampering queries the adversary is allowed to ask for. The latter restriction is necessary in case of arbitrary key relations, as otherwise a generic attack of Gennaro et al. (TCC 2004) shows how to recover the key of almost any cryptographic primitive.

    Download
  • Gate-scrambling Revisited – or: The TinyTable protocol for 2-Party Secure Computation

    Ivan Damgård and Jesper Buus Nielsen and Michael Nielsen and Samuel Ranellucci

    Abstract: We propose a new protocol, nicknamed TinyTable, for maliciously secure 2-party computation in the preprocessing model. One version of the protocol is useful in practice and allows, for instance, secure AES encryption with latency about 1ms and amortized time about 0.5 μμs per AES block on a fast cloud set-up. Another version is interesting from a theoretical point of view: we achieve a maliciously and unconditionally secure 2-party protocol in the preprocessing model for computing a Boolean circuit, where both the communication complexity and preprocessed data size needed is O(s)O(s) where ss is the circuit size, while the computational complexity is O(kϵs)O(kϵs) where kk is the statistical security parameter and ϵ<1ϵ<1 is a constant. For general circuits with no assumption on their structure, this is the best asymptotic performance achieved so far in this model.

    Download
  • Amortized Complexity of Zero-Knowledge Proofs Revisited: Achieving Linear Soundness Slack

    Ronald Cramer, Ivan Damgård , Chaoping Xing, and Chen Yuan

    Abstract. We propose a new zero-knowledge protocol for proving knowledge of short preimages under additively homomorphic functions that map integer vectors to an Abelian group. The protocol achieves amortized efficiency in that it only needs to send O(n) function values to prove knowledge of n preimages. Furthermore we significantly improve previous bounds on how short a secret we can extract from a dishonest prover, namely our bound is a factor O(k) larger than the size of secret used by the honest prover, where k is the statistical security parameter. In the best previous result, the factor was O(k log kn). Our protocol can be applied to give proofs of knowledge for plaintexts in (Ring-)LWE-based cryptosystems, knowledge of preimages of homomorphic hash functions as well as knowledge of committed values in some integer commitment schemes.

    Download
  • Linear-Time Non-Malleable Codes in the Bit-Wise Independent Tampering Model

    Ronald Cramer and Ivan Damgård and Nico Döttling and Irene Giacomelli and Chaoping Xing

    Abstract: Non-malleable codes were introduced by Dziembowski et al. (ICS 2010) as coding schemes that protect a message against tampering attacks. Roughly speaking, a code is non-malleable if decoding an adversarially tampered encoding of a message m produces the original message m or a value m’ (eventually abort) completely unrelated with m. It is known that non-malleability is possible only for restricted classes of tampering functions. Since their introduction, a long line of works has established feasibility results of non-malleable codes against different families of tampering functions. However, for many interesting families, the challenge of finding “good” non-malleable codes remains open. In particular, we would like to have explicit constructions of non-malleable codes with high-rate and efficient encoding/decoding algorithms (i.e. low computational complexity).

    Download
  • On the Communication required for Unconditionally Secure Multiplication

    Ivan Damgård, Jesper Buus Nielsen, Antigoni Polychroniadou and Michael Raskin

    Abstract: Many information-theoretic secure protocols are known for general secure multi-party computation, in the honest majority setting, and in the dishonest majority setting with preprocessing. All known protocols that are efficient in the circuit size of the evaluated function follow the same ”gate-by-gate” design pattern: we work through an arithmetic (boolean) circuit on secret-shared inputs, such that after we process a gate, the output of the gate is represented as a random secret sharing among the players. This approach usually allows non-interactive processing of addition gates but requires communication for every multiplication gate. Thus, while information-theoretic secure protocols are very efficient in terms of computational work, they (seem to) require more communication and more rounds than computationally secure protocols.

    Download
  • Fully Leakage-Resilient Signatures Revisited: Graceful Degradation, Noisy Leakage, and Construction in the Bounded-Retrieval Model.

    Antonio Faonio, Jesper Buus Nielsen, and Daniele Venturi

    Abstract: We construct new leakage-resilient signature schemes. Our schemes remain unforgeable against an adversary leaking arbitrary (yet bounded) information on the entire state of the signer (sometimes known as fully leakage resilience), including the random coin tosses of the signing algorithm. The main feature of our constructions is that they offer a graceful degradation of security in situations where standard existential unforgeability is impossible. This property was recently put forward by Nielsen, Venturi, and Zottarel (PKC 2014) to deal with settings in which the secret key is much larger than the size of a signature. One remarkable such case is the so-called Bounded-Retrieval Model (BRM), where one intentionally inflates the size of the secret key while keeping constant the signature size and the computational complexity of the scheme.

    Download
  • On the Computational Overhead of MPC with Dishonest Majority

    Jesper Buus Nielsen and Samuel Ranellucci

    Abstract. We consider the situation where a large number n of players want to securely compute a large function f with security against an adaptive, malicious adversary which might corrupt t < cn of the parties for some given c ∈ [0, 1). In other words, only some arbitrarily small constant fraction of the parties are assumed to be honest. For any fixed c, we consider the asymptotic complexity as n and the size of f grows. We are in particular interested in the computational overhead, defined as the total computational complexity of all parties divided by the size of f. We show that it is possible to achieve poly-logarithmic computational overhead for all c < 1. Prior to our result it was only known how to get poly-logarithmic overhead for c < 1 2 . We therefore significantly extend the area where we can do secure multiparty computation with polylogarithmic overhead.

    Download
  • Yes, There is an Oblivious RAM Lower Bound!

    Kasper Green Larsen and Jesper Buus Nielsen

    Abstract. An Oblivious RAM (ORAM) introduced by Goldreich and Ostrovsky [JACM’96] is a (possibly randomized) RAM, for which the memory access pattern reveals no information about the operations performed. The main performance metric of an ORAM is the bandwidth overhead, i.e., the multiplicative factor extra memory blocks that must be accessed to hide the operation sequence. In their seminal paper introducing the ORAM, Goldreich and Ostrovsky proved an amortized Ω(lg n) bandwidth overhead lower bound for ORAMs with memory size n. Their lower bound is very strong in the sense that it applies to the “offline” setting in which the ORAM knows the entire sequence of operations ahead of time.

    Download
  • Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives

    Melissa Chase and David Derler and Steven Goldfeder and Claudio Orlandi and Sebastian Ramacher and Christian Rechberger and Daniel Slamanig and Greg Zaverucha

    Abstract: We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parameterizable.

    In our signature constructions, the public key is an image y = f(x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX’16) in constructing an efficient Sigma-protocol for statements over general circuits. We improve this Sigma-protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes.

    Download
  • ZKBoo: Faster Zero-Knowledge for Boolean Circuits

    Irene Giacomelli and Jesper Madsen and Claudio Orlandi

    Abstract: In this paper we describe ZKBoo, a proposal for practically efficient zero-knowledge arguments especially tailored for Boolean circuits and report on a proof-of-concept implementation. As a highlight, we can generate (resp. verify) a non-interactive proof for the SHA-1 circuit in approximately 13ms (resp. 5ms), with a proof size of 444KB. Our techniques are based on the “MPC-in-the-head” approach to zero-knowledge of Ishai et al. (IKOS), which has been successfully used to achieve significant asymptotic improvements. Our contributions include: 1) A thorough analysis of the different variants of IKOS, which highlights their pro and cons for practically relevant soundness parameters; 2) A generalization and simplification of their approach, which leads to faster Sigma-protocols (that can be made non-interactive using the Fiat-Shamir heuristic) for statements of the form “I know x such that y = f(x)” (where f is a circuit and y a public value); 3) A case study, where we provide explicit protocols, implementations and benchmarking of zero-knowledge protocols for the SHA-1 and SHA-256 circuits;

    Download
  • Zero-Knowledge Using Garbled Circuits: How To Prove Non-Algebraic Statements Efficiently

    Marek Jawurek and Florian Kerschbaum and Claudio Orlandi

    Abstract: Zero-knowledge protocols are one of the fundamental concepts in modern cryptography and have countless applications. However, after more than 30 years from their introduction, there are only very few languages (essentially those with a group structure) for which we can construct zero-knowledge protocols that are efficient enough to be used in practice.In this paper we address the problem of how to construct efficient zero-knowledge protocols for generic languages and we propose a protocol based on Yao’s garbled circuit technique.The motivation for our work is that in many cryptographic applications it is useful to be able to prove efficiently statements of the form e.g., “I know x s.t. y=SHA-256(x)” for a common input y (or other “unstructured” languages), but no efficient protocols for this task are currently known.

    Download
  • An Application of Computable Distributions to the Semantics of Probabilistic Programs

    Daniel Huang, Greg Morrisett and Bas Spitters

    Abstract: In this chapter, we explore how (Type-2) computable distributions can be used to give both distributional and (algorithmic) sampling semantics to probabilistic programs with continuous distributions. Towards this end, we first sketch an encoding of computable distributions in a fragment of Haskell. Next, we show how topological domains can be used to model the resulting PCF-like language. Throughout, we hope to emphasize the connection of such an approach with ordinary programming.

    Download
  • Computer-aided proofs for multiparty computation with active security

    Helene Haagh and Aleksandr Karbyshev and Sabine Oechsner and Bas Spitters and Pierre-Yves Strub

    Abstract: Secure multi-party computation (MPC) is a general cryptographic technique that allows distrusting parties to compute a function of their individual inputs, while only revealing the output of the function. It has found applications in areas such as auctioning, email filtering, and secure teleconference. Given their importance, it is crucial that the protocols are specified and implemented correctly. In the programming language community, it has become good practice to use computer proof assistants to verify correctness proofs. In the field of cryptography, EasyCrypt is the state of the art proof assistant. It provides an embedded language for probabilistic programming, together with a specialized logic, embedded into an ambient general purpose higher-order logic.

    Download