International Association
for Cryptologic Research

The Institute of Applied Information Processing and Communications (aka IAIK) is the largest university institute in Austria for research and education in security and privacy. It has been active in this field for more than 30 years and currently employs more than 60 researchers. Within the "Secure Systems" area of our institute Sujoy Sinha Roy is establishing the new research group "Cryptographic Engineering”.

In order to complement our team, we are looking for a fulltime PhD researcher in Post-Quantum Cryptography.

Responsibilities:
The PhD researcher will be working on the implementation and side-channel security aspects of post-quantum cryptography within the “Cyroptografic Engineering” group within the “Secure Systems” area at IAIK.
The PhD candidate will have to start by May/June 2021.

Required Qualifications:
• MSc degree (or close to completion) in computer science, information and computer engineering, software development, mathematics, or a related field.
• Research experience from MSc/BSc projects.
• Outstanding candidates with BSc degree and publications in related research area are also welcome.
• Experience with cryptography, programming, and digital circuit design (ASIC or FPGA) design

How to apply:
Applications, curriculum vitae and other documents should preferably be uploaded here https://free.formcloud.de/formcycle/form/provide/7780/. Please select „7050 – PhD 2021 – crypteng" as a reference number. The application deadline is April 20th 2021.

Closing date for applications:

Contact: For more detailed information please conctact Sujoy Sinha Roy - sujoy.sinharoy@iaik.tugraz.at.

More information: https://www.tugraz.at/index.php?id=50397

The Department of Computer Science at the University of Manchester (UK) wishes to appoint a Senior Lecturer in Systems Security. The new appointment will complement existing world-class research in software security and automated reasoning.

Applicants should be computer scientists with a strong interest and track record in a relevant area of systems security, for example, cryptography, operating systems and virtualization, distributed systems security, authentication, authorization, and accountability. We also encourage applicants with a strong interest and track record in code and data integrity, malware analysis, integrity, trustworthiness, privacy, and anonymity. You will be a member of the Formal Methods Group with access to expertise in program analysis and reasoning methods. We are particularly interested in developing collaborations involving several groups within the department and wider University. For example, an exciting opportunity exists to work closely with the well-known advanced processor technologies group to study applications in massively parallel software and the IoT. Thus, experience and interest in collaborative research are particularly welcome.

You should hold a relevant Ph.D. or equivalent, have an excellent international publication record in top security conferences (e.g., ACM CCS, IEEE S&P, NDSS, USENIX Security). The applicants should show the capability of developing a portfolio of funded research activities in a multidisciplinary environment and have a solid commitment to excellence in teaching.

Closing date for applications:

Contact:

Enquiries about the vacancy, shortlisting and interviews: Dr. Lucas Cordeiro (lucas.cordeiro@manchester.ac.uk) or Dr. Giles Reger (giles.reger@manchester.ac.uk).

General enquiries: hrservices@manchester.ac.uk

More information: https://www.jobs.manchester.ac.uk/displayjob.aspx?isPreview=Yes&jobid=19901

We construct two tightly secure signature schemes based on the computational Diffie-Hellman (CDH) and factoring assumptions in the random oracle model. Our schemes are proven secure in the multi-user setting, and their security loss is constant and does not depend on the number of users or signing queries. They are the first schemes that achieve this based on standard search assumptions, as all existing schemes we are aware of are either based on stronger decisional assumptions, or proven tightly secure in the less realistic single-user setting. Under a concrete estimation, in a truly large scale, the cost of our CDH-based scheme is about half of Schnorr and DSA (in terms of signature size and running time for signing).

Threshold and blind signature schemes have found numerous applications in cryptocurrencies, e-cash, e-voting and other privacy-preserving technologies. In this work, we make advances in bringing lattice-based constructions for these primitives closer to practice.

1. Threshold Signatures. For round optimal threshold signatures, we improve the only known construction by Boneh et al. [CRYPTO'18] as follows:

a. Efficiency. We reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of generated signatures and $\lambda$ is the security parameter. By using lattice hardness assumptions over polynomial rings, this allows to decrease signature bit-lengths from $\widetilde{O}(\lambda^3)$ to $\widetilde{O}(\lambda)$.

b. Towards Adaptive Security. The construction of Boneh et al. satisfies only selective security, where all the corrupted parties must be announced before any signing queries are made. We improve this in two ways: in the ROM, we obtain partial adaptivity where signing queries can be made before the corrupted parties are announced but the set of corrupted parties must be announced all at once. In the standard model, we obtain full adaptivity, where parties can be corrupted at any time but this construction is in a weaker pre-processing model where signers must be provided correlated randomness of length proportional to the number of signatures, in an offline pre-processing phase.

2. Blind Signatures. For blind signatures, we improve the state of art lattice-based construction by Hauck et al.[CRYPTO'20] as follows:

a. Round Complexity. We improve the round complexity from three to two -- this is optimal.

b. Efficiency. Again, we reduce the amount of noise flooding from $2^{\Omega(\lambda)}$ down to $\sqrt{Q_S}$, where $Q_S$ is the bound on the number of signatures and $\lambda$ is the security parameter.

c. Number of Signing Queries. Unlike the scheme from Hauck et al., our construction enjoys a proof that is not restricted to a polylogarithmic number of signatures. Using lattice hardness assumptions over rings, we obtain signatures of bit-lengths bounded as $\widetilde{O}(\lambda)$. In contrast, the signature bit-length in the scheme from Hauck et al. is $\Omega(\lambda^3 + Q_S \cdot \lambda)$.

Concretely, we can obtain blind/threshold signatures of size $\approx 3$ KB using a variant of Dilithium-G with $\approx 128$ bit-security, for adversaries limited to getting $256$ signatures. In contrast, parameters provided by Hauck et al. lead to blind signatures of $\approx 7.73$ MB, for adversaries limited to getting 7 signatures, while concrete parameters are not provided for the construction of threshold signatures by Boneh et al.

Proxy signature (PS) is a kind of digital signature, in which an entity called original signer can delegate his signing rights to another entity called proxy signer. Designated verifier signature (DVS) is a kind of digital signature where the authenticity of any signature can be verified by only one verifier who is designated by the signer when generating it. Designated verifier proxy signature (DVPS) combines the idea of DVS with the concept of proxy signature (PS) and is suitable for being applied in many scenarios from e-tender, e-voting, e-auction, e-health and e-commerce, etc. Many DVPS schemes have been proposed and Identity-based DVPS (IBDVPS) schemes have also been discussed. Certificateless public-key cryptography (CL-PKC) is acknowledged as an appealing paradigm because there exists neither the certificate management issue as in traditional PKI nor private key escrow problem as in Identity-based setting. A number of certificateless designated verifier signature (CLDVS) schemes and many certificateless proxy signature (CLPS) schemes have been proposed. However, to the best of our knowledge, the concept of Certificateless Designated Verifier Proxy Signature (CLDVPS) has not been appeared in the literature. In this paper, we formalize the definition and the security model of CLDVPS schemes. We then construct the first CLDVPS scheme and prove its security.

This note solves the open problem of finding a closed formula for the bias of a rotational differential-linear distinguisher proposed in IACR ePrint 2021/189 (EUROCRYPT 2021), completely generalizing the results on ordinary differential-linear distinguishers due to Blondeau, Leander, and Nyberg (JoC 2017) to the case of rotational differential-linear distinguishers.

Motivated by the goal of designing versatile and flexible secure computation protocols that at the same time require as little interaction as possible, we present new multiparty reusable Non-Interactive Secure Computation (mrNISC) protocols. This notion, recently introduced by Benhamouda and Lin (TCC 2020), is essentially two-round Multi-Party Computation (MPC) protocols where the first round of messages serves as a reusable commitment to the private inputs of participating parties. Using these commitments, any subset of parties can later compute any function of their choice on their respective inputs by just sending a single message to a stateless evaluator, conveying the result of the computation but nothing else. Importantly, the input commitments can be computed without knowing anything about other participating parties (neither their identities nor their number) and they are reusable across any number of desired computations.

We give a construction of mrNISC that achieves standard simulation security, as classical multi-round MPC protocols achieve. Our construction relies on the Learning With Errors (LWE) assumption with polynomial modulus, and on the existence of a pseudorandom function (PRF) in $\mathsf{NC}^1$. We achieve semi-malicious security in the plain model and malicious security by further relying on trusted setup (which is unavoidable for mrNISC). In comparison, the only previously known constructions of mrNISC were either using bilinear maps or using strong primitives such as program obfuscation.

We use our mrNISC to obtain new Multi-Key FHE (MKFHE) schemes with threshold decryption:

$\bullet$ In the CRS model, we obtain threshold MKFHE for $\mathsf{NC}^1$ based on LWE with only $\textit{polynomial}$ modulus and PRFs in $\mathsf{NC}^1$, whereas all previous constructions rely on LWE with super-polynomial modulus-to-noise ratio.

$\bullet$ In the plain model, we obtain threshold levelled MKFHE for $\mathsf{P}$ based on LWE with $\textit{polynomial}$ modulus, PRF in $\mathsf{NC}^1$, and NTRU, and another scheme for constant number of parties from LWE with sub-exponential modulus-to-noise ratio. The only known prior construction of threshold MKFHE (Ananth et al., TCC 2020) in the plain model restricts the set of parties who can compute together at the onset.

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.