International Association
for Cryptologic Research

Private set union (PSU) protocol enables two parties, each holding a set, to compute the union of their sets without revealing anything else to either party. So far, there are two known approaches for constructing PSU protocols. The first mainly depends on additively homomorphic encryption (AHE), which is generally inefficient since it needs to perform a non-constant number of homomorphic computations on each item. The second is mainly based on oblivious transfer and symmetric-key operations, which is recently proposed by Kolesnikov et al. (KRTW, ASIACRYPT 2019). It features good practical performance, which is several orders of magnitude faster than the first one. However, neither of these two approaches is optimal in the sense that their computation and communication complexity are not both $O(n)$, where $n$ is the size of the set. Therefore, the problem of constructing the optimal PSU protocol remains open. In this work, we resolve this open problem by proposing a generic framework of PSU from oblivious transfer and a newly introduced protocol called multi-query reverse private membership test (mq-RPMT). We present two generic constructions of mq-RPMT. The first is based on symmetric-key encryption and general 2PC techniques. The second is based on re-randomizable public-key encryption. Both constructions lead to PSU with linear computation and communication complexity.

By instantiating the generic constructions of mq-RPMT, we obtain two concrete PSU protocols based on SKE and PKE techniques respectively. We implement our two PSU protocols and compare them with the state-of-the-art PSU. Experiments show that our PKE-based protocol has the lowest communication of all schemes, which is $4.1-14.8\times$ lower depending on set size. The running time of our PSU scheme is $1.2-12\times$ faster than that of state-of-the-art depending on network environments.

In this article, we prove a generic lower bound on the number of $\mathfrak{O}$-\textit{orientable} supersingular curves over $\FF_{p^2}$, i.e curves that admit an embedding of the quadratic order $\mathfrak{O}$ inside their endomorphism ring. Prior to this work, the only known effective lower-bound is restricted to small discriminants. Our main result targets the case of fundamental discriminants and we derive a generic bound using the expansion properties of the supersingular isogeny graphs. Our work is motivated by isogeny-based cryptography and the increasing number of protocols based on $\mathfrak{O}$-oriented curves. In particular, our lower bound provides a complexity estimate for the brute-force attack against the new $\mathfrak{O}$-uber isogeny problem introduced by De Feo, Delpech de Saint Guilhem, Fouotsa, Kutas, Leroux, Petit, Silva and Wesolowski in their recent article on the SETA encryption scheme.

While the convergence of Artificial Intelligence (AI) techniques with improved information technology systems ensured enormous benefits to the Internet of Vehicles (IoVs) systems, it also introduced an increased amount of security and privacy threats. To ensure the security of IoVs data, privacy preservation methodologies have gained significant attention in the literature. However, these strategies also need specific adjustments and modifications to cope with the advances in IoVs design. In the interim, Federated Learning (FL) has been proven as an emerging idea to protect IoVs data privacy and security. On the other hand, Blockchain technology is showing prominent possibilities with secured, dispersed, and auditable data recording and sharing schemes. In this paper, we present a comprehensive survey on the application and implementation of Blockchain-Enabled Federated Learning frameworks for IoVs. Besides, probable issues, challenges, solutions, and future research directions for BC-Enabled FL frameworks for IoVs are also presented. This survey can further be used as the basis for developing modern BC-Enabled FL solutions to resolve different data privacy issues and scenarios of IoVs.

Seminal works by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [Journal of Cryptology 2020] and Alwen, Coretti and Dodis [EUROCRYPT 2019] provided the first formal frameworks for studying the widely-used Signal Double Ratchet (DR for short) algorithm.

In this work, we develop a new Universally Composable (UC) definition F_DR that we show is provably achieved by the DR protocol. Our definition captures not only the security and correctness guarantees of the DR already identified in the prior state-of-the-art analyses of Cohn-Gordon et al. and Alwen et al., but also more guarantees that are absent from one or both of these works. In particular, we construct six different modified versions of the DR protocol, all of which are insecure according to our definition F_DR, but remain secure according to one (or both) of their definitions. For example, our definition is the first to capture CCA-style attacks possible immediately after a compromise — attacks that, as we show, the DR protocol provably resists, but were not captured by prior definitions.

We additionally show that multiple compromises of a party in a short time interval, which the DR should be able to withstand, as we understand from its whitepaper, nonetheless introduce a new non-trivial (albeit minor) weakness of the DR. Since the definitions in the literature (including our F_DR above) do not capture security against this more nuanced scenario, we define a new stronger definition F_TR that does.

Finally, we provide a minimalistic modification to the DR (that we call the Triple Ratchet, or TR for short) and show that the resulting protocol securely realizes the stronger functionality F_TR. Remarkably, the modification incurs no additional communication cost and virtually no additional computational cost. We also show that these techniques can be used to improve communication costs in other scenarios, e.g. practical Updatable Public Key Encryption schemes and the re-randomized TreeKEM protocol of Alwen et al. [CRYPTO 2020] for Secure Group Messaging.

Approximate Agreement (AA) allows a set of $n$ parties that start with real-valued inputs to obtain values that are at most within a parameter $\epsilon > 0$ from each other and within the range of their inputs. Existing AA protocols, both for the synchronous network model (where any message is delivered within a known delay $\Delta$ time) and the asynchronous network model, are secure when up to $t < n/3$ of the parties are corrupted and require no initial setup (such as a public-key infrastructure (PKI) for signatures).

We consider AA protocols where a PKI is available, and show the first AA protocol that achieves simultaneously security against $t_s$ corruptions when the network is synchronous and $t_a$ corruptions when the network is asynchronous, for any $0\le t_a < n/3 \le t_s < n/2$ such that $t_a + 2 \cdot t_s < n$. We further show that our protocol is optimal by proving that achieving AA for $t_a + 2 \cdot t_s \ge n$ is impossible (even with setup). Remarkably, this is also the first AA protocol that tolerates more than $n/3$ corruptions in the synchronous network model.

We obtain publicly verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computation from standard group-based assumptions, without relying on pairings. In particular, assuming the sub-exponential hardness of both the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where $n$ denotes the length of the instance: 1. A SNARG for any language that can be decided in non-deterministic time $T$ and space $S$ with communication complexity and verifier runtime $(n + S) \cdot T^{o(1)}$. 2. A SNARG for any language that can be decided in deterministic time $T$ with communication complexity and verifier runtime $n \cdot T^{o(1)}$.

An important cryptographic operation on elliptic curves is hashing to a point on the curve. When the curve is not of prime order, the point is multiplied by the cofactor so that the result has a prime order. This is important to avoid small subgroup attacks for example. A second important operation, in the composite-order case, is testing whether a point belongs to the subgroup of prime order. A pairing is a bilinear map e : G1 ×G2 → GT where G1 and G2 are distinct subgroups of primeorderrofanellipticcurve,andGT isamultiplicativesubgroupof the same prime order r of a finite field extension. Pairing-friendly curves are rarely of prime order. We investigate cofactor clearing and subgroup membership testing on these composite-order curves. First, we general- ize a result on faster cofactor clearing for BLS curves to other pairing- friendly families of a polynomial form from the taxonomy of Freeman, Scott and Teske. Second, we investigate subgroup membership testing for G1 and G2. We fix a proof argument for the G2 case that appeared in a preprint by Scott in late 2021 and has recently been implemented in different cryptographic libraries. We then generalize the result to both G1 and G2 and apply it to different pairing-friendly families of curves. This gives a simple and shared framework to prove membership tests for both cryptographic subgroups.

In this work, we consider the formal verification of the public-key encryption scheme of Saber, one of the selected few post-quantum cipher suites currently considered for potential standardization. We formally verify this public-key encryption scheme's IND-CPA security and $\delta$-correctness properties, i.e., the properties required to transform the public-key encryption scheme into an IND-CCA2 secure and $\delta$-correct key encapsulation mechanism, in EasyCrypt. To this end, we initially devise hand-written proofs for these properties that are significantly more detailed and meticulous than the presently existing proofs. Subsequently, these hand-written proofs serve as a guideline for the formal verification. The results of this endeavor comprise hand-written and computer-verified proofs which demonstrate that Saber's public-key encryption scheme indeed satisfies the desired security and correctness properties.

Uniswap, like other DEXs, has gained much attention this year because it is a non-custodial and publicly verifiable exchange that allows users to trade digital assets without trusted third parties. However, its simplicity and lack of regulation also makes it easy to execute initial coin offering scams by listing non-valuable tokens. This method of performing scams is known as rug pull, a phenomenon that already existed in traditional finance but has become more relevant in DeFi. Various projects such as [34,37] have contributed to detecting rug pulls in EVM compatible chains. However, the first longitudinal and academic step to detecting and characterizing scam tokens on Uniswap was made in [44]. The authors collected all the transactions related to the Uniswap V2 exchange and proposed a machine learning algorithm to label tokens as scams. However, the algorithm is only valuable for detecting scams accurately after they have been executed. This paper increases their data set by 20K tokens and proposes a new methodology to label tokens as scams. After manually analyzing the data, we devised a theoretical classification of different malicious maneuvers in Uniswap protocol. We propose various machine-learning-based algorithms with new relevant features related to the token propagation and smart contract heuristics to detect potential rug pulls before they occur. In general, the models proposed achieved similar results. The best model obtained an accuracy of 0.9936, recall of 0.9540, and precision of 0.9838 in distinguishing non-malicious tokens from scams prior to the malicious maneuver.

The group has a number of post-doc and tenure-track professor openings in the prestigious Advanced Research Institute of Multidisciplinary Sciences at Beijing Institute of Technology, China. We welcome candidates in security, cryptography, blockchains, and systems. The group regularly published papers in renowned venues such as CCS, S&P, DSN, OPODIS, ESORICS, FC, FSE, RSA, and SRDS and has designed and implemented many blockchain systems widely used in industry and academia.

Postdoc: Competitive salary. Housing/renting covered. The postdoc position is for two years and has flexible starting time. After two years, the candidates may be offered a tenure-track position at Beijing Institute of Technology.

Tenure-track professors: housing covered; salary is really competitive, can advise PhD students and postdocs; startup package included; etc.

Closing date for applications:

Contact: Please apply with a CV. Person in contact: Prof. Haibin Zhang: haibin at bit dot edu dot cn

More information: https://bchainzhang.github.io/hbzhang/

This is a time of significant opportunity for Computer Science at Birmingham, with a growing number of outstanding students, world- leading research, the establishment of new institutes, and a growing transnational education and industrial engagement. We are investing in the growth of the senior leadership of the school in a number of key research and education area, including but not limited to all areas of Cyber Security.

The Centre for Cyber Security and Privacy has 14 permanent academics as well as 21 postdocs/PhD students. Our expertise is established on a historic strength in the analysis of security systems using formal methods, and we broadened our scope to cover all aspects of cyber security. We have built an international reputation for our expertise areas such as applied cryptography, automotive security and secure infrastructure, hardware security and the security of IoT devices (https://www.bham.ac.uk/research/centre-for-cyber-security-and-privacy/index.aspx).

We have 3 distinct academic pathways, Research & Education, Education, and Enterprise, Engagement and Impact, and have opportunities in all of these pathways.

Closing date for applications:

Contact:

For informal information about Cyber Security at Birmingham, please contact Prof David Oswald, d.f.oswald@bham.ac.uk

For a confidential and informal discussion about details of the post, please contact Dr Mark Lee, m.g.lee@bham.ac.uk

More information: https://bham.taleo.net/careersection/external/jobdetail.ftl?job=220000G4&tz=GMT%2B00%3A00&tzname=Europe%2FLondon

We explore algorithmic aspects of a free and transitive commutative group action coming from the class field theory of imaginary hyperelliptic function fields. Namely, the Jacobian of an imaginary hyperelliptic curve defined over $\mathbb{F}_q$ acts on a subset of isomorphism classes of Drinfeld modules. We describe an algorithm to compute the group action efficiently. This is a function field analog of the Couveignes-Rostovtsev-Stolbunov group action. Our proof-of-concept C++/NTL implementation only requires a fraction of a second on a standard computer. Also, we state a conjecture --- supported by experiments --- which implies that the current fastest algorithm to solve its inverse problem runs in exponential time. This action is therefore a promising candidate for the construction of \textit{Hard Homogeneous Spaces}, which are the building blocks of several post-quantum cryptographic protocols. This demonstrates the relevance of using imaginary hyperelliptic curves and Drinfeld modules as an alternative to the standard setting of imaginary quadratic number fields and elliptic curves for isogeny-based cryptographic applications. Moreover, our function field setting enables the use of Kedlaya's algorithm and its variants for computing the order of the group in polynomial time when $q$ is fixed. No such polynomial-time algorithm for imaginary quadratic number fields is known. For $q=2$ and parameters similar to CSIDH-512, we compute this order more than 8500 times faster than the record computation for CSIDH-512 by Beullens, Kleinjung and Vercauteren.

Pairing-based cryptographic protocols are typically vulnerable to small-subgroup attacks in the absence of protective measures. To thwart them, one of effective measures is to execute subgroup membership testings for the three $r$-order subgroups $\G_1$, $\G_2$ and $\G_T$, which are generally considered expensive. Inspired by the method given by Scott, we revisit this issue and generalize the testing method in this paper. Our method can be applied to a large class of curves, including curves admitting a twist and without a twist. The resulting implementation shows that for many popular pairing-friendly curves, the proposed technique significantly improves the performance of membership testings for the above three subgroups as compared with the fastest previously known one. More precisely, for $\G_2$ testing on curves admitting a twist, the new technique is about 1.9, 5.1, and 3.6 times faster than the previous one on \textit{BN-446}, \textit{KSS16-P310} and \textit{KSS18-P348}, respectively. For $\G_2$ testing on curves without a twist, there exists no efficient testing method for $\G_2$ in the literature until now. In this situation, the proposed method is about $17.3$ and $20$ times faster than the naive one on \textit{BW13-P310} and \textit{BW9-P286}, respectively.

Homomorphic Encryption (HE) is a cryptosytem that allows us to perform an arbitrary computation on encrypted data. The standard HE, however, has a disadvantage in that the authority is concentrated in the secret key owner as the computation can be performed only on ciphertexts under the same key. In order to overcome this problem, research is underway on Multi-Key Homomorphic Encryption (MKHE), which enables operations between encrypted data possibly under different keys. Despite its strength to cover privacy of multiple parties, the existing MKHE schemes suffer from poor performance that the multiplication cost grows at least quadratically with the number of parties involved.

In this paper, we propose a new notion of the gadget decomposition, which enables arithmetic operations to be performed on the decomposed vectors with guarantee of functionality and noise bound. We redesign the multi-key multiplication algorithm of Chen et al. (ACM CCS 2019) using the homomorphic property of gadget decomposition and thereby reduce the complexity significantly from quadratic to linear in the number of parties involved. Finally, we implement our MKHE schemes and provide benchmarks which outperform the previous results.

In 2020, Kudinov, Kiktenko, and Fedorov pointed out a flaw in the tight security proof of the $SPHINCS^{+}$ construction. This work gives a new tight security proof for $SPHINCS^{+}$. The flaw can be traced back to the security proof for the Winternitz one-time signature scheme (WOTS) used within $SPHINCS^{+}$. In this work, we give a standalone description of the WOTS variant used in SPHINCS+ that we call WOTS-TW. We provide a security proof for WOTS-TW and multi-instance WOTS-TW against non-adaptive chosen message attacks where the adversary only learns the public key after it made its signature query. Afterwards, we show that this is sufficient to give a tight security proof for $SPHINCS^{+}$. We recover almost the same bound for the security of $SPHINCS^{+}$, with only a factor $w$ loss compared to the previously claimed bound, where w is the Winternitz parameter that is commonly set to 16. On a more technical level, we introduce new lower bounds on the quantum query complexity for generic attacks against properties of cryptographic hash functions and analyse the constructions of tweakable hash functions used in $SPHINCS^{+}$ with regard to further security properties.

We show how the Weil pairing can be used to evaluate the assigned characters of an imaginary quadratic order $\mathcal{O}$ in an unknown ideal class $[\mathfrak{a}] \in \mathrm{Cl}(\mathcal{O})$ that connects two given $\mathcal{O}$-oriented elliptic curves $(E, \iota)$ and $(E', \iota') = [\mathfrak{a}](E, \iota)$. When specialized to ordinary elliptic curves over finite fields, our method is conceptually simpler and often faster than a recent approach due to Castryck, Sot\'akov\'a and Vercauteren, who rely on the Tate pairing instead. The main implication of our work is that it breaks the decisional Diffie--Hellman problem for practically all oriented elliptic curves that are acted upon by an even-order class group. It can also be used to better handle the worst cases in Wesolowski's recent reduction from the vectorization problem for oriented elliptic curves to the endomorphism ring problem, leading to a method that always works in sub-exponential time.

We describe a simple MPC protocol in the preprocessing model for computing multivariate quadratic maps. This yields Mesquite, a KKW-style signature scheme which, to our knowledge, produces the shortest signatures of any based on the MQ assumption. For example, our compact parameter set targeting NIST security level I has an average signature size of 8.8KB and runtimes on par with Picnic3 L1.

A wiretap coding scheme (Wyner, Bell Syst. Tech. J. 1975) enables Alice to reliably communicate a message m to an honest Bob by sending an encoding c over a noisy channel chB, while at the same time hiding m from Eve who receives c over another noisy channel chE.

Wiretap coding is clearly impossible when chB is a degraded version of chE, in the sense that the output of chB can be simulated using only the output of chE. A classic work of Csiszár and Körner (IEEE Trans. Inf. Theory, 1978) shows that the converse does not hold. This follows from their full characterization of the channel pairs (chB, chE) that enable information-theoretic wiretap coding. In this work, we show that in fact the converse does hold when considering computational security; that is, wiretap coding against a computationally bounded Eve is possible if and only if chB is not a degraded version of chE. Our construction assumes the existence of virtual black-box (VBB) obfuscation of specific classes of ``evasive'' functions that generalize fuzzy point functions, and can be heuristically instantiated using indistinguishability obfuscation. Finally, our solution has the appealing feature of being universal in the sense that Alice's algorithm depends only on chB and not on chE.

Ciminion is an MPC-friendly pseudo-random function (PRF) recently proposed at Eurocrypt’21. As in the case of other MPC-friendly constructions proposed in the literature (e.g., MiMC, HadesMiMC, Rescue), it aims to minimize the number of multiplications in large finite fields. While MiMC, HadesMiMC, and Rescue are block ciphers, Ciminion is a (modified) Farfalle-like cryptographic function. At the current state of the art, it achieves the best performance in MPC applications. However, Ciminion has a critical weakness. Its security highly relies on the independence of its subkeys, which is achieved by using an expensive key schedule. Many MPC use cases involving symmetric PRFs rely on secretly shared symmetric keys, and hence the expensive key schedule must also be computed in MPC. As a result, Ciminion’s performance is significantly reduced in these use cases. In this paper, we solve this problem. Following the approach introduced by Ciminion’s designers, we propose Megafono, a modified version of Farfalle designed for achieving a small multiplicative complexity without any key schedule. Following this strategy, we present the PRF Hydra, which utilizes both a Lai-Massey construction and a novel construction we name Amaryllises in its nonlinear layer. Amaryllises can be seen as a generalized variant of a Lai-Massey scheme, which allows us to further decrease the multiplicative complexity of Hydra. Based on an extensive security analysis, we implement Hydra in an MPC framework. The results show that it outperforms all MPC-friendly schemes currently published in the literature.

At CRYPTO'19, A. Gohr proposed neural distinguishers for the lightweight block cipher Speck32/64, achieving better results than the state-of-the-art at that point. However, the motivation for using that particular architecture was not very clear, leading us to investigate whether a smaller and/or better performing neural distinguisher exists. This paper studies the depth-10 and depth-1 neural distinguishers proposed by Gohr with the aim of finding out whether smaller or better-performing distinguishers for Speck32/64 exist. We first evaluate whether we can find smaller neural networks that match the accuracy of the proposed distinguishers. We answer this question in affirmative with the depth-1 distinguisher successfully pruned, resulting in a network that remained within one percentage point of the unpruned network's performance. Having found a smaller network that achieves the same performance, we examine if its performance can be improved as well. We also study whether processing the input before giving it to the pruned depth-1 network would improve its performance. To this end, convolutional autoencoders were found that managed to reconstruct the ciphertext pairs successfully, and their trained encoders were used as a preprocessor before training the pruned depth-1 network. We found that, even though the autoencoders achieve a perfect reconstruction, the pruned network did not have the necessary complexity anymore to extract useful information from the preprocessed input, motivating us to look at the feature importance to get more insights. To achieve this, we used LIME, with results showing that a stronger explainer is needed to assess it correctly.