International Association
for Cryptologic Research

Bootstrapping is a term used very often in the context of Fully Homomorphic Encryption (FHE). Anyone who is familiar with FHE knows that bootstrapping is the most sophisticated and compute-intensive component of an FHE scheme. However, very few non-FHE-experts understand what the bootstrapping operation really is and that there are various bootstrapping methods, each with its own tradeoffs. The goal of this paper is to provide a high-level introduction to common bootstrapping methods and evaluate their performance using the existing implementations in OpenFHE and HElib open-source libraries.

Our performance evaluation suggests that the bootstrapping in the Cheon-Kim-Kim-Song (CKKS) scheme provides highest throughput and efficiently achieves large precision for vectors of real numbers, which are often used in machine learning applications. The Ducas-Micciancio (DM) and Chillotti-Gama-Georgieva-Izabachene (CGGI) schemes achieve the smallest latency (typically for small integers or small-precision fixed-point numbers) and provide a general capability for evaluating arbitrary functions (programmable bootstrapping) via lookup tables. The Brakerski-Gentry-Vaikuntanathan (BGV) and Brakerski/Fan-Vercauteren (BFV) schemes provide higher bootstrapping throughput than DM/CGGI for vectors of small integers or finite-field elements but do not support programmable bootstrapping.

The target audience is anyone interested in FHE. We intend to keep this paper up-to-date to include new bootstrapping results as they become available.

In this paper, we present a client-side password hashing method, called PassPro. PassPro uses two secrets and a domain word to shuffle the strings. The shuffled strings are converted into hash values and sent to the identity manager for authentication or identity creation. The shuffling is based on a pseudo-random algorithm. The legitimate user can reproduce the shuffled string again. The hash values are encrypted in the password database with a different key for each user. Therefore, PassPro features- a) client-side password metering, b) client-side password hashing, c) prevention of the domino effect, d) protection of the password database from stealing, e) memory hardness, f) encryption of the hash values using a mutually reproducible secret key, and g) prevention of dictionary and guessing attacks. Also, PassPro guarantees that identity managers, including adversaries, cannot retrieve the original password and user ID of the user. Alternatively, the original user ID and password cannot be retrieved even if the password database is given to the adversary. Furthermore, the user ID and password of a password database are invalid in other domains, even if the same user ID and password are used in multiple domains.

Bulletproofs (Bünz et al. IEEE S&P 2018) are a celebrated ZK proof system that allows for short and efficient proofs, and have been implemented and deployed in several real-world systems. In practice, they are most often implemented in their non-interactive version obtained using the Fiat-Shamir transform. A security proof for this setting is necessary for ruling out malleability attacks. These attacks can lead to very severe vulnerabilities, as they allow an adversary to forge proofs re-using or modifying parts of the proofs provided by the honest parties. An earlier version of this work (Ganesh et al. EUROCRYPT 2022) provided evidence for non-malleability of Fiat-Shamir Bulletproofs. This was done by proving simulation-extractability, which implies non-malleability, in the algebraic group model.

In this work, we generalize the former result and prove simulation extractability in the programmable random oracle model, removing the need for the algebraic group model. Along the way, we establish a generic chain of reductions for Fiat-Shamir-transformed multi-round public-coin proofs to be simulation-extractable in the (programmable) random oracle model, which may be of independent interest.

In this paper, we research the implementation of the AES family with Pauli-X gates, CNOT gates and Toffoli gates as the underlying quantum logic gate set. First, we investigate the properties of quantum circuits and the influence of Pauli-X gates, CNOT gates and Toffoli gates on the performance of the circuits constructed with those gates. Based on the properties of quantum circuits as well as our observations on the classical ones built by Boyar \emph{et al.} and Zou \emph{et al.}, we research the construction of reversible circuits for AES's Substitution-box (S-box) and its inverse (S-box$^{-1}$) by rearranging the classical implementation to three parts. Since the second part is treated as a 4-bit S-box in this paper and can be dealt with by existing tools, we propose a heuristic to search optimized reversible circuits for the first part and the third part. The application of our method reveals that the reversible circuits constructed for AES S-box and its inverse consume fewer qubits with optimized CNOT gate consumption and Toffoli depth. In addition, we study the construction of reversible circuits for the key schedule and the round function of AES by applying various number of S-boxes in parallel. As a result, we report quantum circuits of AES-128, AES-192 and AES-256 with 269, 333 and 397 qubits, respectively. If more qubits are allowed, quantum circuits that outperform state-of-the-art schemes in the metric of $T\cdot M$ value for the AES family can be reported, and it needs only 474, 538 and 602 qubits for AES-128, AES-192 and AES-256, respectively.

The Mixed Integer Linear Programming (MILP) technique has been widely applied in the realm of symmetric-key cryptanalysis. In this paper, we propose a new bitwise breakdown MILP modeling strategy for describing the linear propagation rules of modular addition-based operations. We apply such new techniques to cryptanalysis of the SNOW stream cipher family and find new linear masks: we use the MILP model to find many linear mask candidates among which the best ones are identified with particular algebraic bias evaluation techniques. For SNOW 3G, the correlation of the linear mask we found is the highest on record: such results are highly likely to be optimal according to our analysis. For SNOW 2.0, we find new masks matching the correlation record and many new sub-optimal masks applicable to improving correlation attacks. For SNOW-V/Vi, by investigating both bitwise and truncated linear masks, we find all linear masks having the highest correlation, and prove the optimum of the corresponding truncated patterns under the ``fewest active S-box preferred'' strategy. By using the newly found linear masks, we give correlation attacks on the SNOW family with improved complexities. We emphasize that the newly proposed uniform MILP-aided framework can be potentially applied to analyze LFSR-FSM structures composed of modular addition and S-box as non-linear components.

Non-fungible tokens (NFTs) are unique non-interchangeable digital assets verified and stored using blockchain technology. Quite recently, there has been a surging interest and adoption of NFTs, with sales exceeding \$10 billion in the third quarter of 2021. Given the public state of Blockchain, NFTs owners face a privacy problem. More precisely, an observer can trivially learn the whole NFT collections owned by an address. For some categories of NFTs like arts and game collectibles, owners can sell them for a profit. However, popular marketplaces trade NFTs using public auctions and direct offers. Hence, an observer can learn about the new owner and the NFT purchase price. To tackle those problems, we propose Aegis, a protocol that allows users to add privacy to their NFTs ownership. In Aegis, users can swap NFTs for payment amounts in fungible tokens while hiding the details (i.e., involved parties, the NFTs, and the payment amounts). One of the main properties of Aegis is its complete compatibility with existing NFT standards. We design Aegis by leveraging a zk-SNARK proof system and smart contracts. We build an open-source prototype and perform experiments to evaluate Aegis's performance.

The pair encodings framework is an important result in the simplified design of complex attribute-based encryption schemes. In particular, it reduces the effort of proving security of a scheme to proving security of the associated pair encoding, which can then be transformed into a provably secure pairing-based encryption scheme with a compiler. Especially the symbolic property, as introduced by Agrawal and Chase (EUROCRYPT '17), has proven to be a valuable security notion that is both simple to verify and applies to many schemes. Nevertheless, several practical extensions using full-domain hashes or employing multiple authorities cannot be instantiated with this compiler, and therefore still require complicated proof techniques.

In this work, we present the first compiler for attribute-based encryption schemes that supports such extensions. To this end, we generalize the definitions of pair encodings and the symbolic property. With our compiler, we flexibly instantiate any pair encodings that satisfy this new notion of the symbolic property in any pairing-friendly groups, and generically prove the resulting scheme to be selectively secure. To illustrate the effectiveness of our new compiler, we give several new multi-authority and hash-based constructions.

We present a single-trace attack against lattice-based KEMs using the cumulative distribution table for Gaussian sampling and execute it in a real-world environment. Our analysis takes a single power trace of the decapsulation algorithm as input and exploits leakage of the Gaussian sampling subroutine to reveal the session key. We investigated the feasibility of the attack on different boards and proved that the power consumption traces become less informative with higher clock frequencies. Therefore, we introduce a machine-learning denoising technique, which enhances the accuracy of our attack and leverages its success rate to 100%.

We accomplish the attack on FrodoKEM, a lattice-based KEM and third-round alternate candidate. We execute it on a Cortex-M4 board equipped with an STM32F4 micro-controller clocked at different frequencies.

Aggregate statistics derived from time-series data collected by individual users are extremely beneficial in diverse fields, such as e-health applications, IoT-based smart metering networks, and federated learning systems. Since user data are privacy-sensitive in many cases, the untrusted aggregator may only infer the aggregation without breaching individual privacy. To this aim, secure aggregation techniques have been extensively researched over the past years. However, most existing schemes suffer either from high communication overhead when users join and leave, or cannot tolerate node dropouts. In this paper, we propose a dropout-resistant bandwidth-efficient time-series data aggregation. The proposed scheme does not incur any interaction among users, involving a solo round of user→aggregator communication exclusively. Additionally, it does not trigger a re-generation of private keys when users join and leave. Moreover, the aggregator is able to output the aggregate value by employing the re-encrypt capability acquired during a one-time setup phase, notwithstanding the number of nodes in the ecosystem that partake in the data collection of a certain epoch. Dropout-resistancy, trust-less key management, low-bandwidth and non-interactive nature of our construction make it ideal for many rapid-changing distributed real-world networks. Other than bandwidth efficiency, our scheme has also demonstrated efficiency in terms of computation overhead

The best lattice reduction algorithm known in theory for approximating the Shortest Vector Problem (SVP) over lattices is the slide reduction algorithm (STOC '08 & CRYPTO '20). In this paper, we first improve the running time analysis of computing slide-reduced bases based on potential functions. This analysis applies to a generic slide reduction algorithm that includes (natural variants of) slide reduction and block-Rankin reduction (ANTS '14). We then present a rigorous dynamic analysis of generic slide reduction using techniques originally applied to a variant of BKZ (CRYPTO '11). This provides guarantees on the quality of the current lattice basis during execution. This dynamic analysis not only implies sharper convergence for these algorithms to find a short nonzero vector (rather than a fully reduced basis), but also allows to heuristically model/trace the practical behaviour of slide reduction. Interestingly, this dynamic analysis inspires us to introduce a new slide reduction variant with better time/quality trade-offs. This is confirmed by both our experiments and simulation, which also show that our variant is competitive with state-of-the-art reduction algorithms. To the best of our knowledge, this work is the first attempt of improving the practical performance of slide reduction beyond speeding up the SVP oracle.

In post-quantum cryptography (PQC), Learning With Errors (LWE) is the dominant underlying mathematical problem. For example, in NIST's PQC standardization process, the Key Encapsulation Mechanism (KEM) protocol chosen for standardization was Kyber, an LWE-based scheme. Recently the dual attack surpassed the primal attack in terms of concrete complexity for solving the underlying LWE problem for multiple cryptographic schemes, including Kyber. The dual attack consists of a reduction part and a distinguishing part. When estimating the cost of the distinguishing part, one has to estimate the expected cost of enumerating over a certain number of positions of the secret key. Our contribution consists of giving a polynomial-time approach for calculating the expected complexity of such an enumeration procedure. This allows us to revise the complexity of the dual attack on the LWE-based protocols Kyber, Saber and TFHE. For all these schemes we improve upon the total bit-complexity in both the classical and the quantum setting. As our method of calculating the expected cost of enumeration is fairly general, it might be of independent interest in other areas of cryptography or even in other research areas.

When multiple users have power or rights, there is always the risk of corruption or abuse. Whereas there is no solution to avoid those malicious behaviors, from the users themselves or from external adversaries, one can strongly deter them with tracing capabilities that will later help to revoke the rights or negatively impact the reputation. On the other hand, privacy is an important issue in many applications, which seems in contradiction with traceability. In this paper, we first extend usual tracing techniques based on codes so that not just one contributor can be traced but the full collusion. In a second step, we embed suitable codes into a set $\mathcal V$ of vectors in such a way that, given a vector $\mathbf U \in \mathsf{span}(\mathcal V)$, the underlying code can be used to efficiently find a minimal subset $\mathcal X \subseteq \mathcal V$ such that $\mathbf U \in \mathsf{span}(\mathcal X)$. To meet privacy requirements, we then make the vectors of $\mathsf{span}(\mathcal V)$ anonymous while keeping the efficient tracing mechanism. As an interesting application, we formally define the notion of linearly-homomorphic group signatures and propose a construction from our codes: multiple signatures can be combined to sign any linear subspace in an anonymous way, but a tracing authority is able to trace back all the contributors involved in the signatures of that subspace.

We study the notion of anonymous credentials with Publicly Auditable Privacy Revocation (PAPR). PAPR credentials simultaneously provide conditional user privacy and auditable privacy revocation. The first property implies that users keep their identity private when authenticating unless and until an appointed authority requests to revoke this privacy, retroactively. The second property enforces that auditors can verify whether or not this authority has revoked privacy from an issued credential (i.e. learned the identity of the user who owns that credential), holding the authority accountable. In other words, the second property enriches conditionally anonymous credential systems with transparency by design, effectively discouraging such systems from being used for mass surveillance. In this work, we introduce the notion of a PAPR anonymous credential scheme, formalize it as an ideal functionality, and present constructions that are provably secure under standard assumptions in the Universal Composability framework. The core tool in our PAPR construction is a mechanism for randomly selecting an anonymous committee which users secret share their identity information towards, while hiding the identities of the committee members from the authority. As a consequence, in order to initiate the revocation process for a given credential, the authority is forced to post a request on a public bulletin board used as a broadcast channel to contact the anonymous committee that holds the keys needed to decrypt the identity connected to the credential. This mechanism makes the user de-anonymization publicly auditable.

Recently, SIKE was broken by the Castryck-Decru attack in polynomial time. To avoid this attack, Fouotsa proposed a SIDH-like scheme called M-SIDH, which hides the information of auxiliary points. The countermeasure also leads to huge parameter sizes, and correspondingly the public key size is relatively large.

In this paper, we present several new techniques to compress the public key of M-SIDH. Our method to compress the key is reminiscent of public-key compression in SIDH/SIKE, including torsion basis generation, pairing computation and discrete logarithm computation. We also prove that compressed M-SIDH is secure if M-SIDH is secure.

Experimental results showed that our approach fits well with compressed M-SIDH. It should be noted that most techniques proposed in this paper could be also utilized into other SIDH-like protocols.

Dear IACR members,

Nominations for the 2023 Test-of-Time award (for papers published in 2008) will be accepted until Feb 15, 2023.

https://iacr.org/testoftime

Dear IACR members,

RWC 2023 will take place in Tokyo, Japan on March 27-29 2023.

The registration site is now open:
https://rwc.iacr.org/2023/registration.php

Event date: 19 June to 22 June 2023
Submission deadline: 20 March 2023
Notification: 19 April 2023

Event date: 19 June to 22 June 2023
Submission deadline: 1 March 2023
Notification: 9 April 2023

The security infrastructure we rely on today is considered broken when a scalable quantum computer is successfully realized. Consequently, the NIST in USA initiated a call develop and standardize of new post-quantum cryptography (or PQC also called quantum-resistant cryptography) schemes replacing established public-key mechanisms (NIST PQC). As PQC is supposed to replace modern public-key schemes in the near future, it will only be considered as a feasible alternative if its constructions can be similarly efficiently implemented on many of the embedded processors existing in today’s digital and pervasive environment. These embedded processors make the backbone of computing and communication, actuating the revolution of the IoT today, with a sky-rocketing demand of more ubiquitous intelligence in future. This project will investigate efficient and lightweight implementations of PQC algorithms on an open-source RISC-V processor as would be used for IoT and edge applications. This project will test, evaluate, and scrutinize the practicability of lattice-based quantum resistant cryptographic schemes (from the NIST PQC) for an IoT end-node device by aggressively exploring several optimizations techniques. RISC-V’s instruction set is designed for modularity and extensibility, based on which domain-specific architecture aimed at a particular application like PQC can be developed. The project will analyse the performance bottlenecks in these implementations to determine how best to improve the efficiency of the algorithms while running on RISC-V using existing and/or custom ISE. This will be followed by an investigation of the performance trade-offs of any proposed approaches. Due to the physical vulnerability of such devices, Side Channel Analysis (SCA) is a significant concern, hence physical security of these devices will be taken up.

Applicants must have at least a 2:1 Honours Degree in Electrical and Electronics Engineering, Computer Science, Mathematics or closely related discipline.

International studentships are also available.

Closing date for applications:

Contact: Dr. Ayesha Khalid

More information: https://www.qub.ac.uk/courses/postgraduate-research/phd-opportunities/lightweight-post-quantum-cryptography-on-modern-opensource-riscv-processors.html