International Association
for Cryptologic Research

We describe a technique to backdoor a prime factor of a composite odd integer $N$, so that an attacker knowing a possibly secret factor base $\mathcal{B}$, can efficiently retrieve it from $N$. Such method builds upon Complex Multiplication theory for elliptic curves, by generating primes $p$ associated to $\mathcal{B}$-smooth order elliptic curves over $\mathbb{F}_p$. When such primes $p$ divide an integer $N$, the latter can be efficiently factored using a generalization of Lenstra's Factorization Method over rings bigger than $\mathbb{Z}_N$, and with no knowledge other than $N$ and $\mathcal{B}$. We then formalize semiprimality certificates that, based on a result by Goldwasser and Kilian, allow to prove semiprimality of an integer with no need to reveal any of its factors. We show how our prime generation procedure can be used to efficiently produce semiprimality certificates, ultimately allowing us to sketch a multi-party distributed protocol to generate semiprimes with unknown factorisation, particularly relevant in the setting of distributed RSA modulus generation. We provide and discuss implementations of all proposed protocols and we address security of semiprimality certificates by showing that semiprimes generated within our methods result at least as secure as random semiprimes of same size.

Solving a system of $m$ multivariate quadratic equations in $n$ variables (the $\mathcal MQ$ problem) is one of the main challenges of algebraic cryptanalysis. The XL algorithm (XL for short) is a major approach for solving the $\mathcal MQ$ problem with linearization over a coefficient field. Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing some variables beforehand. In this paper, we present a variant of h-XL, which we call the polynomial XL (PXL). In PXL, the whole $n$ variables are divided into $k$ variables to be fixed and the remaining $n-k$ variables as ``main variables'', and we generate the Macaulay matrix with respect to the $n-k$ main variables over a polynomial ring of the $k$ variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessing $k$ variables, the amount of manipulations required for each guessed value can be reduced. Our complexity analysis indicates that PXL is efficient on the system with $n \approx m$. For example, on systems over ${\mathbb F}_{2^8}$ with $n=m=80$, the number of manipulations required by the hybrid approaches with XL and Wiedemann XL and PXL is estimated as $2^{252}$, $2^{234}$, and $2^{220}$, respectively.

The security of code based constructions is usually assessed by Information Set Decoding (ISD) algorithms. In the quantum setting, amplitude amplification yields an asymptotic square root gain over the classical analogue. However, it is still unclear whether a real quantum circuit could yield actual improvements or suffer an enormous overhead due to its implementation. This leads to different considerations of these quantum attacks in the security analysis of code based proposals. In this work we clarify this doubt by giving the first quantum circuit design of the fully-fledged ISD procedure, an implementation in the quantum simulation library Qibo as well as precise estimates of its complexities. We show that against common belief, Prange's ISD algorithm can be implemented rather efficiently on a quantum computer, namely with only a logarithmic overhead in circuit depth compared to a classical implementation.

As another major contribution, we leverage the idea of classical co-processors to design hybrid classical-quantum trade-offs, that allow to tailor the necessary qubits to any available amount, while still providing quantum speedups. Interestingly, when constraining the width of the circuit instead of its depth we are able to overcome previous optimality results on constraint quantum search.

SNOW-V is a stream cipher recently designed for 5G communication system. In this paper, we propose two efficient algorithms to evaluate the precise correlation of SNOW-V's two main nonlinear components with linear hull effects fully considered. Based on these algorithms, we could efficiently and extensively search much more linear masks than before. The ideas of these algorithms can be generalized to other similar nonlinear components in symmetric cipher. We apply our algorithms to full SNOW-V to search different types of linear approximations with high correlations. Our results depict more linear approximations with higher correlations than those proposed for full SNOW-V and SNOW-$\text{V}_{\boxplus_{32},\boxplus_8}$ recently. The best linear approximation we found has absolute correlation $2^{-47.567}$. There are at least 8, 135 and 1092 linear approximations with absolute correlation greater than $2^{-47.851}$, $2^{-49}$ and $2^{-50}$ respectively, which would derive a fast correlation attack with time/memory/data complexities $2^{240.86}$, $2^{240.37}$ and $2^{236.87}$. It is better than all the previous results of fast correlation attack against full SNOW-V. Moreover, we propose some properties for linear trails with 3 active S-boxes, which give a theoretical explanation that automatic search method lacks of. Our work provides a more comprehensive description for the linear approximation properties of full SNOW-V.

Blockchain is a decentralized ledger applying the peer-to-peer (P2P) network, cryptography and consensus mechanism over distributed network. Especially, the underlying cryptographic algorithms protect the blockchain integrity and data authenticity. However, it is well-known that every single algorithm is associated with a limited lifespan due to the increasing computational power of attackers. The compromise of algorithms directly leads to the compromise of blockchain validity. There are two existing long-term blockchain schemes dealing with this problem, but we observe that in these schemes: 1) the calculation of block hash values is not compatible with existing blockchains; 2) the hash transition procedure is only specified from the first algorithm to the second one, there are multiple possibilities to implement the scheme for a longer time, some of them may lead to the failure of the scheme; 3) the security of their schemes are not formally analyzed and proved. In this paper, we propose an enhanced long-term blockchain scheme as a solution to issue 1 and 2, and we formally prove that our scheme is secure without the limitation of cryptographic algorithms. Besides, we implement our scheme, the results show that our hash transition procedure can be completed between 20 minutes (best case) and several hours (worst case) for a current Bitcoin and Ethereum blockchain, which is very efficient.

Event date: 12 September to 16 September 2022

The Horst Görtz Institute for IT Security (HGI) in Bochum, Germany is one of the most renowned institutes in the field of IT Security in Europe. The HGI hosts 26 faculty members, maintains extensive networks and has produced numerous successful start-ups. HGI is home to the Cluster of Excellence "CASA: Cyber Security in the Age of Large-Scale Adversaries", funded with 30 million euros. This environment offers excellent working conditions in a highly exciting field. In addition, there is a very good working atmosphere in a young and diverse group of researchers.
An Associate Professorship with Tenure Track for Human Factors in Security and Privacy is to be filled at the Faculty of Computer Science of Ruhr-Universität Bochum. Applicants should have an excellent track record in research and teaching in at least one of the following areas:

• Human aspects affecting the design, implementation, and use of cryptography,
• Planning and conduct of empirical studies with end-users, security experts, and software developers, investigating topics such as usable authentication, mobile security, secure messaging,
• Application of qualitative and quantitative methods in IT security research, and development of new methods.

We are looking for a scientist with an internationally visible research profile, who complements existing focus areas. We expect a willingness to cooperate with the Horst Görtz Institute for IT Security and an active role in current and planned projects, especially in the Cluster of Excellence CASA. The Max Planck Institute for Security and Privacy offers additional possibilities for collaboration. The working language is English. Fluent German is not a prerequisite for a successful engagement at HGI. The official job add can be found here: https://www.stellenwerk-bochum.de/jobboerse/w2-tenure-track-professorship-human-factors-security-and-privacy-bochum-211209-507341. Applications with the usual documents are requested by January 10, 2022 to: Dean of the Faculty of Computer Science, Alexander May, e-mail: career@casa.rub.de . Further information can be found here: https://informatik.rub.de/en/ https://casa.rub.de/en/

Closing date for applications:

Contact: Prof. Alexander May, Dean of the Faculty of Computer Science

We show that Bitcoin and other egalitarian crypto-currencies are unstable as store-of-value as they fail to track inflation of local currencies closely, and the price dynamic is purely driven by speculation. Based on rational expectations equilibrium, we argue that if the coins awarded during mining are increased in proportion to increase in difficulty of the underlying cryptographic puzzle, then the price of the coin is likely to track inflation of local currencies closely over medium to long term. Further, a hyper-geometric tapering, instead of a geometric tapering, of the mining award over time is recommended for bootstrapping interest in the crypto-currency.

This article contains a new hash function (indifferentiable from a random oracle) to any ordinary elliptic curve $E_a\!: y^2 = x^3 + ax$ (of invariant $1728$) over a finite field $\mathbb{F}_{\!q}$. Its advantage consists in the necessity to compute (in constant time) only one exponentiation in $\mathbb{F}_{\!q}$, at least for the most practical case $q \equiv 5 \ (\mathrm{mod} \ 8)$. In comparison, for such a $q$ the previous fastest constant-time indifferentiable hash functions to $E_a$ require to compute two exponentiations in $\mathbb{F}_{\!q}$. By the way, the famous Shallue--van de Woestijne hash function (acting as a random oracle) performs four exponentiations in $\mathbb{F}_{\!q}$ even when it is implemented as efficiently as possible. Since it is highly unlikely that there is a hash function to an elliptic curve without exponentiations at all (even if it is supersingular), the result of the given article seems to be unimprovable.

Data, when coupled with state-of-the-art machine learning models, can enable remarkable applications. But, there exists an underlying tension: users wish to keep their data private, and model providers wish to protect their intellectual property. Homomorphic encryption (HE) and multi-party computation (MPC) techniques have been proposed as solutions to this problem; however, both techniques require model providers to fully trust the server performing the machine learning computation. This limits the scale of inference applications since it prevents model providers from leveraging shared public cloud infrastructures.

In this work, we present CHEX-MIX, a solution to the problem of privacy-preserving machine learning between two mutually distrustful parties in an untrusted cloud setting. CHEX-MIX relies on a combination of HE and trusted execution environments (TEEs) and leverages the benefits of each to counter the drawbacks of the other. In particular, we use HE to provide clients with confidentiality guarantees and TEEs to provide model providers with confidentiality guarantees and protect the integrity of computation from malicious cloud adversaries. Unlike prior solutions to this problem, such as multi-key HE, single-key HE, MPC, or TEE-only techniques, our solution assumes that both clients and the cloud can be malicious, makes no collusion assumptions, and frees model providers from needing to maintain private online infrastructures. In this paper, we analyze our solution from a security perspective and detail the advantages that our solution provides over prior works, including its ability to allow model providers to maintain privacy of their software IP. We demonstrate the feasibility of our solution by deploying CHEX-MIX in an Azure confidential computing machine. Our results show that CHEX-MIX can execute at high efficiency, with low communication cost, while providing security guarantees unaddressed by prior work.

Predicate encryption (PE) is a cutting-edge research topic in cryptography, and an essential component of a research route: identity-based encryption (IBE)→attribute-based encryption (ABE)→predicate encryption (PE)→functional encryption (FE). GVW15 predicate encryption scheme is a major predicate encryption scheme. The bottom structure is BGG+14 attribute-based encryption scheme, which is combined with a fully homomorphic encryption (FHE) scheme. A crucial operation of the scheme is modulus reduction, by which the modulus $Q$ of the fully homomorphic encryption ciphertext (also referred to as the inner modulus) is scaled down to the modulus $q$ of the attribute ciphertext (also referred to as the outer modulus). ‘Therefore’, the noise in the fully homomorphic encryption ciphertext (also referred to as the inner noise) is reduced to polynomial size, allowing for the follow-up exhaustion of noise size and hence correct decryption.

We argue in this paper that there is no evidence to support the $P/poly$ validity of GVW15 predicate encryption scheme, that is, when addressing $P/poly$ functions, there is no evidence to show GVW15 scheme can be implemented. In specific, when addressing $P/poly$ functions, there is no indication that the modulus reduction in GVW15 predicate encryption scheme can scale the noise in the fully homomorphic encryption ciphertext (the inner noise) down to polynomial size. Our argument is separated into two parts.

First, under a compact inner modulus $Q$, an intuition is that modulus reduction should reduce the inner noise to about the same size as the outer noise (i.e. the noise in the attribute ciphertext), which is super-polynomial in size. Breaking this intuition requires a special proof which GVW15 predicate encryption (PE) scheme does not provide.

Second, under an enlarged inner modulus $Q$, the outer modulus is enlarged correspondingly. As a result, the static target of modulus reduction is lost. Even so, the size of inner noise can still be reduced to polynomial size by using proper modulus reduction, as long as it can be proved that the ratio of increments of outer modulus and inner modulus is smaller than the ratio of original outer modulus $q$ and original inner modulus $Q$. However, GVW15 PE scheme failed to provide such proof. Moreover, it appears hopeless to get such proof, based on our observations.

The Even-Mansour cipher is a simple method for constructing a (keyed) pseudorandom permutation $E$ from a public random permutation $P:\{0,1\}^n \rightarrow \{0,1\}^n$. It is a core ingredient in a wide array of symmetric-key constructions, including several lightweight cryptosystems presently under consideration for standardization by NIST. It is secure against classical attacks, with optimal attacks requiring $q_E$ queries to $E$ and $q_P$ queries to $P$ such that $q_E \cdot q_P \approx 2^n$. If the attacker is given *quantum* access to both $E$ and $P$, however, the cipher is completely insecure, with attacks using $q_E, q_P = O(n)$ queries known.

In any plausible real-world setting, however, a quantum attacker would have only *classical* access to the keyed permutation $E$ implemented by honest parties, while retaining quantum access to $P$. Attacks in this setting with $q_E \cdot q_P^2 \approx 2^n$ are known, showing that security degrades as compared to the purely classical case, but leaving open the question as to whether the Even-Mansour cipher can still be proven secure in this natural ``post-quantum'' setting.

We resolve this question, showing that any attack in that setting requires $q_E \cdot q^2_P + q_P \cdot q_E^2 \approx 2^n$. Our results apply to both the two-key and single-key variants of Even-Mansour. Along the way, we establish several generalizations of results from prior work on quantum-query lower bounds that may be of independent interest.

This paper focuses on isogeny representations, defined as witnesses of membership to the language of isogenous supersingular curves (the set of triples $D,E_1,E_2$ with a cyclic isogeny of degree $D$ between $E_1$ and $E_2$). This language and its proofs of membership are known to have several fundamental cryptographic applications such as the construction of digital signatures and validation of encryption keys. The first part of our article is dedicated to formalizing known results about isogenies to the framework of languages and proofs, culminating in a proof that the language of isogenous supersingular curves is in \textsf{NP} with the isogeny representation derived naturally from the Deuring Correspondence.

Our main contribution is the design of the suborder representation, a new isogeny representation targetted at the case of (big) prime degree. The core of our new method is the revelation of endomorphisms of smooth norm inside a well-chosen suborder of the codomain's endomorphism ring. These new membership witnesses appear to be opening interesting prospects for isogeny-based cryptography under the hardness of a new computational problem: the SubOrder to Ideal Problem (SOIP). As an application, we introduce pSIDH, a new NIKE based on our new suborder representation.

In the process, we also develop several heuristic algorithmic tools to solve norm equations inside a new family of quaternion orders. These new algorithms may be of independent interest.

Traditional zero-knowledge protocols have been studied and optimized for the setting where a single prover holds the complete witness and tries to convince a verifier about a predicate on the witness, without revealing any additional information to the verifier. In this work, we study the notion of distributed-prover zero knowledge (DPZK) for arbitrary predicates where the witness is shared among multiple mutually distrusting provers and they want to convince a verifier that their shares together satisfy the predicate. We make the following contributions to the notion of distributed proof generation: (i) we propose a new MPC-style security definition to capture the adversarial settings possible for different collusion models between the provers and the verifier, (ii) we discuss new efficiency parameters for distributed proof generation such as the number of rounds of interaction and the amount of communication among the provers, and (iii) we propose a compiler that realizes distributed proof generation from the zero-knowledge protocols in the Interactive Oracle Proofs (IOP) paradigm. Our compiler can be used to obtain DPZK from arbitrary IOP protocols, but the concrete efficiency overheads are substantial in general. To this end, we contribute (iv) a new zero-knowledge IOP $\textsf{Graphene}$ which can be compiled into an efficient DPZK protocol. The $(\mathsf{D} + 1)$-DPZK protocol $\text{D-Graphene}$, with $\mathsf{D}$ provers and one verifier, admits $O(N^{1/c})$ proof size with a communication complexity of $O(\mathsf{D}^2\cdot (N^{1-2/c} + N_s))$, where $N$ is the number of gates in the arithmetic circuit representing the predicate and $N_s$ is the number of wires that depends on inputs from two or more parties. Significantly, only the distributed proof generation in $\text{D-Graphene}$ requires interaction among the provers. $\text{D-Graphene}$ compares favourably with the DPZK protocols obtained from the state-of-art zero-knowledge protocols, even those not modelled as IOPs.

Tamarin Prover is a formal security analysis tool that is used to analyse security properties of various authentication and key exchange protocols. It provides built-ins like Diffie-Hellman, Hashing, XOR, Symmetric and Asymmetric encryption as well as Bilinear pairings. The shortfall in Tamarin Prover is that it does not support elliptic curve point addition operation. In this paper, we present a simple IBE (Identity-Based Encryption) based key exchange protocol and tamarin model. For modelling, we define a function to replace the point addition operation by the concept of pre-computation. We demonstrate that the security model functions for theoretical expectation and is able to resist Man-In-The-Middle (MITM) Attack. This model can be used to analyse the formal security of authentication and key exchange protocols designed based-on the IBE technique.

We give a cryptographic analysis of the Bluetooth Secure Connections Protocol Suite. Bluetooth supports several subprotocols, such as Numeric Comparison, Passkey Entry, and Just Works, in order to match the devices' different input/output capabilities. Previous analyses (e.g., Lindell, CT-RSA'09, or Troncoso and Hale, NDSS'21) often considered (and confirmed) the security of single subprotocols only. Recent practically verified attacks, however, such as the Method Confusion Attack (von Tschirschnitz et al., S&P'21) against Bluetooth's authentication and key secrecy property, often exploit the bad interplay of different subprotocols. Even worse, some of these attacks demonstrate that one cannot prove the Bluetooth protocol suite to be a secure authenticated key exchange protocol. We therefore aim at the best we can hope for and show that the protocol still matches the common key secrecy requirements of a key exchange protocol if one assumes a trust-on-first-use (TOFU) relationship. This means that the adversary needs to mount an active attack during the initial connection, otherwise the subsequent reconnections remain secure. Investigating the cryptographic strength of the Bluetooth protocol, we also look into the privacy mechanism of address randomization in Bluetooth (which is only available in the Low Energy version). We show that the cryptography indeed provides a decent level of address privacy, although this does not rule out identification of devices via other means, such as physical characteristics.

Cryptographic protocols are distributed algorithms that allow entities to perform security-related functions over a (potentially untrusted) network. Such protocols are ubiquitous, and their security is essential to almost any IT system. It is quite challenging to create secure protocols as even small non-obvious mistakes can have fatal consequences. For example, the (very simple) Needham-Schroeder key exchange protocol contains a severe security flaw that went unnoticed for 17 years. For modern security protocols, such as TLS, it is even harder to ensure security. These protocols tend to be much more complex and are typically embedded into environments that introduce their own quirks and subtleties. Formal methods provide a systematic way to perform comprehensive analyses of such protocols concisely and rigorously. They allow us to specify security goals precisely and enable us to prove that a protocol indeed guarantees such properties. Using this approach, we can find attacks (if a proof fails), develop fixes, and formally verify whether our fixes are sufficient. Moreover, we can even exclude unknown classes of attacks on the systems we analyse. Although this field has been quite active in research for several decades now, there are still many open research questions to answer: Existing tools and approaches often struggle with analyses of complex protocols. Proofs are often quite laborious and are susceptible to human errors. Furthermore, modern environments such as Web, Mobile, and IoT also introduce their own complexity and pitfalls and blend into each other, creating new subtleties which can be an additional source of security issues. Hence, we need to develop new methods and techniques to tackle this complexity, mechanise and automate such security analyses to more extent, and take the characteristics of modern environments into account. We are looking for applications from highly talented candidates with a background in computer science, information security, mathematics, or a related field interested in logic, proofs, and formal analysis techniques. We value strong analytical skills and solid programming knowledge.

Closing date for applications:

Contact: Prospective applicants are welcome to discuss with Guidi Schmitz

More information: https://www.royalholloway.ac.uk/cdt

Privacy-preserving Outsourced Computation: The Centre for Doctoral Training in Cyber Security for the Everyday seeks to recruit a PhD student to work on practical privacy-preserving outsourced computation techniques, such as homomorphic encryption (HE). This project will be carried out jointly with KDDI Research, Japan. Fully homomorphic encryption enables the evaluation of arbitrary functions on encrypted data, without requiring access to the secret key. This cryptographic primitive can enable a variety of practical applications in secure outsourced computation, including privacy-preserving data analysis. Cybersecurity systems (e.g., IDS, IPS) collect large amounts of data to detect security events. Analysis of this data may however pose a significant threat to the privacy of users. A privacy-preserving data analysis attempts to alleviate this threat by carrying out the analysis over encrypted data. Removing privacy risks will allow more data sharing, and more enhanced data analysis. The goal of the project is the enhancement of HE for practical use. This could include (for example) the design and security of practical privacy-preserving applications, or proposing improvements and optimisations to existing HE schemes. The Information Security Group (ISG) at Royal Holloway has a strong track record in cryptographic research, including algorithm design and analysis, post-quantum cryptography, homomorphic encryption and applications of secure computation. KDDI Research is the research and innovation arm of KDDI Corporation, one of the largest Japanese telecommunications operators. The ISG and KDDI have a long-term collaboration in the area of cryptography, and the student recruited for this project will work closely with researchers from the two groups. Applicants are expected to have a background in mathematics, computer science, or a related discipline. Prospective applicants are welcome to contact Rachel.Player@rhul.ac.uk to discuss the project.

Closing date for applications:

Contact: Dr Rachel Player

More information: https://www.royalholloway.ac.uk/cdt

The threat of large-scale, general-purpose quantum computers to existing public-key cryptographic solutions has lead to global efforts to standardise post-quantum cryptography as a replacement. In particular, the NIST Post-Quantum Cryptography is now in its third and final round. One of the front-runners for problems to base post-quantum cryptography on are hard problems on lattices. Five out of seven finalists of the NIST processes are based on lattices. Thus, it is a natural question to ask how long it actually takes to solve these problems on lattices. The better we understand this problem the more confidence we can have in the cryptographic solutions soon to be deployed globally. The security of lattice-based cryptography is a pressing research question for a second reason. Many innovations in the field of cryptography in recent years rely on lattices as their foundation. For example, all the ways in which we know how to compute arbitrary functions on encrypted data – homomorphic encryption – are based on lattices. The Information Security Group at Royal Holloway has a strong track record in this area and we are seeking students to join our efforts to address this pressing research question. The directions this PhD can go into are manifold: (asymptotic) algorithm design and analysis, implementations, experimental validation, quantum computing, side-channel analysis, active attacks against protocols using lattice-based primitives, studying special cases relevant in practice. We seek applicants with a background in mathematics and/or computer science or related disciplines. Prospective applicants are welcome to discuss with martin.albrecht@rhul.ac.uk

Closing date for applications:

Contact: Prospective applicants are welcome to discuss with Professor Martin Albrecht

More information: https://www.royalholloway.ac.uk/cdt

The Department of Computer Science at Technische Universität Darmstadt invites applications for two positions as Doctoral Researchers (Research Assistants/PhD Students) in Cryptography and Complexity Theory in the group of Professor Marc Fischlin. The positions are funded through BMBF projects DemoQuanDT and QSYM about Quantum Security. More information about our research is available under: www.cryptoplexity.de The starting date is 01.01.2022. The initial funding for each of the positions is for three years, but the contracts may be extended. Your Profile: Completed university degree (Master’s degree or equivalent) in Computer Science, Mathematics, or a similar discipline Extensive knowledge in the areas of our projects, in particular cryptography and IT security Fluent English language skills Experience in IT system administration is welcome Candidates are expected to contribute to the research, teaching, and administrative tasks of the group. Opportunity for further qualification (doctoral dissertation) is given. The fulfillment of the duties likewise enables the scientific qualifications of the candidate.

Closing date for applications:

Contact: Prof. Dr. Marc Fischlin, E-Mail: jobs@cx.tu-darmstadt.de

More information: https://www.tu-darmstadt.de/universitaet/karriere_an_der_tu/stellenangebote/aktuelle_stellenangebote/stellenausschreibungen_detailansichten_1_442368.en.jsp