International Association
for Cryptologic Research

Maximal extractable value (MEV) in the context of blockchains and cryptocurrencies refers to the highest potential profit that an actor, particularly a miner or validator, can achieve through their ability to include, exclude, or re-order transactions within the blocks. MEV has become a topic of concern within the Web3 community as it impacts the fairness and security of the cryptocurrency ecosystem. In this work, we propose and explore techniques that utilize randomized permutations to shuffle the order of transactions of a committed block before they are executed. We also show that existing MEV mitigation approaches using an encrypted mempool can be readily extended by permutation-based techniques, thus providing multi-layer protection. With a focus on BFT consensus, we then propose BlindPerm, a framework enhancing an encrypted mempool with permutation at essentially no additional overheads and present various optimizations. Finally, we demonstrate how to extend our mitigation technique to support PoW longest-chain consensus protocols.

During the pandemic, the limited functionality of existing privacy-preserving contact tracing systems highlights the need for new designs. Wang et al. proposed an environmental-adaptive framework (CSS '21) but failed to formalize the security. The similarity between their framework and attribute-based credentials (ABC) inspires us to reconsider contact tracing from the perspective of ABC schemes. In such schemes, users can obtain credentials on attributes from issuers and prove the credentials anonymously (i.e., hiding sensitive information of both user and issuer). This work first extends ABC schemes with auditability, which enables designated auditing authorities to revoke the anonymity of particular issuers. We show a concrete construction by adding a DDH-based ``auditable public key'' mechanism to the Connolly et al.'s ABC scheme (PKC '22). In this work we present three contributions regarding the auditable ABC: (1) we refine the environmental-adaptive contact tracing framework, (2) present a formal treatment which includes game-based security definition and a detailed protocol construction. Finally, (3) we implement our construction to showcase the practicality of our protocol.

Proof-of-useful-work (PoUW), an alternative to the widely used proof-of-work (PoW), aims to re-purpose the network's computing power. Namely, users evaluate meaningful computational problems, e.g., solving optimization problems, instead of computing numerous hash function values as in PoW. A recent approach utilizes the training process of deep learning as ``useful work''. However, these works lack security analysis when deploying them with blockchain-based protocols, let alone the informal and over-complicated system design. This work proposes a distributed proof-of-deep-learning (D-PoDL) scheme concerning PoUW's requirements. With a novel hash-traininßg-hash structure and model-referencing mechanism, our scheme is the first deep learning-based PoUW scheme that enables achieving better accuracy distributively. Next, we introduce a transformation from the D-PoDL scheme to a generic D-PoDL blockchain protocol which can be instantiated with two chain selection rules, i.e., the longest-chain rule and the weight-based blockchain framework (LatinCrypt' 21). This work is the first to provide formal proofs for deep learning-involved blockchain protocols concerning the robust ledger properties, i.e., chain growth, chain quality, and common prefix. Finally, we implement the D-PoDL scheme to discuss the effectiveness of our design.

An encryption scheme is Key Dependent Message (KDM) secure if it is safe to encrypt messages that can arbitrarily depend on the secret keys themselves. In this work, we show how to upgrade essentially the weakest form of KDM security into the strongest one. In particular, we assume the existence of a symmetric-key bit-encryption that is circular-secure in the $1$-key setting, meaning that it maintains security even if one can encrypt individual bits of a single secret key under itself. We also rely on a standard CPA-secure public-key encryption. We construct a public-key encryption scheme that is KDM secure for general functions (of a-priori bounded circuit size) in the multi-key setting, meaning that it maintains security even if one can encrypt arbitrary functions of arbitrarily many secret keys under each of the public keys. As a special case, the latter guarantees security in the presence of arbitrary length key cycles. Prior work already showed how to amplify $n$-key circular to $n$-key KDM security for general functions. Therefore, the main novelty of our work is to upgrade from $1$-key to $n$-key security for arbitrary $n$.

As an independently interesting feature of our result, our construction does not need to know the actual specification of the underlying 1-key circular secure scheme, and we only rely on the existence of some such scheme in the proof of security. In particular, we present a universal construction of a multi-key KDM-secure encryption that is secure as long as some 1-key circular-secure scheme exists. While this feature is similar in spirit to Levin's universal construction of one-way functions, the way we achieve it is quite different technically, and does not come with the same ``galactic inefficiency''.

In this work, we extend the MPC-in-the-head framework, used in recent efficient zero-knowledge protocols, to work over the ring $\mathbb{Z}_{2^k}$, which is the primary operating domain for modern CPUs. The proposed schemes are compatible with any threshold linear secret sharing scheme and draw inspiration from MPC protocols adapted for ring operations. Additionally, we explore various batching methodologies, leveraging Shamir's secret sharing schemes and Galois ring extensions, and show the applicability of our approach in RAM program verification. Finally, we analyse different options for instantiating the resulting ZK scheme over rings and compare their communication costs.

Public data can be authenticated by obtaining from a trustworthy website with TLS. Private data, such as user profile, are usually restricted from public access. If a user wants to authenticate his private data (e.g., address) provided by a restricted website (e.g., user profile page of a utility company website) to a verifier, he cannot simply give his username and password to the verifier. DECO (CCS 2020) provides a solution for liberating these data without introducing undesirable trust assumption, nor requiring server-side modification. Their implementation is mainly based on TLS 1.2.

In this paper, we propose an optimized solution for TLS 1.3 websites. We tackle a number of open problems, including the support of X25519 key exchange in TLS 1.3, the design of round-optimal three-party key exchange, the architecture of two-party computation of TLS 1.3 key scheduling, and circuit design optimized for two-party computation. We test our implementation with real world website and show that our optimization is necessary to avoid timeout in TLS handshake.

Deep neural networks (DNNs) represent a powerful technique for assessing cryptographic security concerning side-channel analysis (SCA) due to their ability to aggregate leakages automatically, rendering attacks more efficient without preprocessing. Nevertheless, despite their effectiveness, DNNs employed in SCA are predominantly black-box algorithms, posing considerable interpretability challenges. In this paper, we propose a novel technique called Key Guessing Occlusion (KGO) that acquires a minimal set of sample points required by the DNN for key recovery, which we call OccPoIs. These OccPoIs provide information on which areas of the traces are important to the DNN for retrieving the key, enabling evaluators to know where to refine their cryptographic implementation. After obtaining the OccPoIs, we first explore the leakages found in these OccPoIs to understand what the DNN is learning with first-order Correlation Power Analysis (CPA). We show that KGO obtains relevant sample points that have a high correlation with the given leakage model but also acquires sample points that first-order CPA fails to capture. Furthermore, unlike the first-order CPA in the masking setting, KGO obtains these OccPoIs without the knowledge of the shares or mask. Next, we employ the template attack (TA) using the OccPoIs to investigate if KGO could be used as a feature selection tool. We show that using the OccPoIs with TA can recover the key for all the considered synchronized datasets and is consistent as a feature selection tool even on datasets protected by first-order masking. Furthermore, it also allows a more efficient attack than other feature selections on the first-order masking dataset called ASCADf.

This paper studies the quantum computational complexity of the discrete logarithm and related group-theoretic problems in the context of ``generic algorithms''---that is, algorithms that do not exploit any properties of the group encoding.

We establish a generic model of quantum computation for group-theoretic problems, which we call the quantum generic group model, as a quantum analog of its classical counterpart. Shor's algorithm for the discrete logarithm problem and related algorithms can be described in this model. We show the quantum complexity lower bounds and (almost) matching algorithms of the discrete logarithm and related problems in this model. More precisely, we prove the following results for a cyclic group $\mathcal G$ of prime order.

(1) Any generic quantum discrete logarithm algorithm must make $\Omega(\log |\mathcal G|)$ depth of group operation queries. This shows that Shor's algorithm that makes $O(\log |\mathcal G|)$ group operations is asymptotically optimal among the generic quantum algorithms, even considering parallel algorithms. (2) We observe that some (known) variations of Shor's algorithm can take advantage of classical computations to reduce the number and depth of quantum group operations. We introduce a model for generic hybrid quantum-classical algorithm that captures these variants, and show that these algorithms are almost optimal in this model. Any generic hybrid quantum-classical algorithm for the discrete logarithm problem with a total number of (classical or quantum) group operations $Q$ must make $\Omega(\log |\mathcal G|/\log Q)$ quantum group operations of depth $\Omega(\log\log |\mathcal G| - \log\log Q)$. In particular, if $Q={\rm poly}\log |\mathcal G|$, classical group operations can only save the number of quantum queries by a factor of $O(\log\log |\mathcal G|)$ and the quantum depth remains as $\Omega(\log\log |\mathcal G|)$. (3) When the quantum memory can only store $t$ group elements and use quantum random access memory (qRAM) of $r$ group elements, any generic hybrid quantum-classical algorithm must make either $\Omega(\sqrt{|\mathcal G|})$ group operation queries in total or $\Omega(\log |\mathcal G|/\log (tr))$ quantum group operation queries. In particular, classical queries cannot reduce the number of quantum queries beyond $\Omega(\log |\mathcal G|/\log (tr))$.

As a side contribution, we show a multiple discrete logarithm problem admits a better algorithm than solving each instance one by one, refuting a strong form of the quantum annoying property suggested in the context of password-authenticated key exchange protocol.

The majority of secure messengers have single, centralized service providers that relay ciphertexts between users to enable asynchronous communication. However, in some scenarios such as mass protests in censored networks, relying on a centralized provider is fatal. Mesh messengers attempt to solve this problem by building ad hoc networks in which user clients perform the ciphertext-relaying task. Yet, recent analyses of widely deployed mesh messengers discover severe security weaknesses (Albrecht et al. CT-RSA'21 & USENIX Security'22).

To support the design of secure mesh messengers, we provide a new, more complete security model for mesh messaging. Our model captures forward and post-compromise security, as well as forward and post-compromise anonymity, both of which are especially important in this setting. We also identify novel, stronger confidentiality goals that can be achieved due to the special characteristics of mesh networks (e.g., delayed communication, distributed network and adversary).

Finally, we develop a new protocol, called ASMesh, that provably satisfies these security goals. For this, we revisit Signal's Double Ratchet and propose non-trivial enhancements. On top of that, we add a mechanism that provides forward and post-compromise anonymity. Thus, our protocol efficiently provides strong confidentiality and anonymity under past and future user corruptions. Most of our results are also applicable to traditional messaging.

We prove security of our protocols and evaluate their performance in simulated mesh networks. Finally, we develop a proof of concept implementation.

Postdoctoral Fellowship in Cryptography
Applications are invited from qualified candidates for a 2-year postdoctoral fellowship appointment (extendable for one more year) in cryptography. Expertise in cryptography and strong mathematics background are essential, and knowledge of quantum information and computation are important advantages. The focus of the positions is on quantum-resistant cryptography and its application to securing communication in two-party and group settings.

A Ph.D. degree and evidence of excellence in research are required. Successful applicants are expected to maintain an active program of research, and participate in research activities with academic and industry partners in the grant. The annual salary is $55,000 - $65,000 (CAD) depending on the qualifications and experience. The positions are available immediately.

Applicants should include a cover letter describing their interest in the position, a curriculum vitae, a short research statement and at least two contacts for reference letters. Interested individuals should send their application to espri@ucalgary.ca
Inquiries may be addressed to Rei Safavi-Naini, (rei@ucalgary.ca). Applications will be considered as they are submitted until the position is filled.

About the University of Calgary & Calgary
The University of Calgary is Canada’s leading next-generation university. The university has reached its Eyes High goal to be recognized as one of Canada’s top five research universities. The University of Calgary recognizes that a diverse staff/faculty benefits and enriches the work, learning and research experiences of the entire campus and greater community.

Calgary has been named one of the world's most livable cities for years. Calgary is less than an hour’s drive from the Rocky Mountains and boasts the most extensive urban pathway and bikeway network in North America.

Closing date for applications:

Contact: Rei Safavi-Naini

Event date: 25 May to 26 May 2024
Submission deadline: 4 September 2023
Notification: 15 September 2023

What you do? 1. Design and implement the proving system algorithms that are to be used in zkEVM/zkVM solutions. 2. Optimize Elliptic Curve Primitives and proof generation processes. 3. Survey the emerging zkEVM, zkVM, and various ZKP protocols with in-depth understanding on their academic papers and code implementations. Requirements: 1. Strong background in Math, Cryptography, or Zero Knowledge Proof. 2 Solid experience on Plonk & Halo2 proving systems with both BN and BLS Elliptic Curve families. 3. Proficiency in Rust & Go. 4. Ability to pick up new things beyond cryptography (i.e. details of EVM). 5. Experience in blockchain infrastructure development or cryptography preferred.

Closing date for applications:

Contact: mia

We are looking for a PhD candidate in Secure Computation, focusing on Multiparty Computation (and related cryptographic protocols), and its applications to Machine Learning. For a complete description of the position and to apply, please see: https://www.universiteitleiden.nl/en/vacancies/2023/q3eng/23-48013889phd-candidate-privacy-preserving-machine-learning

Closing date for applications:

Contact: Eleftheria Makri: e.makri@liacs.leidenuniv.nl

More information: https://www.universiteitleiden.nl/en/vacancies/2023/q3eng/23-48013889phd-candidate-privacy-preserving-machine-learning

We are seeking a highly motivated candidate for a fully funded PhD position in Code-Based Cryptography/Cryptanalysis, focusing on theoretical and practical cryptanalysis of code-based schemes, particularly the current NIST PQC candidates.

This position is a collaboration between Ruhr University Bochum (RUB) in Germany and the Technology Innovation Institute (TII) in Abu Dhabi. You will work closely with renowned experts Dr. Andre Esser from TII and Prof. Alexander May from RUB. The primary office is based at RUB, with generous travel opportunities and a planned multiple months research stay at the partnering TII.

The ideal candidate:

• Master's degree (obtained before the starting date) in mathematics, computer science, or a related field
• Strong knowledge of cryptology, particularly in code-based cryptography / cryptanalysis
• Excellent track record of completed classes in cryptography, cryptanalysis, coding theory, etc.
• Curiosity-driven, self-motivated and open to international exchange
• Proficient in spoken/written English as well as in any programming language
• Prior publications or contributed to research projects

You'll enjoy a fully funded position with a competitive salary (100%, E13) for three years, access to cutting-edge research facilities, collaboration with top experts, and ample travel opportunities. The program provides vibrant workplaces, exceptional networking possibilities, and the chance to conduct original research with direct impact on post-quantum cryptographic standards. Program conducted entirely in English, no German required. Starting date negotiable, ideally fall 2023.

To apply, please send the following documents via email:

• Cover letter expressing your interest in the position and summarizing your qualifications (1-2 pages)
• CV highlighting your educational background, research experience, and publications (if any)
• Copies of bachelor’s and master’s certificates
• Contact information for two or more academic references

We're excited to receive your application!

Closing date for applications:

Contact: Andre Esser (andre.esser@tii.ae)

We are looking for a motivated PhD student for a project in provable post-quantum security. The goal of the PhD is to investigate the hardness of mathematical problems supposed to resist quantum attacks. The project is funded by the Italian National Recovery and Resilience Plan (NRRP) DM117. For further information please visit: https://www.unitn.it/en/ateneo/110103/nrrp-dm117-2023 Online application: https://webapps.unitn.it/Apply/en/Web/Home/dott

Closing date for applications:

Contact: Marco Calderini

The Applied Cryptography Group at Technical University of Darmstadt offers a fully funded post-doc position as part of the ERC project CRYPTOLAYER. The goal of this project is to develop cryptographic tools to improve the privacy, scalability and security of next-generation blockchain protocols. Topics of interest include (but are not limited to) threshold cryptography, second-layer protocols, cryptographic wallets, multiparty computation, zero-knowledge and more. You will conduct research and publish/present the results at top venues for research in cryptography and IT Security. The position is to be filled as soon as possible for initially 2 years with the possibility of an extension.

Your profile:

• Completed PhD degree (or equivalent) at a top university in IT security, computer science, mathematics, electrical engineering, or a similar area.
• Publications at top venues for cryptography/IT Security (e.g., EUROCRYPT, CRYPTO, ASIACRYPT, S&P, CCS, TCC),
• Good knowledge in one of the topics mentioned above is a plus.
• Experience in project management and supervising students is a plus.

Your application should contain a CV, list of publications, a short research statement and at least one contact for a reference letter.

TU Darmstadt is a top research university for IT Security, Cryptography, and Computer Science in Europe. We offer an excellent working environment in the heart of the Frankfurt Metropolitan Area, which is internationally well-known for its high quality of life. The review of applications starts immediately until the position is filled.

Closing date for applications:

Contact: Sebastian Faust

The Applied Cryptography Group at Technical University of Darmstadt offers a fully funded Ph.D. position in cryptography. Topics of interest include (but are not limited to) threshold cryptography, cryptography for blockchains, leakage resilient cryptography, multiparty computation and more. You will conduct research and publish/present the results at top venues for research in cryptography and IT Security. The position is to be filled as soon as possible for initially 3 years with the possibility of an extension.

Your profile:

• Completed Master's degree (or equivalent) with excellent grades in computer science, mathematics, or a similar area.
• Strong mathematical and/or algorithmic/theoretical CS background
• Good knowledge in one of the topics mentioned above is a plus.
• Fluent in English

Your application should contain a CV, record of grades, a short motivation letter and at least one contact for a reference letter.

TU Darmstadt is a top research university for IT Security, Cryptography, and Computer Science in Europe. We offer an excellent working environment in the heart of the Frankfurt Metropolitan Area, which is internationally well-known for its high quality of life. The review of applications starts immediately until the position is filled.

Closing date for applications:

Contact: Sebastian Faust

There is an open call for a Postdoc position in the Cyber Security and Applied Cryptograhy research group at the Institute of Computer Science, University of St.Gallen, led by Prof. Katerina Mitrokotsa.

Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are active in several areas, a subset of which include:

• Verifiable computation
• Secure, private and distributed aggregation
• Secure multi-party computation
• Privacy-preserving biometric authentication
• Anonymous credentials
• Distributed and privacy-preserving authentication

Candidates should have a strong background in applied cryptography and provable security, are able to work independently and also collaborate in a team. Applicants must hold a Ph.D., with contributions in the relevant research topics and have publications in good venues.

The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found. The University of St.Gallen conducts excellent research with international implications. The city of St.Gallen is located one hour from Zurich and offers a high quality of life.

Please apply by 20th July 2023 through the job portal (via link).

Closing date for applications:

Contact: Prof. Katerina Mitrokotsa - applications through job portal only.

More information: https://jobs.unisg.ch/offene-stellen/postdoc-fellow-in-cryptography-information-security-m-f-d/25ddb9d0-5c47-41ac-8bde-5789dbaca5c4

We are looking for a bright and motivated PhD student to work in the topics of information security and cryptography.

The student is expected to work on topics that include security and privacy issues in authentication. More precisely, the student will be working on investigating efficient and privacy-preserving authentication that provides: i) provable security guarantees, and ii) rigorous privacy guarantees.

Key Responsibilities:

• Perform exciting and challenging research in the domain of information security and cryptography.
• Support and assist in teaching computer security and cryptography courses.

Profile:

• The PhD student is expected to have a MSc degree or equivalent, and strong background in cryptography, network security and mathematics.
• Experience in one or more domains such as cryptography, design of protocols, secure multi-party computation and differential privacy is beneficial.
• Excellent programming skills.
• Excellent written and verbal communication skills in English

The Chair of Cyber Security, https://cybersecurity.unisg.ch/, led by Prof. Katerina Mitrokotsa, is a part of the Institute of Computer Science (ICS) at the University of St.Gallen. Our research interests are centered around information security and applied cryptography, with the larger goal of safeguarding communications and providing strong privacy guarantees. We are currently active in multiple areas including the design of provably secure cryptographic protocols and cryptographic primitives that can be employed for reliable authentication, outsourcing computations in cloud-assisted settings, network security problems as well as secure and privacy-preserving machine learning. As a doctoral student you will be a part of the Doctoral School of Computer Science (DCS), https://dcs.unisg.ch.

The starting date for the position is flexible and come with a very competitive salary. The selection process runs until the suitable candidate has been found.

Please apply by 20th July 2023 through the job portal (via link).

Closing date for applications:

Contact: Prof. Katerina Mitrokotsa - applications through job portal only.

More information: https://jobs.unisg.ch/offene-stellen/funded-phd-student-in-applied-cryptography-privacy-preserving-authentication-m-f-d/e7a9e90b-02cd-45d0-ad4f-fc02131eaf86

Shor's algorithm solves the discrete logarithm problem (DLP) efficiently by taking advantage of the commutativity structure of the group underlying the problem. To counter Shor's algorithm, Horan et al. propose a DLP analogue in the semidirect product semigroup $G\rtimes \mathrm{End}(G)$, given a (semi)group $G$, to construct a quantum-resistant Diffie-Hellman key exchange based on it. For general (semi)groups, the semidirect product discrete logarithm problem (SPDLP) can be reduced to the hidden shift problem where Kuperberg's subexponential quantum algorithm is applicable. In this paper, we consider a specific case where $G$ is an elliptic curve over a finite field and we show that SPDLP on elliptic curves can be solved efficiently using an adaptation of Shor's algorithm for the standard elliptic curve discrete logarithm problem (ECDLP). This result points out that one should not use elliptic curves as the platforms for the semidirect product key exchange.