International Association
for Cryptologic Research

This article discusses existing attacks and known weaknesses of BLS aggregate signatures. The goal is clarify the threat model of BLS aggregate signatures, what security properties that they have and do not have. It’s unfortunate that the weaknesses are not documented anywhere in BLS RFC draft v4 [1]. Confusion, ambiguity, misunderstanding all may cause security issues in practice. We hope that this article can help cryptographic practitioners make informed decisions when using BLS aggregate signatures and deploy mitigations at the application/protocol layer because BLS aggregate signatures might not have security guarantees that you need.

We investigate the existence of constant-round post-quantum black-box zero-knowledge protocols for $\mathbf{NP}$. As a main result, we show that there is no constant-round post-quantum black-box zero-knowledge argument for $\mathbf{NP}$ unless $\mathbf{NP}\subseteq \mathbf{BQP}$. As constant-round black-box zero-knowledge arguments for $\mathbf{NP}$ exist in the classical setting, our main result points out a fundamental difference between post-quantum and classical zero-knowledge protocols. Combining previous results, we conclude that unless $\mathbf{NP}\subseteq \mathbf{BQP}$, constant-round post-quantum zero-knowledge protocols for $\mathbf{NP}$ exist if and only if we use non-black-box techniques or relax certain security requirements such as relaxing standard zero-knowledge to $\epsilon$-zero-knowledge. Additionally, we also prove that three-round and public-coin constant-round post-quantum black-box $\epsilon$-zero-knowledge arguments for $\mathbf{NP}$ do not exist unless $\mathbf{NP}\subseteq \mathbf{BQP}$.

We propose protocols for obliviously evaluating finite-state machines, i.e., the evaluation is shared between the provider of the finite-state machine and the provider of the input string in such a manner that neither party learns the other's input, and the states being visited are hidden from both. For alphabet size $|\Sigma|$, number of states $|Q|$, and input length $n$, previous solutions have either required a number of rounds linear in $n$ or communication $\Omega(n|\Sigma||Q|\log|Q|)$. Our solutions require 2 rounds with communication $O(n(|\Sigma|+|Q|\log|Q|))$. We present two different solutions to this problem, a two-party one and a setting with an untrusted but non-colluding helper.

The Tor anonymity network is often abused by some attackers to (anonymously) convey attack traffic. These attacks abuse Tor exit relays (i.e., the relays through which traffic exits Tor) by making it appear the attack originates there; as a result, many website operators indiscriminately block all Tor traffic (by blacklisting all exit IPs), reducing the usefulness of Tor.

Recent research shows that majority of these attacks are ones that generate high traffic volume (e.g., Denial-of-Service attacks). This suggests that a simple solution such as throttling traffic flow at the Tor exits may permit early detection of these attacks.

However, naively monitoring and throttling traffic at the Tor exits can endanger the privacy of the network's users. Indeed, many recent works have proposed private measurement systems that support safe aggregation of exit statistics. However, these systems do not permit identification of "unlinkable" connections that are part of a high-volume attack. Doing so could allow Tor to take proper remedial actions, such as dropping the attack traffic, but care must be taken to protect privacy.

We present ZXAD (pronounced "zed-zad"), the first zero-knowledge based private Tor exit abuse detection system. ZXAD detects large-volume traffic attacks without revealing any information, apart from the fact that some user is conveying a high volume of traffic through Tor. We formally prove the correctness and security of ZXAD. We also measure two proof-of-concept implementations of our zero-knowledge proofs and show that ZXAD operates with low bandwidth and processing overheads.

Given $2n$-to-$n$ compression functions $h_1,h_2,h_3$, we build a new $5n$-to-$n$ compression function $\mathrm{T}_5$, using only $3$ compression calls: $\mathrm{T}_5(m_1, m_2, m_3, m_4, m_5) := h_3( h_1(m_1, m_2)\oplus m_5, h_2(m_3, m_4)\oplus m_5) \oplus m_5$.

We prove that this construction matches Stam's bound, by providing $\tilde{O}(q^2/2^n)$ collision security and $O(q^3/2^{2n}+ nq/2^n)$ preimage security (the latter term dominates in the region of interest, when $q<2^{n/2}$). In particular, it provides birthday security for hashing $5$ inputs using three $2n$-to-$n$ compression calls, instead of only $4$ inputs in prior constructions.

Thus, we get a sequential variant of the Merkle-Damgård (MD) hashing, where $t$ message blocks are hashed using only $3t/4$ calls to the $2n$-to-$n$ compression functions; a $25\%$ saving over traditional hash function constructions. This time reduces to $t/4$ (resp. $t/2$) sequential calls using $3$ (resp. $2$) parallel execution units; saving a factor of $4$ (resp. $2$) over the traditional MD-hashing, where parallelism does not help to process one message.

We also get a novel variant of a Merkle tree, where $t$ message blocks can be processed using $0.75(t-1)$ compression function calls and depth $0.86 \log_2 t$, thereby saving $25\%$ in the number of calls and $14\%$ in the update time over Merkle trees. We provide two modes for a local opening of a particular message block: conservative and aggressive. The former retains the birthday security, but provides longer proofs and local verification time than the traditional Merkle tree.

For the aggressive variant, we reduce the proof length to a $29\%$ overhead compared to Merkle trees ($1.29\log_2 t$ vs $\log_2 t$), but the verification time is now 14\% faster ($0.86\log_2 t$ vs $\log_2 t$). However, birthday security is only shown under a plausible conjecture related to the 3-XOR problem, and only for the (common, but not universal) setting where the root of the Merkle tree is known to correspond to a valid $t$-block message.

We give an exposition of supersingular isogeny graphs, quaternion ideal graphs and Bruhat–Tits trees, and of their connections. Bruhat–Tits trees are combinatorial objects whose vertices and edges have a very simple representation as two-by-two matrices, which, as we show, is useful for understanding certain aspects of the corresponding elliptic curves and isogenies. Moreover Bruhat–Tits trees can be given an orientation and a notion of depth that we translate into the setting of supersingular isogeny graphs. We give some suggestions towards using Bruhat–Tits trees as a tool for cryptanalysis of certain cryptosystems based on supersingular isogeny graphs.

The construction of linear codes from functions over finite fields has been extensively studied in the literature since determining the parameters of linear codes based on functions is rather easy due to the nice structure of functions. In this paper, we derive 3-weight and 4-weight linear codes from weakly regular plateaued unbalanced functions in the recent construction method of linear codes over the finite fields of odd characteristics. The Hamming weights and their weight distributions for proposed codes are determined by using the Walsh transform values and Walsh distribution of the employed functions, respectively. We next derive projective 3-weight punctured codes with good parameters from the constructed codes. These punctured codes may be almost optimal due to the Griesmer bound, and they can be employed to obtain association schemes. We also derive projective 2-weight and 3-weight subcodes with flexible dimensions from partially bent functions, and these subcodes can be employed to design strongly regular graphs. We finally show that all constructed codes are minimal, which approve that they can be employed to design high democratic secret sharing schemes.

We introduce folding schemes for $\mathsf{NP}$, an interactive protocol between a prover and a verifier to combine two $N$-sized $\mathsf{NP}$ instances over a finite field $\mathbb{F}$ into a single $N$-sized instance such that the folded instance is satisfiable only if the original instances are satisfiable. In particular, we devise a folding scheme for relaxed R1CS, a characterization of $\mathsf{NP}$ that is especially amenable to folding. The verifier's cost and the communication in the folding scheme are both $O_\lambda(1)$, where $\lambda$ is the security parameter, assuming any additively-homomorphic commitment scheme that provides $O_\lambda(1)$-sized commitments to $N$-sized vectors over $\mathbb{F}$. Additionally, the protocol is honest-verifier zero-knowledge and public coin, so it can be made non-interactive in the ROM using the Fiat-Shamir transform.

We then construct incrementally verifiable computation (IVC) from folding schemes by using a "verifier circuit" that at each recursive step folds an entire R1CS instance representing computation (including a copy of the verifier circuit) at its prior step into a running relaxed R1CS instance. A distinctive aspect of our approach to IVC is that it achieves the smallest verifier circuit (a key metric to minimize in IVC) in the literature: the circuit is constant-sized and its size is dominated by two group scalar multiplications. We then show that the running relaxed R1CS instance can be proven in zero-knowledge with a succinct proof using a variant of an existing zkSNARK.

Putting these together, we obtain Nova, a new zero-knowledge proof system for incremental computations, where for an $N$-sized computation with $C$-sized steps, the prover runs in $O_\lambda(N)$ time to produce $O_\lambda(\log{C})$-sized proofs that can be verified in $O_\lambda(C)$ time. Nova does not require a trusted setup nor performs FFTs, so it can be efficiently instantiated with any cycles of elliptic curves where DLOG is hard. Furthermore, at each step, the prover time is dominated by two $\approx$$C$-sized multiexponentiations. Finally, Nova can achieve $O_\lambda(\log{C})$ verification time at the cost of employing a pairing-friendly elliptic curve where SXDH is hard.

Side channel attacks are serious concern for implementation of cryptosystems. Masking is an effective countermeasure against them and masked implementation of block ciphers has been attracting active research. It is an obstacle to efficient masked implementation that the complexity of an evaluation of multiplication is quadratic in the order of masking. A direct approach to this problem is to explore methods to reduce the number of multiplications required to represent an S-box. An alternative approach proposed by Carlet et al. in 2015 is to represent an S-box as composition of polynomials with low algebraic degrees. We follow the latter approach and propose to use a special type of polynomials with a low algebraic degree as components, which we call generalized multiplication (GM) polynomials. The masking scheme for multiplication can be applied to a GM polynomial, which is more efficient than the masking scheme for a polynomial with a low algebraic degree. Our experimental results show that, for 4-/6-/8-bit permutations, the proposed decomposition method is more efficient than the method by Carlet et al. in most cases in terms of the number of evaluations of low-algebraic-degree polynomials required by masking.

The supersingular isogeny-based key encapsulation (SIKE) suite stands as an attractive post-quantum cryptosystem with its relatively small public keys. Public key sizes in SIKE can further be compressed by computing pairings and solving discrete logarithms in certain subgroups of finite fields. This comes at a cost of precomputing and storing large discrete logarithm tables. In this paper, we propose several techniques to optimize memory requirements in computing discrete logarithms in SIKE, and achive to reduce table sizes by a factor of 4. We implement our techniques and verify our theoretical findings.

In recent years a new type of block ciphers and hash functions over a (large) field, such as MiMC and GMiMC, have been designed. Their security, particularly over a prime field, is mainly determined by algebraic cryptanalysis techniques, such as Gr\"obner basis and interpolation attacks. In SAC 2019, Li and Preneel presented low memory interpolation cryptanalysis against the MiMC and Feistel-MiMC designs.

In this work we answer the open question posed in their work and show that low memory interpolation cryptanalysis can be extended to unbalanced Feistel networks (UFN) with low degree functions, and in particular to the GMiMC design. Our attack applies to UFNs with expanding and contracting round functions keyed either via identical (univariate) or distinct round keys (multivariate). Since interpolation attacks do not necessarily yield the best possible attacks over a binary extension field, we focus our analysis on prime fields GF(p).

Our next contribution is to develop an improved technique for a more efficient key recovery against UFNs with expanding round function. We show that the final key recovery step can be reduced not only to the gcd but also to the root finding problem. Despite its higher theoretical complexity, we show that our approach has a particularly interesting application on Sponge hash functions based on UFNs, such as GMiMCHash.

We illustrate for the first time how our root finding technique can be used to find collision, second preimage and preimage attacks on (reduced round) members of the GMiMCHash family. In addition, we support our theoretical analysis with small-scale experimental results.

Multiparty computation protocols (MPC) are said to be \emph{secure against covert adversaries} if the honest parties are guaranteed to detect any misbehavior by the malicious parties with a constant probability. Protocols that, upon detecting a cheating attempt, additionally allow the honest parties to compute certificates, which enable third parties to be convinced of the malicious behavior of the accused parties, are called \emph{publicly verifiable}. In this work, we make several contributions to the domain of MPC with security against covert adversaries.

We identify a subtle flaw in a protocol of Goyal, Mohassel, and Smith (Eurocrypt 2008) and show how to modify their original construction to obtain security against covert adversaries.

We present generic compilers that transform arbitrary passively secure preprocessing protocols, i.e. protocols where the parties have no private inputs, into protocols that are secure against covert adversaries and publicly verifiable. Using our compiler, we construct the first efficient variants of the BMR and the SPDZ protocols that are secure and publicly verifiable against a covert adversary that corrupts all but one party and also construct variants with covert security and identifiable abort.

We observe that an existing impossibility result by Ishai, Ostrovsky, and Seyalioglu (TCC 2012) can be used to show that there exist certain functionalities that cannot be realized by parties, that have oracle-access to broadcast and arbitrary two-party functionalities, with information-theoretic security against a covert adversary.

Cryptographic objects with updating capabilities have been proposed by Bellare, Goldreich and Goldwasser (CRYPTO'94) under the umbrella of incremental cryptography. They have recently seen increased interest, motivated by theoretical questions (Ananth et al., EC'17) as well as concrete practical motivations (Lehmann et al., EC'18; Groth et al. CRYPTO'18; Klooss et al., EC'19). In this work, the form of updatability we are particularly interested in is that primitives are key-updatable and allow to update old cryptographic objects, e.g., signatures or message authentication codes, from the old key to the updated key at the same time without requiring full access to the new key (i.e., only via a so-called update token).

Inspired by the rigorous study of updatable encryption by Lehmann and Tackmann (EC'18) and Boyd et al. (CRYPTO'20), we introduce a definitional framework for updatable signatures (USs) and message authentication codes (UMACs). We discuss several applications demonstrating that such primitives can be useful in practical applications, especially around key rotation in various domains, as well as serve as building blocks in other cryptographic schemes. We then turn to constructions and our focus there is on ones that are secure and practically efficient. In particular, we provide generic constructions from key-homomorphic primitives (signatures and PRFs) as well as direct constructions. This allows us to instantiate these primitives from various assumptions such as DDH or CDH (latter in bilinear groups), or the (R)LWE and the SIS assumptions. As an example, we obtain highly practical US schemes from BLS signatures or UMAC schemes from the Naor-Pinkas-Reingold PRF.

This paper proposes a new ultra lightweight cipher RAGHAV. RAGHAV is a Substitution-Permutation (SP) network, which operates on 64 bit plaintext and supports a 128/80 bit key scheduling. It needs only 994.25 GEs by using 0.13µm ASIC technology for a 128 bit key scheduling. It also needs less memory i.e. 2204 bytes of FLASH memory , which is less as compared to all existing S-P network lightweight ciphers. This paper presents a complete security analysis of RAGHAV, which includes basic attacks like linear cryptanalysis and differential cryptanalysis. This paper also covers advanced attack like zero correlation attack, Biclique attack, Algebraic attack, Avalanche effect, key collision attack and key schedule attack. In this cipher,use of block permutation helps the design to improve the throughput. RAGHAV cipher uses 8 bit permutations with S-Box which results in better diffusion mechanism. RAGHAV consumes very less power around 24mW which is less as compared to all existing lightweight ciphers. RAGHAV cipher scores on all design metrics and is best suited for applications like IoT.

Within the scope of the NIST Privacy-Enhancing Cryptography (PEC) project, the preliminary draft "Toward a PEC use-case suite" is open for public comments. See https://csrc.nist.gov/Projects/pec/suite for the document, contact info and suggested feedback template.

Feedback by March 2021 is most welcome. Subsequent feedback will also be appreciated. It is expected that a followup draft version will later be posted for a new period of public comments.

Event date: 9 April 2021
Submission deadline: 29 March 2021
Notification: 2 April 2021

Cryptology forms the backbone of modern digital security. While in theory it is known how to make secure cryptosystems that are asymptotically secure, a considerable gap with practice is demonstrated time and again by breaks of practical, implemented cryptosystems, deployed as part of a larger security ecosystem.

The project “concrete cryptology” aims to provide concrete and meaningful security guarantees from low-level implementation to high-level deployment. Our focus here is on algorithmic aspects of side-channel attacks, as well as integrating security claims regarding side-channel resistance into the context of the larger cryptosystem. Our aim is to provide research that is practically relevant, for instance by exploiting access to Simula’s HPC resources to evaluate novel attacks.

The postdoc will have considerable freedom in selecting specific problems to work on within the larger scope of the project. We are looking for interested candidates who have completed, or are about to complete, a PhD degree in cryptology or a suitably related relevant field.

Simula UiB offers

• Excellent opportunities for performing high-quality research, as part of a highly competent and motivated team of international researchers and engineers;

• An informal and inclusive international working environment - where master students, PhDs, Postdocs and seniors work closely together;

• Generous support for travel and opportunities to build international networks, through established collaboration with industry, exchange programs and research visits with other universities, and funding to attend conferences.

• A competitive salary. Starting salary from NOK 535 200

• Numerous benefits: company cabin, BabyBonus, sponsored social events, generous equipment budgets, comprehensive travel/health insurance policy, etc.

• Relocation assistance: accommodation, visas, complimentary Norwegian language courses, etc.

• Wellness and work-life balance.

For more information and applying: https://www.simula.no/about/job/postdoc-concrete-cryptology

Closing date for applications:

Contact: Åsfrid Persson, Simula UiB AS

More information: https://www.simula.no/about/job/postdoc-concrete-cryptology

As part of the SecInt Doctoral College (SecInt-DK), TU Wien is offering four positions as university assistant (Pre-Doc) for 4 years. Expected start: 01.05.2021.

Tasks:

• Collaboration on current research projects
• Deepening scientific knowledge
• Collaboration in academic teaching
• Writing a dissertation and publications
• Participation in regular events organized by the SecInt Doctoral College
• Completion of an internship with one of our international research partners
• Presentation of research results and participation in scientific event

The Research Projects: The SecInt Doctoral college offers 4 interdisciplinary research projects from the areas of Formal Methods, Security and Privacy, and Machine Learning, that are each supervised by at least two professors from the corresponding research areas. Additional details on the individual projects can be found at https://secint.visp.wien/projects and https://jobs.tuwien.ac.at/Job/147334.

We offer:

• Diverse and exciting tasks, with lots of interdisciplinary collaboration
• Continuing personal and professional education and flexible working hours
• Central location with very good accessibility in a city regularly ranked first worldwide for life quality
• Possibility of an internship with one of our international research partners
• Very competitive salary

Your profile:

• Completion of a master or diploma curriculum in computer science, electrical engineering or another related field
• Experience in Mathematical Modeling, Computational Logic, Formal Methods, Security and Privacy, Robotics and/or Machine Learning
• Very good skills in English communication and writing.
• Readiness for interdisciplinary collaboration
• Team competences, problem-solving skills and innovative ability

A predoctoral researcher at TU Wien currently receives a minimum of EUR 2228/month gross, 14 times/year for 30 hours/week and EUR 2971/month for 40 hours/week.

We look forward to receiving your application until 11.04.2021

Closing date for applications:

Contact: https://jobs.tuwien.ac.at/Job/147334

More information: https://secint.visp.wien/application/

In this paper, we present a unified approach to quantifying the information leakages in the most general code-based masking schemes. Specifically, by utilizing a uniform representation, we highlight first that the side-channel resistance of all code-based masking schemes can be quantified by an all-in-one framework consisting of two easy-to-compute parameters (the dual distance and the number of conditioned codewords) from a coding-theoretic perspective. In particular, we use signal-to-noise ratio (SNR) and mutual information (MI) as two complementary metrics, where a closed-form expression of SNR and an approximation of MI are proposed by connecting both metrics to the two coding-theoretic parameters.

Second, taking the connection between Reed-Solomon code and SSS (Shamir's Secret Sharing) scheme, the SSS-based masking is viewed as a special case of generalized code-based masking. Hence as a straightforward application, we evaluate the impact of public points on the side-channel security of SSS-based masking schemes, namely the polynomial masking, and enhance the SSS-based masking by choosing optimal public points for it. Interestingly, we show that given a specific security order, more shares in SSS-based masking leak more information on secrets in an information-theoretic sense. Finally, our approach provides a systematic method for optimizing the side-channel resistance of every code-based masking. More precisely, this approach enables us to select optimal linear codes (parameters) for the generalized code-based masking by choosing appropriate codes according to the two coding-theoretic parameters. Summing up, we provide a best-practice guideline for the application of code-based masking to protect cryptographic implementations.

Deep learning has played an important role in many fields. It shows significant potential to cryptanalysis. Differential cryptanalysis is an important method in the field of block cipher cryptanalysis. The key point of differential cryptanalysis is to find a differential distinguisher with longer rounds or higher probability. Firstly, we describe how to construct the ciphertext pairs required for differential cryptanalysis based on deep learning. Based on this, we train 9-round and 8-round differential distinguisher of SIMON32 based on deep residual neural networks. Secondly, we explore the impact of the input difference patterns on the accuracy of the distinguisher based on deep learning. For the input difference with Hamming weight of 1, the accuracy of 9-round distinguisher is different between the first 16 bits and the last 16 bits for non-zero bit positions. This is mainly caused by that its nonlinear operation is mainly concentrated in the first 16 bits. We also find that the accuracy of the distinguisher is different even if the input differences come from the differential characteristics with the same probability. Finally, we construct a last subkey recovery attack on 11-Round SIMON32 with practical data and time complexities. Our attack only uses about 29 chosen plaintexts and only needs about 45s for an attack with a success rate of over 90% using our workstation, which does not exceed 2^18:5 11-round encryption. At the same time, we extend the neural 9-round distinguisher to a 11-round distinguisher based on SAT, and propose a last subkey recovery attack on 13-Round SIMON32 using 2^12:5 chosen plaintexts with a success rate of over 90%. Compared with traditional approach, the complexity of the method based on deep learning is lower, both in time complexity and data complexity.