International Association
for Cryptologic Research

We are inviting applications for a fully-funded PhD position at the Cluster of Excellence CASA. As the successful candidate, you will join the project Robust Certification of Quantum Devices and conduct fundamental research in the areas of:

Nonlocal games and self-testing

Quantum information and cryptography

Group and representation theory

At Bochum, you can expect a vibrant atmosphere of excellent research that spans across many areas of computer science and mathematics. In addition to an exciting research project and a friendly and stimulating work environment, we can offer a generous travel budget that allows for attending relevant conferences and summer schools to present your work to the international community, visiting collaborators, etc. The PhD program is entirely in English. You will be employed on a fully-funded position (100%, E13 salary) with an initial appointment of three years. The starting date is negotiable, but ideally in fall 2023. Your profile:

By default, you have a MSc degree (or be close to completing one) in computer science, mathematics, physics or related fields. Outstanding candidates with a BSc degree will also be considered.

You have an excellent track record in classes related to quantum information and cryptography, and/or more generally in mathematics and theoretical computer science.

You are curiosity driven, enjoy combining creativity with mathematical precision, and are open to interdisciplinary collaborations.

You are fluent in written and spoken English (no German required).

To apply, please email qi@rub.de with subject “CASA PhD Position” and the following information:

Brief cover letter describing your background and research interests.

CV, including transcripts (BSc + MSc).

Electronic contact details of 2 referees.

Any other relevant material (MSc thesis draft, BSc thesis, publications, …).

Applications received by July 10, 2023 will receive full consideration. We strongly encourage applications from members of any underrepresented group.

Closing date for applications:

Contact: qi@rub.de

About Pagoda
Pagoda is shepherding a future where NEAR becomes the blockchain operating system. We believe that re-inventing how software is made and distributed is our greatest opportunity to open economic access to those who are not fully integrated into the global economy. Our products empower people to find opportunity, invent new experiences, and collaborate. Let's build an Open Web world. A world where people control their assets, data, and power of governance.

About The Role
Pagoda is looking for a software engineer with experience building and maintaining cryptography and Zero-Knowledge projects. You will be the in-house expert on cryptography and Zero-Knowledge technology. You will initiate, implement, and lead a variety of projects in this area, including integrating the results of Zero-Knowledge research done by teams in the Near community into NEAR Protocol. Your work will have a major impact on the scalability and decentralization of NEAR Protocol.

What You'll Be Doing:

Apply advances in cryptography and Zero-Knowledge technology to improve security, scalability, and decentralization of NEAR Protocol.

Audit external ZK projects in the NEAR ecosystem and seek opportunities to integrate them into NEAR Protocol

Act as a subject matter expert and provide consultation to internal and external teams on Zero-Knowledge technology

What We're Looking For:

Knowledge and experience with cryptography

Knowledge and experience with Zero-Knowledge

Demonstrated experience writing well-structured, clean, maintainable code

Ability to learn new languages, APIs and SDKs quickly

Knowledge of Rust or other low-level language

Strong communication and remote friendly working skills

Bachelor’s Degree in Computer Science or related fields is a must

Familiarity with Ethereum development and related technologies (web3.js, ethers.js etc)

Familiarity with other crypto or blockchain technologies

Closing date for applications:

Contact: Jo Mount, Senior Recruiter - NEAR-Pagoda

More information: https://boards.greenhouse.io/pagoda/jobs/6736262002?gh_jid=6736262002

The Universitat Oberta de Catalunya (UOC) is a leading university of quality online education that is rooted in Catalonia and open to the world. It offers people lifelong learning to help them and society advance, while carrying out research into the knowledge society. It is the 2nd Spanish-speaking online educational institution in the world with more than 70.000 students in the academic year 2017/2018.

UOC has a research center, the Internet Interdisciplinary Institute (IN3), specialized in studying the study of the Internet and the effects of the interaction between digital technologies and human activity. Inside this research center there are 10 renowed research groups, one of them is the K-riptography and Information Security for Open Networks (KISON).

KISON is a research group focused on creating technologies for the protection of the security of networks, the information transmitted through them and the privacy of their users. The KISON group research lines focus on the compatibility of the security of decentralized networks (e.g. ad-hoc, P2P or IoT networks) and the protection of information in the Internet (especially multimedia contents) with users' rights to privacy.

We offer a two-year post-doc research position and a three-year PhD student position.

See the details at UOC website.

Closing date for applications:

Contact: Helena Rifà-Pous

More information: https://selection.uoc.edu/web/offersjob/offerdetails.aspx?offerID=90896BA916D3CDFD2D61A6285C121189E58DFA9D755F8FA3E04CC901FF357818

LIP6 and QAT teams have recently introduced several new protocols and approaches for the cryptographic verification of delegated quantum computations: - robust verification (PRX Quantum, 2021, arXiv:2109.04042) - multiparty verification (arXiv:2303.08865) - general framework for verification (arXiv:2206.00631) We are looking for a strong #phdstudent in cryptography to continue push the boundaries of what can be done to build trust in a future quantum-enabled computing environment. We are especially looking for motivated students mastering one or more of the following techniques: - composable security frameworks - post-quantum cryptography - construction of pseudo-random functions - random-oracle model Quantum mechanics fluency is not a necessity at first but can be acquired by interactions with the team. The PhD will be localized at LIP6 and Ecole normale supérieure (Paris), with opportunities to visit other research groups within Europe. Supervision will be done jointly by Elham Kashefi and Harold Ollivier. Funding is already secured. Send a CV + transcript + and motivation letter before june 30.

Closing date for applications:

Contact: Elham Kashefi (ekashefi@gmail.com) Harold Ollivier (harold.ollivier@inria.fr)

More information: https://qat.inria.fr

It all started with ECDSA nonces and keys duplications in a large amount of X.509 certificates generated by Cisco ASA security gateways, detected through TLS campaigns analysis.

After some statistics and blackbox keys recovery, it continued by analyzing multiple firmwares for those hardware devices and virtual appliances to unveil the root causes of these collisions. It ended up with keygens to recover RSA keys, ECDSA keys and signatures nonces.

The current article describes our journey understanding Cisco ASA randomness issues through years, leading to CVE-2023-20107 [CVE-2023-20107, CSCvm90511]. More generally, it also provides technical and practical feedback on what can and cannot be done regarding entropy sources in association with DRBGs and other random processing mechanisms.

In recent years, progress in practical applications of secure multi-party computation (MPC), fully homomorphic encryption (FHE), and zero-knowledge proofs (ZK) motivate people to explore symmetric-key cryptographic algorithms, as well as corresponding cryptanalysis techniques (such as differential cryptanalysis, linear cryptanalysis), over general finite fields $\mathbb{F}$ or the additive group induced by $\mathbb{F}^n$. This investigation leads to the break of some MPC/FHE/ZK-friendly symmetric-key primitives, the United States format-preserving encryption standard FF3-1 and the South-Korean standards FEA-1 and FEA-2. In this paper, we revisit linear cryptanalysis and give general results of linear approximations over arbitrary finite Abelian groups. We consider the nonlinearity, which is the maximal non-trivial linear approximation, to characterize the resistance of a function against linear cryptanalysis. The lower bound of the nonlinearity of a function $F:G\rightarrow H$ over an arbitrary finite Abelian group was first given by Pott in 2004. However, the result was restricted to the case that the size of $G$ divides the size of $H$ due to its connection to relative difference sets. We complete the generalization from $\mathbb{F}_2^n$ to finite Abelian groups and give the lower bound of $\lambda_F$ for all different cases. Our result is deduced by the new links that we established between linear cryptanalysis and differential cryptanalysis over general finite Abelian groups.

Amortized bootstrapping offers a way to refresh multiple ciphertexts of a fully homomorphic encryption scheme in parallel more efficiently than refreshing a single ciphertext at a time. Micciancio and Sorrell (ICALP 2018) first proposed the technique to bootstrap $n$ LWE ciphertexts simultaneously, reducing the total cost from $\tilde{O}(n^2)$ to $\tilde{O}(3^\epsilon n^{1+\frac{1}{\epsilon}})$ for arbitrary $\epsilon > 0$. Several recent works have further improved the asymptotic cost. Despite these amazing progresses in theoretical efficiency, none of them demonstrates the practicality of batched LWE ciphertext bootstrapping. Moreover, most of these works only support limited functional bootstrapping, i.e. only supporting the evaluation of some specific type of function when performing bootstrapping.

In this work, we propose a construction that is not only asymptotically efficient (requiring only $\tilde{O}(n)$ polynomial multiplications for bootstrapping of $n$ LWE ciphertexts) but also concretely efficient. We implement our scheme as a C++ library and show that it takes $< 5$ms per LWE ciphertext to bootstrap for a binary gate, which is an order of magnitude faster than the state-of-the-art C++ implementation on LWE ciphertext bootstrapping in OpenFHE. Furthermore, our construction supports batched arbitrary functional bootstrapping. For a 9-bit messages space, our scheme takes ${\sim}6.7$ms per LWE ciphertext to evaluate an arbitrary function with bootstrapping, which is about two to three magnitudes faster than all the existing schemes that achieve a similar functionality and message space.

In this work, we focus on maliciously secure 3PC for binary circuits with honest majority. While the state-of-the-art (Boyle et al. CCS 2019) has already achieved the same amortized communication as the best-known semi-honest protocol (Araki et al. CCS 2016), they suffer from a large computation overhead: when comparing with the best-known implementation result (Furukawa et al. Eurocrypt 2017) which requires $9\times$ communication cost of Araki et al., the protocol by Boyle et al. is around $4.5\times$ slower than that of Furukawa et al.

In this paper, we design a maliciously secure 3PC protocol that matches the same communication as Araki et al. with comparable concrete efficiency as Furukawa et al. To obtain our result, we manage to apply the distributed zero-knowledge proofs (Boneh et al. Crypto 2019) for verifying computations over $\mathbb{Z}_2$ by using \emph{prime} fields and explore the algebraic structure of prime fields to make the computation of our protocol friendly for native CPU computation.

Experiment results show that our protocol is around $3.5\times$ faster for AES circuits than Boyle et al. We also applied our protocol to the binary part (e.g. comparison and truncation) of secure deep neural network inference, and results show that we could reduce the time cost of achieving malicious security in the binary part by more than $67\%$.

Besides our main contribution, we also find a hidden security issue in many of the current probabilistic truncation protocols, which may be of independent interest.

Sampling random values from a discrete Gaussian distribution with high precision is a major and computationally intensive operation of upcoming or existing cryptographic standards. FALCON is one such algorithm that the National Institute of Standards and Technology chose to standardize as a next-generation, quantum-secure digital signature algorithm. The discrete Gaussian sampling of FALCON has both flexibility and efficiency needs—it constitutes 72% of total signature generation in reference software and requires sampling from a variable mean and standard deviation. Unfortunately, there are no prior works on accelerating this complete sampling procedure. In this paper, we propose a hardware-software co-design for accelerating FALCON’s discrete Gaussian sampling subroutine. The proposed solution handles the flexible computations for setting the variable parameters in software and executes core operations with low latency, parameterized, and custom hardware. The hardware parameterization allows trading off area vs. performance. On a Xilinx SoC FPGA Architecture, the results show that compared to the reference software, our solution can accelerate the sampling up to 9.83× and the full signature scheme by 2.7×. Moreover, we quantified that our optimized multiplier circuits can improve the throughput over a straightforward implementation by 60%.

A succinct zero knowledge proof for regular language mem- bership, i.e., to prove a secret string behind an encryption (hash) belongs to a regular language is useful, e.g., for asserting that an encrypted email is free of malware. The great challenge in practice is that the regular language used is often huge. We present zkreg, a distributed commit- and-prove system that handles such complexity. In zkreg, cryptographic operations are encoded using arithmetic circuits, and input acceptance is modeled as a zero knowledge subset problem using Σ-protocols. We in- troduce a Feedback Commit-and-Prove (FB-CP) scheme, which connects Σ-protocols and the Groth16 system with O(1) proof size and verifier cost. We present a close-to-optimal univariate instantiation of zk-VPD, a zero knowledge variation of the KZG polynomial commitment scheme, based on which an efficient zk-subset protocol is developed. We develop a 2-phase proof scheme to further exploit the locality of Aho-Corasick automata. To demonstrate the performance and scalability of zkreg, we prove that all ELF files (encrypted and hashed) in a Linux CentOS 7 are malware free. Applying inner pairing product argument, we obtain an aggregated proof of 1.96 MB which can be verified in 6.5 seconds.

We present a new, simple candidate broadcast encryption scheme for $N$ users with parameter size poly$(\log N)$. We prove security of our scheme under a non-standard variant of the LWE assumption where the distinguisher additionally receives short Gaussian pre-images, while avoiding zeroizing attacks. This yields the first candidate optimal broadcast encryption that is plausibly post-quantum secure, and enjoys a security reduction to a simple assumption. As a secondary contribution, we present a candidate ciphertext-policy attribute-based encryption (CP-ABE) scheme for circuits of a-priori bounded polynomial depth where the parameter size is independent of the circuit size, and prove security under an additional non-standard assumption.

A decade of active research has led to practical constructions of zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) that are now being used in a wide variety of applications. Despite this astonishing progress, overheads in proof generation time remain significant.

In this work, we envision a world where consumers with low computational resources can outsource the task of proof generation to a group of untrusted servers in a privacy-preserving manner. The main requirement is that these servers should be able to collectively generate proofs at a faster speed (than the consumer). Towards this goal, we introduce a framework called zk-SNARKs-as-a-service ($\mathsf{zkSaaS}$) for faster computation of zk-SNARKs. Our framework allows for distributing proof computation across multiple servers such that each server is expected to run for a shorter duration than a single prover. Moreover, the privacy of the prover's witness is ensured against any minority of colluding servers.

We design custom protocols in this framework that can be used to obtain faster runtimes for widely used zk-SNARKs, such as Groth16 [EUROCRYPT 2016], Marlin [EUROCRYPT 2020], and Plonk [EPRINT 2019]. We implement proof of concept zkSaaS for the Groth16 and Plonk provers. In comparison to generating these proofs on commodity hardware, we show that not only can we generate proofs for a larger number of constraints (without memory exhaustion), but can also get $\approx 22\times$ speed-up when run with 128 parties for $2^{25}$ constraints with Groth16 and $2^{21}$ gates with Plonk.

A fundamental result in classical cryptography is that pseudorandom generators are equivalent to one-way functions and in fact implied by nearly every classical cryptographic primitive requiring computational assumptions. In this work, we consider a variant of pseudorandom generators called quantum pseudorandom generators (QPRGs), which are quantum algorithms that (pseudo)deterministically map short random seeds to long pseudorandom strings. We provide evidence that QPRGs can be as useful as PRGs by providing cryptographic applications of QPRGs such as commitments and encryption schemes.

Our main result is showing that QPRGs can be constructed assuming the existence of logarithmic-length quantum pseudorandom states. This raises the possibility of basing QPRGs on assumptions weaker than one-way functions. We also consider quantum pseudorandom functions (QPRFs) and show that QPRFs can be based on the existence of logarithmic-length pseudorandom function-like states.

Our primary technical contribution is a method for pseudodeterministically extracting uniformly random strings from Haar-random states.

In this paper, we study oblivious key-value stores (OKVS) that enable encoding n key-value pairs into length $m$ encodings while hiding the input keys. The goal is to obtain high rate, $n/m$, with efficient encoding and decoding algorithms. We present $\mathsf{RB\text{-}OKVS}$ built on random band matrices that obtains near-optimal rates as high as 0.97 whereas prior works could only achieve rates up to 0.81 with similar encoding times.

Using $\mathsf{RB\text{-}OKVS}$, we obtain state-of-the-art protocols for private set intersection (PSI) and union (PSU). Our semi-honest PSI has up to 12% smaller communication and 13% reductions in monetary cost with slightly larger computation. We also obtain similar improvements for both malicious and circuit PSI. For PSU, our protocol obtains improvements of up to 22% in communication, 40% in computation and 21% in monetary cost. In general, we obtain the most communication- and cost-efficient protocols for all the above primitives.

Finally, we present the first connection between OKVS and volume-hiding encrypted multi-maps (VH-EMM) where the goal is to outsource storage of multi-maps while hiding the number of values associated with each key (i.e., volume). We present $\mathsf{RB\text{-}MM}$ with 16% smaller storage, 5x faster queries and 8x faster setup than prior works.

We propose $\mathcal{S}\mathfrak{ublon}\mathcal{K}-$ a new zero-knowledge succinct non-interactive argument of knowledge (zkSNARK). $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ builds on $\mathcal{P}\mathfrak{lon}\mathcal{K}$ [EPRINT'19], a popular state-of-the-art practical zkSNARK. Our new construction preserves all the great features of $\mathcal{P}\mathfrak{lon}\mathcal{K}$, i.e., it supports constant size proofs, constant time proof verification, a circuit-independent universal setup, as well as support for custom gates and lookup gates. Moreover, $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ achieves improved prover running time over $\mathcal{P}\mathfrak{lon}\mathcal{K}$. In $\mathcal{P}\mathfrak{lon}\mathcal{K}$, the prover runtime grows with circuit size. Instead, in $\mathcal{S}\mathfrak{ublon}\mathcal{K}$, the prover runtime grows with the size of the "active part" of the circuit. For instance, consider circuits encoding conditional execution, where only a fraction of the circuit is exercised by the input. For such circuits, the prover runtime in $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ grows only with the exercised execution path.

As an example, consider the zkRollup circuit. This circuit involves executing one of $n$ code segments $k$ times. For this case, using $\mathcal{P}\mathfrak{lon}\mathcal{K}$ involves proving a circuit of size $n\cdot k$ code segments. In $\mathcal{S}\mathfrak{ublon}\mathcal{K}$, the prover costs are close to proving a $\mathcal{P}\mathfrak{lon}\mathcal{K}$ proof for a circuit of size roughly $k$ code segments. Concretely, based on our implementation, for parameter choices derived from rollup contracts on Ethereum, $n =8, k = \{2^{10}\ldots 2^{16}\}$, the $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ prover is approximately $4.6\times$ faster than the $\mathcal{P}\mathfrak{lon}\mathcal{K}$ prover. Proofs in $\mathcal{S}\mathfrak{ublon}\mathcal{K}$ are 2.4KB, and can be verified in under 50ms.

We study secure multi-party computation (MPC) protocols for branching circuits that contain multiple sub-circuits (i.e., branches) and the output of the circuit is that of a single active branch. Crucially, the identity of the active branch must remain hidden from the protocol participants.

While such circuits can be securely computed by evaluating each branch and then multiplexing the output, such an approach incurs a communication cost linear in the size of the entire circuit. To alleviate this, a series of recent works have investigated the problem of reducing the communication cost of branching executions inside MPC (without relying on fully homomorphic encryption). Most notably, the stacked garbling paradigm [Heath and Kolesnikov, CRYPTO'20] yields garbled circuits for branching circuits whose size only depends on the size of the largest branch. Presently, however, it is not known how to obtain similar communication improvements for secure computation involving more than two parties.

In this work, we provide a generic framework for branching multi-party computation that supports any number of parties. The communication complexity of our scheme is proportional to the size of the largest branch and the computation is linear in the size of the entire circuit. We provide an implementation and benchmarks to demonstrate practicality of our approach.

In this paper, we pose the problem of defining technical privacy guarantees for anonymizing stories. This is a challenge that arises in practice in contexts like journalism and memoir writing, and can be crucial in determining whether a story gets told and how effectively it is presented. While recent decades have seen leaps and bounds in the development of approaches like differential privacy for numerical and categorical data sets, none of these techniques are directly applicable to settings where narrative structure is crucial to preserve. Here we begin an exploration of what kind of definitions could be achievable in such settings, and discuss the building blocks and interdisciplinary collaborations that could shape new solutions. Having scientific guarantees for anonymity in narrative forms could have far-reaching effects - in the peace of mind of potential tellers and subjects of stories, as well as in the legal sphere. This could ultimately expand the kinds of stories that can be told.

Threshold signatures are digital signature schemes in which a set of $n$ signers specify a threshold $t$ such that any subset of size $t$ is authorized to produce signatures on behalf of the group. There has recently been a renewed interest in this primitive, largely driven by the need to secure highly valuable signing keys, e.g., DNSSEC keys or keys protecting digital wallets in the cryptocurrency ecosystem. Of special interest is FROST, a practical Schnorr threshold signature scheme, which is currently undergoing standardization in the IETF and whose security was recently analyzed at CRYPTO'22.

We continue this line of research by focusing on FROST's unforgeability combined with a practical distributed key generation (DKG) algorithm. Existing proofs of this setup either use non-standard heuristics, idealized group models like the AGM, or idealized key generation. Moreover, existing proofs do not consider all practical relevant optimizations that have been proposed. We close this gap between theory and practice by presenting the Schnorr threshold signature scheme Olaf, which combines the most efficient known FROST variant FROST3 with a variant of Pedersen's DKG protocol (as commonly used for FROST), and prove its unforgeability. Our proof relies on the AOMDL assumption (a weaker and falsifiable variant of the OMDL assumption) and, like proofs of regular Schnorr signatures, on the random oracle model.

Hybrid post-quantum cryptography is a cautious approach that aims to guard against the threat posed by the quantum computer, through the simultaneous use of Post- Quantum (PQ) and classical (i.e. pre-quantum) cryptosystems, in case the post-quantum schemes used would turn out to be insecure.

Regarding the hybridization of Key Encapsulation Mechanisms (KEMs), most recent studies focus on how to safely combine the symmetric keys output by a parallel execution of classical and post-quantum KEMs. As simple as this architecture is, it however appears not to be the most efficient, computationally speaking as well as regarding the bandwidth of the exchanges.

Hence, we propose a new method to hybridize several KEMs more effectively, by combining the underlying Public Key Encryption schemes (PKEs) in an innovative variant of the cas- cade composition that we call "leaking-cascade". We prove that this architecture constitutes an IND-CPA-secure robust combiner for the encryption schemes, which permits to create an IND-CCA2 KEM upon the generated hybrid PKE. The leaking-cascade is at least as computationally effective as the commonly used parallel combination, and has a bandwidth gain - when it comes to the ciphertext produced - that may exceed 13 % compared to the latter.

Non-Interactive Zero-Knowledge proofs (NIZK) allow a prover to convince a verifier that a statement is true by sending only one message and without conveying any other information. In the CRS model, many instantiations have been proposed from group-theoretic assumptions. On the one hand, some of these constructions use the group structure in a black-box way but rely on pairings, an example being the celebrated Groth-Sahai proof system. On the other hand, a recent line of research realized NIZKs from sub-exponential DDH in pairing-free groups using Correlation Intractable Hash functions, but at the price of making non black-box usage of the group.

As of today no construction is known to simultaneously reduce its security to pairing-free group problems and to use the underlying group in a black-box way.

This is indeed not a coincidence: in this paper, we prove that for a large class of NIZK either a pairing-free group is used non black-box by relying on element representation, or security reduces to external hardness assumptions. More specifically our impossibility applies to two incomparable cases. The first one covers Arguments of Knowledge (AoK) which proves that a preimage under a given one way function is known. The second one covers NIZK (not necessarily AoK) for hard subset problems, which captures relations such as DDH, Decision-Linear and Matrix-DDH.