International Association
for Cryptologic Research

Public-key quantum money is a cryptographic proposal for using highly entangled quantum states as currency that is publicly verifiable yet resistant to counterfeiting due to the laws of physics. Despite significant interest, constructing provably-secure public-key quantum money schemes based on standard cryptographic assumptions has remained an elusive goal. Even proposing plausibly-secure candidate schemes has been a challenge.

These difficulties call for a deeper and systematic study of the structure of public-key quantum money schemes and the assumptions they can be based on. Motivated by this, we present the first black-box separation of quantum money and cryptographic primitives. Specifically, we show that collision-resistant hash functions cannot be used as a black-box to construct public-key quantum money schemes where the banknote verification makes classical queries to the hash function. Our result involves a novel combination of state synthesis techniques from quantum complexity theory and simulation techniques, including Zhandry's compressed oracle technique.

The use of data as a product and service has given momentum to the extensive uptake of complex machine learning algorithms that focus on performing prediction with popular tree-based methods such as decision trees classifiers. With increasing adoption over a wide array of sensitive applications, a significant need to protect the confidentiality of the classifier model and user data is identified. The existing literature safeguards them using interactive solutions based on expensive cryptographic approaches, where an encrypted classifier model interacts with the encrypted queries and forwards the encrypted classification to the user. Adding to that, the state-of-art protocols for protecting the privacy of the model do not contain model-extraction attacks.

We design an efficient virtual black-box obfuscator for binary decision trees and use the random oracle paradigm to analyze the security of our construction. To thwart model-extraction attacks, we restrict to evasive decision trees, as black-box access to the classifier does not allow a PPT adversary to extract the model. While doing so, we present an encoder for hiding parameters in an interval-membership function. Our exclusive goal behind designing the obfuscator is that, not only will the solution increase the class of functions that has cryptographically secure obfuscators, but also address the open problem of non-interactive prediction in privacy-preserving classification using computationally inexpensive cryptographic hash functions.

We propose a novel methodology to obtain $B$lind signatures that is fundamentally based on the idea of hiding part of the underlying plain signatures under a $Z$ero-knowledge argument of knowledge of the whole signature (hence the shorthand, $BZ$). Our proposal is necessarily non-black-box and stated in the random oracle model. We illustrate the technique by describing two instantiations: a classical setting based on the traditional discrete logarithm assumption, and a post-quantum setting based on the commutative supersingular isogeny Diffie-Hellman (CSIDH) assumption.

Event date: 23 April 2023
Submission deadline: 28 February 2023
Notification: 21 March 2023

Event date: 19 June to 22 June 2023
Submission deadline: 17 March 2023
Notification: 19 April 2023

Event date: 22 April 2023
Submission deadline: 3 March 2023
Notification: 17 March 2023

The Department of Computer Science is looking to establish a new research group in Digital Resilience, through the recruitment to four new posts initially, to support the national agenda in how as a nation we can respond to, or recover readily from, a shock or disruptive process to our digital infrastructure. The Digital Resilience strategy is an opportunity to broaden the department’s work to consider new aspects of the growing dependence on, and protection of, networked digital systems, to include research in technologies and architectures for digital resilience, cyber resilience, learning for disruption resistance and recovery, risk modelling and analysis, online crime and fraud, misinformation and disinformation, forensics, and other related fields. The Professor in Digital Resilience represents an exciting opportunity for a strategic, forward-looking academic leader with international recognition in research and teaching to lead this new Research Group in Digital Resilience. This involves establishing the group, recruiting to and developing the team, and supporting the University to develop this innovative multi-disciplinary agenda.

Closing date for applications:

Contact: For further information about this unique and exciting opportunity, please email our recruitment partner Simon Critchley simon@dixonwalter.co.uk or reach out to our Head of Department Prof. Steve Schneider (s.schneider@surrey.ac.uk) to find out more.

More information: https://jobs.surrey.ac.uk/vacancy.aspx?ref=054122-R

Tasks:

• Active research in the area of intrusion detection systems (IDS) for critical infrastructures, secure cyber-physical systems, and artificial intelligence / machine learning for traffic analysis
• Implementation and evaluation of new algorithms and methods
• Cooperation and knowledge transfer with industrial partners
• Publication of scientific results
• Assistance with teaching

Requirements:

• Master’s degree (or equivalent) in Computer Science or related disciplines
• Strong interest in IT security and/or networking and distributed systems
• Knowledge of at least one programming language (C++, Java, etc.) and one scripting language (Perl, Python, etc.) or strong willingness to quickly learn new programming languages
• Linux/Unix skills
• Knowledge of data mining, machine learning, statistics and result visualization concepts is of advantage
• Excellent working knowledge of English; German is of advantage
• Excellent communication skills

For more information about the vacant position please contact Prof. A. Panchenko (E-Mail: itsec-jobs.informatik@lists.b-tu.de).

We value diversity and therefore welcome all applications – regardless of gender, nationality, ethnic and social background, religion/belief, disability, age, sexual orientation, and identity. The BTU Cottbus-Senftenberg strives for a balanced gender relation in all employee groups. Applicants with disabilities will be given preferential treatment if they are equally qualified.

Applications containing the following documents:

• A detailed Curriculum Vitae
• Transcript of records from your Master studies
• An electronic version of your Master thesis, if possible

should be sent in a single PDF file as soon as possible, but not later than 05.02.2023 at itsec-jobs.informatik@lists.b-tu.de.

Closing date for applications:

Contact: Prof. Dr.-Ing. Andriy Panchenko (email: itsec-jobs.informatik@lists.b-tu.de)

More information: https://www.informatik.tu-cottbus.de/~andriy/

Tasks:

• Independent lead of a group of 3 PhD students
• Active research in the area of intrusion detection systems (IDS) for critical infrastructures, secure cyber-physical systems, and artificial intelligence / machine learning for traffic analysis, honeypots, privacy enhancing techniques
• Scientific coordination of project work
• Implementation and evaluation of new algorithms and methods
• Cooperation and knowledge transfer with industrial partners
• Publication of scientific results

Requirements:

• Excellent PhD degree related to IT Security
• Publications in renowned peer-reviewed international conferences/journals
• Master’s degree (or equivalent) in Computer Science, Electrical Engineering, Applied Math or related disciplines
• Knowledge of at least one programming language (C++, Java, etc.) and one scripting language (Perl, Python, etc.) or strong willingness to quickly learn new programming languages
• Excellent working knowledge of English; German is of advantage
• Excellent communication skills

For more information about the vacant position please contact Prof. A. Panchenko (E-Mail: itsec-jobs.informatik@lists.b-tu.de).

We value diversity and therefore welcome all applications – regardless of gender, nationality, ethnic and social background, religion/belief, disability, age, sexual orientation, and identity. The BTU Cottbus-Senftenberg strives for a balanced gender relation in all employee groups. Applicants with disabilities will be given preferential treatment if they are equally qualified.

Applications containing the following documents:

• A detailed Curriculum Vitae with a list of publications
• Transcript of records from your Master studies and PhD Degree
• An electronic version of your PhD thesis, if possible

should be sent in a single PDF file as soon as possible, but not later than 05.2.2023 at itsec-jobs.informatik@lists.b-tu.de.

Closing date for applications:

Contact: Prof. A. Panchenko (email: itsec-jobs.informatik@lists.b-tu.de)

More information: https://www.informatik.tu-cottbus.de/~andriy/

There is a line of 'lookup' protocols to show that all elements of a sequence $f\in{\mathbb F}^n$ are contained in a table $t\in{\mathbb F}^d$, for some field ${\mathbb F}$. Lookup has become an important primitive in Zero Knowledge Virtual Machines, and is used for range checks and other parts of the proofs of a correct program execution. In this note we give several variants of the protocol. We adapt it to the situation when there are multiple lookups with the same table (as is usually the case with range checks), and handle also 'bounded lookup' that caps the number of repetitions.

Fully Homomorphic Encryption enables arbitrary computations over encrypted data and it has a multitude of applications, e.g., secure cloud computing in healthcare or finance. Multi-Key Homomorphic Encryption (MKHE) further allows to process encrypted data from multiple sources: the data can be encrypted with keys owned by different parties.

In this paper, we propose a new variant of MKHE instantiated with the TFHE scheme. Compared to previous attempts by Chen et al. and by Kwak et al., our scheme achieves computation runtime that is linear in the number of involved parties and it outperforms the faster scheme by a factor of 4.5-6.9x, at the cost of a slightly extended pre-computation. In addition, for our scheme, we propose and practically evaluate parameters for up to 128 parties, which enjoy the same estimated security as parameters suggested for the previous schemes (100 bits). It is also worth noting that our scheme—unlike the previous schemes—did not experience any error in any of our nine experiments, each running 1 000 trials.

We present several new heuristic algorithms to compute class polynomials and modular polynomials modulo a prime $P$. For that, we revisit the idea of working with supersingular elliptic curves. The best known algorithms to this date are based on ordinary curves, due to the supposed inefficiency of the supersingular case. While this was true a decade ago, the recent advances in the study of supersingular curves through the Deuring correspondence motivated by isogeny-based cryptography has provided all the tools to perform the necessary tasks efficiently. Our main ingredients are two new heuristic algorithms to compute the $j$-invariants of supersingular curves having an endomorphism ring contained in some set of isomorphism class of maximal orders. The first one is derived easily from the existing tools of isogeny-based cryptography, while the second introduces new ideas to perform that task efficiently for a big number of maximal orders. From there, we obtain two main results. First, we show that we can associate these two algorithms with some operations over the quaternion algebra ramified at $P$ and infinity to compute directly Hilbert and modular polynomials $\mod P$. In that manner, we obtain the first algorithms to compute Hilbert (resp. modular) polynomials modulo $P$ for a good portion of all (resp. all) primes $P$ with a complexity in $O(\sqrt{|D|})$ for the discriminant $D$ (resp. $O(\ell^2)$ for the level $\ell$). Due to the (hidden) complexity dependency on $P$, these algorithms do not outperform the best known algorithms for all prime $P$ but they still provide an asymptotic improvement for a range of prime going up to a bound that is sub-exponential in $|D|$ (resp. $\ell$). Second, we revisit the CRT method for both class and modular polynomials. We show that applying our second heuristic algorithm over supersingular curves to the CRT approach yields the same asymptotic complexity as the best known algorithms based on ordinary curves and we argue that our new approach might be more efficient in practice. The situation appears especially promising for modular polynomials, as our approach reduces the asymptotic cost of elliptic curve operations by a linear factor in the level $\ell$. We obtain an algorithm whose asymptotic complexity is now fully dominated by linear algebra and standard polynomial arithmetic over finite fields.

We introduce a new notion of {\em multiverse threshold signatures} (MTS). In an MTS scheme, multiple universes -- each defined by a set of (possibly overlapping) signers, their weights, and a specific security threshold -- can co-exist. A universe can be (adaptively) created via a non-interactive asynchronous setup. Crucially, each party in the multiverse holds constant-sized keys and releases compact signatures with size and computation time both independent of the number of universes. Given sufficient partial signatures over a message from the members of a specific universe, an aggregator can produce a short aggregate signature relative to that universe.

We construct an MTS scheme building on BLS signatures. Our scheme is practical, and can be used to reduce bandwidth complexity and computational costs in decentralized oracle networks. As an example data point, consider a multiverse containing 2000 nodes and 100 universes (parameters inspired by Chainlink's use in the wild) each of which contains arbitrarily large subsets of nodes and arbitrary thresholds. Each node computes and outputs 1 group element as its partial signature; the aggregator performs under 0.7 seconds of work for each aggregate signature, and the final signature of size 192 bytes takes 6.4 ms (or 198K EVM gas units) to verify. For this setting, prior approaches when used to construct MTS, yield schemes that have one of the following drawbacks: (i) partial signatures that are 97$\times$ larger, (ii) have aggregation times 311$\times$ worse, or (iii) have signature size 39$\times$ and verification gas costs 3.38$\times$ larger. We also provide an open-source implementation and a detailed evaluation.

Since the invention of Bitcoin, cryptocurrencies have gained huge popularity. Crypto wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency funds. Deterministic wallet is an advanced wallet mecha- nism that has been proposed to achieve some appealing virtues, such as low-maintenance, easy backup and recovery, supporting functionalities required by cryptocurrencies, and so on. However, the existing deter- ministic wallet schemes especially in the quantum world still have a long way to be practical. The first barrier is how to build a deterministic wallet scheme without relying on the state, i.e., stateless. The stateful deterministic wallet scheme must internally maintain and keep refreshing synchronously a parameter named state which makes the implementa- tion in practice become more complex. And once one of the states is leaked, thereafter the security notion of unlinkability is cannot be guar- anteed (referred to as the weak security notion of forward unlinkability). The second barrier is how to derive the session secret keys from the master secret key in one-way. There are security shortfalls in previous works, they suffer a fatal vulnerability when a minor fault happens (say, one derived key is compromised somehow), then the damage is not lim- ited to the leaked derived key, instead, it spreads to the master key and the whole system collapses. The third barrier is how to build a post- quantum secure deterministic wallet scheme supporting hot/cold setting, which is important since nearly all popular cryptocurrencies relied on the hardness problems that can be broken by quantum adversaries, and the hot/cold setting is a widely adopted method to effectively reduce the exposure chance of secret keys and hence improving the security of the system. The last barrier is how to build a deterministic wallet scheme with standard security notion of unforgeability. It is motivated by pre- vious works which are based on a weaker/nonstandard unforgeability notion, in which the adversary is only allowed to query and forge the signatures w.r.t. the public keys that were assigned by the challenger.

In this work, we present a new deterministic wallet scheme in quantum world, which is stateless, supports hot/cold setting, satisfiies stronger security notions, and is more efficient. In particular, we reformalize the syntax and security models for deterministic wallets, capturing the func- tionality and security requirements (including full unlinkability and stan- dard unforgeability) imposed by the practice in cryptocurrency. Then we propose a deterministic wallet construction and prove its security in the quantum random oracle model. Finally, we show our wallet scheme is more practicable by analyzing an instantiation of our wallet scheme based on the signature scheme Falcon.

Multi-signature is a protocol where a set of signatures jointly sign a message so that the final signature is significantly shorter than concatenating individual signatures together. Recently, it finds applications in blockchain, where several users want to jointly authorize a payment through a multi-signature. However, in this setting, there is no centralized authority and it could suffer from a rogue key attack where the attacker can generate his own keys arbitrarily. Further, to minimize the storage on blockchain, it is desired that the aggregated public-key and the aggregated signature are both as short as possible. In this paper, we find a compiler that converts a kind of identification (ID) scheme (which we call a linear ID) to a multi-signature so that both the aggregated public-key and the aggregated signature have a size independent of the number of signers. Our compiler is provably secure. The advantage of our results is that we reduce a multi-party problem to a weakly secure two-party problem. We realize our compiler with two ID schemes. The first is Schnorr ID. The second is a new lattice-based ID scheme, which via our compiler gives the first regular lattice-based multi-signature scheme with key-and-signature compact without a restart during signing process.

Many applications in finance and healthcare need access to data from multiple organizations. While these organizations can benefit from computing on their joint datasets, they often cannot share data with each other due to regulatory constraints and business competition. One way mutually distrusting parties can collaborate without sharing their data in the clear is to use secure multiparty computation (MPC). However, MPC’s performance presents a serious obstacle for adoption as it is difficult for users who lack expertise in advanced cryptography to optimize. In this paper, we present Silph, a framework that can automatically compile a program written in a high-level language to an optimized, hybrid MPC protocol that mixes multiple MPC primitives securely and efficiently. Compared to prior works, our compilation speed is improved by up to 30000×. On various database analytics and machine learning workloads, the MPC protocols generated by Silph match or outperform prior work by up to 3.6×.

Two multivariate digital signature schemes, Rainbow and GeMSS, made it into the third round of the NIST PQC competition. However, either made its way to being a standard due to devastating attacks (in one case by Beullens, the other by Tao, Petzoldt, and Ding). How should multivariate cryptography recover from this blow? We propose that, rather than trying to fix Rainbow and HFEv- by introducing countermeasures, the better approach is to return to the classical Oil and Vinegar scheme. We show that, if parametrized appropriately, Oil and Vinegar still provides competitive performance compared to the new NIST standards by most measures (except for key size). At NIST security level 1, this results in either 128-byte signatures with 44 kB public keys or 96-byte signatures with 67 kB public keys. We revamp the state-of-the-art of Oil and Vinegar implementations for the Intel/AMD AVX2, the Arm Cortex-M4 microprocessor, the Xilinx Artix-7 FPGA, and the Armv8-A microarchitecture with the Neon vector instructions set.

We present SCALLOP: SCALable isogeny action based on Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and OSIDH, we use the group action of an imaginary quadratic order’s class group on the set of oriented supersingular curves. Compared to CSIDH, the main benefit of our construction is that it is easy to compute the class-group structure; this data is required to uniquely represent— and efficiently act by— arbitrary group elements, which is a requirement in, e.g., the CSI-FiSh signature scheme by Beullens, Kleinjung and Vercauteren. The index-calculus algorithm used in CSI-FiSh to compute the class-group structure has complexity L(1/2), ruling out class groups much larger than CSIDH-512, a limitation that is particularly problematic in light of the ongoing debate regarding the quantum security of cryptographic group actions. Hoping to solve this issue, we consider the class group of a quadratic order of large prime conductor inside an imaginary quadratic field of small discriminant. This family of quadratic orders lets us easily determine the size of the class group, and, by carefully choosing the conductor, even exercise significant control on it— in particular supporting highly smooth choices. Although evaluating the resulting group action still has subexponential asymptotic complexity, a careful choice of parameters leads to a practical speedup that we demonstrate in practice for a security level equivalent to CSIDH-1024, a parameter currently firmly out of reach of index-calculus-based methods. However, our implementation takes 35 seconds (resp. 12.5 minutes) for a single group-action evaluation at a CSIDH-512-equivalent (resp. CSIDH-1024-equivalent) security level, showing that, while feasible, the SCALLOP group action does not achieve realistically usable performance yet.

Critical and widely used cryptographic protocols have repeatedly been found to contain flaws in their design and their implementation. A prominent class of such vulnerabilities is logical attacks, i.e. attacks that solely exploit flawed protocol logic. Automated formal verification methods, based on the Dolev-Yao (DY) attacker, excel at finding such flaws, but operate only on abstract specification models. Fully automated verification of existing protocol implementations is today still out of reach. This leaves open whether widely used protocol implementations are secure. Unfortunately, this blind spot hides numerous attacks, notably recent logical attacks on widely used TLS implementations introduced by implementation bugs. We answer by proposing a novel and effective technique that we call DY model-guided fuzzing, which precludes logical attacks against protocol implementations. The main idea is to consider as possible test cases the set of abstract DY executions of the DY attacker, and use a mutation-based fuzzer to explore this set. The DY fuzzer concretizes each abstract execution to test it on the program under test. This approach enables reasoning at a more structural and security-related level of messages (e.g. decrypt a message and re-encrypt it with a different key) as opposed to random bit-level modifications that are much less likely to produce relevant logical adversarial behaviors. We implement a full-fledged and modular DY protocol fuzzer. We demonstrate its effectiveness by fuzzing three popular TLS implementations, resulting in the discovery of four novel vulnerabilities.

In recent works of Li the noisy subset product problem (also known as subset product with errors) was invented and applied to cryptography. To better understand its hardness, we give a quantum annealing algorithm for it. Our algorithm is the first algorithm for the problem. We also give the first quantum annealing algorithm for the subset product problem. The efficiencies of both algorithms rely on the fundamental efficiency of quantum annealing. At the end we give two lattice algorithms for both problems via solving the closest vector problem. The complexities of the lattice algorithms depend on the complexities of solving the closest vector problem in two special lattices. They are efficient when the special closest vector problems fall into the regime of bounded distance decoding problems that can be efficiently solved using existing methods based on the LLL algorithm or Babai's nearest plane algorithm.