International Association
for Cryptologic Research

In recent years, quantum technology has been rapidly developed. As security analyses for symmetric ciphers continue to emerge, many require an evaluation of the resources needed for the quantum circuit implementation of the encryption algorithm. In this regard, we propose the quantum circuit decision problem, which requires us to determine whether there exists a quantum circuit for a given permutation f using M ancilla qubits and no more than K quantum gates within the circuit depth D. Firstly, we investigate heuristic algorithms and classical SAT-based models in previous works, revealing their limitations in solving the problem. Hence, we innovatively propose an improved SAT-based model incorporating three metrics of quantum circuits. The model enables us to find the optimal quantum circuit of an arbitrary 3 or 4-bit S-box under a given optimization goal based on SAT solvers, which has proved the optimality of circuits constructed by the tool, LIGHTER-R. Then, by combining different criteria in the model, we find more compact quantum circuit implementations of S-boxes such as RECTANGLE and GIFT. For GIFT S-box, our model provides the optimal quantum circuit that only requires 8 gates with a depth of 31. Furthermore, our model can be generalized to linear layers and improve the previous SAT-based model proposed by Huang et al. in ASIACRYPT 2022 by adding the criteria on the number of qubits and the circuit depth.

Machine learning as a service requires the client to trust the server and provide its own private information to use this service. Usually, clients may worry that their private data is being collected by server without effective supervision, the server aims to ensure proper management of the user data, thereby fostering the advancement of its services. In this work, we focus on private decision tree evaluation (PDTE) which can alleviates the privacy concerns associated with classification tasks using decision tree. After the evaluation, except for some hyperparameters, the client only receives the classification results of their private data from server, while the server learns nothing.

Firstly, we propose three amortized efficient private comparison algorithms: TECMP, RDCMP and CDCMP, which are based on leveled homomorphic encryption. They are non-interactive, high precision (up to 26624-bit), many-to-many, and output expressive, achieving an amortized cost of less than 1 ms under 32-bit, which is an order of magnitude faster than the state-of-the-art. Secondly, we propose three batch PDTE schemes using our private comparison: TECMP-PDTE, RDCMP-PDTE and CDCMP-PDTE. Due to the batch operations, we utilized a clear rows relation (CRR) algorithm, which obfuscates the position and classification results of the different row data. Finally, in decision tree exceeding 1000 nodes with 16-bit each, the amortized runtime of TECMP-PDTE and RDCMP-PDTE both more than 56$\times$ faster than state-of-the-art, while the TECMP-PDTE with CRR still achieves 14$\times$ speedup. Even in a single row and a tree of fewer than 100 nodes with 64-bit, and the TECMP-PDTE maintains a comparable performance with the current work.

We propose a novel KZG-based sum-check scheme, dubbed $\mathsf{Losum}$, with optimal efficiency. Particularly, its proving cost is one multi-scalar-multiplication of size $k$---the number of non-zero entries in the vector, its verification cost is one pairing plus one group scalar multiplication, and the proof consists of only one group element.

Using $\mathsf{Losum}$ as a component, we then construct a new lookup argument, named $\mathsf{Locq}$, which enjoys a smaller proof size and a lower verification cost compared to the state of the arts $\mathsf{cq}$, $\mathsf{cq}$+ and $\mathsf{cq}$++. Specifically, the proving cost of $\mathsf{Locq}$ is comparable to $\mathsf{cq}$, keeping the advantage that the proving cost is independent of the table size after preprocessing. For verification, $\mathsf{Locq}$ costs four pairings, while $\mathsf{cq}$, $\mathsf{cq}$+ and $\mathsf{cq}$++ require five, five and six pairings, respectively. For proof size, a $\mathsf{Locq}$ proof consists of four $\mathbb{G}_1$ elements and one $\mathbb{G}_2$ element; when instantiated with the BLS12-381 curve, the proof size of $\mathsf{Locq}$ is $2304$ bits, while $\mathsf{cq}$, $\mathsf{cq}$+ and $\mathsf{cq}$++ have $3840$, $3328$ and $2944$ bits, respectively. Moreover, $\mathsf{Locq}$ is zero-knowledge as $\mathsf{cq}$+ and $\mathsf{cq}$++, whereas $\mathsf{cq}$ is not. $\mathsf{Locq}$ is more efficient even compared to the non-zero-knowledge (and more efficient) versions of $\mathsf{cq}$+ and $\mathsf{cq}$++.

Vector commitments gain a lot of attention because of their wide usage in applications such as blockchain and accumulator. Mercurial vector commitments and mercurial functional commitments (MFC), as significant variants of VC, are the central techniques to construct more advanced cryptographic primitives such as zero-knowledge set and zero-knowledge functional elementary database (ZK-FEDB). However, the current MFC only supports linear functions, limiting its application, i.e. building the ZK-FEDB that only supports linear function queries. Besides, to our best knowledge, the existing MFC and ZK-FEDBs, including the one proposed by Zhang and Deng (ASIACRYPT '23) using RSA accumulators, are all in the group model and cannot resist the attack of quantum computers.

To break these limitations, we formalize the first system model and security model of MFC for circuits. Then, we target some specific properties of a new falsifiable assumption, i.e. the $\mathsf{BASIS}$ assumption proposed by Wee and Wu (EUROCRYPT '23) to construct the first lattice-based succinct mercurial functional commitment for circuits. To the application, we show that our constructions can be used to build the first lattice-based ZK-FEDB directly within the existing generic framework.

An inner product argument (IPA) is a cryptographic primitive used to construct a zero-knowledge proof (ZKP) system, which is a notable privacy-enhancing technology. We propose a novel efficient IPA called $\mathsf{Cougar}$. $\mathsf{Cougar}$ features cubic root verifier and logarithmic communication under the discrete logarithm (DL) assumption. At Asiacrypt2022, Kim et al. proposed two square root verifier IPAs under the DL assumption. Our main objective is to overcome the limitation of square root complexity in the DL setting. To achieve this, we combine two distinct square root IPAs from Kim et al.: one with pairing ($\mathsf{Protocol3}$) and one without pairing ($\mathsf{Protocol4}$). To construct $\mathsf{Cougar}$, we first revisit $\mathsf{Protocol4}$ and reconstruct it to make it compatible with the proof system for the homomorphic commitment scheme. Next, we utilize $\mathsf{Protocol3}$ as the proof system for the reconstructed $\mathsf{Protocol4}$. Furthermore, we provide a soundness proof for $\mathsf{Cougar}$ in the DL assumption.

The revelations of Edward Snowden in 2013 rekindled concerns within the cryptographic community regarding the potential subversion of cryptographic systems. Bellare et al. (CRYPTO'14) introduced the notion of Algorithm Substitution Attacks (ASAs), which aim to covertly leak sensitive information by undermining individual cryptographic primitives. In this work, we delve deeply into the realm of ASAs against protocols built upon cryptographic primitives. In particular, we revisit the existing ASA model proposed by Berndt et al. (AsiaCCS'22), providing a more fine-grained perspective. We introduce a novel ASA model tailored for protocols, capable of capturing a wide spectrum of subversion attacks. Our model features a modular representation of subverted parties within protocols, along with fine-grained definitions of undetectability. To illustrate the practicality of our model, we applied it to Lindell's two-party ECDSA protocol (CRYPTO'17), unveiling a range of ASAs targeting the protocol's parties with the objective of extracting secret key shares. Our work offers a comprehensive ASA model suited to cryptographic protocols, providing a useful framework for understanding ASAs against protocols.

Blind signatures enable a receiver to obtain signatures on messages of its choice without revealing any message to the signer. Round-optimal blind signatures are designed as a two-round interactive protocol between a signer and receiver. Coincidentally, the choice of message is not important in many applications, and is routinely set as a random (unstructured) message by a receiver. With the goal of designing more efficient blind signatures for such applications, Hanzlik (Eurocrypt '23) introduced a new variant called non-interactive blind signatures (NIBS). These allow a signer to asynchronously generate partial signatures for any recipient such that only the intended recipient can extract a blinded signature for a random message. This bypasses the two-round barrier for traditional blind signatures, yet enables many known applications. Hanzlik provided new practical designs for NIBS from bilinear pairings. In this work, we investigate efficient NIBS with post-quantum security. We design the first practical NIBS, as well as non-interactive partially blind signatures called tagged NIBS, from lattice-based assumptions. We also propose a new generic paradigm for NIBS from circuit-private leveled homomorphic encryption achieving optimal-sized signatures (i.e., same as any non-blind signature). Finally, we propose new enhanced security properties for NIBS, that could be of practical and theoretical interest.

A PhD position is available at IIIT Bangalore under Prof Ashish Choudhury. Prof Ashish’s research addresses all aspects of security and privacy in distributed systems, especially cryptographic protocols and fault-tolerant distributed consensus. He is particularly interested in secure multiparty computation and classical consensus protocols. Please explore https://sites.google.com/view/ashish-choudhury to learn more about his research topics. The candidate should have a reasonable background in computer science and its mathematical foundations. The applicant must hold a master’s degree in the relevant research field. The position is available for starting in August 2024. The candidate has to appear for a written exam followed by an interview, which will be typically conducted sometime in June 2024. If you are interested, please apply against the formal advertisement for the PhD admissions for the August 2024 cycle whose details are available at https://www.iiitb.ac.in/courses/master-of-science-by-researchdoctor-of-philosophy

Closing date for applications:

Contact: ashish.choudhury@iiitb.ac.in

More information: https://www.iiitb.ac.in/courses/master-of-science-by-researchdoctor-of-philosophy

Event date: 14 July to 19 July 2024

Salary: 36,024 to 41,732 GBP
Closing Date: 13th May 2024

We are looking for a postdoc with expertise on electronic-voting or related topics. The successful post holder is expected to start 1 July 2024 or as soon as possible thereafter and will run until 31st October 2026. The position will be based in the Department of Computer Science and its highly regarded Surrey Centre for Cyber Security (SCCS), working with Dr. Cătălin Drăgan.

The Surrey Centre for Cyber Security (SCCS) is a widely recognized centre of excellence for cyber security research and teaching. There are approximately 17 permanent academic members and 15 non-academic researchers with expertise on voting, formal modelling and verification, applied cryptography, trust systems, social media, communication and networks, and blockchain and distributed ledger technologies over key sectors such as government, finance, communications, transport and cross-sector technologies.

Qualifications:

• We are looking for applicants that demonstrate strong research and analytical skills, have strong communication skills and enthusiasm for developing their own research ideas.
• Applicants should have expertise in one of the following areas: e-voting, or formal verification of cryptographic protocols, or provable security.
• A PhD in Computer Science, Mathematics, or other closely related area (or be on course of getting one very soon at the time of application).

Closing date for applications:

Contact: Cătălin Drăgan c.dragan@surrey.ac.uk

More information: https://jobs.surrey.ac.uk/Vacancy.aspx?id=13834&forced=2

Bosch Research is developing an open source cloud platform (https://carbynestack.io) for computing on encrypted data using Secure Multi-party Computation (MPC). Potential use cases include, but are not limited to, Privacy-Preserving Machine Learning and Privacy-Preserving Data Analytics. For such large computations on big data, active secure MPC becomes quite expensive. Bosch Research is therefore trying to reduce the computational and communication costs of MPC by optimizing the underlying cryptographic primitives and protocols.

Thus, we are looking for a highly motivated PhD candidate with a strong background in applied cryptography and preferably also MPC. The candidates should meet the following requirements:

• Education: Hold an M.Sc. degree (or equivalent) with excellent grades in IT security or computer science.
• Experience and Knowledge: Strong background in (applied) cryptography with a particular focus on cryptographic protocols/MPC, including security models and basic security proof techniques. Good software development/programming skills.
• Personality and Working Practice: Self-motivated and enthusiastic, independent, reliable, creative, and able to work in an international team with diverse background.
• Language: Fluent English language skills

If the above requirements apply to you, you are welcome to read on. The successful candidate will:

• become a part of the team and advance research on MPC,
• develop novel approaches to improve the practical efficiency of actively secure MPC protocols,
• design efficient MPC protocols for diverse use-cases, and
• publish and present your results in top-tier journals and at conferences.

The position is based at the Bosch Research Campus in Renningen, Germany, fully funded for three years, no teaching duties, with 30 days annual leave, and the usual benefits.

Closing date for applications:

Contact: Please submit your application, including your CV, transcripts of records from your Master studies, and a cover letter including your research background and research interest, via: https://smrtr.io/hmG3C

More information: https://youtu.be/OctvCi2pHJY

Event date: 3 December to 4 December 2024
Submission deadline: 30 July 2024
Notification: 5 September 2024

Event date: 7 March to 9 March 2026

Event date: 26 March to 28 March 2025

Event date: 18 December to 21 December 2024
Submission deadline: 8 September 2024
Notification: 18 October 2024

Event date: 4 September 2024
Submission deadline: 15 June 2024
Notification: 15 July 2024

Event date: 2 September to 6 September 2024
Submission deadline: 14 June 2024

I am looking for Ph.D. students in the area of analysing and preventing physical side channels in embedded devices. Two positions are available, which, as usual in the UK, enable the post holder to cover their tuition fees as well as enable them to cover their living expenses.

The research topics that I am recruiting for are:

• Pre-silicon modelling and analysis: you should be familiar with utilising a typical HW design flow, power simulation tools, and you should have an interest in developing skills in leakage modelling as well as analysis.
• Statistical detection and analysis methods: you should be comfortable with probability theory and statistics, and you should have an interest in exploring sophisticated statistical approaches in the context of exploiting and detecting leakage. This research may also touch on statistical learning methods.
• Implementation and analysis of post-quantum schemes: you should be familiar with low level software implementations (aka Assembly programming), and have an interest in exploring implementation options (potentially also considering dedicated hardware, e.g. the impact of dedicated instructions) to develop secure and reasonably efficient post-quantum implementations.

If you feel that you fit with one (or several) of the three topics, or, if you believe that you can make a good case for another topic, then please get in touch (see contact info below). Please send me a transcript of records, and a short (1 page) statement explaining why you want to do a PhD with me). If I think that you are a viable candidate, I will guide you through the application process.

I am now a faculty member and thus part of the Birmingham Centre for Security and Privacy. You can find information about this research group here: https://www.birmingham.ac.uk/research/centre-for-cyber-security-and-privacy. This is a sizeable research group, which offers companionship via other PhD students and staff members, as well as opportunities via many good relationships with industry.

Closing date for applications:

Contact: Prof. Elisabeth Oswald (sca-research@pm.me, or m.e.oswald@bham.ac.uk).

Hadamard product is a point-wise product for two vectors. This paper presents a new scheme to prove Hadamard-product relation as a sub-protocol for SNARKs based on univariate polynomials. Prover uses linear cryptographic operations to generate the proof containing logarithmic field elements. The verification takes logarithmic cryptographic operations with constant numbers of pairings in bilinear group. The construction of the scheme is based on the Lagrange-based KZG commitments (Kate, Zaverucha, and Goldberg at Asiacrypt 2010) and the folding technique. We construct an inner-product protocol from folding technique on univariate polynomials in Lagrange form, and by carefully choosing the random polynomials suitable for folding technique, we construct a Hadamard-product protocol from the inner-product protocol, giving an alternative to prove linear algebra relations in linear time, and the protocol has a better concrete proof size than previous works.

Fully Homomorphic Encryption (FHE) is a powerful Privacy-Enhancing Technology (PET) that enables computations on encrypted data without having access to the secret key. While FHE holds immense potential for enhancing data privacy and security, creating its practical applications is associated with many difficulties. A significant barrier is the absence of easy-to-use, standardized components that developers can utilize as foundational building blocks. Addressing this gap requires constructing a comprehensive library of FHE components, a complex endeavor due to multiple inherent problems. We propose a competition-based approach for building such a library. More concretely, we present FHERMA, a new challenge platform that introduces black-box and white-box challenges, and fully automated evaluation of submitted FHE solutions. The initial challenges on the FHERMA platform are motivated by practical problems in machine learning and blockchain. The winning solutions get integrated into an open-source library of FHE components, which is available to all members of the PETs community under the Apache 2.0 license.