International Association
for Cryptologic Research

The Department of computing science seeks 2 postdoctoral fellows to projects in computer security and software engineering. The fellowship is full-time for two years with access June 2021 or otherwise agreed.

The Department of Computing Science (www.cs.umu.se) is a dynamic department with about 130 employees from over twenty countries. We are providing research and education within a broad spectrum of areas, and offer education on basic, advanced, and PhD levels. The research is internationally well recognized and includes basic research, methods development, and software development, and research and development within various application domains.

The successful candidates will join the new software system security research group. You will contribute to projects in computer security and software engineering such as developing new approaches to detect or prevent software vulnerabilities or scalable static analysis algorithms to extract security properties.

The stipend project is financed by the Kempe foundations. The stipend is full-time for two years with starting date 1st of June, 2021, or to be negotiated. The stipend amounts to 330 000 SEK per year (around 32500 euro). The stipend is not subject to tax.

Application deadline is 15 March 2021.

Closing date for applications:

Contact: Prof. Bartel: alexandre.bartel@cs.umu.se

More information: https://www.umu.se/en/work-with-us/postdoctoral-scholarships/6-237-21/

Thanks to everyone for confirming the importance of the Cryptology ePrint Archive by alerting us that it was not reachable.

The problem has now been fixed

--The eprint editors & maintainers

At CRYPTO 2019, Gohr improved attacks on Speck32/64 using deep learning. In 2020, Chen et al. proposed a neural aided statistical attack that is more generic. Chen et’s attack is based on a statistical distinguisher that covers a prepended differential transition and a neural distinguisher. When the probability of the differential transition is pq, its impact on the data complexity is O(p^{-2}q^{-2}. In this paper, we propose an improved neural aided statistical attack based on a new concept named Homogeneous Set. Since partial random ciphertext pairs are filtered with the help of homogeneous sets, the differential transition’s impact on the data complexity is reduced to O(p^{−1}q^{−2}). As a demonstration, the improved neural aided statistical attack is applied to round-reduced Speck. And several better attacks are obtained.

Gohr has proposed the only deep learning-based distinguisher model at Crypto 2019, which is used to distinguish reduced Speck32/64 and a pseudorandom permutation. This distinguisher model can be applied to many symmetric ciphers. Given a plaintext differential, Gohr’s distinguisher model can learn differences between two distributions from adequate single ciphertext pairs. In this paper, we propose a new neural distinguisher model which takes k > 2 ciphertext pairs as the analysis object. A non-uniform distribution can produce many derived features that will not appear in a single ciphertext pair. Our neural distinguisher model can exploit these derived features from k ciphertext pairs. Taking Gohr’s distinguisher model as the baseline model, we firstly construct strong baseline distinguishers for five reduced ciphers. Then our neural distinguishers for five ciphers are also constructed using the new distinguisher model proposed in this paper. Experiments show our neural distinguishers can always obtain distinguishing accuracy promotions under various settings of k. When combining k samples incorrectly classified by baseline distinguishers into one group, our neural distinguishers can still distinguish correctly with a non-negligible probability. It indicates that derived features have been successfully captured by our neural distinguishers. The distinguishing accuracy promotion also comes from derived features. Our neural distinguishers can also be used to improve the key recovery attack on 11-round Specck32/64. Besides, compared with the raw attack scheme provided by Gohr, we propose a new key recovery attack scheme that can further reduce the time complexity.

Modern SoC designs include several reset domains that enable asynchronous partial resets while obviating complete system boot. Unfortunately, asynchronous resets can introduce security vulnerabilities that are difficult to detect through traditional validation. In this paper, we address this problem through a new security validation framework, SoCCCAR, that accounts for asynchronous resets. The framework involves (1) efficient extraction of reset-controlled events while avoiding combinatorial explosion, and (2) concolic testing for systematic exploration of the extracted design space. Our experiments demonstrate that SoCCAR can achieve almost perfect detection accuracy and verification time of a few seconds on realistic SoC designs.

Garbled Circuits (GCs) represent fundamental and powerful tools in cryptography, and many variants of GCs have been considered since their introduction. An important property of the garbled circuits is that they can be evaluated securely if and only if exactly 1 key for each input wire is obtained: no less and no more.

In this work we study the case when: 1) some of the wire-keys are missing, but we are still interested in computing the output of the garbled circuit and 2) the evaluator of the GC might have both keys for a constant number of wires. We start to study this question in terms of non-interactive multi-party computation (NIMPC) which is strongly connected with GCs. In this notion there is a fixed number of parties ($n$) that can get correlated information from a trusted setup. Then these parties can send an encoding of their input to an evaluator, which can compute the output of the function. Similarly to the notion of ad hoc secure computation proposed by Beimel et al. [ITCS 2016], we consider the case when less than $n$ parties participate in the online phase, and in addition we let these parties colluding with the evaluator. We refer to this notion as Threshold NIMPC. In addition, we show that when the number of parties participating in the online phase is a fixed threshold $l\leq n$ then it is possible to securely evaluate any $l$-input function. We build our result on top of a new secret-sharing scheme (which can be of independent interest) and on the results proposed by Benhamouda, Krawczyk and Rabin [Crypto 2017]. Our protocol can be used to compute any function in NC1 in the information-theoretic setting and any function in $P$ assuming one-way functions. As a second (and main) contribution, we consider a slightly different notion of security in which the number of parties that can participate in the online phase is not specified, and can be any number $c$ above the threshold $l$ (in this case the evaluator cannot collude with the other parties). We solve an open question left open by  Beimel, Ishai and Kushilevitz [Eurocrypt 2017] showing how to build a secure protocol for the case when $c$ is constant, under the Learning with Errors assumption. 

We show a lattice-based solution for commit-and-prove transparent circuit zero-knowledge (ZK) with polylog-communication, the first not depending on PCPs.

We start from compressed $\Sigma$-protocol theory (CRYPTO 2020), which is built around basic $\Sigma$-protocols for opening an arbitrary linear form on a long secret vector that is compactly committed to. These protocols are first compressed using a recursive ``folding-technique'' adapted from Bulletproofs, at the expense of logarithmic rounds. Proving in ZK that the secret vector satisfies a given constraint -- captured by a circuit -- is then by (blackbox) reduction to the linear case, via arithmetic secret-sharing techniques adapted from MPC. Commit-and-prove is also facilitated, i.e., when commitment(s) to the secret vector are created ahead of any circuit-ZK proof. On several platforms (incl. DL) this leads to logarithmic communication. Non-interactive versions follow from Fiat-Shamir.

This abstract modular theory strongly suggests that it should somehow be supported by a lattice-platform as well. However, when going through the motions and trying to establish low communication (on an SIS-platform), a certain significant lack in current understanding of multi-round protocols is exposed.

Namely, as opposed to the DL-case, the basic $\Sigma$-protocol in question typically has poly-small challenge space. Taking into account the compression-step -- which yields non-constant rounds -- and the necessity for parallelization to reduce error, there is no known tight result that the compound protocol admits an efficient knowledge extractor. We resolve the state of affairs here by a combination of two novel results which are fully general and of independent interest. The first gives a tight analysis of efficient knowledge extraction in case of non-constant rounds combined with poly-small challenge space, whereas the second shows that parallel repetition indeed forces rapid decrease of knowledge error.

Moreover, in our present context, arithmetic secret sharing is not defined over a large finite field but over a quotient of a number ring and this forces our careful adaptation of how the linearization techniques are deployed.

We develop our protocols in an abstract framework that is conceptually simple and can be flexibly instantiated. In particular, the framework applies to arbitrary rings and norms.

As a byproduct, our compressed $\Sigma$-protocol can double as a PoK for an SIS preimage. In this mode of operation, it improves the communication-efficiency of the PoK by Bootle et al. (CRYPTO 2020).

Blind signatures, introduced by Chaum (Crypto’82), allows a user to obtain a signature on a message without revealing the message itself to the signer. Thus far, all existing constructions of round-optimal blind signatures are known to require one of the following: a trusted setup, an interactive assumption, or complexity leveraging. This state-of-the-affair is somewhat justified by the few known impossibility results on constructions of round-optimal blind signatures in the plain model (i.e., without trusted setup) from standard assumptions. However, since all of these impossibility results only hold under some conditions, fully (dis)proving the existence of such round-optimal blind signatures has remained open.

In this work, we provide an affirmative answer to this problem and construct the first round-optimal blind signature scheme in the plain model from standard polynomial-time assumptions. Our construction is based on various standard cryptographic primitives and also on new primitives that we introduce in this work, all of which are instantiable from classical and post-quantum standard polynomial-time assumptions. The main building block of our scheme is a new primitive called a blind-signature-conforming zero-knowledge (ZK) argument system. The distinguishing feature is that the ZK property holds by using a quantum polynomial-time simulator against non-uniform classical polynomial-time adversaries. Syntactically one can view this as a delayed-input three-move ZK argument with a reusable first message, and we believe it would be of independent interest.

Group key exchange (GKE) protocols let a group of users jointly establish fresh and secure key material. Many flavors of GKE have been proposed, differentiated by, among others, whether group membership is static or dynamic, whether a single key or a continuous stream of keys is established, and whether security is provided in the presence of state corruptions (post-compromise security). In all cases, an indispensable ingredient to the rigorous analysis of a candidate solution is a corresponding formal security model. We observe, however, that most GKE-related publications are more focused on building new constructions that have more functionality or are more efficient than prior proposals, while leaving the job of identifying and working out the details of adequate security models a subordinate task.

In this systematization of knowledge we bring the formal modeling of GKE security to the fore by revisiting the intuitive goals of GKE, critically evaluating how these goals are reflected (or not) in the established models, and how they would be best considered in new models. We classify and compare characteristics of a large selection of game-based GKE models that appear in the academic literature, including those proposed for GKE with post-compromise security. We observe a range of shortcomings in some of the studied models, such as dependencies on overly restrictive syntactical constrains, unrealistic adversarial capabilities, or simply incomplete definitions. Our systematization enables us to identify a coherent suite of desirable characteristics that we believe should be represented in all general purpose GKE models. To demonstrate the feasibility of covering all these desirable characteristics simultaneously in one concise definition, we conclude with proposing a new generic reference model for GKE.

The ultimate goal in modern secure e-voting is to enable everyone to verify whether the final election result correctly reflects the votes chosen by the (human) voters, without exposing how each individual voted. These fundamental security properties are called end-to-end verifiability and voter privacy.

Unfortunately, it turns out to be very challenging to pursue these properties simultaneously, especially when the latter must be future-proofed against the rise of quantum computers. In this work, we show, for the first time, a practical approach to do this.

We present Epoque, the first end-to-end verifiable, voter-private, post-quantum-secure homomorphic e-voting protocol. It achieves its properties through the combination of practical lattice-based cryptographic primitives only, in a novel way. We formally prove all our security claims under common trust and hardness assumptions.

At the core of Epoque lies an efficient identity-based encryption (IBE) scheme with blazingly fast master-key decryption. It is the component that makes the efficient tallying of thousands or millions of ballots a practical possibility. In order to demonstrate its practicality, we fully implemented it and provide detailed benchmarks; we believe this latter contribution is of independent interest beyond the specific e-voting application.

Secure multi-party computation (MPC) allows multiple parties to perform secure joint computations on their private inputs. Today, applications for MPC are growing with thousands of parties wishing to build federated machine learning models or trusted setups for blockchains. To address such scenarios we propose a suite of novel MPC protocols that maximize throughput when run with large numbers of parties. In particular, our protocols have both communication and computation complexity that decrease with the number of parties. Our protocols build on prior protocols based on packed secret-sharing, introducing new techniques to build more efficient computation for general circuits. Specifically, we introduce a new approach for handling linear attacks that arise in protocols using packed secret-sharing and we propose a method for unpacking shared multiplication triples without increasing the asymptotic costs. Compared with prior work, we avoid the $\log |C|$ overhead required when generically compiling circuits of size $|C|$ for use in a SIMD computation, and we improve over folklore ``committee-based'' solutions by a factor of $O(s)$, the statistical security parameter. In practice, our protocol is up to $10X$ faster than any known construction, under a reasonable set of parameters.

In this work, we study verifiable random functions (VRF) that may resist quantum threats. VRFs have a wide range of applications and play a key role in Proof-of-Stake blockchains, such as Algorand. Our main proposal is a VRF construction X-VRF based on XMSS signature scheme. Our construction is the first quantum-safe VRF proposal based on symmetric primitives. Being based on symmetric-key primitives that have long been studied, X-VRF provides strong confidence that it can withstand quantum attacks in the long run. Despite its stateful nature, we empower XMSS with blockchain so that the users do not need to maintain individual states. While increasing the usability of XMSS, our technique also enforces honest behaviour when creating an X-VRF output so as to satisfy the fundamental uniqueness property of VRFs. We show how X-VRF can be used in the Algorand setting to extend it to a quantum-safe blockchain, and provide various instances of X-VRF, each may suit a different setting. Our X-VRF instances are the most efficient quantum-safe VRF proposals in the literature.Our extensive performance evaluation, analysis, and implementation indicates the effectiveness of our pro-posed constructions in practice. In particular, we show that X-VRF can maintain a very competitive throughput close to the existing Algorand protocol and can produce substantially more transactions per second than Bitcoin.

Let $\mathbb{F}_{\!q}$ be a finite field and $E_b\!: y^2 = x^3 + b$ be an ordinary (i.e., non-supersingular) elliptic curve (of $j$-invariant $0$) such that $\sqrt{b} \in \mathbb{F}_{\!q}$ and $q \not\equiv 1 \: (\mathrm{mod} \ 27)$. For example, these conditions are fulfilled for the group $\mathbb{G}_1$ of the curves BLS12-381 ($b=4$) and BLS12-377 ($b=1$) and for the group $\mathbb{G}_2$ of the curve BW6-761 ($b=4$). The curves mentioned are a de facto standard in the real world pairing-based cryptography at the moment. This article provides a new constant-time hash function $H\!: \{0,1\}^* \to E_b(\mathbb{F}_{\!q})$ indifferentiable from a random oracle. Its main advantage is the fact that $H$ computes only one exponentiation in $\mathbb{F}_{\!q}$. In comparison, the previous fastest constant-time indifferentiable hash functions to $E_b(\mathbb{F}_{\!q})$ compute two exponentiations in $\mathbb{F}_{\!q}$. In particular, applying $H$ to the widely used BLS multi-signature with $m$ different messages, the verifier should perform only $m$ exponentiations rather than $2m$ ones during the hashing phase.

An (n,m)-function is a mapping from GF(2^n) to GF(2^m). Such functions have numerous applications across mathematics and computer science, and in particular are used as building blocks of block ciphers in symmetric cryptography. The classes of APN and AB functions have been identified as cryptographically optimal with respect to providing resistance against two of the most powerful known cryptanalytic attacks, namely differential and linear cryptanalysis. The classes of APN and AB functions are directly related to optimal objects in many other branches of mathematics, and have been a subject of intense study since at least the early 90's. Finding new constructions of these functions is hard; one of the most significant practical issues is that any tentatively new function must be proven inequivalent to all the known ones. Testing equivalence can be significantly simplified by computing invariants, i.e. properties that are preserved by the appropriate equivalence relation. In this paper, we survey the known invariants for CCZ- and EA-equivalence, with a particular focus on their utility in distinguishing between inequivalent instances of APN and AB functions. We evaluate each invariant with respect to how easy it is to implement in practice, how efficiently it can be calculated on a computer, and how well it can distinguish between distinct EA- and CCZ-equivalence classes.

The safety of the Bitcoin blockchain relies on strong network synchrony. Therefore, violating the blockchain safety requires strong adversaries who control a mining pool with 51% hash rate. In this paper, we show that the network synchrony does not hold in the real world Bitcoin network, which can be exploited to amortize the cost of various attacks. Towards that, first we construct the Bitcoin ideal world functionality to formally specify its ideal execution model in a synchronous network. We then develop a large-scale data collection system through which we connect with more than 36K IP addresses of the Bitcoin nodes and identify 359 mining nodes. We contrast the Bitcoin ideal functionality against real world measurements to expose network anomalies that can be exploited to optimize the existing attacks. Particularly, we observe high block propagation delay in the Bitcoin network causing weak network synchronization: on average, in 9.97 minutes, only 39% nodes have the up-to-date blockchain. Through a fine-grained analysis, we discover non-uniform block propagation delay among the mining nodes showing that the Bitcoin network is asynchronous. To realize the threat of asynchronous network, we present the HashSplit attack that allows an adversary to orchestrate concurrent mining on multiple branches of the blockchain to violate common prefix and chain quality properties. We also propose the attack countermeasures by releasing a Bitcoin Core version that closely models the Bitcoin ideal functionality. Our measurements, theoretical modeling, pro-posed attack, and countermeasures open new directions in the security evaluation of Bitcoin and similar blockchain systems

The one-time-pad (OTP) is a classical yet the strongest cipher. Although the OTP offers perfect secrecy and is quantum-safe, it has cryptographic as well as operational weaknesses. Cryptographically its encryption is malleable. Operationally a key used more than once by mistake can lead to successful breaking of the OTP. Hence, there is a need for extensions of OTP to address these two weaknesses simultaneously keeping all the strength of OTP intact. To address this need, we propose two extensions of OTP. In the process we also prove a relation between block ciphers and Latin rectangles.

Event date: 17 March to 20 March 2021
Submission deadline: 25 March 2021

PhD Fellow position in Cybersecurity for 5G

The University of South-Eastern Norway (USN) seeks a dedicated an able phd fellow for work in cybersecurity for the 5G core networks. The context is for critical communications and specifically for emergency services, which in Norway will be migrating from Tetra to 4G/5G commercial networks during the next 5-6 years. This is a paid position and the duration is 3 years fulltime work. The phd fellow will join the Secure Distributed Systems reach group, and the research will be done in the context of the Raksha research project. Raksha is a RCN funded joint project with SINTEF Digital as the leading partner; Other partners and advisors include the University of Oslo, SimulaMet and the Norwegian Communications Authority, the Norwegian Security Authority, etc.

Special conditions: Due to the sensitive nature of the research topic, it is a requirement the applicant must be an EU national or come form a NATO country. Additionally, citizens from Australia or New Zealand may apply. (Background: A Norwegian security clearance may be required.) This is an absolute requirement.

NOTE: Students that will complete their master’s degree no later than June 2021 may apply.

A (rough and unofficial) English translation of the Norwegian-only announcement can be requested.

Closing date for applications:

Contact: Professor Geir M. Køien

More information: https://www.jobbnorge.no/ledige-stillinger/stilling/193704/stipendiat-i-cybersikkerhet-5g

Event date: 17 August to 20 August 2021
Submission deadline: 30 April 2021
Notification: 3 June 2021

This paper presents HashWires, a hash-based range proof protocol that is applicable in settings for which there is a trusted third party (typically a credential issuer) that can generate commitments. We refer to these as "credential-based" range proofs (CBRPs). HashWires improves upon hashchain solutions that are typically restricted to micro-payments for small interval ranges, achieving an exponential speedup in proof generation and verification time. In terms of proof size and computational cost, we show that HashWires compares favorably against Bulletproofs for both 32- and 64-bit numeric values. Although CBRPs are inherently less flexible than general zero-knowledge range proofs, we provide a number of applications in which a credential issuer can leverage HashWires to provide range proofs for private values, without having to rely on heavyweight cryptographic tools and assumptions.