International Association
for Cryptologic Research

The Research Training Group "Cybercrime and Forensic Computing" aims to systematically analyse research questions arising from the interaction between computer science and criminal law. The following research areas are particularly relevant to the PhD position: Cryptography, Provable Security, and Secure Messaging. PhD students from computer science (especially applied cryptography and information security) and law collaborate and are supervised by a large group of PIs. The particular research project supervised by Paul Rösler focuses on stronger privacy and anonymity in secure messaging protocols. More information about the project can be found at https://cybercrime.fau.de

Necessary qualifications: Applicants should have an excellent academic record and hold an MSc or an equivalent university degree in computer science or related disciplines, and have the goal to finish a PhD degree within three years.

Supplementary description: The positions will commence on October 1, 2024. FAU aims to increase the number of women in scientific positions. Female candidates are therefore particularly encouraged to apply. In case of equal qualifications, candidates with disabilities will take precedence. Please submit your complete application documents by April 10, 2024 to cybercrime-applications@fau.de. Please mention in your application at least one research area from the above list which you are specifically interested in. Interviews will commence between 13. and 17.05.2024 in Erlangen.

Founded in 1743 and situated at the heart of the Nuremberg Metropolitan Region, FAU is a strong research university with an international perspective and one of the largest universities in Germany. FAU’s outstanding research and teaching is reflected in top positions in both national and international rankings, as well as the high amount of DFG funding which its researchers are able to secure.

Closing date for applications:

Contact: Paul Rösler (paul.roesler@fau.de)

More information: https://www.jobs.fau.de/jobs/2-phd-positions-m-f-d-salary-level-13-tv-l-in-computer-science-full-time-and-1-phd-position-m-f-d-salary-level-13-tv-l-in-law-part-time-75-91270455/

A verifiable delay function $\texttt{VDF}(x,T)\rightarrow (y,\pi)$ maps an input $x$ and time parameter $T$ to an output $y$ together with an efficiently verifiable proof $\pi$ certifying that $y$ was correctly computed. The function runs in $T$ sequential steps, and it should not be possible to compute $y$ much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., $y=x^{2^T}$. There are two constructions for the proof of exponentiation (PoE) certifying that $y=x^{2^T}$, with Wesolowski (Eurocrypt'19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS'19).

A recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt'22) are short-lived proofs and signatures, which are proofs and signatures which are only sound for some time $t$, but after that can be forged by anyone. For this they rely on "watermarkable VDFs", where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on "zero-knowledge VDFs", where instead of the output $y$, one just proves knowledge of this output. The existing proposals for watermarkable and zero-knowledge VDFs all build on Wesolowski's PoE, for the watermarkable VDFs there's currently no security proof.

In this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al.. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zero-knowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al's construction in several dimensions (faster forging times, weaker assumptions).

A key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for $y=x^{2^T}$, but instead give a (watermarked or zk) proof for the more basic statement that $x',y'$ satisfy $x'=x^r,y'=y^r$ for some $r$, together with a normal PoE for $y'=(x')^{2^T}$.

This paper introduces a new approach to construct zero-knowledge large language models (zkLLM) based on the Folding technique. We first review the concept of Incrementally Verifiable Computation (IVC) and compare the IVC constructions based on SNARK and Folding. Then we discuss the necessity of Non-uniform IVC (NIVC) and present several Folding schemes that support more expressive circuits, such as SuperNova, Sangria, Origami, HyperNova, and Protostar. Based on these techniques, we propose a zkLLM design that uses a RAM machine architecture with a set of opcodes. We define corresponding constraint circuits for each opcode and describe the workflows of the prover and verifier. Finally, we provide examples of opcodes to demonstrate the circuit construction methods. Our zkLLM design achieves high efficiency and expressiveness, showing great potential for practical applications.

Multi-valued Validated Asynchronous Byzantine Agreement ($\mathsf{MVBA}$) is one essential primitive for many distributed protocols, such as asynchronous Byzantine fault-tolerant scenarios like atomic broadcast ($\mathsf{ABC}$), asynchronous distributed key generation, and many others. Recent surge of efforts have pushed the communication complexity of such protocols from $O(\ell n^2 + \lambda n^2 + n^3)$ (Cachin et al, CRYPTO'00), to $O(\ell n^2 + \lambda n^2)$ (Abbraham et al, PODC'19) and finally to optimal $O(\ell n + \lambda n^2)$ (Lu et al, PODC' 20), for $\ell$-bit inputs across a network of $n$ nodes, with security parameter $\lambda$.

However, those constructions of $\mathsf{MVBA}$ heavily rely on ``heavyweight'' cryptographic tools, such as non-interactive threshold signatures. The computational cost of algebraic operations, the susceptibility to quantum attacks, and the necessity of a trusted setup associated with threshold signatures present significant remaining challenges. There is a growing interest in information-theoretic or hash-based constructions (historically called signature-free constructions). Unfortunately, the state-of-the-art hash-based $\mathsf{MVBA}$ (Duan et al., CCS'23) incurs a large $O(\ell n^2 + \lambda n^3)$-bits communication, which in turn makes the hash-based $\mathsf{MVBA}$ inferior performance-wise comparing with the ``classical'' ones. Indeed, this was clearly demonstrated in our experimental evaluations.

To make hash-based $\mathsf{MVBA}$ actually realize its full potential, in this paper, we introduce an $\mathsf{MVBA}$ with adaptive security, and $\widetilde{O}(\ell n + \lambda n^2)$ communication, exclusively leveraging conventional hash functions. Our new $\mathsf{MVBA}$ achieves nearly optimal communication, devoid of heavy operations, surpassing both threshold signature-based schemes and the hash-based scheme in many practical settings, as demonstrated in our experiments. For example, in scenarios with a network size of $n = 201$ and an input size of $1.75$ MB, our $\mathsf{MVBA}$ exhibits a latency that is 81\% lower than that of the existing hash-based $\mathsf{MVBA}$ and 47\% lower than the threshold signature-based $\mathsf{MVBA}$. Our new construction also achieves optimal parameters in other metrics such as $O(1)$ rounds and $O(n^2)$ message complexity, except with a sub-optimal resilience, tolerating up to $20\%$ Byzantine corruptions (instead of $33\%$). Given its practical performance advantages, our new hash-based $\mathsf{MVBA}$ naturally leads to better asynchronous distributed protocols, by simply plugging it into existing frameworks.

SHA2 has been widely adopted across various traditional public-key cryptosystems, post-quantum cryptography, personal identification, and network communication protocols, etc. Hence, ensuring the robust security of SHA2 is of critical importance. There have been several differential fault attacks based on random word faults targeting SHA1 and SHACAL-2. However, extending such random word-based fault attacks to SHA2 proves significantly more difficult due to the heightened complexity of the boolean functions in SHA2.

In this paper, assuming random word faults, we find some distinctive differential properties within the boolean functions in SHA2. Leveraging these findings, we propose a new differential fault attack methodology that can be effectively utilized to recover the final message block and its corresponding initial vector in SHA2, forge HMAC-SHA2 messages, extract the key of SHACAL-2, and extend our analysis to similar algorithm like SM3. We validate the effectiveness of these attacks through rigorous simulations and theoretical deductions, revealing that they indeed pose substantial threats to the security of SHA2. In our simulation-based experiments, our approach necessitates guessing $T$ bits within a register, with $T$ being no more than $5$ at most, and having a approximate $95\%$ (for SHA512) probability of guessing just $1$ bit. Moreover, upon implementing a consecutive series of 15 fault injections, the success probability for recovering one register (excluding the guessed bits) approaches $100\%$. Ultimately, approximately 928 faulty outputs based on random word faults are required to carry out the attack successfully.

Large Language Models (LLMs) have emerged as powerful tools in various domains involving blockchain security (BS). Several recent studies are exploring LLMs applied to BS. However, there remains a gap in our understanding regarding the full scope of applications, impacts, and potential constraints of LLMs on blockchain security. To fill this gap, we conduct a literature review on LLM4BS.

As the first review of LLM's application on blockchain security, our study aims to comprehensively analyze existing research and elucidate how LLMs contribute to enhancing the security of blockchain systems. Through a thorough examination of scholarly works, we delve into the integration of LLMs into various aspects of blockchain security. We explore the mechanisms through which LLMs can bolster blockchain security, including their applications in smart contract auditing, identity verification, anomaly detection, vulnerable repair, and so on. Furthermore, we critically assess the challenges and limitations associated with leveraging LLMs for blockchain security, considering factors such as scalability, privacy concerns, and adversarial attacks. Our review sheds light on the opportunities and potential risks inherent in this convergence, providing valuable insights for researchers, practitioners, and policymakers alike.

In federated learning, secure aggregation (SA) protocols like Flamingo (S\&P'23) and LERNA (ASIACRYPT'23) have achieved efficient multi-round SA in the malicious model. However, each round of their aggregation requires at least three client-server round-trip communications and lacks support for aggregation result verification. Verifiable SA schemes, such as VerSA (TDSC'21) and Eltaras et al.(TIFS'23), provide verifiable aggregation results under the security assumption that the server does not collude with any user. Nonetheless, these schemes incur high communication costs and lack support for efficient multi-round aggregation. Executing SA entirely within Trusted Execution Environment (TEE), as desined in SEAR (TDSC'22), guarantees both privacy and verifiable aggregation. However, the limited physical memory within TEE poses a significant computational bottleneck, particularly when aggregating large models or handling numerous clients.

In this work, we introduce OPSA, a multi-round one-pass secure aggregation framework based on TEE to achieve efficient communication, streamlined computation and verifiable aggregation all at once. OPSA employs a new strategy of revealing shared keys in TEE and instantiates two types of masking schemes. Furthermore, a result verification module is designed to be compatible with any type of SA protocol instantiated under the OPSA framework with weaker security assumptions. Compared with the state-of-the-art schemes, OPSA achieves a 2$\sim$10$\times$ speedup in multi-round aggregation while also supporting result verification simultaneously. OPSA is more friendly to scenarios with high network latency and large-scale model aggregation.

To resist the regimes of ubiquitous surveillance imposed upon us in every facet of modern life, we need technological tools that subvert surveillance systems. Unfortunately, while cryptographic tools frequently demonstrate how we can construct systems that safeguard user privacy, there is limited motivation for corporate entities engaged in surveillance to adopt these tools, as they often clash with profit incentives. This paper demonstrates how, in one particular aspect of everyday life -- customer loyalty programs -- users can subvert surveillance and attain anonymity, without necessitating any cooperation or modification in the behavior of their surveillors.

We present the CheckOut system, which allows users to coordinate large anonymity sets of shoppers to hide the identity and purchasing habits of each particular user in the crowd. CheckOut scales up and systematizes past efforts to subvert loyalty surveillance, which have been primarily ad-hoc and manual affairs where customers physically swap loyalty cards to mask their real identities. CheckOut allows increased scale while ensuring that the necessary computing infrastructure does not itself become a new centralized point of privacy failure.

Of particular importance to our scheme is a protocol for loyalty programs that offer reward points, where we demonstrate how CheckOut can assist users in paying each other back for loyalty points accrued while using each others' loyalty accounts. We present two different mechanisms to facilitate redistributing rewards points, offering trade-offs in functionality, performance, and security.

Accumulation schemes are a simple yet powerful primitive that enable highly efficient constructions of incrementally verifiable computation (IVC). Unfortunately, all prior accumulation schemes rely on homomorphic vector commitments whose security is based on public-key assumptions. It is an interesting open question to construct efficient accumulation schemes that avoid the need for such assumptions.

In this paper, we answer this question affirmatively by constructing an accumulation scheme from *non-homomorphic* vector commitments which can be realized from solely symmetric-key assumptions (e.g. Merkle trees). We overcome the need for homomorphisms by instead performing spot-checks over error-correcting encodings of the committed vectors.

Unlike prior accumulation schemes, our scheme only supports a bounded number of accumulation steps. We show that such *bounded-depth* accumulation still suffices to construct proof-carrying data (a generalization of IVC). We also demonstrate several optimizations to our PCD construction which greatly improve concrete efficiency.

Fail-stop signatures are digital signatures that allow a signer to prove that a specific forged signature is indeed a forgery. After such a proof is published, the system can be stopped.

We introduce a new simple ECDSA fail-stop signature scheme. Our proposal is based on the minimal assumption that an adversary with a quantum computer is not able to break the (second) preimage resistance of a cryptographically-secure hash function. Our scheme is as efficient as traditional ECDSA, does not limit the number of signatures that a signer can produce, and relies on minimal security assumptions. Using our construction, the signer has minimal computational overhead in the signature producing phase and produces a signature indistinguishable from a 'regular' ECDSA signature.

Existing DAG-based BFT protocols exhibit long latency to commit decisions. The primary reason for such a long latency is having a leader every 2 or more “rounds”. Even under honest leaders, these protocols require two or more reliable broadcast (RBC) instances to commit the proposal submitted by the leader (leader vertex), and additional RBCs to commit other proposals (non-leader vertices). In this work, we present Sailfish, the first DAG-based BFT that supports a leader vertex in each round. Under honest leaders, Sailfish maintains a commit latency of one RBC round plus $1\delta$ to commit the leader vertex (where $\delta$ is the actual transmission latency of a message) and only an additional RBC round to commit non-leader vertices.

We propose a new key exchange protocol based on the Generalised Diffie-Hellman Key Exchange. In the latter, instead of using a group-action, we consider a semigroup action. In our proposal, the semigroup is the set of oriented knots in $\mathbb{S}^3$ with the operation of connected sum. As a semigroup action, we choose the action of the semigroup on itself through the connected sum. For the protocol to work, we need to use knot invariants, which allow us to create the shared secret key starting from the same knot represented in two different ways. In particular, we use finite type invariants. The security of the protocol is guaranteed by the hardness of decomposing knots in the semigroup.

Secure multi-party computation aims to allow a set of players to compute a given function on their secret inputs without revealing any other information than the result of the computation. In this work, we focus on the design of secure multi-party protocols for shared polynomial operations. We consider the classical model where the adversary is honest-but-curious, and where the coefficients (or any secret values) are either encrypted using an additively homomorphic encryption scheme or shared using a threshold linear secret-sharing scheme. Our protocols terminate after a constant number of rounds and minimize the number of secure multiplications. In their seminal article at PKC 2006, Mohassel and Franklin proposed constant-rounds protocols for the main operations on (shared) polynomials. In this work, we improve the fan-in multiplication of nonzero polynomials, the multi-point polynomial evaluation and the polynomial interpolation (on secret points) to reach a quasi-linear complexity (instead of quadratic in Mohassel and Franklin's work) in the degree of shared input/output polynomials. Computing with shared polynomials is a core component of designing multi-party protocols for privacy-preserving operations on private sets, like private disjointness test or private set intersection. Using our new protocols, we are able to improve the complexity of such protocols and to design the first variant which always returns a correct result.

We present a construction for secure computation of differentially private sparse histograms that aggregates the inputs from a large number of clients. Each client contributes a value to the aggregate at a specific index. We focus on the case where the set of possible indices is superpolynomially large. Hence, the resulting histogram will be sparse, i.e., most entries will have the value zero.

Our construction relies on two non-colluding servers and provides security against malicious adversaries that may control one of the servers and any numbers of clients. It achieves communication and computation complexities linear in the input size, and achieves the optimal error $O\big(\frac{\log(1/\delta)}{\epsilon}\big)$, independent of the size of the domain of indices. We compute the communication cost of our protocol, showing its scalability. For a billion clients, the communication cost for each server is under 26 KiB per client.

Our paper solves an open problem of the work of Bell et al. (CCS'22) which presented a solution for the semi-honest setting while incurring sublinear overhead in its efficiency. We formalize a proof approach for proving malicious security in settings where the output and possible additional information revealed during the execution need to provide differential privacy.

Rescue-XLIX is an Arithmetization-Oriented Substitution-Permutation Network over prime fields $\mathbb{F}_p$ which in one full round first applies a SPN based on $x \mapsto x^d$ followed by a SPN based on the inverse power map $x \mapsto x^\frac{1}{d}$. In a recent work, zero-dimensional Gröbner bases for SPN and Poseidon sponge functions have been constructed by utilizing weight orders. Following this approach we construct zero-dimensional Gröbner bases for Rescue-XLIX ciphers and sponge functions.

This paper gives the first lattice-based two-round threshold signature based on lattice assumptions for which the first message is independent of the message being signed without relying on fully-homomorphic encryption. Our construction supports arbitrary thresholds and is scalable to support a large number of signers, say n = 1024.

Our construction provides a careful instantiation of a generic threshold signature construction by Tessaro and Zhu (EUROCRYPT ’23) based on specific linear hash functions, which in turns can be seen as a generalization of the FROST scheme by Komlo and Goldberg (SAC ’20). Our reduction techniques are new in the context of lattice-based cryptography. Also, our scheme does not use any heavy tools, such as NIZKs or homomorphic trapdoor commitments.

Threshold Schnorr signatures are seeing increased adoption in practice, and offer practical defenses against single points of failure. However, one challenge with existing randomized threshold Schnorr signature schemes is that signers must carefully maintain secret state across signing rounds, while also ensuring that state is deleted after a signing session is completed. Failure to do so will result in a fatal key-recovery attack by re-use of nonces.

While deterministic threshold Schnorr signatures that mitigate this issue exist in the literature, all prior schemes incur high complexity and performance overhead in comparison to their randomized equivalents. In this work, we seek the best of both worlds; a deterministic and stateless threshold Schnorr signature scheme that is also simple and efficient.

Towards this goal, we present Arctic, a lightweight two-round threshold Schnorr signature that is deterministic, and therefore does not require participants to maintain state between signing rounds. As a building block, we formalize the notion of a Verifiable Pseudorandom Secret Sharing (VPSS) scheme, and define Shine, an efficient VPSS construction. Shine is secure when the total number of participants is at least 2t − 1 and the adversary is assumed to corrupt at most t − 1; i.e., in the honest majority model.

We prove that Arctic is secure under the discrete logarithm assumption in the random oracle model, similarly assuming at minimum 2t − 1 number of signers and a corruption threshold of at most t − 1. For moderately sized groups (i.e., when n ≤ 20), Arctic is more than an order of magnitude more efficient than prior deterministic threshold Schnorr signatures in the literature. For small groups where n ≤ 10, Arctic is three orders of magnitude more efficient.

VOLE-in-the-head paradigm recently introduced by Baum et al. (Crypto 2023) allows transforming zero-knowledge protocols in the designated verifier setting into public-coin protocols, which can be made non-interactive and publicly verifiable. Our transformation applies to a large class of ZK protocols based on vector oblivious linear evaluation (VOLE) and leads to resulting ZK protocols that have linear proof size and are simpler, smaller, and faster than related approaches based on MPC-in-the-head. We propose a new candidate post-quantum signature scheme from the Multivariate Quadratic(MQ) problem based on a new protocol for the VOLE-in-the-head paradigm, which significantly reduces the signature size compared to previous works. We achieve a signature size of 2.5KB for a 128-bit security level. Compared to the state-of-the-art MQ-based signature schemes, our signature scheme achieves a factor from 3 to 4 improvement in terms of the signature size while keeping the computational efficiency competitive

Direct Anonymous Attestation (DAA) is a cryptographic protocol that enables users with a Trusted Platform Module (TPM) to authenticate without revealing their identity. Thus, DAA emerged as a good privacy-enhancing solution. Current standards have security based on factorization and discrete logarithm problem making them vulnerable to quantum computer attacks. Recently, a number of lattice-based DAA has been propose in the literature to start transition to quantum-resistant cryptography. In addition to these, DAA has been adapted to Vehicle Ad-hoc NETwork system (VANETs) to offer secure vehicule-to-vehicule/infrastructure communication (V2V and V2I). In this paper, we provide an implementation of the most advanced post-quantum DAA for VANETs. We explore the cryptographic foundations, construction methodologies, and the performance of this scheme, offering insights into their suitability for various real-world use cases.

Fully Homomorphic Encryption (FHE) is a cryptographic primitive that allows performing arbitrary operations on encrypted data. Since the conception of the idea in [RAD78], it was considered a holy grail of cryptography. After the first construction in 2009 [Gen09], it has evolved to become a practical primitive with strong security guarantees. Most modern constructions are based on well-known lattice problems such as Learning with Errors (LWE). Besides its academic appeal, in recent years FHE has also attracted significant attention from industry, thanks to its applicability to a considerable number of real-world use-cases. An upcoming standardization effort by ISO/IEC aims to support the wider adoption of these techniques. However, one of the main challenges that standards bodies, developers, and end users usually encounter is establishing parameters. This is particularly hard in the case of FHE because the parameters are not only related to the security level of the system, but also to the type of operations that the system is able to handle. In this paper, we provide examples of parameter sets for LWE targeting particular security levels that can be used in the context of FHE constructions. We also give examples of complete FHE parameter sets, including the parameters relevant for correctness and performance, alongside those relevant for security. As an additional contribution, we survey the parameter selection support offered in open-source FHE libraries.