International Association
for Cryptologic Research

We are offering postdoc positions in the Cryptography and Data Security Group at the Department of Mathematics, Informatics and Mechanics, University of Warsaw, Poland. More information about our group can be found at http://www.crypto.edu.pl/.

Successful candidates can work on several projects related to cryptography, in particular on smart contracts, blockchain, leakage-resilient and tamper-resilient algorithms, and on countermeasures against hardware Trojans.

The salary will depend on qualifications and will be in the range of approximately PLN 7000 - 8,500 (net/month).

Successful candidates can start from October 2018 or later.

Closing date for applications: 1 February 2019

Contact: Stefan Dziembowski

More information: http://www.crypto.edu.pl/positions

Overview

Algorand is the next generation blockchain platform and digital currency. Possessing a thorough and thoughtfully constructed decentralized economy where all transactions are safe, fast and uncensored while scalable to billions of users, Algorand will help unleash the economic potential of people across the globe as we democratize access to financial instruments.

The Team

The Algorand team combines technological luminaries and proven business leaders. Algorand is founded by Silvio Micali, MIT Ford Professor of Engineering and recipient of the Turing Award in Computer Science.

Our office is located in the heart of downtown Boston. All positions are in this location, though remote work is possible for exceptional candidates.

The Role

This is a senior level role where you will have the opportunity to influence the design and implementation of Algorand’s core cryptographic protocols and schemes.

You’ll be working closely with senior cryptographers at the company to research and prototype new cryptographic schemes and protocols. This involves contribution to cutting-edge research, and industry standards.

Cryptography research engineers are expected to have deep domain knowledge or cryptography, math, algorithms, and be comfortable studying research papers and prototyping.

Responsibilities

You will join a small, extremely capable, and enthusiastic Boston-based team. Your ideas and your innovation will help shape the new blockchain and cryptocurrency ecosystem of tomorrow. The current suite of projects are implemented in primarily Go and C++.

The core product will be open sourced.

Closing date for applications: 1 July 2019

Contact: Sergey Gorbunov, sergey (at) algorand.com

More information: https://www.algorand.com/careers/

Event date: 3 December to 4 December 2018
Submission deadline: 1 October 2018

Event date: 8 April to 12 April 2019
Submission deadline: 16 November 2018
Notification: 17 December 2018

A paper by Karati and Sarkar at Asiacrypt'17 has pointed out the potential for Kummer lines in genus one, by observing that its SIMD-friendly arithmetic is competitive with the status quo. A more recent preprint explores the connection with (twisted) Edwards curves. In this paper we extend this work and significantly simplify their treatment. We show that their Kummer line is the x-line of a Montgomery curve translated by a point of order two, and exhibit a natural isomorphism to a twisted Edwards curve. Moreover, we show that the Kummer line presented by Gaudry and Lubicz can be obtained via the action of a point of order two on the y-line of an Edwards curve. The maps connecting these curves and lines are all very simple. As an example, we present the first implementation of the qDSA signature scheme based on the squared Kummer line. Finally we present close estimates on the number of isomorphism classes of Kummer lines.

This paper shows the security against quantum chosen-ciphertext attacks (QCCA security) of the KEM in Saito, Yamakawa, and Xagawa (EUROCRYPT 2018) in the QROM. The proof is very similar to that for the CCA security in the QROM, easy to understand, and as tight as the original proof.

Since $(t,n)$-threshold secret sharing (SS) was initially proposed by Shamir and Blakley separately in 1979, it has been widely used in many aspects. Later on, Asmuth and Bloom presented a $(t,n)$-threshold SS scheme based on the Chinese Remainder Theorem(CRT) for integers in 1983. However, compared with the most popular Shamir's $(t,n)$-threshold SS scheme, existing CRT based schemes have a lower information rate, moreover, they are harder to construct. To overcome these shortcomings of the CRT based scheme, 1) we first propose a generalized $(t,n)$-threshold SS scheme based on the CRT for the polynomial ring over a finite field. We show that our scheme is ideal, i.e., it is perfect in security and has the information rate 1. By comparison, we show that our scheme has a better information rate and is easier to construct compared with existing threshold SS schemes based on the CRT for integers. 2) We show that Shamir's scheme, which is based on the Lagrange interpolation polynomial, is a special case of our scheme. Therefore, we establish the connection among threshold schemes based on the Lagrange interpolation, schemes based on the CRT for integers and our scheme. 3) As a natural extension of our threshold scheme, we present a weighted threshold SS scheme based on the CRT for polynomial rings, which inherits the above advantages of our threshold scheme over existing weighted schemes based on the CRT for integers.

The increasing number of cryptocurrencies, as well as the rising number of actors within each single cryptocurrency, inevitably leads to tensions between the respective communities. As with open source projects, (protocol) forks are often the result of broad disagreement. Usually, after a permanent fork both communities ``mine'' their own business and the conflict is resolved. But what if this is not the case? In this paper, we outline the possibility of malicious forking and consensus techniques that aim at destroying the other branch of a protocol fork. Thereby, we illustrate how merged mining can be used as an attack method against a permissionless PoW cryptocurrency, which itself involuntarily serves as the parent chain for an attacking merge mined branch of a hard fork.

We present $\mathsf{CLARC}$ (Cryptographic Library for Anonymous Reputation and Credentials), an anonymous credentials system (ACS) combined with an anonymous reputation system.

Using $\mathsf{CLARC}$, users can receive attribute-based credentials from issuers. They can efficiently prove that their credentials satisfy complex (access) policies in a privacy-preserving way. This implements anonymous access control with complex policies.

Furthermore, $\mathsf{CLARC}$ is the first ACS that is combined with an anonymous reputation system where users can anonymously rate services. A user who gets access to a service via a credential, also anonymously receives a review token to rate the service. If a user creates more than a single rating, this can be detected by anyone, preventing users from spamming ratings to sway public opinion.

To evaluate feasibility of our construction, we present an open-source prototype implementation.

We propose the first identity-based encryption (IBE) scheme that is (almost) tightly secure against chosen-ciphertext attacks. Our scheme is efficient, in the sense that its ciphertext overhead is only seven group elements, three group elements more than that of the state-of-the-art passively (almost) tightly secure IBE scheme. Our scheme is secure in a multi-challenge setting, i.e., in face of an arbitrary number of challenge ciphertexts. The security of our scheme is based upon the standard symmetric external Diffie-Hellman assumption in pairing-friendly groups, but we also consider (less efficient) generalizations under weaker assumptions.

In this work, we propose two IPE schemes achieving both adaptive security and full attribute-hiding in the prime-order bilinear group, which improve upon the unique existing result satisfying both features from Okamoto and Takashima [Eurocrypt '12] in terms of efficiency.

- Our first IPE scheme is based on the standard $k$-Lin assumption and has shorter master public key and shorter secret keys than Okamoto and Takashima's IPE under weaker DLIN=$2$-lin assumption.

- Our second IPE scheme is adapted from the first one; the security is based on the XDLIN assumption (as Okamoto and Takashima's IPE) but now it also enjoys shorter ciphertexts.

Technically, instead of starting from composite-order IPE and applying existing transformation, we start from an IPE scheme in a very restricted setting but already in the prime-order group, and then gradually upgrade it to our full-fledged IPE scheme. This method allows us to integrate Chen et al.'s framework [Eurocrypt '15] with recent new techniques [TCC '17, Eurocrypt '18] in an optimized way.

This work focuses on side-channel resilient design strategies for symmetric-key cryptographic primitives targeting lightweight applications. In light of NIST's lightweight cryptography project, design choices for block ciphers must consider not only security against traditional cryptanalysis, but also side-channel security, while adhering to low area and power requirements. In this paper, we explore design strategies for substitution-permutation network (SPN)-based block ciphers that make them amenable to low-cost threshold implementations (TI) - a provably secure strategy against side-channel attacks. The core building blocks for our strategy are cryptographically optimal 4x4 S-Boxes, implemented via repeated iterations of simple cellular automata~(CA) rules. We present highly optimized TI circuits for such S-Boxes, that consume nearly 40% less area and power as compared to popular lightweight S-Boxes such as PRESENT and GIFT. We validate our claims via implementation results on ASIC using 180nm technology. We also present a comparison of TI circuits for two popular lightweight linear diffusion layer choices - bit permutations and MixColumns using almost-maximum-distance-separable (almost-MDS) matrices. We finally illustrate design paradigms that combine the aforementioned TI circuits for S-Boxes and diffusion layers to obtain fully side-channel secure SPN block cipher implementations with low area and power requirements.

RaCoSS is a signature scheme based on the syndrome decoding problem over the random linear code and proposed by Fukushima, Roy, Xu, Kiyomoto, Morozov, and Takagi. This scheme is cryptanalyzed Bernstein, Hülsing, Lange, and Panny (pqc-forum on 23 Dec. 2017).

Roy, Morozov, Fukushima, Kiyomoto, and Takagi recently gave a patch and call the patched scheme as RaCoSS-R (ISEC Conf. on 25 Jul. 2018).

This short note describes how to break RaCoSS-R by modifying the forgery attack against RaCoSS.

The success rate is the most common evaluation metric for measuring the performance of a particular side channel attack scenario. We improve on an analytic formula for the success rate.

Byzantine broadcast is a fundamental primitive for secure computation. In a setting with $n$ parties in the presence of an adversary controlling at most $t$ parties, while a lot of progress in optimizing communication complexity has been made for $t < n/2$, little progress has been made for the general case $t<n$, especially for information-theoretic security. In particular, all information-theoretic secure broadcast protocols for $\ell$-bit messages and $t<n$ and optimal round complexity $\mathcal{O}(n)$ have, so far, required a communication complexity of $\mathcal{O}(\ell n^2)$. A broadcast extension protocol allows a long message to be broadcast more efficiently using a small number of single-bit broadcasts. Through broadcast extension, so far, the best achievable round complexity for $t<n$ setting with the optimal communication complexity of $\mathcal{O}(\ell n)$ is $\mathcal{O}(n^4)$ rounds.

In this work, we construct a new broadcast extension protocol for $t<n$ with information-theoretic security. Our protocol improves the round complexity to $\mathcal{O}(n^3)$ while maintaining the optimal communication complexity for long messages. Our result shortens the gap between the information-theoretic setting and the computational setting, and between the optimal communication protocol and the optimal round protocol in the information-theoretic setting for $t<n$.

We design, implement, and evaluate a zero knowledge succinct non-interactive argument (SNARG) for Rank-1 Constraint Satisfaction (R1CS), a widely-deployed NP language undergoing standardization. Our SNARG has a transparent setup, is plausibly post-quantum secure, and uses lightweight cryptography. A proof attesting to the satisfiability of $n$ constraints has size $O(\log^2 n)$; it can be produced with $O(n \log n)$ field operations and verified with $O(n)$. At 128 bits of security, proofs are less than 250kB even for several million constraints, more than 10x shorter than prior SNARGs with similar features.

A key ingredient of our construction is a new Interactive Oracle Proof (IOP) for solving a univariate analogue of the classical sumcheck problem [LFKN92], originally studied for multivariate polynomials. Our protocol verifies the sum of entries of a Reed--Solomon codeword over any subgroup of a field.

We also provide libiop, a library for writing IOP-based arguments, in which a toolchain of transformations enables programmers to write new arguments by writing simple IOP sub-components. We have used this library to specify our construction and prior ones, and plan to open-source it.

Recent advances in cryptography promise to let us run complex algorithms in the encrypted domain. However, these results are still mostly theoretical since the running times are still much larger than their equivalents in the plaintext domain. In this context, Majority Judgment is a recent proposal for a new voting system with several interesting practical advantages, but which implies a more involved tallying process than first-past-the-post voting. To protect voters' privacy, such a process needs to be done by only manipulating encrypted data.

In this paper, we then explore the possibility of computing the (ordered) winners in the Majority Judgment election without leaking any other information, using homomorphic encryption and multiparty computation. We particularly focus on the practicality of such a solution and, for this purpose, we optimize both the algorithms and the implementations of several cryptographic building blocks. Our result is very positive, showing that this is as of now possible to attain practical running times for such a complex privacy-protecting tallying process, even for large-scale elections.

We construct efficient and tightly secure pseudorandom functions (PRFs) with only logarithmic security loss and short secret keys. This yields very simple and efficient variants of well-known constructions, including those of Naor-Reingold (FOCS 1997) and Lewko-Waters (ACM CCS 2009). Most importantly, in combination with the construction of Banerjee, Peikert and Rosen (EUROCRYPT 2012) we obtain the currently most efficient LWE-based PRF from a weak LWE-assumption with a much smaller modulus than the original construction. In comparison to the only previous construction with this property, which is due to Doettling and Schroeder (CRYPTO 2015), we use a modulus of similar size, but only a single instance of the underlying PRF, instead of $\lambda \cdot \omega(\log \lambda)$ parallel instances, where $\lambda$ is the security parameter. Like Doettling and Schroeder, our security proof is only almost back-box, due to the fact that the number of queries made by the adversary and its advantage must be known a-priori.

Technically, we introduce all-prefix universal hash functions (APUHFs), which are hash functions that are (almost-)universal, even if any prefix of the output is considered. We give simple and very efficient constructions of APUHFs, and show how they can be combined with the augmented cascade of Boneh et al. (ACM CCS 2010) to obtain our results. Along the way, we develop a new and more direct way to prove security of PRFs based on the augmented cascade.

Side-channel countermeasure designers often face severe performance overheads when trying to protect a device. Widely applied countermeasures such as masking and shuffling entail generating a large amount of random numbers, which can result in a computational bottleneck. To mitigate the randomness cost, this work evaluates low-randomness versions of both masking and shuffling, namely Recycled Randomness Masking (RRM) and Reduced Randomness Shuffling (RRS). These countermeasures employ memory units to store generated random numbers and reuse them in subsequent computations,making them primarily suitable for implementation on devices with sufficient memory. Both RRM and RRS are evaluated using the MI-based framework in the context of horizontal attacks. The evaluation exhibits the tradeoff between the randomness cost and the noisy leakage security level offered by the countermeasures, enabling the designer to fine-tune a masking or shuffling scheme and maximize the security level achieved for a certain cost.

We give a new signature scheme for isogenies that combines the class group actions of CSIDH with the notion of Fiat-Shamir with aborts. Our techniques allow to have signatures of size less than one kilobyte at the 128-bit security level, even with tight security reduction (to a non-standard problem) in the quantum random oracle model. Hence our signatures are potentially shorter than lattice signatures, but signing and verification are currently very expensive.