International Association
for Cryptologic Research

Proving knowledge soundness of an interactive proof from scratch is often a challenging task. This has motivated the evelopment of various special soundness frameworks which, in a nutshell, separate knowledge extractors into two parts: (1) an extractor to produce a set of accepting transcripts conforming to some structure; (2) a witness recovery algorithm to recover a witness from a set of transcripts with said structure. These frameworks take care of (1), so it suffices for a protocol designer to specify (2) which is often simple(r).

Recently, works by Bünz–Fisch (TCC’23) and Aardal et al. (CRYPTO’24) provide new frameworks, called almost special soundness and predicate special soundness, respectively. To handle insufficiencies of special soundness, they deviate from its spirit and augment it in different ways. The necessity for their changes is that special soundness does not allow the challenges for useful sets of transcripts to depend on the transcripts themselves, but only on the challenges in the transcripts. As a consequence, (generalised) special soundness cannot express extraction strategies which reduce a computational problem to finding “inconsistent” accepting transcripts, for example in PCP/IOP-based or lattice-based proof systems, and thus provide (very) sub-optimal extractors. In this work, we introduce adaptive special soundness which captures extraction strategies exploiting inconsistencies between transcripts, e.g. transcripts containing different openings of the same commitment. Unlike (generalised) special soundness (Attema, Fehr, and Resch (TCC’23)), which specifies a target transcript structure, our framework allows specifying an extraction strategy which guides the extractor to sample challenges adaptively based on the history of prior transcripts. We extend the recent (almost optional) extractor of Attema, Fehr, Klooß and Resch (EPRINT 2023/1945) to our notion, and argue that it encompasses almost special soundness and predicate special soundness in many cases of interest.

As a challenging application, we modularise and generalise the lattice Bulletproofs analysis by Bünz–Fisch (TCC’23) using the adaptive special soundness framework. Moreover, we extend their analysis to the ring setting for a slightly wider selection of rings than rational integers.

Multilateral Trade Credit Set-off (MTCS) is a process run by a service provider that collects trade credit data (i.e. obligations from a firm to pay another firm) from a network of firms and detects cycles of debts that can be removed from the system. The process yields liquidity savings for the participants, who can discharge their debts without relying on expensive loans. We propose an MTCS protocol that protects firms' sensitive data, such as the obligation amount or the identity of the firms they trade with. Mathematically, this is analogous to solving the Minimum Cost Flow (MCF) problem over a graph of $n$ firms, where the $m$ edges are the obligations. State-of-the-art techniques for Secure MCF have an overall complexity of $O(n^{10} \log n)$ communication rounds, making it barely applicable even to small-scale instances. Our solution leverages novel secure techniques such as Graph Anonymization and Network Simplex to reduce the complexity of the MCF problem to $O(max(n, \log\log{n+m}))$ rounds of interaction per pivot operations in which $O(max(n^2, nm))$ comparisons and multiplications are performed. Experimental results show the tradeoff between privacy and optimality.

The COOL protocol of Chen (DISC'21) is a major advance that enables perfect security for various tasks (in particular, Byzantine Agreement in Synchrony and Reliable Broadcast in Asynchrony). For an input of size $L$ bits, its communication complexity is $O(nL+n^2 \log n)$, which is optimal up to a $\log n$ factor. Unfortunately, Chen’s analysis is rather intricate and complex.

Our main contribution is a simple analysis of a new variant of COOL based on elementary counting arguments. Our main consistency proof takes less than two pages (instead of over 20 pages), making the COOL protocol much more accessible. In addition, the simple analysis allows us to improve the protocol by reducing one round of communication and reducing the communication complexity by 40%.

In addition, we suggest a new way of extracting the core properties of COOL as a new primitive, which we call Graded Dispersal. We show how Graded Dispersal can then be used to obtain efficient solutions for Byzantine Agreement, Verifiable Information Dispersal, Gradecast, and Reliable Broadcast (in both Synchrony and Asynchrony, where appropriate). Our improvement of COOL directly applies here, and we improve the state-of-the-art in all those primitives by reducing at least one round and 40% communication.

The question of whether the complexity class P equals NP is a major unsolved problem in theoretical computer science. In this paper, we introduce a new language, the Add and XNOR (the negation of exclusive or (XOR)) problem, which has the simplest structure and perfect randomness, by extending the subset sum problem. We prove that P $\neq$ NP as it shows that an exhaustive search is necessary to solve the Add and XNOR problem. That is, problems that are verifiable in polynomial time are not necessarily solvable in polynomial time.

We present a compact quantum circuit for factoring a large class of integers, including some whose classical hardness is expected to be equivalent to RSA (but not including RSA integers themselves). To our knowledge, it is the first polynomial-time circuit to achieve sublinear qubit count for a classically-hard factoring problem; the circuit also achieves sublinear depth and nearly linear gate count. We build on the quantum algorithm for squarefree decomposition discovered by Li, Peng, Du and Suter (Nature Scientific Reports 2012), which relies on computing the Jacobi symbol in quantum superposition. Our circuit completely factors any number $N$, whose prime decomposition has distinct exponents, and finds at least one non-trivial factor if not all exponents are the same. In particular, to factor an $n$-bit integer $N=P^2 Q$ (with $P$ and $Q$ prime, and $Q<2^m$ for some $m$), our circuit uses $\widetilde{O}(m)$ qubits and has depth at most $\widetilde{O}(m + n/m)$, with $\widetilde{O}(n)$ quantum gates. When $m=\Theta(n^a)$ with $2/3 < a < 1$, the space and depth are sublinear in $n$, yet no known classical algorithms exploit the relatively small size of $Q$ to run faster than general-purpose factoring algorithms. We thus believe that factoring such numbers has potential to be the most concretely efficient classically-verifiable proof of quantumness currently known.

The technical core of our contribution is a new space-efficient quantum algorithm to compute the Jacobi symbol of $A$ mod $B$, in the regime where $B$ is classical and much larger than $A$. Crucially, our circuit reads the bits of the classical value $B$ in a streaming fashion, never storing more than $\widetilde{O}(\log A)$ qubits of quantum information at one time. In the context of the larger Jacobi algorithm for factoring $N = P^2Q$, this reduces the overall qubit count to be roughly proportional to the length of $Q$, rather than the length of $N$. Our circuit for computing the Jacobi symbol is also highly gate-efficient and parallelizable, achieving gate count $\widetilde{O}(\log B)$ and depth at most $\widetilde{O}(\log A + \log B/\log A)$. Finally, we note that our circuit for computing the Jacobi symbol generalizes to related problems, such as computing the greatest common divisor, and thus could be of independent interest.

We introduce a new approach between classical security proofs of modes of operation and dedicated security analysis for known cryptanalysis families: General Practical Cryptanalysis. This allows us to analyze generically the security of the sum of two keyed permutations against known attacks. In many cases (of course, not all), we show that the security of the sum is strongly linked to that of the composition of the two permutations. This enables the construction of beyond-birthday bound secure low-latency PRFs by cutting a known-to-be-secure block cipher into two equal parts. As a side result, our general analysis shows an inevitable difficulty for the key recovery based on differential-type attacks against the sum, which leads to a correction of previously published attacks on the dedicated design Orthros.

Fully Homomorphic Encryption (FHE) enables secure computation of functions on ciphertexts without requiring decryption. Specifically, AP-like HE schemes exploit an intrinsic bootstrapping method called blind rotation. In blind rotation, a look-up table is homomorphically evaluated on the input ciphertext through the iterative multiplication of monomials. However, the algebraic structure of the multiplicative group of monomials imposes certain limitations on the input and output plaintext space: 1. only a fraction of the input plaintext space can be bootstrapped, 2. the output plaintext space is restricted to subsets of real numbers.

In this paper, we design a novel bootstrapping method called slot blind rotation. The key idea of our approach is to utilize the automorphism group instead of monomials. More specifically, the look-up table is encoded into a single polynomial using SIMD (Single Instruction Multiple Data) packing and is rotated via a series of homomorphic multiplications and automorphisms. This method achieves two significant advantages: 1. the entire input plaintext space can be bootstrapped, 2. a more broad output plaintext space, such as complex numbers or finite field/rings can be supported.

Finally, we present a new HE scheme leveraging the slot blind rotation technique and provide a proof-of-concept implementation. We also demonstrate the the benchmark results and provide recommended parameter sets.

This article presents a cryptanalysis of a 19th-century encrypted manuscript discovered in the archives of Conde de Siete Fuentes in Tenerife, Canary Islands, Spain. The manuscript, preserved by the heirs of the 6th Count of Valle de Salazar, utilizes a polyalphabetic substitution cipher. The cryptanalysis was performed by applying statistical frequency analysis and developing a Python script for decryption, resulting in the authors successfully deciphering the message. The decrypted letter reveals political communications discussing the strategic positioning of Tenerife as the capital, the dissolution of local councils, and the influence of key political figures. The analysis compares the cipher with historical encryption techniques, and identifies the unique characteristics of the manuscript’s encryption method. The study highlights the political dynamics and alliances within Tenerife’s nobility and their interactions with the central Spanish government, providing significant insights into, both, the cryptographic practices and political maneuvers of the time.

Event date: 7 July to 12 July 2025
Submission deadline: 24 February 2024
Notification: 6 May 2025

Event date: 7 July to 12 July 2025
Submission deadline: 24 February 2025
Notification: 6 May 2025

Event date: 26 May to 28 May 2025
Submission deadline: 26 January 2025
Notification: 24 February 2025

Event date: 31 March to 2 April 2025
Submission deadline: 30 November 2024
Notification: 20 January 2025

Department of Mathematics and Computer Science - Institute of Computer Science 2 Positions for Research Associates (m/f/d) with 100% full-time employment limited until 31.07.2027 Salary Group 13 TV-L FU Reference: WiMi EASEPROFIT Responsibilities: Collaboration in the EASEPROFIT joint project with academic and industry partners from the financial sector. The work involves the development of innovative post-quantum cryptography and security protocols for the "typical" financial transactions between banks and customers over the internet. Further information can be found at http://www.mi.fu-berlin.de/en/inf/groups/ag-comm/index.html. Requirements: Applicants must have completed a scientific degree (Master’s or equivalent) in Computer Science, Mathematics, or a related field. The position can be designed as either a PhD position or a postdoctoral position (for candidates with an existing doctorate). (Professional) Experience: Knowledge of mathematical cryptography and experience with security protocols are required. Additional knowledge in post-quantum cryptography or cryptographic protocols in the financial sector is an advantage.

Closing date for applications:

Contact: Please send your application until 31.12.2024 with relevant documents in PDF format (preferably as a single file) electronically by email, including the reference number, to g.wunder@fu-berlin.de (cc: stefanie.bahe@fu-berlin.de).

More information: https://www.fu-berlin.de/universitaet/beruf-karriere/jobs/wiss/19_fb-mathematik-und-informatik/MI-WiMi-EASEPROFIT.html

The Theory of Computer Science Group from the Informatics Institute of the University of Amsterdam is seeking a PhD student to carry out cutting-edge research in cryptography, with an expected focus on Secure Multi-Party Computation. This position is funded by the NWO Gravitation project “Challenges in Cyber Security”, a collaboration with partners from TU Eindhoven, Radboud University, CWI and Vrije Universiteit Amsterdam.

For more information and to apply, please visit https://werkenbij.uva.nl/en/vacancies/phd-position-in-secure-multi-party-computation-netherlands-13605. The closing date for the applications is 15 April 2025 (for full consideration, you are encouraged to apply on or before 15 March 2025).

Closing date for applications:

Contact: Divya Ravi (d.ravi@uva.nl)

More information: https://werkenbij.uva.nl/en/vacancies/phd-position-in-secure-multi-party-computation-netherlands-13605

Multiple Tenure Track and Tenured Faculty Positions Available at USF. Job IDs: 38362 38363 38364

Closing date for applications:

Contact: See the advertisement for the details.

More information: https://www.usf.edu/work-at-usf/careers/

The CSE Department at UC Santa Cruz invites applications for PhD students and postdocs in applied cryptography, security/privacy, private computation, metadata-private communication, and secure databases/systems. Candidates should have background or interest in one or more of the following areas: applied cryptography, searchable encryption, secure databases/systems, oblivious and multi-party computation, hardware enclaves, computer/cloud security, side-channel/leakage-abuse attacks/defenses, and anonymous communication (including traffic-analysis resistance).

My group’s focus is on bridging the security/efficiency gap between cryptography/security and real-world systems/databases. We conduct our research and publish our findings in top-tier venues in security (e.g., USENIX Security, IEEE Security & Privacy, CCS, NDSS), cryptography (e.g., CRYPTO, Eurocrypt), and systems/databases (e.g., SIGMOD, VLDB, SOSP). Our research mission is to develop cryptographic solutions and real systems that are simultaneously practical, efficient, and provably secure. You can review my recent publications on my website: https://idemertzis.com .

(1) PhD applicants should hold a BS/MS in computer science, electrical and computer engineering, information security, mathematics, or a related field, with strong analytical, mathematical, coding, and software engineering skills. Interested candidates should email me their CV, a brief summary of research experience and interests, and a personal website link (if available).
Please submit your application here: https://grad.soe.ucsc.edu/admissions​ (Computer Science & Engineering→ Apply to PhD) and mention my name in your application.

(2) Post-doctoral applicants please email me your CV and your research statement (if available).

Closing Date for Application: December 20, 2024

Closing date for applications:

Contact: Ioannis Demertzis (idemertz@ucsc.edu)

The Research Unit of Privacy Enhanced Technologies at TU Wien is offering a 40 hours/week position as university assistant (prae-doc) limited to expected 4 years. **PhD position in Privacy-Enhancing Technologies at the Vienna University of Technology**.

The TU Wien, Austria's leading institution for technology and science, invites applications for a PhD position in Privacy-Enhancing Technologies (PET). Our research spans cryptographic protocols, zero-knowledge proof systems, information-theoretic approaches such as differential privacy, and challenges in distributed settings, including privacy-preserving cryptocurrencies. We aim to advance both fundamental theory and practical solutions with real-world impact.

Your profile:

• Academic Excellence: Outstanding Master’s degree in Computer Science, Mathematics, or a closely related field.
• Problem-Solving Passion: Enthusiastic about tackling challenging and complex problems.
• Curiosity: Eager to learn and grow in a dynamic research environment.
• Team Spirit: Positive thinker with a supportive and collaborative mindset.
• Research Experience: Prior experience in privacy, cryptography, or distributed systems is an advantage but not required.
• Communication: Proficient in written and spoken English for effective collaboration and dissemination of research.
• Independent Thinking: Capable of working autonomously while contributing to a team-oriented environment.
• Innovative Mindset: Open to exploring novel approaches and solutions in privacy-enhancing technologies.

How to apply

Applications must be submitted over the TU Wien here https://jobs.tuwien.ac.at/Job/244516"> More information: https://www.pets.wien

Closing date for applications:

Contact: Univ. Prof. Dr. Dominique Schröder

More information: https://jobs.tuwien.ac.at/Job/244516

We are looking for a motivated PhD student to work on Post-quantum cryptography for Cloud Computing. The position is fully funded with 3.5-year duration and the starting date is negotiable. The applicant should have a solid background in Computer Science, Mathematics, or relevant fields. If interested, please send your CV and transcripts to us.

Closing date for applications:

Contact: Willy Susilo (wsusilo@uow.edu.au) and Dung Hoang Duong (hduong@uow.edu.au)

We are looking for

a candidate with internationally outstanding qualification in an early career phase with promising potential (W2 Tenure Track) or

an experienced candidate with an outstanding scientific track record and international visibility (W3)

to represent the field of "Cybersecurity and Artificial Intelligence" in both research and teaching. The scientific focus of the position should be on application-oriented aspects of cybersecurity with strong references to machine learning and other artificial intelligence techniques, e.g.:

Safeguarding AI processes and systems against cyberattacks;

Analysis and defense against cyberattacks and attack methods that specifically exploit AI;

Applying AI techniques to detect and analyze cyberattacks and to improve cybersecurity;

Methods of AI, esp. machine learning with special security and privacy properties.

For more information on the structure of the professorship and the opportunity to apply, please refer to the full advertisement on the TU Darmstadt website.

Closing date for applications:

Contact: For further information or questions, please contact Prof. Dr. Michael Waidner (professor of TU Darmstadt and CEO of ATHENE): michael.waidner@tu-darmstadt.de

More information: https://www.tu-darmstadt.de/universitaet/karriere_an_der_tu/stellenangebote/aktuelle_stellenangebote/stellenausschreibungen_detailansichten_1_572736.en.jsp