International Association
for Cryptologic Research

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

The Information Security Group at Royal Holloway University of London is seeking to recruit a postdoctoral research assistant (PDRA) to work in the area of cryptography. The position is available for immediate start, for up to 26 months (until 31 March 2021).

The PDRA will work alongside Prof. Carlos Cid, Dr. Martin Albrecht and other cryptographic researchers at Royal Holloway on topics connected to the design and analysis of cryptographic key exchange protocols that support incorporating key material from diverse sources. This post is part of the AQuaSec project, a Innovate UK-funded research project with 17 partners from industry and academia, aiming to develop technologies for quantum-safe communications by integrating post-quantum cryptography with techniques from quantum cryptography.

Applicants for this role should have already completed, or be close to completing, a PhD in a relevant discipline, with an outstanding research track record in cryptography. Experience in cryptographic protocol design is a plus.

Established in 1990, the Information Security Group at Royal Holloway was one of the first dedicated academic groups in the world to conduct research and teaching in information security. The ISG is today a world-leading interdisciplinary research group with 20 full-time members of staff, several postdoctoral research assistants and over 50 PhD students working on a range of subjects in cyber security, in particular cryptography. The post is based in Egham, Surrey where Royal Holloway is situated in a beautiful, leafy campus near to Windsor Great Park and within commuting distance from London.

Closing date for applications: 12 March 2019

Contact: Informal enquiries about this position can be made to Prof. Carlos Cid (carlos.cid AT rhul.ac.uk)

More information: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0219-048

The Security and Privacy research division (https://secpriv.tuwien.ac.at) at the Vienna University of Technology (TU Wien) is seeking a candidate for a postdoc position of two years, ideally starting in Spring 2019. The successful applicant will enjoy full research independence and further contribute to the teaching activities in security and privacy at TU Wien.

Candidates with a research background in the following areas are particularly invited to apply:

- Formal methods for security and privacy;

- Intersection between Machine Learning and security and privacy;

- Blockchain technologies;

- Web security.

TU Wien has about 20,000 students and a heavy emphasis on research. The Faculty of Informatics comprises about 3,000 students and is the largest one in Austria. Vienna hosts several outstanding research institutes (including IST Austria, AIT, SBA, RIAT) with a strong focus on security and privacy and a long-standing collaboration track.

The postdoctoral researcher salary is highly competitive and ruled by level B1 of the Austrian Collective Agreement for the university staff, currently amounting to EUR 3.711,10 per/month/gross (14 times a year).

Finally, Vienna has repeatedly been ranked number 1 worldwide in the Mercer Quality of Living Survey.

TU Wien is committed to increasing female employment in leading scientific positions. Female applicants are explicitly encouraged to apply, and preference will be given to female applications when scientifically equally qualified.

Expressions of interest should be submitted by e-mail to christopher.vomastek (at) tuwien.ac.at and include in a single pdf

• A cover letter stating the candidate\'s motivation to apply, and the reason(s) why they should be selected for the position;

• A CV;

• A short research statement;

• Three most significant publications;

• The contact details of two referees.

Expressions of interest submitted by February 25, 2019 will receive full consideration.

Closing date for applications: 25 February 2019

Contact: Univ.-Prof. Dr. Matteo Maffei, matteo.maffei (at) tuwien.ac.at

The boomerang attack is a variant of differential cryptanalysis which regards a block cipher $E$ as the composition of two sub-ciphers, i.e., $E=E_1\circ E_0$, and which constructs distinguishers for $E$ with probability $p^2q^2$ by combining differential trails for $E_0$ and $E_1$ with probability $p$ and $q$ respectively. However, the validity of this attack relies on the dependency between the two differential trails. Murphy has shown cases where probabilities calculated by $p^2q^2$ turn out to be zero, while techniques such as boomerang switches proposed by Biryukov and Khovratovich give rise to probabilities greater than $p^2q^2$. To formalize such dependency to obtain a more accurate estimation of the probability of the distinguisher, Dunkelman et al. proposed the sandwich framework that regards $E$ as $\tilde{E_1}\circ E_m \circ \tilde{E_0}$, where the dependency between the two differential trails is handled by a careful analysis of the probability of the middle part $E_m$. Recently, Cid et al. proposed the Boomerang Connectivity Table (BCT) which unifies the previous switch techniques and incompatibility together and evaluates the probability of $E_m$ theoretically when $E_m$ is composed of a single S-box layer. In this paper, we revisit the BCT and propose a generalized framework which is able to identify the actual boundaries of $E_m$ which contains dependency of the two differential trails and systematically evaluate the probability of $E_m$ with any number of rounds. To demonstrate the power of this new framework, we apply it to two block ciphers SKNNY and AES. In the application to SKNNY, the probabilities of four boomerang distinguishers are re-evaluated. It turns out that $E_m$ involves 5 or 6 rounds and the probabilities of the full distinguishers are much higher than previously evaluated. In the application to AES, the new framework is used to exclude incompatibility and find high probability distinguishers of AES-128 under the related-subkey setting. As a result, a 6-round distinguisher with probability $2^{-109.42}$ is constructed. Lastly, we discuss the relation between the dependency of two differential trails in boomerang distinguishers and the properties of components of the cipher.