International Association
for Cryptologic Research

Event date: 9 September to 13 September 2024
Submission deadline: 15 March 2024

Event date: 17 September to 19 September 2024
Submission deadline: 16 April 2024
Notification: 20 June 2024

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

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

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

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

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

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

Closing date for applications:

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

More information: https://smrtr.io/hmG3C

The Young Investigator Group “COSYS - Control Systems and Cyber Security Lab” at the Chair of IT Security at the Brandenburg University of Technology Cottbus-Senftenberg has an open PhD/Postdoc position in the following areas:

• Privacy-Enhancing Technologies in Cyber-Physical Systems.
• AI-based Network Attack Detection and Simulation.
• AI-enabled Penetration Testing.

The available position is funded as 100% TV-L E13 tariff in Germany and limited until 31.07.2026, with possibility for extension. Candidates must hold a Master’s degree (PhD degree for Postdocs) or equivalent in Computer Science or related disciplines, or be close to completing it. If you are interested, please send your CV, transcript of records from your Master studies, and an electronic version of your Master's thesis (if possible), as a single pdf file. Applications will be reviewed until the position is filled.

Closing date for applications:

Contact: Ivan Pryvalov (ivan.pryvalov@b-tu.de)

The successful candidate will contribute to the formal security specification and design of cryptographic protocols in the Open Finance area. In Open Finance we envision multiple entities, each holding private data, that want to perform joint computation over this data to offer to customers the best possible financial products. The main goal of the project is to investigate what are the security requirements for Open Finance, and then provide a formal security specification (e.g., in the Universal Composable framework) of such a system. The successful candidate will then work on designing a protocol that matches this security definition, and in the final stage of the project, will implement part of the system, focusing on a specific use case. The candidate will be supported by members of the Business School to successfully complete the first phase of the project related to understanding the basic security requirements of an Open Finance system. The majority of the project will be related to the formal design of the system that will be supported by members of the School of Informatics. The project is funded by Input-Output Global. Candidates must have a Ph.D. (or nearing completion) in cryptography or related fields. Evidence of strong research experience as demonstrated through publications at top-tier conferences or high-impact journals is essential. We are looking for a highly motivated candidate with strong initiative and commitment to excellence, and an ability to conduct world-class research. The successful candidate will have the opportunity to work remotely if they require that (as long as they are in the UK). For more info, we refer to the application page. Application deadline 12/03/2024, 23:59GMT

Closing date for applications:

Contact: Michele Ciampi michele.ciampi@ed.ac.uk

More information: https://elxw.fa.em3.oraclecloud.com/hcmUI/CandidateExperience/en/sites/CX_1001/job/9810

We present a new post-quantum Public Key Encryption scheme (PKE) named Supersingular Isogeny Lollipop Based Encryption or SILBE. SILBE is obtained by leveraging the generalized lollipop attack of Castryck and Vercauteren on the M-SIDH Key exchange by Fouotsa, Moriya and Petit. Doing so, we can in fact make of SILBE a post-quantum secure Updatable Public Key Encryption scheme (UPKE). SILBE is the first isogeny-based UPKE which is not based on group actions. In its core, SILBE extensively uses both the Deuring Correspondence and Kani's Lemma, two central concepts in Isogeny-Based Cryptography.

While classic result in the 1980s establish that one-way functions (OWFs) imply the existence of pseudorandom generators (PRGs) which in turn imply pseudorandom functions (PRFs), the constructions (most notably the one from OWFs to PRGs) is complicated and inefficient.

Consequently, researchers have developed alternative \emph{direct} constructions of PRFs from various different concrete hardness assumptions. In this work, we continue this thread of work and demonstrate the first direct constructions of PRFs from average-case hardness of the time-bounded Kolmogorov complexity problem $\mktp[s]$, where given a threshold, $s(\cdot)$, and a polynomial time-bound, $t(\cdot)$, $\mktp[s]$ denotes the language consisting of strings $x$ with $t$-bounded Kolmogorov complexity, $K^t(x)$, bounded by $s(|x|)$.

In more detail, we demonstrate a direct PRF construction with quasi-polynomial security from mild average-case of hardness of $\mktp[2^{O(\sqrt{\log n})}]$ w.r.t the uniform distribution. We note that by earlier results, this assumption is known to be equivalent to the existence of quasi-polynomially secure OWFs; as such, our results yield the first direct (quasi-polynomially secure) PRF constructions from a natural hardness assumptions that also is known to be implied by (quasi-polynomially secure) PRFs.

Perhaps surprisingly, we show how to make use of the Nisan-Wigderson PRG construction to get a cryptographic, as opposed to a complexity-theoretic, PRG.

The Fiat-Shamir transform [1] is a well-known and widely employed technique for converting sound public-coin interactive protocols into sound non-interactive protocols. Even though the transformation itself is relatively clear and simple, some implementations choose to deviate from the specifications, for example for performance reasons. In this short note, we present a vulnerability arising from such a deviation in a KZG-based PLONK verifier implementation. This deviation stemmed from the incorrect computation of the last challenge of the PLONK protocol [2], where the KZG batching proof challenge was computed before, and, hence, independently from the KZG evaluation proofs. More generally, such a vulnerability may affect any KZG [3] implementation where one uses batched KZG proof evaluations for at least two distinct evaluation points. We call an attack enabled by such a deviation a Last Challenge Attack. For concreteness, we show that when a PLONK verifier implementation presents such a deviation, a malicious PLONK prover can mount a Last Challenge Attack to construct verifiable proofs of false statements. The described vulnerability was initially discovered as part of an audit, and has been responsibly disclosed to the developers and fixed. A proof of concept of the vulnerability, in which a proof is forged for an arbitrary public input, is made available.

In addition to the above, in this work we also provide a security proof of the knowledge-soundness of the batched KZG scheme with evaluations for at least two distinct values.

Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF, which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the Paillier encryption scheme (both in the random-oracle model). We then show that an eVRF can be used to solve several long-standing open problems in threshold cryptography. In particular, we construct (1) a one-round fully simulatable distributed key-generation protocols (after a single two-round initialization phase), (2) a two-round fully simulatable signing protocols for multiparty Schnorr with a deterministic variant, (3) a two-party ECDSA protocol that has a deterministic variant, (4) a threshold Schnorr signing where the parties can later prove that they signed without being able to frame another group, (5) an MPC-friendly and verifiable HD-derivation. Efficient simulatable protocols of this round complexity were not known prior to this work. All of our protocols are concretely efficient.

The possible effects of irradiation on security controllers implemented in CMOS technology are studied. First, the decrease of the effectiveness of a light sensor/detector as countermeasure against laser fault injection is analysed. Second, the use of irradiation as fault injection method is proposed.

Proofs of Liabilities (PoL) allow an untrusted prover to commit to its liabilities towards a set of users and then prove independent users' amounts or the total sum of liabilities, upon queries by users or third-party auditors. This application setting is highly dynamic. User liabilities may increase/decrease arbitrarily and the prover needs to update proofs in epoch increments (e.g., once a day for a crypto-asset exchange platform). However, prior works mostly focus on the static case and trivial extensions to the dynamic setting open the system to windows of opportunity for the prover to under-report its liabilities and rectify its books in time for the next check, unless all users check their liabilities at all epochs. In this work, we develop Notus, the first dynamic PoL system for general liability updates that avoids this issue. Moreover, it achieves $O(1)$ query proof size, verification time, and auditor overhead-per-epoch. The core building blocks underlying Notus are a novel zero-knowledge (and SNARK-friendly) RSA accumulator and a corresponding zero-knowledge MultiSwap protocol, which may be of independent interest. We then propose optimizations to reduce the prover's update overhead and make Notus scale to large numbers of users ($10^6$ in our experiments). Our results are very encouraging, e.g., it takes less than $2$ms to verify a user's liability and the proof size is $256$ Bytes. On the prover side, deploying Notus on a cloud-based testbed with eight 32-core machines and exploiting parallelism, it takes ${\sim}3$ minutes to perform the complete epoch update, after which all proofs have already been computed.

Confidentiality and authentication are two main security goals in secure electronic mail (e-mail). Furthermore, deniability is also a significant security property for some e-mail applications to protect the privacy of the sender. Although searchable encryption solves the keyword searching problem in a secure e-mail system, it also breaks the deniability of the system. Because the adversary can obtain the information of the data sender and data user from the trapdoor as well as ciphertext used for keyword searching. At the same time, efficiency is another problem in mobile computing. To overcome the issues, we put forward deniably authenticated searchable public key encryption (DA-SPKE) which can apply to the deniable e-mail system. We first define the DA-SPKE model and propose the DA-SPKE scheme. Then we prove its security in the random oracle model and evaluate its efficiency. Finally, we use it in a deniably secure e-mail system to protect both data senders’ and data users' privacy.

As post-quantum cryptography transitions toward practical deployment, the significance of extensive cryptanalysis is on the rise. Three out of the four NIST-PQC round 4 candidates are forms of code-based cryptography. Analyses of asymptotic complexity in information set decoding (ISD) algorithms have been a central focus in the field of code-based cryptography. Recently, Esser, May and Zweydinger (Eurocrypt '22) demonstrate the practicality of the May--Meurer--Thomae (MMT) algorithm by decoding McEliece-1284. Esser and Zweydinger (Eurocrypt '23) propose the time-memory trade-off variant of Becker--Joux--May--Meurer (BJMM) decoding, which solves QC-3138. These works have paved the way for the cryptanalysis of ISD in real-world scenarios.

In this work, we further advance the progress of the abovementioned studies by performing a concrete analysis of MMT decoding. We improve the list construction in MMT so that the number of both candidates and representations in the enumeration phase is increased without the need for additional time and memory. Our new algorithm is theoretically 5.1 times faster than the BJMM algorithm for Classic McEliece I instance. We achieve the minimum time complexity across all categories of Classic McEliece among all ISD algorithms. Moreover, compared with the BJMM algorithm, our MMT algorithm reduces the bit security by 1 to 3 bits for all code based NIST-PQC round 4 candidates. Practical security estimates confirm that all the candidates have sufficiently strong bit security, except for Classic McEliece III, with a 1-bit deficiency.

In addition, we implement our new MMT algorithm in a GPU environment and provide the new record of the McEliece-1409 instance, along with implementation details and experimental analyses. Our study verifies the practical reliability of the code-based candidates against current ISD algorithms.

This paper presents a heuristic ideal obfuscation scheme based on the learning problem, which di ers from that of Jain, Lin, and Luo [JLLW23]. The paper adopts a method similar to Brakerski, Dottling, Garg, and Malavolta [BDGM22, BDGM20] for constructing iO. It first introduces a variant of the LWR problem and proves its pseudorandomness. Based on the variant of the LWR problem, it constructs LHE, then combines it with sFHE constructed from the LWE problem to further construct the ideal obfuscation scheme. In comparison to the approach by Jain et al., this paper is relatively more specific. Additionally, the paper incorporates the quantum random oracle construction by Jelle Don, et al.[DFMS22] to provide a more concrete quantum random oracle used in the proposed obfuscation scheme.

In this work we consider the task of designing information-theoretic MPC protocols for which the state of a given party can be recovered from a small amount of parties, a property we refer to as local repairability. This is useful when considering MPC over dynamic settings where parties leave and join a computation, a scenario that has gained notable attention in recent literature. Thanks to the results of (Cramer et al. EUROCRYPT'00), designing such protocols boils down to constructing a linear secret-sharing scheme (LSSS) with good locality, that is, each share is determined by only a small amount of other shares, that also satisfies the so-called multiplicativity property. Previous constructions that achieve locality (e.g. using locally recoverable codes---LRCs) do not enjoy multiplicativity, and LSSS that are multiplicative (e.g. Shamir's secret-sharing) do not satisfy locality. Our construction bridges this literature gap by showing the existence of an LSSS that achieves both properties simultaneously.

Our results are obtained by making use of well known connection between error correcting codes and LSSS, in order to adapt the LRC construction by (Tamo & Barg, IEEE Transactions on Information Theory 2014) to turn it into a LSSS. With enough care, such coding-theoretic construction yields our desired locality property, but it falls short at satisfying multiplicativity. In order to address this, we perform an extensive analysis of the privacy properties of our scheme in order to identify parameter regimes where our construction satisfies multiplicativity.

Finally, since our LSSS satisfies locality, every share is determined by a small amount of shares. However, in an MPC context it is not enough to let the (small set of) parties to send their shares to the repaired party, since this may leak more information than the regenerated share. To obtain our final result regarding MPC with local repairability, we construct a lightweight MPC protocol that performs such repairing process without any leakage. We provide both a passively secure construction (for the plain multiplicative regime) and an actively secure one (for strong multiplicativity).

We present STIR (Shift To Improve Rate), an interactive oracle proof of proximity (IOPP) for Reed-Solomon codes that achieves the best known query complexity of any concretely efficient IOPP for this problem. For $\lambda$ bits of security, STIR has query complexity $O(\log d + \lambda \cdot \log \log d )$, while FRI, a popular protocol, has query complexity $O(\lambda \cdot \log d )$ (including variants of FRI based on conjectured security assumptions). STIR relies on a new technique for recursively improving the rate of the tested Reed-Solomon code.

We provide an implementation of STIR compiled to a SNARK. Compared to a highly-optimized implementation of FRI, STIR achieves an improvement in argument size that ranges from $1.25\times$ to $2.46\times$ depending on the chosen parameters, with similar prover and verifier running times. For example, in order to achieve 128 bits of security for degree $2^{26}$ and rate $1/4$, STIR has argument size $114$ KiB, compared to $211$ KiB for FRI.

Garbling schemes are one of the most fundamental objects in cryptography and have been studied extensively due to their broad applicability. The state-of-the-art is a construction in which XOR gates are free and AND gates require $3\kappa/2+\mathcal{O}(1)$ bits per gate, due to Rosulek and Roy (CRYPTO'21). An important technique in their garbling is slicing, which partitions the labels into two equal-length slices. In this paper, we explore the feasibility of the slicing technique for garbling schemes beyond the results introduced by Rosulek and Roy, demonstrating both its potential and its limitations.

In particular, we extend this technique to demonstrate the garbling of certain higher fan-in gadgets, and then use this to show that it is possible to garble 2-input AND gates at a cost of $4\kappa/3 +\mathcal{O}(1)$ bits. We then give a separation result showing that sliced garbling cannot be used to garble higher fan-in gadgets of degree $\geq 3$ when restricted to making queries that are linear functions of the input labels to the random oracle. We further demonstrate the usefulness of our techniques in the context of oblivious garbling, a newly introduced concept for capturing circuit hiding from the garbler. The complexity of our construction is superior to that of universal circuits, and grows linearly with circuit size.

In this work, we present two generic frameworks for leakage-resilient attribute-based encryption (ABE), which is an improved version of ABE that can be proven secure even when part of the secret key is leaked. Our frameworks rely on the standard assumption ($k$-Lin) over prime-order groups. The first framework is designed for leakage-resilient ABE with attribute-hiding in the bounded leakage model. Prior to this work, no one had yet derived a generic leakage-resilient ABE framework with attribute-hiding. The second framework provides a generic method to construct leakage-resilient ABE in the continual leakage model. It is compatible with Zhang et al.'s work [DCC 2018] but more generic. Concretely, Zhang et al.'s framework cannot act on some specific ABE schemes while ours manages to do that. Technically, our frameworks are built on the predicate encoding of Chen et al.'s [EUROCRYPT 2015] combined with a method of adding redundancy. At last, several instantiations are derived from our frameworks, which cover the cases of zero inner-product predicate and non-zero inner-product predicate.

Zero-knowledge virtual machine (zkVM) is a novel applica- tion of succinct and non-interactive zero-knowledge proof protocols that allows for verifiable computation over arbitrary codes. In this paper, we present a new paradigm to build such a zkVM via data parallel circuits. Our parallelization happens at the opcode and the basic block level. Such a design allows us to eliminate almost all of the circuit overhead for opcodes, including the control flow and the data flow which can be substantial in a zero-knowledge circuit. The size of our circuit is dynamic and optimal in the sense that it only costs the sum of all individual op- codes that are executed in the program, (i.e., you only pay as much as you use); while in all previous designs, the circuit is of a constant size, de- termined by the product of a) the upper limit of the number of opcodes, and b) the size of a super opcode circuit that is capable of handling every type of opcode. Further, we present an asymmetric GKR prover that is tailored to the data parallelism in our zkVM design, accompanied by various optimized constraint gadgets. The use of GKR prover also leads to significant re- ductions in the number of witnesses that are to be committed: GKR allows us to commit only the input and output of the circuits, whereas in previous Plonkish-based solutions, the prover needs to commit to all the witnesses

In this work, we present novel protocols over rings for semi-honest secure three-party computation (3-PC) and malicious four-party computation (4-PC) with one corruption. Compared to state-of-the-art protocols in the same setting, our protocols require fewer low-latency and high-bandwidth links between the parties to achieve high throughput. Our protocols also reduce the computational complexity by requiring up to 50 percent fewer basic instructions per gate. Further, our protocols achieve the currently best-known communication complexity (3, resp. 5 elements per multiplication gate) with an optional preprocessing phase to reduce the communication complexity of the online phase to 2 (resp. 3) elements per multiplication gate. In homogeneous network settings, i.e. all links between the parties share similar network bandwidth and latency, our protocols achieve up to two times higher throughput than state-of-the-art protocols. In heterogeneous network settings, i.e. all links between the parties share different network bandwidth and latency, our protocols achieve even larger performance improvements. We implemented our protocols and multiple other state-of-the-art protocols (Replicated 3-PC, Astra, Fantastic Four, Tetrad) in a novel open-source C++ framework optimized for achieving high throughput. Five out of six implemented 3-PC and 4-PC protocols achieve more than one billion 32-bit multiplication or more than 32 billion AND gates per second using our implementation in a 25 Gbit/s LAN environment. This is the highest throughput achieved in 3-PC and 4-PC so far and between two and three orders of magnitude higher than the throughput MP-SPDZ achieves in the same settings.