International Association
for Cryptologic Research

The computation of step functions over encrypted data is an essential issue in homomorphic encryption due to its fundamental application in privacy-preserving computing. However, an effective method for homomorphically computing general step functions remains elusive in cryptography. This paper proposes two polynomial approximation methods for general step functions to tackle this problem. The first method leverages the fact that any step function can be expressed as a linear combination of shifted sign functions. This connection enables the homomorphic evaluation of any step function using known polynomial approximations of the sign function. The second method boosts computational efficiency by employing a composite polynomial approximation strategy. We present a systematic approach to construct a composite polynomial $f_k \circ f_{k-1} \circ \cdots \circ f_1$ that increasingly approximates the step function as $k$ increases. This method utilizes an adaptive linear programming approach that we developed to optimize the approximation effect of $f_i$ while maintaining the degree and coefficients bounded. We demonstrate the effectiveness of these two methods by applying them to typical step functions such as the round function and encrypted data bucketing, implemented in the HEAAN homomorphic encryption library. Experimental results validate that our methods can effectively address the homomorphic computation of step functions.

Side-Channel Analysis (SCA) is critical in evaluating the security of cryptographic implementations. The search for hyperparameters poses a significant challenge, especially when resources are limited. In this work, we explore the efficacy of a multifidelity optimization technique known as BOHB in SCA. In addition, we proposed a new objective function called $ge_{+ntge}$, which could be incorporated into any Bayesian Optimization used in SCA. We show the capabilities of both BOHB and $ge_{+ntge}$ on four different public datasets. Specifically, BOHB could obtain the least number of traces in CTF2018 when trained in the Hamming weight and identity leakage model. Notably, this marks the first reported successful recovery of the key for the identity leakage model in CTF2018.

Kyber KEM, the NIST selected PQC standard for Public Key Encryption and Key Encapsulation Mechanisms (KEMs) has been subjected to a variety of side-channel attacks, through the course of the NIST PQC standardization process. However, all these attacks targeting the decapsulation procedure of Kyber KEM either require knowledge of the ciphertexts or require to control the value of ciphertexts for key recovery. However, there are no known attacks in a blind setting, where the attacker does not have access to the ciphertexts. While blind side-channel attacks are known for symmetric key cryptographic schemes, we are not aware of such attacks for Kyber KEM. In this paper, we fill this gap by proposing the first blind side-channel attack on Kyber KEM. We target leakage of the pointwise multiplication operation in the decryption procedure to carry out practical blind side-channel attacks resulting in full key recovery. We perform practical validation of our attack using power side-channel from the reference implementation of Kyber KEM taken from the pqm4 library, implemented on the ARM Cortex-M4 microcontroller. Our experiments clearly indicate the feasibility of our proposed attack in recovering the full key in only a few hundred to few thousand traces, in the presence of a suitably accurate Hamming Weight (HW) classifier.

There are long line of researches on the fundamental distributed key generation (DKG) protocols. Unfortunately, all of them suffer from a large cubic total communication, due to the fact that $O(n)$ participants need to {\em broadcast} to all $n$ participants.

We introduce the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring $\widetilde{\mathcal{O}}(n^{2.5}\lambda)$ total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element. This property makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. Additionally, both DKG protocols straightforwardly imply an improved (single-shot) common coin protocol.

At the core of our techniques, we develop a simple-yet-effective methodology via deterministic sharding that arbitrarily groups nodes into shards; and a new primitive called consortium-dealer secret sharing, to enable a shard of nodes to securely contribute a secret to the whole population only at the cost of one-dealer. We also formalize simulation-based security for publicly verifiable secret sharing (PVSS), making it possible for a modular analysis for DKG. Those might be of independent interest.

In side-channel analysis (SCA), the success of an attack is largely dependent on the dataset sizes and the number of instances in each class. The generation of synthetic traces can help to improve attacks like profiling attacks. However, manually creating synthetic traces from actual traces is arduous. Therefore, automating this process of creating artificial traces is much needed. Recently, diffusion models have gained much recognition after beating another generative model known as Generative Adversarial Networks (GANs) in creating realistic images. We explore the usage of diffusion models in the domain of SCA. We proposed frameworks for a known mask setting and unknown mask setting in which the diffusion models could be applied. Under a known mask setting, we show that the traces generated under the proposed framework preserved the original leakage. Next, we demonstrated that the artificially created profiling data in the unknown mask setting can reduce the required attack traces for a profiling attack. This suggests that the artificially created profiling data from the trained diffusion model contains useful leakages to be exploited.

VOX is a UOV-like signature scheme submitted to Round 1 additional signatures of NIST PQC standardization process. In 2023 Furue and Ikematsu proposed a rectangular MinRank attack on VOX, resulting in the submitters changing their parameters to counter this attack. In this paper we propose a new type of MinRank attack called padded MinRank attack. We show that the attack is highly efficient in its running time, taking less than one minute to break eight of nine parameters and about eight hours for the remaining one. Therefore the parameters of VOX should be reexamined to ensure its safety.

A succinct non-interactive argument (SNARG) for $\mathsf{NP}$ allows a prover to convince a verifier that an $\mathsf{NP}$ statement $x$ is true with a proof of size $o(|x| + |w|)$, where $w$ is the associated $\mathsf{NP}$ witness. A SNARG satisfies adaptive soundness if the malicious prover can choose the statement to prove after seeing the scheme parameters. In this work, we provide the first adaptively-sound SNARG for $\mathsf{NP}$ in the plain model assuming sub-exponentially-hard indistinguishability obfuscation, sub-exponentially-hard one-way functions, and either the (polynomial) hardness of the discrete log assumption or the (polynomial) hardness of factoring. This gives the first adaptively-sound SNARG for $\mathsf{NP}$ from falsifiable assumptions. All previous SNARGs for $\mathsf{NP}$ in the plain model either relied on non-falsifiable cryptographic assumptions or satisfied a weak notion of non-adaptive soundness (where the adversary has to choose the statement it proves before seeing the scheme parameters).

Power-of-two cyclotomics is a popular choice when instantiating the BGV scheme because of its efficiency and compliance with the FHE standard. However, in power-of-two cyclotomics, the linear transformations in BGV bootstrapping cannot be decomposed into sub-transformations for acceleration with existing techniques. Thus, they can be highly time-consuming when the number of slots is large, degrading the advantage brought by the SIMD property of the plaintext space. By exploiting the algebraic structure of power-of-two cyclotomics, this paper derives explicit decomposition of the linear transformations in BGV bootstrapping into NTT-like sub-transformations, which are highly efficient to compute homomorphically. Moreover, multiple optimizations are made to evaluate homomorphic linear transformations, including modified BSGS algorithms, trade-offs between level and time, and specific simplifications for thin and general bootstrapping. We implement our method on HElib. With the number of slots ranging from 4096 to 32768, we obtain a 7.35x$\sim$143x improvement in the running time of linear transformations and a 4.79x$\sim$66.4x improvement in bootstrapping throughput, compared to previous works or the naive approach.

We continue the study of blockcipher-based (tweakable) correlation robust hash functions, which are central building blocks of circuit garbling and oblivious-transfer extension schemes. As results, we first enhance the multi-user tweakable correlation robust notion of Guo et al. (CRYPTO 2020) with a {\it key leaking oracle} that tells the adversary whether a certain user key satisfies the adversarially-chosen predicate. We then investigate the state-of-the-art hash construction of Guo et al. with respect to our new security definition, providing security proof as well as matching attacks. As an application, we exhibit an OT extension protocol with non-trivial multi-user security.

Event date: 19 August to 22 August 2024
Submission deadline: 15 March 2024
Notification: 20 May 2024

Event date: 2 September to 4 September 2024
Submission deadline: 3 May 2024
Notification: 5 June 2024

Event date: 3 June to 6 June 2024
Submission deadline: 26 February 2024
Notification: 22 March 2024

The team require specialized role to bring in-depth knowledge and experience with ZK proofs and related tools and frameworks. This expertise will facilitate expedited prototyping, research, design of the proving system, and help in developing ZK-friendly solutions for the requirements of multiple components of the Nomos blockchain. The constant flux of tasks, varying in size and scope, requires a team member who can seamlessly integrate into the team and contribute immediately.

Key Responsibilities

Develop an in-depth understanding of the multi-layered architecture of Nomos and how Zero Knowledge proofs can be effectively utilized at various stages. Collaborate with other researchers and developers to ensure that Nomos's systems and protocols are efficiently designed and implemented. Address and solve upgradeability concerns related to ZK schemes and ensure consensus proofs are ZK-friendly. Design and help implement privacy-centered protocols that require the use of ZK proofs. Evaluate and integrate ZK tools and frameworks to optimize the performance and efficiency of our systems. Stay abreast of the latest developments and trends in the field of Zero Knowledge proofs and blockchain technology. Provide support and guidance to the team on ZK proofs related issues.

You ideally will have

A strong technical background, preferably with a degree in Computer Science, Mathematics, or a related field (PhD-level or equivalent in industry); relevant research experience.

Extensive knowledge and experience with Zero Knowledge proofs, cryptography, and blockchain technology.

Deep understanding of Zero-Knowledge proof systems (zk-SNARK, circom, Plonk/Halo2, zk-STARK), elliptic curve cryptography, and circuit design.

Previous experience in a similar role, where you successfully contributed to the development of complex systems using ZK proofs.

Closing date for applications:

Contact: Angel

More information: https://grnh.se/60ae0cb71us

The SandboxAQ team is looking for a Research Scientist to help functionalize the next generation of cryptographic systems. A successful candidate will be comfortable with research in post-quantum cryptography. We are open to strong candidates that reinforce existing expertise of the team as well as candidates extending our expertise. They will be part of a team of diverse cryptographers and engineers, where they will play a key role in efficient and effective enablement of the technologies being developed. They can learn more about what we’ve been doing so far by checking out the publications of our permanent researchers: Carlos Aguilar Melchor, Martin Albrecht, Nina Bindel, James Howe, Andreas Hülsing, and Anand Kumar Narayanan

Core Responsibilities

• Research and design of new post-quantum cryptography primitives and protocols
• Engage in team collaborations to meet ambitious product and engineering goals
• Present research discoveries and developments including updates and results clearly and efficiently both internally and externally, verbally and in writing

Minimum Qualifications

• PhD in Mathematics or Computer Science or equivalent practical experience
• Strong background in post-quantum cryptography with a proven publication record at flagship conferences
• Deep understanding of cryptographic primitives and protocols
• Capacity to work both as an individual contributor and on collaborative projects with strong teamwork skills

Preferred Qualifications

• Experience in C, C++, Rust or Go, or equivalent skills to implement and validate innovative cryptographic constructions and/or protocols
• Experience with the real-world aspects of cryptography
• Experience contributing to open source projects and standardization bodies
• Curiosity in a variety of domains of cryptography, security, privacy, or engineering

SandboxAQ is committed to equal employment opportunities and offers competitive compensation. For more details have a look at the official job offer https://www.sandboxaq.com/careers-list?gh_jid=5072034004

Closing date for applications:

Contact: carlos.aguilar@sandboxaq.com

More information: https://www.sandboxaq.com/careers-list?gh_jid=5072034004

The UCLouvain Crypto Group is opening two short-term positions (3 to 6 months) in the field of side-channel secure cryptographic implementation. This project consists in either developing a masked hardware implementation of the Ascon AEAD, or developing a software masking of Dilithium for micro-controllers (with possibly other countermeasures). The goal of the project is to research and develop high-quality and well-documented open-source implementations, along with preliminary side-channel security evaluations, as part of the SIMPLE-Crypto (https://simple-crypto.org) initiative. The work will take place in the dynamic research environment of the Crypto Group at UCLouvain (Louvain-la-Neuve, Belgium) and the SIMPLE-Crypto team, in collaboration with other Ph.D. students, post-doctoral researchers and professors. The candidates should have experience in physical side-channel security and have strong implementation skills (hardware or micro-controller programming, depending on the chosen project). Remote work is possible. Applications will be examined continously.

Closing date for applications:

Contact: Candidates are invited to send a resume and motivation letter to Dr. Gaetan Cassiers and Pr. Francois-Xavier Standaert (email: first name dot last name at uclouvain.be).

More information: https://simple-crypto.org

A zero-knowledge proof of training (zkPoT) enables a party to prove that they have correctly trained a committed model based on a committed dataset without revealing any additional information about the model or the dataset. An ideal zkPoT should offer provable security and privacy guarantees, succinct proof size and verifier runtime, and practical prover efficiency. In this work, we present Kaizen, a zkPoT targeted for deep neural networks (DNNs) that achieves the above ideals all at once. In particular, our construction enables a prover to iteratively train their model by the (mini-batch) gradient-descent algorithm where the number of iterations need not be fixed in advance; at the end of each iteration, the prover generates a commitment to the trained model attached with a succinct zkPoT, attesting to the correctness of the entire training process. The proof size and verifier time are independent of the iteration number.

Kaizen relies on two essential building blocks to achieve both prover efficiency and verification succinctness. First, we construct an optimized GKR-style (sumcheck-based) proof system for the gradient-descent algorithm with concretely efficient prover cost; this scheme allows the prover to generate a proof for each iteration of the training process. Then, we recursively compose these proofs across multiple iterations to attain succinctness. As of independent interests, we propose a framework for recursive composition of GKR-style proofs and techniques, such as aggregatable polynomial commitment schemes, to minimize the recursion overhead.

Benchmarks indicate that Kaizen can handle a large model of VGG-$11$ with $10$ million parameters and batch size $16$. The prover runtime is $22$ minutes (per iteration), which is $\mathbf{43\times}$ faster than generic recursive proofs, while we further achieve at least $\mathbf{224 \times}$ less prover memory overhead. Independent of the number of iterations and, hence, the size of the dataset, the proof size is $1.36$ megabytes, and the verifier runtime is only $103$ milliseconds.

Matrix multiplication is a common operation in applications like machine learning and data analytics. To demonstrate the correctness of such an operation in a privacy-preserving manner, we propose zkMatrix, a zero-knowledge proof for the multiplication of committed matrices. Among the succinct non-interactive zero-knowledge protocols that have an $O(\log n)$ transcript size and $O(\log n)$ verifier time, zkMatrix stands out as the first to achieve $O(n^2)$ prover time and $O(n^2)$ RAM usage for multiplying two $n \times n$ matrices. Significantly, zkMatrix distinguishes itself as the first zk-SNARK protocol specifically designed for matrix multiplication. By batching multiple proofs together, each additional matrix multiplication only necessitates $O(n)$ group operations in prover time.

To improve the throughput of Byzantine Fault Tolerance (BFT) consensus protocols, the Directed Acyclic Graph (DAG) topology has been introduced to parallel data processing, leading to the development of DAG-based BFT consensus. However, existing DAG-based works heavily rely on Reliable Broadcast (RBC) protocols for block broadcasting, which introduces significant latency due to the three communication steps involved in each RBC. For instance, DAGRider, a representative DAG-based protocol, exhibits a best latency of 12 steps, considerably higher than non-DAG protocols like PBFT, which only requires 3 steps. To tackle this issue, we propose LightDAG, which replaces RBC with lightweight broadcasting protocols such as Consistent Broadcast (CBC) and Plain Broadcast (PBC). Since CBC and PBC can be implemented in two and one communication steps, respectively, LightDAG achieves low latency. In our proposal, we present two variants of LightDAG, namely LightDAG1 and LightDAG2, each providing a trade-off between the best latency and the expected worst latency. In LightDAG1, every block is broadcast using CBC, which exhibits a best latency of 5 steps and an expected worst latency of 14 steps. Since CBC cannot guarantee the totality property, we design a block retrieval mechanism in LightDAG1 to assist replicas in retrieving missing blocks. LightDAG2 utilizes a combination of PBC and CBC for block broadcasting, resulting in a best latency of 4 steps and an expected worst latency of $12(t+1)$ steps, where $t$ represents the number of actual Byzantine replicas. Since a Byzantine replica may equivocate through PBC, LightDAG2 prohibits blocks from directly referencing contradictory blocks. To ensure liveness, we propose a mechanism to identify and exclude Byzantine replicas if they engage in equivocation attacks. Extensive experiments have been conducted to evaluate LightDAG, and the results demonstrate its feasibility and efficiency.

Secure merge considers the problem of combining two sorted lists into a single sorted secret-shared list. Merge is a fundamental building block for many real-world applications. For example, secure merge can implement a large number of SQL-like database joins, which are essential for almost any data processing task such as privacy-preserving fraud detection, ad conversion rates, data deduplication, and many more.

We present two constructions with communication bandwidth and rounds tradeoff. Logstar, our bandwidth-optimized construction, takes inspiration from Falk and Ostrovsky (ITC, 2021) and runs in $O(n\log^*n)$ time and communication with $O(\log n)$ rounds. In particular, for all conceivable $n$, the $\log^*n$ factor will be equal to the constant $2$ and therefore we achieve a near-linear running time. Median, our rounds-optimized construction, builds on the classic parallel median-based merge approach of Valiant (SIAM J. Comput., 1975), and requires $O(n \log^c n)$, $1
We introduce two additional constructions that merge input lists of different sizes. SquareRootMerge, merges lists of sizes $n^{\frac{1}{2}}$ and $n$, and runs in $O(n)$ time and communication with $O(\log n)$ rounds. CubeRootMerge is inspired by Blunk et al.'s (2022) construction and merges lists of sizes $n^{\frac{1}{3}}$ and $n$. It runs in $O(n)$ time and communication with $O(1)$ rounds.

We optimize our constructions for concrete efficiency. Today, concretely efficient secure merge protocols rely on standard techniques such as GMW or generic sorting. These approaches require a $O(n \log n)$ sized circuit of $O(\log n)$ depth. In contrast, our constructions are efficient and achieve superior asymptotics. We benchmark our constructions and obtain significant improvements. For example, Logstar reduces bandwidth costs $\approx 3.3\times$ and Median reduces rounds $\approx2.43\times$.

Threshold symmetric encryption (TSE), introduced by Agrawal et al. [DiSE, CCS 2018], provides scalable and decentralized solution for symmetric encryption by ensuring that the secret-key stays distributed at all times. They avoid having a single point of attack or failure, while achieving the necessary security requirements. TSE was further improved by Christodorescu et al. [ATSE, CCS 2021] to support an amortization feature which enables a “more privileged” client to encrypt records in bulk by interacting only once with the key servers, while decryption must be performed individually for each record, potentially by a “less privileged” client. However, typical enterprises collect or generate data once and query it several times over its lifecycle in various data processing pipelines; i.e., enterprise workloads are often decryption heavy! ATSE does not meet the bar for this setting because of linear interaction / computation (in the number of records to be decrypted) – our experiments show that ATSE provides a sub-par throughput of a few hundred records / sec.

We observe that a large class of queries read a subsequence of records (e.g. a time window) from the database. With this access structure in mind, we build a new TSE scheme which allows for both encryption and decryption with flexible granularity, in that a client’s interactions with the key servers is at most logarithmic in the number of records. Our idea is to employ a binary-tree access structure over the data, where only one interaction is needed to decrypt all ciphertexts within a sub-tree, and thus only log-many for any arbitrary size sub-sequence. Our scheme incorporates ideas from binary-tree encryption by Canetti et al. [Eurocrypt 2003] and its variants, and carefully merges that with Merkle-tree commitments to fit into the TSE setting. We formalize this notion as hierarchical threshold symmetric-key encryption (HiSE), and argue that our construction satisfies all essential TSE properties, such as correctness, privacy and authenticity with respect to our definition. Our analysis relies on a well-known XDH assumption and a new assumption, that we call $\ell$-masked BDDH, over asymmetric bilinear pairing in the programmable random oracle model. We also show that our new assumption does hold in generic group model.

We provide an open-source implementation of HiSE. For practical parameters, we see 65$\times$ improvement in latency and throughput over ATSE. HiSE can decrypt over 6K records / sec on server-grade hardware, but the logarithmic overhead in HiSE’s encryption (not decryption) only lets us encrypt up to 3K records / sec (about 3-4.5$\times$ slowdown) and incurs roughly 500 bytes of ciphertext expansion per record – while reducing this penalty is an important future work, we believe HiSE can offer an acceptable tradeoff in practice.