International Association
for Cryptologic Research

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.

Physical attacks are serious threats to hardware implementations of any strong cryptographic primitive. Particularly, fault injection attack is considered as a powerful technique to successfully attack embedded cryptographic implementations since various fault injection mechanisms from simple clock glitches to more advanced techniques like laser fault injection can lead to devastating attacks, even with just a single successfully injected fault. Given these critical attack vectors, researchers in academia and industry came up with a long list of dedicated countermeasures to thwart such attacks.

However, the validation of proposed countermeasures is mostly performed on custom adversary models that are often not tightly coupled with the actual physical behavior of available fault injection mechanisms and techniques and, hence, fail to model the reality accurately. Furthermore, using custom models complicates comparison between different designs and evaluation results. As a consequence, we aim to close this gap by proposing a simple, generic, and consolidated fault injection adversary model in this work that can be perfectly tailored to existing fault injection mechanisms and their physical behavior in hardware. To demonstrate the advantages of our adversary model, we apply it to a cryptographic primitive (i.e., an ASCON S-box) and evaluate it based on different attack vectors. We further show that our proposed adversary model can be used and integrated into the state-of-the-art fault verification tool VerFI. Finally, we provide a discussion on the benefits and differences of our approach compared to already existing evaluation methods and briefly discuss limitations of current available verification tools.

A sizable body of work has identified the importance of architecture and application level security when using logic locking, a family of module level supply chain security techniques, to secure processor ICs. However, prior logic locking research proposes configuring logic locking using only module level considerations. To begin our work, we perform a systematic design space exploration of logic locking in modules throughout a processor IC. This exploration shows that locking with only module level considerations cannot guarantee architecture/application level security, regardless of the locking technique used. To remedy this, we propose a tool-driven security-aware approach to enhance the 2 most effective candidate locking locations, on-chip memory and data path. We show that through minor design modifications of the on-chip memory and data path architecture, one can exponentially improve the architecture/application level security of prior locking art with only a modest design overhead. Underlying our design space exploration and security-aware design approach is ObfusGEM, an open-source logic locking simulation framework released with this work to quantitatively evaluate the architectural effectiveness of logic locking in custom processor architecture configurations.

The Schnorr-Lyubashevsky approach has been shown able to produce secure and efficient signature schemes without trapdoors in the lattice-based setting, exploiting Gaussian distributions in the Euclidean metric and rejection sampling to tune the signature probability distributions. Translating such an approach to the code-based setting has revealed to be challenging, especially for codes in the Hamming metric. In this paper, we propose a new adaptation of the Schnorr-Lyubashevsky framework to codes in the Hamming metric exploiting restricted vectors, which allows avoiding existing attacks. We provide some preliminary arguments to assess the security level of the new scheme and for computing the relevant parameters. We show that the new scheme achieves compact keys and signatures even without considering structured codes.

Designing a block cipher or cryptographic permutation can be approached in many different ways. One such approach, popularized by AES, consists in grouping the bits along the S-box boundaries, e.g., in bytes, and in consistently processing them in these groups. This aligned approach leads to hierarchical structures like superboxes that make it possible to reason about the differential and linear propagation properties using combinatorial arguments. In contrast, an unaligned approach avoids any such grouping in the design of transformations. However, without hierarchical structure, sophisticated computer programs are required to investigate the differential and linear propagation properties of the primitive. In this paper, we formalize this notion of alignment and study four primitives that are exponents of different design strategies. We propose a way to analyze the interactions between the linear and the nonlinear layers w.r.t. the differential and linear propagation, and we use it to systematically compare the four primitives using non-trivial computer experiments. We show that alignment naturally leads to different forms of clustering, e.g., of active bits in boxes, of two-round trails in activity patterns, and of trails in differentials and linear approximations.

In this paper, we for the first time show dedicated quantum collision attacks on SHA-256 and SHA-512. The attacks reach 38 and 39 steps, respectively, which significantly improve the classical attacks for 31 and 27 steps. Both attacks adopt the framework of the previous work that converts many semi-free-start collisions into a 2-block collision, and are faster than the generic attack in the cost metric of time-space tradeoff. We observe that the number of required semi-free-start collisions can be reduced in the quantum setting, which allows us to convert the previous classical 38 and 39 step semi-free-start collisions into a collision. The idea behind our attacks is simple and will also be applicable to other cryptographic hash functions.

Due to their use in crypto-currencies, threshold ECDSA signatures have received much attention in recent years. Though efficient solutions now exist both for the two party, and the full threshold scenario, there is still much room for improvement, be it in terms of protocol functionality, strengthening security or further optimising efficiency.

In the past few months, a range of protocols have been published, allowing for a non interactive -- and hence extremely efficient -- signing protocol; providing new features, such as identifiable aborts (parties can be held accountable if they cause the protocol to fail), fairness in the honest majority setting (all parties receive output or nobody does) and other properties. In some cases, security is proven in the strong simulation based model.

We combine ideas from the aforementioned articles with the suggestion of Castagnos \textit{et al.} (PKC 2020) to use the class group based $\mathsf{CL}$ framework so as to drastically reduce bandwidth consumption.

Building upon this latter protocol we present a new, maliciously secure, full threshold ECDSA protocol that achieving additional features without sacrificing efficiency. Our most basic protocol boasts a non interactive signature algorithm and identifiable aborts. We also propose a more advanced variant that also achieves adaptive security (for the $n$-out-of-$n$ case) and proactive security. Our resulting constructions improve upon state of the art Paillier's based realizations achieving similar goals by up to a 10 factor in bandwidth consumption.