International Association
for Cryptologic Research

The Department of Computer Science at the University of Copenhagen is seeking candidates for a full professorship in Theoretical Computer Science (TCS). More specifically, we are inviting exceptional candidates from the broad fields of algorithms, complexity, and cryptography including privacy.

We are looking for an outstanding, experienced researcher with an innovative mind-set and intellectual curiosity to strengthen and complement the research profile of the Algorithms and Complexity Section, headed by Professor Mikkel Thorup. The Algorithms and Complexity Section is part of an exciting environment including the Basic Algorithms Research Copenhagen (BARC) centre, joint with the IT University of Copenhagen, and involving extensive collaborations with the Technical University of Denmark (DTU) and Lund University on the Swedish side of the Oresund Bridge. We aim to attract top talent from around the world to an ambitious, creative, collaborative, and fun environment. Using the power of mathematics, we strive to create fundamental breakthroughs in algorithms and complexity theory, but we also have a track record of start-ups and surprising algorithmic discoveries leading to major industrial applications.

The University of Copenhagen was founded in 1479 and is the oldest and largest university in Denmark. It is often ranked as the best university in Scandinavia and consistently as one of the top places in Europe. Within computer science, it is ranked number 1 in the European Union (post-Brexit) by the Shanghai Ranking.

The department offers a friendly and thriving international research and working environment with opportunities to build up internationally competitive research groups. Working conditions at the University of Copenhagen support a healthy work-life balance and Copenhagen is a family-friendly capital city.

The application deadline is May 24, 2020.

For more information, see https://candidate.hr-manager.net/ApplicationInit.aspx/?cid=1307&departmentId=18971&ProjectId=151668

Closing date for applications:

Contact: Head of Section, Professor Mikkel Thorup (mthorup@di.ku.dk; cell phone +45 2117 9123) and Head of Department, Professor Mads Nielsen (madsn@di.ku.dk; cell phone +45 2460 0599).

More information: https://candidate.hr-manager.net/ApplicationInit.aspx/?cid=1307&departmentId=18971&ProjectId=151668

Event date: 12 November to 13 November 2020
Submission deadline: 26 July 2020
Notification: 16 August 2020

Event date: to
Submission deadline: 30 July 2020

The Institute of Cybersecurity and Cryptology (iC2) at the School of Computing and Information Technology (SCIT), University of Wollongong, Australia, is looking to recruit a new Associate Research Fellow (Level A) who will work on the ARC DP200100144 project titled “Securing Public Cloud Storage with Protection against Malicious Senders”. The Associate Research Fellow will perform the research tasks specified by the project, which include the design of advanced Attribute-Based Encryption and Zero-Knowledge proof systems and their implementations in the cloud platform. The candidate must have solid background and research experience in cryptographic scheme design and implementation. It is expected that the candidate will complete all the research tasks required by the project within the specified timeframe and make significant contributions to the research activities within iC2. The candidate will be mentored by the iC2 Director Professor Willy Susilo to develop novel security solutions for achieving the goals aimed by the ARC DP200100144 project. You will be prompted to respond to a selection criteria questionnaire as part of the application process. Please make sure that you address the selection criteria in addition to submitting your CV. For further information about the position please contact Professor Willy Susilo. Women are underrepresented in this discipline and are encouraged to apply.

Closing date for applications:

Contact: Prof. Willy Susilo (wsusilo at uow dot edu dot au)

More information: https://uowjobs.taleo.net/careersection/in/jobdetail.ftl?job=200507&tz=GMT%2B10%3A00&tzname=Australia%2FSydney

We are proud to announce the winners of the 2020 IACR Test-of-Time Award. This award honors papers published at the 3 IACR flagship conferences 15 years ago which have had a lasting impact on the field.

The Test-of-Time award for Eurocrypt 2005 is awarded to "Fuzzy Identity-Based Encryption " (Amit Sahai and Brent Waters), for laying the foundations of attribute-based encryption and other advanced notions of encryption.

The Test-of-Time award for Crypto 2005 is awarded to "Finding collisions in the full SHA-1 " (Xiaoyun Wang, Yiqun Lisa Yin and Hongbo Yu), for a breakthrough in the cryptanalysis of hash functions.

The Test-of-Time award for Asiacrypt 2005 is awarded to "Discrete-Log-Based Signatures May Not Be Equivalent to Discrete Log" (Pascal Paillier and Damien Vergnaud), developing a new meta-reduction approach in the security proof of cryptosystems.

For more information, see https://www.iacr.org/testoftime.

We present novel strategies and concrete algorithms for the parallel computation of the Supersingular Isogeny-based Diffie-Hellman key exchange (SIDH) protocol when executed on multi-core platforms. The most relevant design idea exploited by our approach is that of concurrently computing scalar multiplication operations along with a parallelized version of the strategies required for constructing and evaluating large smooth degree isogenies. We report experimental results showing that a three-core implementation of our parallel approach achieves an acceleration factor of 1.57 compared against a sequential implementation of the SIKE protocol.

Incentive systems (such as customer loyalty systems) are omnipresent nowadays and deployed in several areas such as retail, travel, and financial services. Despite the benefits for customers and companies, this involves large amounts of sensitive data being transferred and analyzed. These concerns initiated research on privacy-preserving incentive systems, where users register with a provider and are then able to privately earn and spend incentive points.

In this paper we construct an incentive system that improves upon the state-of-the-art in several ways: – We improve efficiency of the Earn protocol by replacing costly zero-knowledge proofs with a short structure-preserving signature on equivalence classes. – We enable tracing of remainder tokens from double-spending transactions without losing backward unlinkability. – We allow for secure recovery of failed Spend protocol runs (where usually, any retries would be counted as double-spending attempts). – We guarantee that corrupt users cannot falsely blame other corrupt users for their double-spending.

We propose an extended formal model of incentive systems and a concrete instantiation using homomorphic Pedersen commitments, ElGamal encryption, structure-preserving signatures on equivalence classes (SPS-EQ), and zero-knowledge proofs of knowledge. We formally prove our construction secure and present benchmarks showing its practical efficiency.

Reputation is a major component of trustworthy systems. In this work, we describe how to leverage reputation to establish a highly scalable and efficient blockchain. In order to avoid potential safety concerns stemming from the subjective and volatile nature of reputation, we propose a proof-of-reputation/proof-of-stake-hybrid (in short, PoR/PoS-hybrid) blockchain design. Although proof-of-stake and proof-of-reputation have been separately studied, to our knowledge, our proposal is the first cryptographically secure design of proof-of-reputation-based (in short PoR-based) blockchains; and it is the first blockchain that fortifies its PoR-based security by optimized Nakamoto-style consensus. This results in a ledger protocol which is provably secure if the reputation system is accurate, and preserves its basic safety properties even if it is not, as long as the majority of the stake in the system remains in honest hands. Our results put emphasis on reputation fairness as a key feature of any reputation-based lottery. We devise a definition of reputation fairness that ensures fair participation while giving chances to newly joining parties to participate and potentially build a reputation. We also describe a concrete lottery in the random oracle model which achieves this definition of fairness. Our treatment of reputation-fairness can be of independent interest.

Fault attack is a class of active implementation based attacks which introduces controlled perturbations in the normal operation of a system to produce faulty outcomes. In case of ciphers, these faulty outcomes can lead to leakage of secret information, such as the secret key. The effectiveness and practicality of fault attacks largely depend on the underlying fault model and the type of fault induced. In this paper, we analyse the drawbacks of persistent fault model in case of error correction code (ECC) enabled systems. We further propose a novel fault attack called Intermittent Fault Attack which is well suited for ECC-enabled DRAM modules. We demonstrate the practicality of our attack model by inducing single bit faults using pinpointed Rowhammer technique in S-Boxes of block ciphers in an ECC protected system.

In this paper we present PQ-WireGuard, a post-quantum variant of the handshake in the WireGuard VPN protocol (NDSS 2017). Unlike most previous work on post-quantum security for real-world protocols, this variant does not only consider post-quantum confidentiality (or forward secrecy) but also post-quantum authentication. To achieve this, we replace the Diffie-Hellman-based handshake by a more generic approach only using key-encapsulation mechanisms (KEMs). We establish security of PQ-WireGuard, adapting the security proofs for WireGuard in the symbolic model and in the standard model to our construction. We then instantiate this generic construction with concrete post-quantum secure KEMs, which we carefully select to achieve high security and speed. We demonstrate competitiveness of PQ-WireGuard presenting extensive benchmarking results comparing to widely deployed VPN solutions.

The key transform of the REESSE1+ asymmetric cryptosystem is Ci = (Ai * W ^ l(i)) ^ d (% M) with l(i) belonging to Omg = {5, 7, ..., 2n + 3} for i = 1, ..., n, where l(i) is called a lever function. In this paper, the authors give a simplified transform Ci = Ai * W ^ l(i) (% M) and a new lever function l(i) from {1, ..., n} to Omg = {+/-5, ..., +/-(n + 4)}, where "+/-" means the selection of the "+" or "-" sign, and discuss the necessity and sufficiency of the new l(i), namely that a simplified private key is insecure if l(i) is only a fixed integer, and secure at present if l(i) is a one-to-one function. Further, the sufficiency of the new l(i) is expounded from four aspects: (i) indeterminacy of the new l(i), (ii) insufficient conditions for the neutralizing the powers of W and W ^ -1 even if Omg = {5, ..., n + 4}, (iii) verification by examples, and (iv) running times of continued fraction attack and W-parameter intersection attack which are two most efficient algorithms so far but not determinate polynomial time ones. Last, the authors elaborate a relation between a lever function and a random oracle.

In this work we propose three new algorithms for 4-way vectorization of the well known Montgomery ladder. The first algorithm requires three multiplication rounds which is optimal. The computation of the Montgomery ladder includes a multiplication by a constant which is small for curves that are used in practice. In this case, using the round optimal algorithm is not the best choice. Our second algorithm requires two multiplication rounds, a squaring round and a round for the multiplication by the constant. This provides an improvement over the first algorithm. The third algorithm improves upon the first two for fixed base scalar multiplication, where the base point is small. The well known Montgomery curves Curve25519 and Curve448 are part of the TLS protocol, version~1.3. For these two curves, we provide constant time assembly implementations of the shared secret computation phase of the Diffie-Hellman key agreement protocol. Timing results on the Haswell and Skylake processors show significant speed improvements in comparison to best known existing implementations corresponding to previously published works.

Oblivious compaction is a crucial building block for hash-based oblivious RAM. Asharov et al. recently gave a O(n) algorithm for oblivious tight compaction. Their algorithm is deterministic and asymptotically optimal, but it is not practical to implement because the implied constant is $\gg 2^{38}$. We give a new algorithm for oblivious tight compaction that runs in time $< 16014.54n$. As part of our construction, we give a new result in the bootstrap percolation of random regular graphs.

We show that the single-server computational PIR protocol proposed by Holzbaur, Hollanti and Wachter-Zeh in 2020 is not private, in the sense that the server can recover in polynomial time the index of the desired file with very high probability. The attack relies on the following observation. Removing rows of the query matrix corresponding to the desired file yields a large decrease of the dimension over $\mathbb{F}_q$ of the vector space spanned by the rows of this punctured matrix. Such a dimension loss only shows up with negligible probability when rows unrelated to the requested file are deleted.

The currentCovid-19 pandemic shows that our modern globalized world can be heavily affected by a quickly spreading, highly infectious, deadly virus in a matter of weeks. It became apparent that manual contact tracing and quarantining of suspects can only be effective in the first days of the spread before the exponential growth overwhelms the health authorities.By automating tracing processes and quarantining everyone who came in contactwith infected people, as well as arriving travelers, it should be possible to quickly loosen lockdown measures. Countries like China, Singapore and Israel hastily developed privacy-endangering schemes to computationally trace contacts using user-generated location histories or mass surveillance data [2]. For instance, there are already reports of deanonymizations of South Korean citizens from their published “anonymized” data set of infected people [3]. To approach this conflict of interests we propose to evaluate a privacy-preserving contact tracing system. Our main contributions are: * Identification and formulation of privacy risks of contact tracing. * Design of a privacy-preserving approach to contact tracing.

Our preliminary evaluation shows that the proposed approach is feasible indifferent scenarios derived from real-world case studies.

In this work, we design and implement the first protocol for RSA modulus construction that can support thousands of parties and offers security against an arbitrary number of corrupted parties.

In a nutshell, we design the ``best'' protocol for this scale that is secure against passive corruption, then amplify it to obtain active security using efficient non-interactive zero-knowledge arguments. Our protocol satisfies a stronger security guarantee where a deviating party can be identified when the protocol aborts (referred to as security with identifiable-abort) and allows for ``public verifiability''.

Our passively secure protocol extends the recent work of Chen et al. that, in turn, is based on the blueprint introduced in the original work of Boneh-Franklin protocol (CRYPTO 1997, J. ACM, 2001). Specifically, we reduce the task of sampling a modulus to secure distributed multiplication, which we implement via an efficient threshold additively homomorphic encryption (AHE) scheme based on the Ring-LWE assumption. This results in a protocol where the amortized per-party communication cost grows logarithmically in the number of parties. In order to keep the parties lightweight, we employ an ``untrusted'' coordinator that is connected to all parties and performs all public and broadcast operations.

We amplify this protocol to obtain active security (with identifiable-abort) by attaching zero-knowledge proofs. We instantiate our ZK proof system by composing two different types of ZK proof systems: (1) the Ligero sub-linear zero-knowledge proof system (Ames et al., CCS 2017), and (2) $$\Sigma$$-protocol for proving the knowledge of a discrete logarithm in unknown order groups (Shoup, Eurocrypt 2000).

We implemented both the passive and the active variants of our protocol and ran experiments using 2 to 4,000 parties. This is the first such implementation of any MPC protocol that can scale to more than 1,000 parties. For generating a 2048-bit modulus among 1,000 parties, our passive protocol executed in under 4 minutes and the active variant ran in 22 minutes.

The majority of recently demonstrated deep-learning side-channel attacks use a single neural network classifier to recover the key. The potential benefits of combining multiple classifiers have not been explored yet in the side-channel attack's context. In this paper, we show that, by combining several CNN classifiers which use different attack points, it is possible to considerably reduce (more than 40% on average) the number of traces required to recover the key from an FPGA implementation of AES by power analysis. We also show that not all combinations of classifiers improve the attack efficiency.

Given a vectorial function $F:\mathbb{F}_2^n \mapsto \mathbb{F}_2^m$, the indicator $1_{{\cal G}_F}$ of its graph ${\cal G}_F=\{(x,F(x)); x\in \mathbb{F}_2^n\}$ allows to express the algebraic degree of $F$ in a simple way. Exploiting the formula, obtained in a previous paper, for the graph indicator of a composite function $G\circ F$, that involves only a sum of products of $1_{{\cal G}_F}$ and $1_{{\cal G}_G}$, we deduce bounds on the algebraic degree of $G\circ F$, whose efficiency comes from the fact that the algebraic degree of the product of two Boolean functions is bounded above by the sum of their algebraic degrees, while for a composition, it is bounded above by their product. One of these bounds, that depends on the algebraic degrees of $G$ and $1_{{\cal G}_F}$, is tight, general, simple, and most often efficient (for the case where it is not efficient, we give an improved bound, that is a little more complex). As far as we know, it is the first efficient upper bound ever found, that works without any condition on the vectorial functions. It provides a new criterion for the choice of S-boxes in block ciphers. It implies as a corollary a known bound assuming the divisibility of the Walsh transform values by a power of 2. It gives a better view why this latter bound works. Our results nicely generalize to more than two functions. \\ When $F$ is a permutation, our expression of the algebraic degree of $G\circ F$ simplifies into a formula involving the algebraic degrees of the products of a coordinate function of $G$ and coordinate functions of $F^{-1}$. This implies and improves another known bound showing that the algebraic degree of $F^{-1}$ has more impact on that of $G\circ F$ than that of $F$ itself, and providing a criterion for the choice of S-boxes in block ciphers when they are permutations: both algebraic degrees of $F$ and $F^{-1}$ should be as large a possible. Our approach by graph indicators gives an explanation to this interesting fact. Our results include all the known efficient bounds as particular cases, and clarify the reasons why they work. We also deduce the exact expression of the algebraic degree of the composition of three functions, leading to a bound that is much more efficient than what we obtain by applying the known bound two times. We also obtain two bounds on the algebraic degree of $G \circ F$, given the divisibility by powers of 2 of coefficients in the numerical normal forms of component functions of $F^{-1}$, and their sums with a coordinate function of $G$. We study their consequences and generalizations.

Since its selection as the winner of the SHA-3 competition, Keccak, with all its variants, has found a large number of applications. It is, for instance, a common building block in schemes submitted to NIST's post-quantum cryptography project. In many of these applications, Keccak processes ephemeral secrets. In such a setting, side-channel adversaries are limited to a single observation, meaning that differential attacks are inherently prevented. If, however, such a single trace of Keccak can already be sufficient for key recovery has so far been unknown.

In this paper, we change the above by presenting the first single-trace attack targeting Keccak. Our method is based on soft-analytical side-channel attacks and, thus, combines template matching with message passing in a graphical model of the attacked algorithm. As a straight-forward model of Keccak does not yield satisfactory results, we describe several optimizations for the modeling and the message-passing algorithm. Their combination allows attaining high attack performance in terms of both success rate as well as computational runtime.

We evaluate our attack assuming generic software (microcontroller) targets and thus use simulations in the generic noisy Hamming-weight leakage model. Hence, we assume relatively modest profiling capabilities of the adversary. Nonetheless, the attack can reliably recover secrets in a large number of evaluated scenarios at realistic noise levels. Consequently, we demonstrate the need for countermeasures even in settings where DPA is not a threat.

We present a new multiparty protocol for the distributed generation of biprime RSA moduli, with security against any subset of maliciously colluding parties assuming oblivious transfer and the hardness of factoring.

Our protocol is highly modular, and its uppermost layer can be viewed as a template that generalizes the structure of prior works and leads to a simpler security proof. We introduce a combined sampling-and-sieving technique that eliminates both the inherent leakage in the approach of Frederiksen et al. (Crypto'18), and the dependence upon additively homomorphic encryption in the approach of Hazay et al. (JCrypt'19). We combine this technique with an efficient, privacy-free check to detect malicious behavior retroactively when a sampled candidate is not a biprime, and thereby overcome covert rejection-sampling attacks and achieve both asymptotic and concrete efficiency improvements over the previous state of the art.