International Association
for Cryptologic Research

Two postdoc positions in the research group of Julian Loss at CISPA Helmholtz Center for Information Security in Saarbrücken, Germany. The positions are for two years, funded by ERC project CRYPTOSYSTEMS.

Our research focuses on cryptography and its applications to distributed computing, e.g., making consensus and blockchain protocols more secure and scalable.

The candidate should have a strong background in cryptography or distributed computing.

Closing date for applications:

Contact: Julian Loss

More information: https://www.julianloss.com

Event date: 2 December to 6 December 2024

PRESENT is an ultra-lightweight block cipher designed by Bogdanov et al., and has been widely studied since its proposal. It supports 80-bit and 128-bit keys, which are referred as PRESENT-80 and PRESENT-128, respectively. Up to now, linear cryptanalysis is the most effective method on attacking this cipher, especially when accelerated with the pruned Walsh transform. Combing pruned Walsh transform with multiple linear attacks, one can recover the right key for 28-round PRESENT-80 and -128. Later, this method is further improved with affine pruned Walsh transform by adding more zeros in the Walsh spectrum through rejecting some data. This leads to the 29-round attack on PRESENT-128 with full codebook.

In this paper, we follow the affine pruned Walsh transform accelerated linear method, and propose 29-round attacks on both PRESENT-80 and PRESENT-128 without using full codebook. Both attacks rely on a statistical model depicting distributions of the experimental correlation when some data are artificially rejected in its computation. Besides, detailed analysis of complexity reduction for each linear hull used in attacking PRESENT is also provided and supported by an automatic tool. Our 29-round attack on PRESENT-80 mainly benefits from this tool. According to our knowledge, both attacks are the best ones on PRESENT so far.

In July 2022, the US National Institute for Standards and Technology (NIST) announced the first set of Post-Quantum Cryptography standards: Kyber, Dilithium, Falcon, and SPHINCS+. Shortly after, NIST published a call for proposals for additional post-quantum signature schemes to complement their initial portfolio. In 2023, 50 submissions were received, and 40 were accepted as round-1 candidates for future standardization. In this paper, we study the suitability and performance of said candidates on the popular Arm Cortex-M4microcontroller. We integrate the suitable implementations into the benchmarking framework pqm4 and provide benchmarking results on the STM32L4R5ZI featuring 640 KB of RAM. pqm4 currently includes reference implementations for 15 submissions and M4-optimized implementations for five submissions. For the remaining candidates, we describe the reasons that hinder integration - the predominant reason being large key size or excessive memory consumption. While the performance of reference implementations is rather meaningless and often does not correlate with the performance of well-optimized implementations, this work provides some first indication of which schemes are most promising on microcontrollers. The publicly available implementations in pqm4 also provide a good starting point for future optimization efforts. Initially, we were hoping for a much higher code quality than for initial submissions to NIST's previous PQC project. However, we got grossly disappointed: Half of the submissions make use of dynamic memory allocations, often completely without reason; Many implementations have compiler warnings, sometimes hinting at more serious issues; Many implementations do not pass simple sanitizer tests such as using valgrind; Multiple implementations make use of static memory.

Post-Quantum Cryptography (PQC) was proposed due to the potential threats quantum computer attacks against conventional public key cryptosystems, and four PQC algorithms besides CRYSTALS-Dilithium (Dilithium for short) have so far been selected for NIST standardization. However, the selected algorithms are still vulnerable to side-channel attacks in practice, and their physical security need to be further evaluated. This study introduces two efficient power analysis attacks, the optimized fast two-stage approach and the single-bit approach, aimed at reducing the key guess space in NTT polynomial multiplication on an STM32F405 device (ARM Cortex-M4 core). Our findings reveal that the optimized approach outperforms the conservative approach and the fast two-stage approach proposed in ICCD 2021 by factors of 519 and 88, respectively. Similarly, the single-bit approach demonstrates speedups of 365 and 62 times compared to these two approaches, respectively.

SNOVA is a variant of a UOV-type signature scheme over a noncommutative ring. In this article, we demonstrate that certain parameters provided by authors in SNOVA fail to meet the NIST security level, and the complexities are lower than those claimed by SNOVA.

Bootstrapping is a key operation in fully homomorphic encryption schemes that enables the evaluation of arbitrary multiplicative depth circuits. In the BFV scheme, bootstrapping corresponds to reducing the size of accumulated noise in lower bits while preserving the plaintext in the upper bits. The previous instantiation of BFV bootstrapping is achieved through the digit extraction procedure. However, its performance is highly dependent on the plaintext modulus, so only a limited form of the plaintext modulus, a power of a small prime number, was used for the efficiency of bootstrapping.

In this paper, we present a novel approach to instantiate BFV bootstrapping, distinct from the previous digit extraction-based method. The core idea of our bootstrapping is to utilize CKKS bootstrapping as a subroutine, so the performance of our method mainly depends on the underlying CKKS bootstrapping rather than the plaintext modulus.

We implement our method at a proof-of-concept level to provide concrete benchmark results. When performing the bootstrapping operation for a 51-bits plaintext modulus, our method improves the previous digit extraction-based method by a factor of 37.9 in latency and 29.4 in throughput. Additionally, we achieve viable bootstrapping performance for large plaintext moduli, such as 144-bits and 234-bits, which has never been measured before.

Most multivariate proof systems require, at some point, an algebraic check against the rows of the trace. One popular protocol for this is known as zerocheck which is a sumcheck based protocol which proves a constraint function is zero over the $n$-dimensional Boolean hypercube. One of the drawbacks of running zerocheck over a small field, is that it usually involves a large number of evaluations of the constraint polynomial over a cryptographically large extension field $\mathbb{G}$.

We describe several improvements to the zerocheck protocol over a small field $\mathbb{F}$ which both reduce the number of constraint evaluations the prover needs to perform and shifts some computation from the extension field back into the base field $\mathbb{F}$. Specifically, for a table of length $2^n$, integer parameter $1\leq k \leq n$ and constraint function $C$ of degree $d$ with evaluation costs $C_{\mathbb{F}}, C_{\mathbb{G}}$ we show the protocol can be performed with prover cost roughly \[ 2^n\left(1 + \frac{C_{\mathbb{G}}}{2^k C_{\mathbb{F}}}\right)(d - 1)C_{\mathbb{F}}. \] To check the proof, the verifier needs to perform a single interpolation of degree $2^kd$ and $n$ interpolations of degree $d$. Thus varying $k$ allows for a tradeoff between prover and verifier cost.

Key Transparency (KT) systems enable service providers of end-to-end encrypted communication (E2EE) platforms to maintain a Verifiable Key Directory (VKD) that maps each user's identifier, such as a username or email address, to their identity public key(s). Users periodically monitor the directory to ensure their own identifier maps to the correct keys, thus detecting any attempt to register a fake key on their behalf to Meddler-in-the-Middle (MitM) their communications. We introduce and formalize a new primitive called Multi-Device Verifiable Key Directory (MVKD), which strengthens both the security, privacy, and usability guarantees of VKD by leveraging the multi-device setting. We formalize three properties for a MVKD (completeness, extraction-based soundness, and privacy), striking a non-trivial balance between strong guarantees and the limitations imposed by a truly practical system. We then present a new MVKD system called ELEKTRA. This system combines the core of the Keybase KT system (running in production since 2014) with ideas from SEEMless (Chase et. al., 2019) and RZKS (Chen et. al., 2022). Our construction is the first to achieve the above multi-device guarantees while having formal security and privacy proofs. Finally, we implement ELEKTRA and present benchmarks demonstrating its practicality.

Recommender systems are effective mechanisms for recommendations about what to watch, read, or taste based on user ratings about experienced products or services. To achieve higher quality recommendations, e-commerce parties may prefer to collaborate over partitioned data. Due to privacy issues, they might hesitate to work in pairs and some solutions motivate them to collaborate. This study examines how to estimate trust-based predictions on arbitrarily partitioned data in which two parties have ratings for similar sets of customers and items. A privacy- preserving scheme is proposed, and it is justified that it efficiently offers trust-based predictions on partitioned data while preserving privacy.

SAT, SMT, MILP, and CP, have become prominent in the differential cryptanalysis of cryptographic primitives. In this paper, we review the techniques for constructing differential characteristic search models in these four formalisms. Additionally, we perform a systematic comparison encompassing over 20 cryptographic primitives and 16 solvers, on both easy and hard instances of optimisation, enumeration and differential probability estimation problems.

Private Set Intersection (PSI) is a widely used protocol that enables two parties to securely compute a function over the intersected part of their shared datasets and has been a significant research focus over the years. However, recent studies have highlighted its vulnerability to Set Membership Inference Attacks (SMIA), where an adversary might deduce an individual's membership by invoking multiple PSI protocols. This presents a considerable risk, even in the most stringent versions of PSI, which only return the cardinality of the intersection. This paper explores the evaluation of anonymity within the PSI context. Initially, we highlight the reasons why existing works fall short in measuring privacy leakage, and subsequently propose two attack strategies that address these deficiencies. Furthermore, we provide theoretical guarantees on the performance of our proposed methods. In addition to these, we illustrate how the integration of auxiliary information, such as the sum of payloads associated with members of the intersection (PSI-SUM), can enhance attack efficiency. We conducted a comprehensive performance evaluation of various attack strategies proposed utilizing two real datasets. Our findings indicate that the methods we propose markedly enhance attack efficiency when contrasted with previous research endeavors. The effective attacking implies that depending solely on existing PSI protocols may not provide an adequate level of privacy assurance. It is recommended to combine privacy-enhancing technologies synergistically to enhance privacy protection even further.

A cipher scheme related to ChaCha with the variation of using 64 bit operations instead of 32 bits, and the same 512 bit state size, is presented. We will provide strong argumentation to assert that the same security of ChaCha can be obtained with half number of instructions for the same number of 20 rounds. Also, an strategy to implement this cipher on SIMD extensions is presented, with a maximal throughput of about 3.37 bytes per cycle on a 256 bit SIMD extension with at least 11 vector registers.

Laconic cryptography enables secure two-party computation (2PC) on unbalanced inputs with asymptotically-optimal communication in just two rounds of communication. In particular, the receiver (who sends the first-round message) holds a long input and the sender (who sends the second-round message) holds a short input, and the size of their communication to securely compute a function on their joint inputs only grows with the size of the sender's input and is independent of the receiver's input size. The work on laconic oblivious transfer (OT) [Cho et al. CRYPTO 2017] and laconic private set intersection (PSI) [Alamati et al. TCC 2021] shows how to achieve secure laconic computation for OT and PSI from the Diffie-Hellman assumption.

In this work, we push the limits further and achieve laconic branching programs from the Diffie-Hellman assumption. In particular, the receiver holds a large branching program $P$ and the sender holds a short input $x$. We present a two-round 2PC protocol that allows the receiver to learn $x$ iff $P(x) =1$, and nothing else. The communication only grows with the size of $x$ and the depth of $P$, and does not further depend on the size of $P$.

In a seminal work, Ishai et al. (FOCS–2006) studied the viability of designing unconditionally secure protocols for key agreement and secure multi-party computation (MPC) using an anonymous bulletin board (ABB) as a building block. While their results establish the feasibility of key agreement and honest-majority MPC in the ABB model, the optimality of protocols with respect to their round and communication complexity is not studied. This paper enriches this study of unconditional security in the ABB model in multiple ways.

- We present a key agreement protocol with a novel combinatorial insight to offer a 200% throughput over the (FOCS–2006) study; i.e., using the same number of messages, we can (almost) double the bit-length of the agreed key. We also prove the near optimality of our approach.

- We offer unconditionally secure protocols for the (random) string oblivious transfer functionalities. We present a $1$-round chosen message random string oblivious transfer and show how to extend it to a non-interactive (random) string oblivious transfer protocol and a $2$-round chosen message string oblivious transfer.

- We prove a $1$-round lower bound for BEC under certain conditions.

Central to our technical contributions is the abstraction of a distributional variant of the random ABB functionality. Investigating the concrete efficiency of founding MPC from this primitive leads to fascinating new mathematical challenges in well-established MPC models, which will be of broader interest to the community.

Despite decades of effort, a stubborn chasm exists between the theory and practice of device-level biometric authentication. Deployed authentication algorithms rely on data that leaks private information about the biometric; thus systems rely on externalized security measures such as trusted execution environments. In particular, the authentication algorithms themselves provide no cryptographic security guarantees.

This is particularly frustrating given the long line of research that has developed theoretical tools---known as fuzzy extractors---that enable secure, privacy preserving biometric authentication with public enrollment data. Unfortunately, the best known constructions involving these rigorous tools can only provide substantial true accept rates with an estimated security of $32$ bits for the iris (Simhadri et al., ISC 2019) and 45 bits for the face (Zhang, Cui, and Yu, ePrint 2021/1559).

This work introduces FiveEyes, an iris key derivation system that integrates an improved feature extractor with a fuzzy extractor that leverages a new mechanism, which we formally analyze, for selecting verification subsets based on statistics of the iris. (These statistics are computed from a class disjoint dataset from our test set.) We present various parameter regimes in order to highlight different true accept rates: 1. $65$ bits of security (equivalent to $87$ bits with a password) at $12\%$ true accept rate, and 2. $50$ bits of security (equivalent to $72$ bits with a password) at $45\%$ true accept rate. We remark that powerful techniques are known that amplify true accept rates (Davida et al., IEEE S&P 1998); in particular, for the first time these results indicate practical viability of biometric authentication with strongcryptographic security.

The use of zero-knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK) and similar types of proofs has become increasingly popular as a solution for improving scalability, privacy, and interoperability of blockchain systems. However, even with the most advanced proving systems, verifying a single SNARK proof can require a significant amount of computational resources making it expensive to be performed on-chain. This becomes a noticeable bottleneck in scaling SNARK-based applications.

Further efficiency improvement to avoid this bottleneck lies in utilizing distributed recursive proof composition to aggregate multiple existing proofs into one that verifies all underlying proofs.

Building upon this concept, we present a new protocol for decentralized recursive proof aggregation allowing one unique proof to aggregate many input proofs to be efficiently verified on-chain, increasing the throughput and cost efficiency of SNARK-based blockchains. The protocol is designed for decentralized environments where independent actors (provers) can join and contribute to the proof generation process. We also present an incentive scheme for such actors. The protocol is abstract enough to be used with a variety of proving systems that support recursive aggregation.

Event date: 16 December to 20 December 2024
Submission deadline: 10 July 2024
Notification: 10 September 2024

The Security and Privacy Research Unit at TU Wien is offering a fully funded PhD position under the supervision of Dr. Zeta (Georgia) Avarikioti and Univ.-Prof. Dr. Matteo Maffei. If you are interested, please apply at https://tools.spycode.at/recruiting/call/4.

Closing date for applications:

Contact: Zeta Avarikioti and Mattero Maffei

More information: https://tools.spycode.at/recruiting/call/4

We are looking for motivated postdoctoral candidates with experience using zero-knowledge proofs in cutting edge applications and hardware acceleration. The candidate will be working with the Adaptive Computing and Embedded Systems (ACES) Lab at UC San Diego, led by Farinaz Koushanfar. In particular, the student will be working on incorporating zero-knowledge proofs into emerging learning paradigms. Alongside this, the candidate should have experience with GPU/FPGA acceleration, as they will be collaborating with senior PhD students to build an end-to-end zero-knowledge proof accelerator. This position is fully-funded.

Requirements:

• Ph.D. in Computer Engineering, Computer Science, or a closely related field
• Strong ability in at least C/C++ or Rust
• Familiarity with popular open-source zero-knowledge proof frameworks
• Publication record in top venues, with proven research record around zero-knowledge proofs
• Strong theoretical understanding of zero-knowledge proofs and its various constructions
• Ability to work on-site in San Diego

To apply, please send your CV to Farinaz Koushanfar at the email: [email protected]

Closing date for applications:

Contact: Farinaz Koushanfar ([email protected])