Cryptology and Network Security

Over years of the development of secure multi-party computation (MPC), many sophisticated functionalities have been made practical and multi-dimensional operations occur more and more frequently in MPC protocols, especially in protocols involving datasets of vector elements, such as privacy-preserving biometric identification and privacy-preserving machine learning. In this paper, we introduce a new kind of correlation, called tensor triples, which is designed to make multi-dimensional MPC protocols more efficient. We will discuss the generation process, the usage, as well as the applications of tensor triples and show that it can accelerate privacy-preserving biometric identification protocols, such as FingerCode, Eigenfaces and FaceNet, by more than 1000 times, with reasonable offline costs.

Secure multi-party computation (MPC) in a three-party, honest majority scenario is currently the state-of-the-art for running machine learning algorithms in a privacy-preserving manner. For efficiency reasons, fixed-point arithmetic is widely used to approximate computation over decimal numbers. After multiplication in fixed-point arithmetic, truncation is required to keep the result’s precision. In this paper, we present an efficient three-party truncation protocol secure in the presence of an active adversary without pre-processing and improve on the current state-of-the-art in MPC over rings using replicated secret sharing (RSS). By adding an efficient consistency check, we lift the efficient but only passively secure three-party truncation protocol from the ABY3 framework by Mohassel and Rindal into the malicious setting without pre-processed data. Our benchmark indicates performance improvements of an order of magnitude in the offline phase for a single batch training. Finally, we apply our protocol to a real-world application for diagnostic prediction based on publicly available ECG heartbeat data. We achieve an improvement by a factor of two in the total throughput for both LAN and WAN settings.

Blockchain technology has revolutionized decentralized transactional data storage, fostering trustless interactions via consensus mechanisms involving miners. The security of these systems hinges on digital signatures, predominantly elliptic curve cryptography, which is at risk from quantum computing advancements. To tackle scalability and cost issues of on-chain transactions, off-chain solutions, notably payment channel networks (PCNs), have been introduced. Among these solutions, adaptor signatures (AS) have emerged as a pivotal cryptographic tool, allowing secure and efficient off-chain interactions by extending conventional signature schemes with additional hard relations tailored for payment channels. Existing post-quantum secure AS schemes, such as LAS and SQI-AS, face challenges ranging from high off-chain communication costs to security vulnerabilities. These schemes often lack consideration for the unlinkability notion of AS and may fail to deliver promised security guarantees. In response to these challenges, our contribution aims to bridge the gap in practical and secure post-quantum AS solutions. Our work introduces an isogeny-based adaptor signature utilizing the CSI-FiSh signature scheme. We define a variant, Modified CSI-FiSh (MCSI-FiSh), which incorporates a strong random self-reducible relation derived from CSIDH. Our proposed adaptor signature scheme for MCSI-FiSh not only verifies a valid signature but also ensures the release of a witness. We provide rigorous security proofs, demonstrating our scheme’s resilience against pre-signature adaptability, strong-full extractability and unlinkability. Our scheme is the first post-quantum adaptor signature offering unlinkability and strong-full extractability. We remark that the overhead of our scheme is also minimal in terms of communication cost and signature size compared to the existing post-quantum adaptor signature.

Bounded-collusion identity-based encryption (BC-IBE) is a variant of identity-based encryption, where an adversary obtains at most d secret user-keys for a collusion-parameter d. From results of existing work, there are generic constructions of BC-IBE, which starts from public key encryption (PKE) schemes with several properties. In particular, we consider BC-IBE schemes constructed from post-quantum PKE schemes submitted to the NIST-PQC competition (denoted by NIST-PQC PKE schemes). Although it is possible to construct a post-quantum BC-IBE scheme by applying a NIST-PQC PKE scheme to an existing generic construction, the public parameter-size of the resulting scheme is not compact. In this paper, we propose a post-quantum BC-IBE scheme whose public parameter-size is more compact. To this end, we construct a new generic construction of the objective BC-IBE by employing probabilistic group testing techniques, while existing BC-IBE schemes are constructed by using error-correcting codes or cover-free families. As a result, we can obtain post-quantum BC-IBE schemes with more compact public parameters by applying NIST-PQC PKE schemes to our generic construction.

We construct a 1-out-of-N oblivious transfer (OT) protocol based on the Module-Learning with Errors assumption, which considers the scenario where the sender has N private values \(x_1,...,x_{N}\), the receiver holds a chosen index i and is allowed to obtain \(x_i\) but nothing else, and the sender cannot know the receiver’s choice. Under the semi-honest model, our protocol achieves statistical sender security and computational receiver security, which means such protocol guarantees sender’s security against computationally unbounded adversaries. In terms of communication cost, our protocol achieves the minimal interaction between the sender and the receiver, which is two-round.

Post-Quantum Cryptography (PQC) algorithms are currently being standardised and their early implementations are not as efficient as the well-established public key cryptography (PKC) algorithms that have benefited from decades of optimisations. We report on our efforts to accelerate the Number Theoretic Transform (NTT), the most computationally expensive primitive in the Kyber (ML-KEM) and Dilithium (ML-DSA) PQC algorithms selected by NIST for standardisation. Our target platform is the OpenTitan Big Number Accelerator (OTBN), part of the first open-source silicon root-of-trust chip. We implemented the Kyber NTT in OTBN assembly, using only the existing instructions, and identified its bottlenecks. We then restructured the code to exploit parallelism and defined additional assembly instructions for the open-source co-processor that would enable execution of our vectorised implementation. Our hardware/software co-design approach yielded a significant performance improvement: NTT ran 21.1 times faster than the baseline implementation which used only OTBN’s existing instructions. Our approach fully leverages the potential for parallelism and maximally exploits the existing capabilities of OTBN. Some of our optimisations are fairly general and might be successfully applied to other contexts, including accelerating other algorithms on other platforms.

Fully traceable k-times anonymity is a security property concerning anonymous signatures: if a user produces more than k anonymous signatures, its identity is disclosed and all its previous signatures can be identified. In this paper, we show how this property can be achieved for delegation-supported signature schemes, especially proxy signatures, where the signer allows a delegate to sign on its behalf, and sanitizable signatures, where a signer allows a delegate to modify certain parts of the signed messages. In both cases, we formalize the primitive, give a suitable security model, provide a scheme and then prove its security under the DDH assumption. The size of the keys/signatures is logarithmic in k in our two schemes, making them suitable for practical applications, even for large k.

Mix networks (mixnets) enhance anonymity by routing client messages through multiple hops, intentionally delaying or reordering these messages to ensure unlinkability. However, this process increases end-to-end latency, potentially degrading the client experience. To address this issue, LARMix (NDSS, 2024) proposed a low-latency routing methodology specifically designed for stratified mixnet architectures. Our paper extends this concept to Free Routes mixnet designs, where, unlike stratified topologies, there are no restrictions on node connections. We adapt several state-of-the-art low-latency routing strategies from both mix and Tor networks to optimize the Free Routes topology. Despite the benefits, low-latency routing can cause certain mixnodes to receive disproportionate amounts of traffic. To overcome this challenge, we introduce a novel load-balancing algorithm that evenly distributes traffic among nodes without significantly compromising low-latency characteristics. Our analytical and simulation experiments demonstrate a considerable reduction in latency compared to uniform routing methods, with negligible loss in message anonymity, defined as the confusion an adversary experiences when correlating messages exiting the mixnet to an initially targeted input message. Additionally, we provide an analysis of adversarial strategies, revealing a balanced trade-off between low latency and adversary advantages.

Security models provide a way of formalising security properties in a rigorous way, but it is sometimes difficult to ensure that the model really fits the concept that we are trying to formalise. In this paper, we illustrate this fact by showing the discrepancies between the security model of anonymity in linkable ring signatures and the security that is actually expected for this kind of signature. These signatures allow a user to sign anonymously within an ad hoc group generated from the public keys of the group members, but all their signatures can be linked together. Reading the related literature, it seems obvious that users’ identities must remain hidden even when their signatures are linked, but we show that, surprisingly, almost none of the anonymity models guarantee this property. We illustrate this by presenting two counter-examples which are secure in most anonymity model of linkable ring signatures, but which trivially leak a signer’s identity after only two signatures.

A natural fix to this model, already introduced in some previous work, is proposed in a corruption model where the attacker can generate the keys of certain users themselves, which seems much more coherent in a context where the group of users can be constructed in an ad hoc way at the time of signing. We believe that these two changes make the security model more realistic. Indeed, within the framework of this model, our counter-examples becomes insecure. Furthermore, we show that most of the schemes in the literature we surveyed appear to have been designed to achieve the security guaranteed by the latest model, which reinforces the idea that the model is closer to the informal intuition of what anonymity should be in linkable ring signatures.

We formalize the primitive in the universal composition setting and propose efficient constructions for STMs in the unstructured reference string model. We also showcase that STMs are eminently useful in the blockchain setting by providing three applications: (i) stakeholder decision-making for Proof of Work (PoW) blockchains, specifically, Bitcoin, (ii) fast bootstrapping for Proof of Stake (PoS) blockchains, and (iii) proofs of data availability for consensus scaling.

Payment channels are one of the most prominent off-chain scaling solutions for blockchain systems. However, regulatory institutions have difficulty embracing them, as the channels lack insights needed for Anti-Money Laundering (AML) auditing purposes. Our work tackles the problem of a formal reliable and controllable inspection of off-ledger payment channels, by offering a novel approach for maintaining and reliably auditing statistics of payment channels. We extend a typical trustless Layer 2 protocol and provide a lightweight and scalable protocol s.t.: (i) every state channel is provably auditable w.r.t. a configurable set of policy queries, s.t. a regulator can retrieve reliable insights about the channel; (ii) no information beyond the answers to auditing queries is leaked; (iii) the cryptographic operations are inexpensive, the setup is simple, and storage complexity is independent of the transaction graph’s size. We present a concrete protocol, based on Hydra Isomorphic State Channels (FC’21), and tie the creation of a state channel to real-world identifiers, both in a plain and privacy-preserving manner. For this, we employ verifiable credentials for decentralized identifiers, specifically verifiable Legal Entity Identifiers (vLEI) that increasingly gain traction for financial service providers and regulated institutions.

Stablecoins are digital assets designed to maintain a consistent value relative to a reference point, serving as a vital component in Blockchain, and Decentralized Finance (DeFi) ecosystem. Typical implementations of stablecoins via smart contracts come with important downsides such as a questionable level of privacy, potentially high fees, and lack of scalability. We put forth a new design, \(\mathbf {\textsf{PARScoin}}\), for a Privacy-preserving, Auditable, and Regulation-friendly Stablecoin that mitigates these issues while enabling high performance both in terms of speed of settlement and for scaling to large numbers of users as our performance analysis demonstrates. Our construction is blockchain-agnostic and is analyzed in the Universal Composition (UC) framework, offering a secure and modular approach for its integration into the broader blockchain ecosystem.