International Association
for Cryptologic Research

Two paradigms for secure MPC are synchronous and asynchronous protocols, which differ substantially in terms of the guarantees they provide. While synchronous protocols tolerate more corruptions and allow every party to give its input, they are very slow because the speed depends on the conservatively assumed worst-case delay $\Delta$ of the network. In contrast, asynchronous protocols are as fast as the actual network allows, i.e., run in time proportional to the actual maximal network delay $\delta$, but unavoidably parties with slow network connections cannot give input.

This paper proposes a new, composable model (of UC functionalities) capturing the best of both worlds. Each party obtains the output as fast as the network allows (a property called responsiveness), and it is guaranteed that all parties obtain the same output. We consider different corruption thresholds: correctness, privacy, and responsiveness are guaranteed for less than $T_C$, $T_P$, and $T_R$ corruptions, respectively, while termination is always guaranteed. We achieve a trade-off between correctness, privacy and responsiveness: For any $T_R\leq\frac{1}{3}n$, one can achieve $T_C = T_P=\min\{\frac{1}{2}n,n-2T_R\}$. In particular, setting $T_R = \frac{1}{4}n$ allows us to obtain $T_C = T_P = \frac{1}{2}n$, hence achieving substantial responsiveness, yet correctness and privacy much better than in an asynchronous protocol and as good as for a purely synchronous (slow) protocol.

This result is achieved by a black-box compiler for combining an asynchronous and a synchronous protocol, involving new protocol techniques that may have applications in other contexts, and by devising an asynchronous protocol with $T_C = T_P = n-2T_R$, improving the correctness and privacy of known protocols achieving $T_C=T_P=\frac{1}{3}n$.

We finally close the long-standing problem of constructing a noninteractive zero-knowledge (NIZK) proof system for any NP language with security based on the plain Learning With Errors (LWE) problem, and thereby on worst-case lattice problems. Our proof system instantiates the framework recently developed by Canetti et al. [EUROCRYPT'18], Holmgren and Lombardi [FOCS'18], and Canetti et al. [STOC'19] for soundly applying the Fiat--Shamir transform using a hash function family that is correlation intractable for a suitable class of relations. Previously, such hash families were based either on ``exotic'' assumptions (e.g., indistinguishability obfuscation or optimal hardness of certain LWE variants) or, more recently, on the existence of circularly secure fully homomorphic encryption (FHE). However, none of these assumptions are known to be implied by plain LWE or worst-case hardness.

Our main technical contribution is a hash family that is correlation intractable for arbitrary size-$S$ circuits, for any polynomially bounded $S$, based on plain LWE (with small polynomial approximation factors). The construction combines two novel ingredients: a correlation-intractable hash family for log-depth circuits based on LWE (or even the potentially harder Short Integer Solution problem), and a ``bootstrapping'' transform that uses (leveled) FHE to promote correlation intractability for the FHE decryption circuit to arbitrary (bounded) circuits. Our construction can be instantiated in two possible ``modes,'' yielding a NIZK that is either computationally sound and statistically zero knowledge in the common random string model, or vice-versa in the common reference string model.

In the implicit certification model, the process of verifying the validity of the signer's public key is combined with the verification of the signature itself. When compared to traditional, explicit certificates, the main advantage of the implicit approach lies in the shorter public key validation data. This property is particularly important in resource-constrained scenarios where public key validation is performed very often, which is common in vehicular communications (V2X) that employ pseudonym certificates. In this article, we propose a Schnorr-based implicit certification procedure that is more efficient than the state of the art. We then integrate the proposed solution with a popular V2X-oriented pseudonym certificate provisioning approach, the (unified) butterfly key expansion, showing the corresponding performance gains. As an additional contribution, we show that butterfly keys are vulnerable to existential forgery attacks under certain conditions, and also discuss how this issue can be fixed in an effective and efficient manner.

The importance of efficient MPC in today's world needs no retelling. An obvious barebones requirement to execute protocols for MPC is the ability of parties to communicate with each other. Traditionally, we solve this problem by assuming that every pair of parties in the network share a dedicated secure link that enables reliable message transmission. This assumption is clearly impractical as the number of nodes in the network grows, as it has today. In their seminal work, Dwork, Peleg, Pippenger and Upfal introduced the notion of almost-everywhere secure primitives in an effort to model the reality of large scale global networks and study the impact of limited connectivity on the properties of fundamental fault-tolerant distributed tasks. In this model, the underlying communication network is sparse and hence some nodes may not even be in a position to participate in the protocol (all their neighbors may be corrupt, for instance). A protocol for almost everywhere reliable message transmission, which would guarantee that a large subset of the network can transmit messages to each other reliably, implies a protocol for almost-everywhere agreement where nodes are required to agree on a value despite malicious or byzantine behavior of some subset of nodes, and an almost-everywhere agreement protocol implies a protocol almost-everywhere secure MPC that is unconditionally or information-theoretically secure. The parameters of interest are the degree $d$ of the network, the number $t$ of corrupted nodes that can be tolerated and the number $x$ of nodes that the protocol may give up. Prior work achieves $d = O(1)$ for $t = O(n/\log n)$ and $d = O(\log^{q}n)$ for $t = O(n)$ for some fixed constant $q > 1$.

In this work, we first derive message protocols which are efficient with respect to the total number of computations done across the network. We use this result to show an abundance of networks with $d = O(1)$ that are resilient to $t = O(n)$ random corruptions. This randomized result helps us build networks which are resistant to worst-case adversaries. In particular, we improve the state of the art in the almost everywhere reliable message transmission problem in the worst-case adversary model by showing the existence of an abundance of networks that satisfy $d = O(\log n)$ for $t = O(n)$, thus making progress on this question after nearly a decade. Finally, we define a new adversarial model of corruptions that is suitable for networks shared amongst a large group of corporations that: (1) do not trust each other, and (2) may collude, and construct optimal networks achieving $d = O(1)$ for $t = O(n)$ in this model.

Decryption failure is a common phenomenon in most lattice-based public-key schemes. To reduce the rate of decryption failure, application of error correction code can be helpful. However, the literature of error correcting codes typically addresses computational performances and error correcting capabilities of the codes; their security properties are yet to be investigated. Hence, direct porting of an error correcting code in a cryptographic scheme could open new avenues to the attacks. For example, a recent work has exploited non-constant-time execution of the BCH error correcting code to reduce the security of the lattice-based public-key scheme LAC.

In this work we analyze the decoding algorithm of the BCH code and design a constanttime version of the BCH decoding algorithm. To study the computational overhead of the countermeasures, we integrated our constant-time BCH code in the reference and optimized implementations of the LAC scheme and observed nearly 1.1 and 3.0 factor slowdown respectively for the CCA-secure primitives.

Smart contracts are envisioned to be one of the killer applications of decentralized cryptocurrencies. They enable self-enforcing payments between users depending on complex program logic. Unfortunately, Bitcoin – the largest and by far most widely used cryptocurrency – does not offer support for complex smart contracts. Moreover, simple contracts that can be executed on Bitcoin are often cumbersome to design and very costly to execute. In this work we present FastKitten, a practical framework for executing arbitrarily complex smart contracts at low costs over decentralized cryptocurrencies which are designed to only support simple transactions. To this end, FastKitten leverages the power of trusted computing environments (TEEs), in which contracts are run off-chain to enable efficient contract execution at low cost. We formally prove that FastKitten satisfies strong security properties when all but one party are malicious. Finally, we report on a prototype implementation which supports arbitrary contracts through a scripting engine, and evaluate performance through benchmarking a provably fair online poker game. Our implementation illustrates that FastKitten is practical for complex multi-round applications with a very small latency. Combining these features, FastKitten is the first truly practical framework for complex smart contract execution over Bitcoin.

Recently, Cramer et al. (CRYPTO 2018) presented a protocol, SPDZ2k, for actively secure multiparty computation for dishonest majority in the pre-processing model over the ring $Z_{2^k}$, instead of over a prime field $F_p$. Their technique used oblivious transfer for the pre-processing phase, more specifically the MASCOT protocol (Keller et al. CCS 2016). In this paper we describe a more efficient technique for secure multiparty computation over $Z_{2^k}$ based on somewhat homomorphic encryption. In particular we adapt the Overdrive approach (Keller et al. EUROCRYPT 2018) to obtain a protocol which is more like the original SPDZ protocol (Damg{\aa}rd et al. CRYPTO 2012).

To accomplish this we introduce a special packing technique for the BGV encryption scheme operating on the plaintext space defined by the SPDZ2k protocol, extending the ciphertext packing method used in SPDZ to the case of $Z_{2^k}$. We also present a more complete pre-processing phase for secure computation modulo $2^k$ by adding a new technique to produce shared random bits. These are needed in a number of online protocols and are quite expensive to generate using the MASCOT-based method given in the original SPDZ2k paper.

Our approach can be applied to both the Low-Gear and High-Gear variant of Overdrive, and it leads to a protocol whose overall efficiency is three to six times better than the OT-based methodology.

One of three tasks in a secure genome analysis competition called IDASH 2018 was to develop a solution for privacy-preserving GWAS computation based on homomorphic encryption. The scenario is that a data holder encrypts a number of individual records, each of which consists of several phenotype and genotype data, and provide the encrypted data to an untrusted server. Then, the server performs a GWAS algorithm based on homomorphic encryption without the decryption key and outputs the result in encrypted state so that there is no information leakage on the sensitive data to the server. We develop a privacy-preserving semi-parallel GWAS algorithm by applying an approximate homomorphic encryption scheme HEAAN. Fisher scoring and semi-parallel GWAS algorithms are modified to be efficiently computed over homomorphically encrypted data with several optimization methodologies; substitute matrix inversion by an adjoint matrix, avoid computing a superfluous matrix of super-large size, and transform the algorithm into an approximate version. Our modified semi-parallel GWAS algorithm based on homomorphic encryption which achieves 128-bit security takes $30$--$40$ minutes for $245$ samples containing $10,000$--$15,000$ SNPs. Compared to the true $p$-value from the original semi-parallel GWAS algorithm, the $F_1$ score of our $p$-value result is over $0.99$.

The problem of solving a system of quadratic equations in multiple variables---known as multivariate-quadratic or MQ problem---is the underlying hard problem of various cryptosystems. For efficiency reasons, a common instantiation is to consider quadratic equations over $\F_2$. The current state of the art in solving the \MQ problem over $\F_2$ for sizes commonly used in cryptosystems is enumeration, which runs in time $\Theta(2^n)$ for a system of $n$ variables. Grover's algorithm running on a large quantum computer is expected to reduce the time to $\Theta(2^{n/2})$. As a building block, Grover's algorithm requires an "oracle", which is used to evaluate the quadratic equations at a superposition of all possible inputs. In this paper, we describe two different quantum circuits that provide this oracle functionality. As a corollary, we show that even a relatively small quantum computer with as little as 92 logical qubits is sufficient to break MQ instances that have been proposed for 80-bit pre-quantum security.

This paper introduces a constant-time implementation for a quasi-cyclic moderate-density-parity-check (QC-MDPC) code based encryption scheme. At a $2^{80}$ security level, the software takes 14679937 Cortex-M4 and 1560072 Haswell cycles to decrypt a short message, while the previous records were 18416012 and 3104624 (non-constant-time) cycles. Such speed is achieved by combining two techniques: 1) performing each polynomial multiplication in $\mathbb{F}_2[x]/(x^r-1)$ and $\mathbb{Z}[x]/(x^r-1)$ using a sequence of ``constant-time rotations'' and 2) bitslicing.

Based on the identity-based encryption (IBE) from lattices by Agrawal et al. (Eurocrypt'10), Micciancio and Peikert (Eurocrypt'12) presented a CCA1-secure public-key encryption (PKE), which has the best known efficiency in the standard model and can be used to obtain a CCA2-secure PKE from lattices by using the generic BCHK transform (SIAM J. Comput., 2006) with a cost of introducing extra overheads to both computation and storage for the use of other primitives such as signatures and commitments. In this paper, we propose a more efficient standard model CCA2-secure PKE from lattices by carefully combining a different message encoding (which encodes the message into the most significant bits of the LWE's ``secret term'') with several nice algebraic properties of the tag-based lattice trapdoor and the LWE problem (such as unique witness and additive homomorphism). Compared to the best known lattice-based CCA1-secure PKE in the standard model due to Micciancio and Peikert (Eurocrypt'12), we not only directly achieve the CCA2-security without using any generic transform (and thus do not use signatures or commitments), but also reduce the noise parameter roughly by a factor of 3. This improvement makes our CCA2-secure PKE more efficient in terms of both computation and storage. In particular, when encrypting a 256-bit (resp., 512-bit) message at 128-bit (resp., 256-bit) security, the ciphertext size of our CCA2-secure PKE is even 33-44% (resp., 36-46%) smaller than that of their CCA1-secure PKE.

We investigate the minimal number of group elements and prover running time in a zk-SNARK when using only a symmetric ``linear'' knowledge assumption, like the $d$-Power Knowledge of Exponent assumption, rather than a ``quadratic'' one as implicitly happens in the most efficient known construction by Groth [Groth16]. The proofs of [Groth16] contain only 3 group elements. We present 4 element proofs for quadratic arithmetic programs/rank 1 constraint systems under the $d$-PKE with very similar prover running time to [Groth16]. Central to our construction is a simple lemma for ``batching'' knowledge checks, which allows us to save one proof element.

The KECCAK hash function is the winner of the SHA-3 competition (2008 -- 2012) and became the SHA-3 standard of NIST in 2015. In this paper, we focus on practical collision attacks against round-reduced SHA-3 and some KECCAK variants. Following the framework developed by Dinur et al. at FSE~2012 where 4-round collisions were found by combining 3-round differential trails and 1-round connectors, we extend the connectors to up to three rounds and hence achieve collision attacks for up to 6 rounds. The extension is possible thanks to the large degree of freedom of the wide internal state. By linearizing S-boxes of the first round, the problem of finding solutions of 2-round connectors is converted to that of solving a system of linear equations. When linearization is applied to the first two rounds, 3-round connectors become possible. However, due to the quick reduction in the degree of freedom caused by linearization, the connector succeeds only when the 3-round differential trails satisfy some additional conditions. We develop dedicated strategies for searching differential trails and find that such special differential trails indeed exist. To summarize, we obtain the first real collisions on six instances, including three round-reduced instances of SHA-3, namely 5-round SHAKE128, SHA3-224, and SHA3-256, and three instances of KECCAK contest, namely KECCAK[$1440,160,5,160$], KECCAK[$640,160,5,160$] and KECCAK[$1440,160,6,160$], improving the number of practically attacked rounds by two. It is remarked that the work here is still far from threatening the security of the full 24-round SHA-3 family.

Event date: 23 June to 26 June 2019
Submission deadline: 22 March 2019
Notification: 17 May 2019

Event date: 14 July to 17 July 2019
Submission deadline: 15 March 2019
Notification: 15 April 2019

Event date: 14 July to 17 July 2019
Submission deadline: 1 March 2019
Notification: 14 April 2019

Event date: 25 September to 27 September 2019
Submission deadline: 8 April 2019
Notification: 10 June 2019

Event date: 31 May to 2 June 2019
Submission deadline: 1 April 2019
Notification: 22 April 2019

There is a vacancy for a Ph.D. position in cryptography and data security at the Secure and Reliable Communication group (https://www.uib.no/rg/selmer) in the Department of Informatics, University of Bergen. The position is for a fixed-term period of 3 years with the possibility of a 4th year, consisting of 25 % compulsory work (e.g. teaching responsibilities at the department) distributed across the employment period.

We are particularly interested in applicants who are highly motivated to contribute to cryptographic privacy-enhancing technologies, blockchain technology, lattice/code-based cryptography, and coding theory.

We can offer:

• a good and professionally challenging working environment
• salary at pay grade 51 (Code 1017/Pay range 20, alternative 9) in the state salary scale. This constitutes a gross annual salary of NOK 449 400. Further promotions are made according to the length of service in the position.
• enrolment in the Norwegian Public Service Pension Fund
• Good welfare benefits (https://www.uib.no/en/foremployees/30808/welfare)

Closing date for applications: 10 March 2019

Contact: Chunlei Li (chunlei.li (at) uib.no)

More information: https://www.jobbnorge.no/en/available-jobs/job/165213/phd-position-in-cryptography-and-data-security

Dr. Yang Zhang at CISPA Helmholtz Center for Information Security is looking for multiple fully-funded Ph.D. students working on machine learning security and privacy and biomedical privacy.

Yang (https://yangzhangalmo.github.io/) is a research group leader at CISPA Helmholtz Center for Information Security. Previously, he was a postdoc working with Michael Backes at CISPA from January 2017 to December 2018. CISPA located at Saarbruecken, Germany, is the newest member of the Helmholtz Association, the largest scientific organization in Germany fully committed to scientific excellence and to tackling the grand research challenges in their respective fields. CISPA as the first investment of Helmholtz in computer science is one of the top research centers in information security, it is constantly ranked top-3 in the field worldwide, see csrankings.org.

Requirements:

• A bachelor/master degree in Computer Science, Information Security, Mathematics with excellent grades
• Excellent programming skills
• Excellent English
• Good knowledge about machine learning

What we offer:

• Full-time working contract (E13 level salary)
• Excellent research environment
• Strong supervision

To apply, please send your CV to yang.zhang (at) cispa.saarland

Closing date for applications: 1 June 2019

Contact: Yang Zhang, research group leader, yang.zhang (at) cispa.saarland