Abstract We present new protocols for Asynchronous Verifiable Secret Sharing for Shamir (i.e., threshold $$t t < n ) sharing of secrets. Our protocols: Use only “lightweight” cryptographic primitives, such as hash functions; Can share secrets over rings such as $${\mathbb {Z}}/(p^k)$$ Z / ( p k ) as well as finite fields $$\mathbb {F}_q$$ F q ; Provide optimal resilience, in the sense that they tolerate up to $$t < n/3$$ t < n / 3 corruptions, where n is the total number of parties; Are complete, in the sense that they guarantee that if any honest party receives their share then all honest parties receive their shares; Employ batching techniques, whereby a dealer shares many secrets in parallel and achieves an amortized communication complexity that is linear in n, at least on the “happy path”, where no party provably misbehaves.

In this work, we extend the MPC-in-the-Head framework, used in recent efficient zero-knowledge protocols, to work over the ring $$\mathbb {Z}_{2^k}$$ , which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir’s secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.

Zero-Knowledge protocols have increasingly become both popular and practical in recent years due to their applicability in many areas such as blockchain systems. Unfortunately, public verifiability and small proof sizes of zero-knowledge protocols currently come at the price of strong assumptions, large prover time, or both, when considering statements with millions of gates. In this regime, the most prover-efficient protocols are in the designated verifier setting, where proofs are only valid to a single party that must keep a secret state.

We present a unified view of the two-party and multi-party computation protocols based on oblivious transfer first outlined in Nielsen et al. (CRYPTO 2012) and Larraia et al. (CRYPTO 2014). We present a number of modifications and improvements to these earlier presentations, as well as full proofs of the entire protocol. Improvements include a unified pre-processing and online MAC methodology, mechanisms to pass between different MAC variants and fixing a minor bug in the protocol of Larraia et al. in relation to a selective failure attack. It also fixes a minor bug in Nielsen et al. resulting from using Jensen’s inequality in the wrong direction in an analysis.

We consider the issue of securing dark pools/markets in thefinancial services sector. Currently, these markets are executed via trusted third parties, which opens potential for market operators to conduct fraud. We present a potential solution to this problem by using Multi-Party Computation (MPC) to enable a trusted third party to be emulated in software for three popular market mechanisms: continuous double auction (CDA), periodic auction (PA), and scheduled volume matching (SVM). Our experiments show that whilst the predominate market clearing mechanism of CDA is not currently viable when executed using MPC, SVM (a popular market mechanism for dark pools) is viable. We present experimental validation of this conclusion by presenting the expected throughputs for such markets in two popular MPC paradigms: the two party dishonest majority setting, and the honest majority three party setting.

The HighGear protocol (Eurocrypt 2018) is the fastest currently known approach to preprocessing for the SPDZ Multi-Party Computation scheme. Its backbone is formed by an Ideal Lattice-based Somewhat Homomorphic Encryption Scheme and accompanying Zero-Knowledge proofs. Unfortunately, due to certain characteristics of HighGear such current implementations limit the security parameters in a number of places. This is mainly due to memory and bandwidth consumption constraints. In this work we present a new approach to the ZKPoKs for the SPDZ Multi-Party Computation scheme. We rigorously formalize the original approach of HighGear and show how to improve upon it using a different proof strategy. This allows us to increase the security of the underlying protocols, whilst simultaneously also increasing the performance in terms of memory and bandwidth consumption as well as overall throughput of the SPDZ offline phase.

We discuss the widely increasing range of applications of a cryptographic technique called multi-party computation. For many decades, this was perceived to be of purely theoretical interest, but now it has started to find application in a number of use cases. We highlight in this paper a number of these, ranging from securing small high-value items such as cryptographic keys, through to securing an entire database.

We discuss the design of symmetric primitives, in particular Pseudo-Random Functions (PRFs) which are suitable for use in a secret-sharing based MPC system. We consider three different PRFs: the Naor-Reingold PRF, a PRF based on the Legendre symbol, and a specialized block cipher design called MiMC. We present protocols for implementing these PRFs within a secret-sharing based MPC system, and discuss possible applications. We then compare the performance of our protocols. Depending on the application, different PRFs may offer different optimizations and advantages over the classic AES benchmark. Thus, we cannot conclude that there is one optimal PRF to be used in all situations.

The authors describe a method to bootstrap a packed BGV ciphertext which does not depend (as much) on any special properties of the plaintext and ciphertext moduli. Prior ‘efficient’ methods such as that of Gentry et al . (PKC 2012) required a ciphertext modulus q which was close to a power of the plaintext modulus p . This enables the authors’ method to be applied in a larger number of situations. The authors’ basic bootstrapping technique makes use of a representation based on polynomials of the group over the finite field , followed by polynomial interpolation of the reduction mod p map over the coefficients of the algebraic group. This technique is then extended to the full BGV packed ciphertext space, using a method whose depth depends only logarithmically on the number of packed elements. This method may be of interest as an alternative to the method of Alperin‐Sheriff and Peikert (CRYPTO 2013). To aid efficiency, the authors utilise the ring/field switching technique of Gentry et al . (SCN 2012, JCS 2013).

With over 1.6 billion debit and credit cards in use worldwide, the EMV system (a.k.a. "Chip-and-PIN") has become one of the most important deployed cryptographic protocol suites. Recently, the EMV consortium has decided to upgrade the existing RSA based system with a new system relying on Elliptic Curve Cryptography (ECC). One of the central components of the new system is a protocol that enables a card to establish a secure channel with a card reader. In this paper we provide a security analysis of the proposed protocol, we propose minor changes/clarifications to the "Request for Comments" issued in Nov 2012, and demonstrate that the resulting protocol meets the intended security goals.

We present a runtime environment for executing secure programs via a multi-party computation protocol in the preprocessing model. The runtime environment is general and allows arbitrary reactive computations to be performed. A particularly novel aspect is that it automatically determines the minimum number of rounds needed for a computation, given a specific instruction sequence, and it then uses this to minimize the overall cost of the computation. Various experiments are reported on, on various non-trivial functionalities. We show how, by utilizing the ability of modern processors to execute multiple threads at a time, one can obtain various tradeoffs between latency and throughput

SPDZ (pronounced “Speedz”) is the nickname of the MPC protocol of Damgård et al. from Crypto 2012. In this paper we both resolve a number of open problems with SPDZ; and present several theoretical and practical improvements to the protocol. In detail, we start by designing and implementing a covertly secure key generation protocol for obtaining a BGV public key and a shared associated secret key. We then construct both a covertly and actively secure preprocessing phase, both of which compare favourably with previous work in terms of efficiency and provable security. We also build a new online phase, which solves a major problem of the SPDZ protocol: namely prior to this work preprocessed data could be used for only one function evaluation and then had to be recomputed from scratch for the next evaluation, while our online phase can support reactive functionalities. This improvement comes mainly from the fact that our construction does not require players to reveal the MAC keys to check correctness of MAC’d values. These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

The security of contemporary homomorphic encryption schemes over cyclotomic number field relies on fields of very large dimension. This large dimension is needed because of the large modulus-to-noise ratio in the key-switching matrices that are used for the top few levels of the evaluated circuit. However, a smaller modulus-to-noise ratio is used in lower levels of the circuit, so from a security standpoint it is permissible to switch to lower-dimension fields, thus speeding up the homomorphic operations for the lower levels of the circuit. However, implementing such field-switching is nontrivial, since these schemes rely on the field algebraic structure for their homomorphic properties. A basic ring-switching operation was used by Brakerski, Gentry and Vaikuntanathan, over rings of the form Z[X]/(X2n+1), in the context of bootstrapping. In this work we generalize and extend this technique to work over any cyclotomic number field, and show how it can be used not only for bootstrapping but also during the computation itself (in conjunction with the “packed ciphertext” techniques of Gentry, Halevi and Smart).

We propose a general multiparty computation protocol secure against an active adversary corrupting up to $$n-1$$ of the n players. The protocol may be used to compute securely arithmetic circuits over any finite field $$\mathbb {F}_{p^k}$$ . Our protocol consists of a preprocessing phase that is both independent of the function to be computed and of the inputs, and a much more efficient online phase where the actual computation takes place. The online phase is unconditionally secure and has total computational (and communication) complexity linear in n, the number of players, where earlier work was quadratic in n. Moreover, the work done by each player is only a small constant factor larger than what one would need to compute the circuit in the clear. We show this is optimal for computation in large fields. In practice, for 3 players, a secure 64-bit multiplication can be done in 0.05 ms. Our preprocessing is based on a somewhat homomorphic cryptosystem. We extend a scheme by Brakerski et al., so that we can perform distributed decryption and handle many values in parallel in one ciphertext. The computational complexity of our preprocessing phase is dominated by the public-key operations, we need $$O(n^2/s)$$ operations per secure multiplication where s is a parameter that increases with the security parameter of the cryptosystem. Earlier work in this model needed $$\varOmega (n^2)$$ operations. In practice, the preprocessing prepares a secure 64-bit multiplication for 3 players in about 13 ms.

The authors show that a number of existing methods for side-channel defence are essentially the same techniques presented in different contexts. By abstracting this technique, they present necessary conditions which need to be satisfied for it to be successful in preventing side-channel analysis. They also show that concrete application of the technique via randomised field representation produces more efficient implementations than application of the technique via randomised projective coordinates.

The physical security of application-specific embedded processors such as those found in smart-cards has become increasingly important since they are used more and more as conduits for sensitive financial and identity information. The advent of side-channel attacks has meant that a combination of algorithm, software, and hardware defense is required. In this paper, we reexamine the issue of nondeterministic processors, simplifying previous designs using a multithreaded architecture. From this simplification, we are able to construct a formally reasoned assessment of the security level offered by such a device.

In this paper, we simplify and extend the Eta pairing, originally discovered in the setting of supersingular curves by Barreto , to ordinary curves. Furthermore, we show that by swapping the arguments of the Eta pairing, one obtains a very efficient algorithm resulting in a speed-up of a factor of around six over the usual Tate pairing, in the case of curves that have large security parameters, complex multiplication by an order of Qopf (radic-3), and when the trace of Frobenius is chosen to be suitably small. Other, more minor savings are obtained for more general curves

We describe how using a redundant Montgomery representation allows for high-performance SIMD-based implementations of RSA and elliptic curve cryptography. This is in addition to the known benefits of immunity from timing attacks afforded by the use of such a representation. We present some preliminary implementation timings using the SSE2 instruction set on a Pentium 4 processor and show that an SIMD parallel implementation of RSA can be around twice as fast as traditional sequential code. This is especially useful given the larger 2,048 bit RSA keys which are now being proposed for standard security levels. Finally, we remark on other application areas that improve the security of our work in the context of side-channel analysis while maintaining high performance.

Differential power analysis (DPA) has become a real-world threat to the security of cryptographic hardware devices such as smart-cards. By using cheap and readily available equipment, attacks can easily compromise algorithms running on these devices in a non-invasive manner. Adding non-determinism to the execution of cryptographic algorithms has been proposed as a defence against these attacks. One way of achieving this non-determinism is to introduce random additional operations to the algorithm which produce noise in the power profile of the device. We describe the addition of a specialised processor pipeline stage which increases the level of potential non-determinism and hence guards against the revelation of secret information.