International Association
for Cryptologic Research

As an emerging joint learning model, federated deep learning is a promising way to combine model parameters of different users for training and inference without collecting users’ original data. However, a practical and efficient solution has not been established in previous work due to the absence of effcient matrix computation and cryptography schemes in the privacy-preserving federated learning model, especially in partially homomorphic cryptosystems. In this paper, we propose a practical and efficient privacy-preserving federated learning framework (PEPFL). First, we present a lifted distributed ElGamal cryptosystem that can be applied to federated learning and solve the multi-key problem in federated learning. Secondly, we develop a practical partially single instruction multiple data (PSIMD) parallelism scheme that can encode a plaintext matrix into single plaintext to conduct the encryption, improving effectiveness and reducing communication cost in partially homomorphic cryptosystems. In addition, a novel privacy-preserving federated learning framework is designed by using momentum gradient descent (MGD) with a convolutional neural network (CNN) and the designed cryptosystem. Finally, we evaluate the security and performance of PEPFL. The experiment results demonstrate that the scheme is practicable, effective, and secure with low communication and computational costs.

Federated learning (FL), as an emerging distributed learning framework, can combine training from different users without collecting users’ original data, protecting privacy to a certain extent. However, there are no efficient privacy protection technologies applicable to IoT. One challenge in IoT is to reduce the client-server communication cost and solve communication failure questions. Another challenge is how to utilize highquality data to guarantee training performance. To solve these challenges, we present a privacy-preserving and optimal fraction FL framework based on elliptic curve cryptosystem (ECC) and k-nearest neighbor (KNN) method in an ad-hoc network. Firstly, we propose an improved multiple key EC-ElGamal cryptosystem (MEEC), which can reduce computation overhead and improve the encryption efficiency owing to the lightweight EC-ElGamal cryptosystem with shorter keys and ciphertext. Secondly, we propose the first ad-hoc FL framework with an ad-hoc quit and join algorithm, solving the communication failure questions, guaranteeing the optimal power computation. Thirdly, we raise a Euclidean fraction scheme based on an improved KNN method, which can quickly obtain the optimal training data from the heterogeneity data, avoiding low-quality data or malicious data to join the training. Finally, security analysis and performance evaluation have been performed. Compared with the existing solutions, our scheme is secure, practicable, efficient with low communication and computational costs in IoT.

Trading goods lies at the backbone of the modern economy and the recent advent of cryptocurrencies has opened the door for trading decentralized (digital) assets: A large fraction of the value of cryptocurrencies comes from the inter-currency exchange and trading, which has been arguably the most successful application of decentralized money. The security issues observed with centralized, custodial cryptocurrency exchanges have motivated the design of atomic swaps, a protocol for coin exchanges between any two users. Yet, somewhat surprisingly, no atomic swap protocol exists that simultaneously satisfies the following simple but desired properties: (i) non-custodial, departing from a third party trusted holding the coins from users during the exchange; (ii) universal, that is, compatible with all (current and future) cryptocurrencies; (iii) multi-asset, supporting the exchange of multiple coins in a single atomic swap.

From a theoretical standpoint, in this work we show a generic protocol to securely swap $n$ coins from any (possible multiple) currencies for $\tilde{n}$ coins of any other currencies, for any $n$ and $\tilde{n}$. We do not require any custom scripting language supported by the corresponding blockchains, besides the bare minimum ability to verify signatures on transactions. For the special case when the blockchains use ECDSA or Schnorr signatures, we design a practically efficient protocol based on adaptor signatures and time-lock puzzles. As a byproduct of our approach, atomic swaps transactions no longer include custom scripts and are identical to standard one-to-one transactions. We also show that our protocol naturally generalizes to any cycle of users, i.e., atomic swaps with more than two participants. To demonstrate the practicality of our approach, we have evaluated a prototypical implementation of our protocol for Schnorr/ECDSA signatures and observed that an atomic swap requires below one second on commodity machines. Even on blockchains with expressive smart contract support (e.g., Ethereum), our approach reduces the on-chain cost both in terms of transaction size and gas cost.

In this paper we study and relate several invariants connected to the solving degree of a polynomial system. This provides a rigorous framework for estimating the complexity of solving a system of polynomial equations via Groebner bases methods. Our main results include a connection between the solving degree and the last fall degree and one between the degree of regularity and the Castelnuovo--Mumford regularity.

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.