Cryptology ePrint Archive
Not a member yet
24907 research outputs found
Sort by
Towards Lightweight CKKS: On Client Cost Efficiency
Get PDFFully homomorphic encryption (FHE) enables clients with small devices to securely delegate their computations to powerful servers. However, to delegate these computations, a client should generate and transmit several gigabytes of FHE keys to the server. Reducing the size of FHE keys without compromising efficiency is therefore highly desirable, particularly for applications involving mobile and IoT devices.
In this work, we propose two new key management systems, and , which reduce the client-side cost of FHE. The system significantly reduces the key size without any compromise in the efficiency of homomorphic computation compared to the state-of-the-art key management system by Lee-Lee-Kim-No [Asiacrypt 2023]. The system further reduces the key size at the expense of granularity in homomorphic computation.
Our systems rely on a new ring switching technique for keys that bridges FHE keys with different parameters. This technique decouples the rings of FHE keys during transmission and computation. In our approach, the client generates and sends ``transmission keys\u27\u27 with size-optimal parameters, and the server generates ``evaluation keys\u27\u27 with computation-optimal parameters.
We evaluate the communication costs of and on the tasks studied in Lee-Lee-Kim-No. The transmission key sizes for CKKS bootstrapping with ring dimension are -- MB for and MB for . These are -- and -- smaller than Lee-Lee-Kim-No, respectively. For the secure ResNet-20 inference, the key sizes for and are -- MB and MB, respectively. These are -- and -- smaller than Lee-Lee-Kim-No
LOHEN: Layer-wise Optimizations for Neural Network Inferences over Encrypted Data with High Performance or Accuracy
Get PDFFully Homomorphic Encryption (FHE) presents unique challenges in programming due to the contrast between traditional and FHE language paradigms. A key challenge is selecting ciphertext configurations (CCs) to achieve the desired level of security, performance, and accuracy simultaneously. Finding the design point satisfying the goal is often labor-intensive (probably impossible), for which reason previous works settle down to a reasonable CC that brings acceptable performance. When FHE is applied to neural networks (NNs), we have observed that the distinct layered architecture of NN models opens the door for a performance improvement by using layer-wise CCs, because a globally chosen CC may not be the best possible CC for every layer individually. This paper introduces LOHEN, a technique crafted to attain high performance of NN inference by enabling to use layer-wise CC efficiently. Empowered with a cryptographic gadget that allows switching between arbitrary CCs, LOHEN allocates layer-wise CCs for individual layers tailored to their structural properties, while minimizing the increased overhead incurred by CC switching with its capability to replace costly FHE operations. LOHEN can also be engineered to attain higher accuracy, yet deliver higher performance compared to state-of-the-art studies, by additionally adopting the multi-scheme techniques in a layer-wise manner. Moreover, the developers using LOHEN are given the capability of customizing the selection policy to adjust the desired levels of performance and accuracy, subject to their demands. Our evaluation shows that LOHEN improves the NN inference performance in both of these cases when compared to the state-of-the-art. When used to improve the CKKS-only inference, LOHEN improves the NN inference performance of various NNs 1.08--2.88x. LOHEN also improves the performance of mixed-scheme NN inference by 1.34--1.75x without accuracy loss. These two results along with other empirical analyses, advocate that LOHEN can widely help improve the performance of NN inference over FHE
Arbigraph: Verifiable Turing-Complete Execution Delegation
Get PDFDependence on online infrastructure is rapidly growing as services like online payments and insurance replace traditional options, while others, like social networks, offer new capabilities.
The centralized service operators wield unilateral authority over user conflicts, content moderation, and access to essential services.
In the context of payments, blockchains provide a decentralized alternative.
They also enable decentralized execution of stateful programs called smart contracts.
But those lack the contextual understanding and interpretative capabilities that would enable reasoning about complex scenarios.
Advancements in machine learning (ML) are raising interest in actually-smart contracts, but blockchain computation constraints prohibit direct ML inference execution.
While many projects deploy computation delegation mechanisms, they lack Turing-completeness, prohibit parallel computation, or suffer from high overhead.
We present Arbigraph, a blockchain-based execution delegation protocol.
Like previous optimistic solutions, the parties submit their computation results, allowing a smart contract to arbitrate in case of dispute.
But Arbigraph employs a novel dual-graph data structure and takes advantage of the nature of the dispute process to achieve Turing completeness, constant-time memory access, and parallel execution.
We formalize the problem and show that Arbigraph guarantees completeness, soundness, and progress.
Experiments on LLM inference as well as matrix multiplication, which is at the core of ML inference, demonstrate that parallelization speedup grows linearly with matrix dimensions.
We demonstrate Arbigraph\u27s practical cost with a deployment on the Avalanche blockchain.
Arbigraph thus enables decentralized, context-aware decision-making and unlocks unprecedented use cases for blockchains
A Multi-Differential Approach to Enhance Related-Key Neural Distinguishers
Get PDFAt CRYPTO 2019, Gohr pioneered the integration of differential cryptanalysis with neural networks, demonstrating significant advantages over traditional distinguishers. Subsequently, at Inscrypt 2020, Su et al. proposed the concept of constructing polyhedral differential neural distinguishers by leveraging multiple effective input differences. More recently, at FSE 2024, Bellini et al. introduced a general-purpose tool for automating the training of single-key differential neural distinguishers for various block ciphers. Inspired by this body of work, we aim to extend automated search techniques to related-key differential neural distinguishers, enabling the discovery of effective input differences and key differences for such distinguishers. To achieve this, we employ a genetic optimization algorithm to identify effective differential combinations. To validate the efficacy of our method, we apply it to the Simeck and Simon cipher families, successfully identifying effective differential combinations for the three variants of Simeck and ten variants of Simon. Furthermore, inspired by the concept of polyhedral neural distinguishers, we adopt a novel data format that leverages multiple distinct input differences and key differences to construct positive and negative samples, providing the neural network with a richer set of features. Our approach not only identify high-quality distinguishers for previously unexplored cipher variants but also achieve higher accuracy for related-key differential neural distinguishers compared to the state-of-the-art
Quantum Periodic Distinguisher Construction: Symbolization Method and Automated Tool
Get PDFAs one of the famous quantum algorithms, Simon\u27s algorithm enables the efficient derivation of the period of periodic functions in polynomial time. However, the complexity of constructing periodic functions has hindered the widespread application of Simon\u27s algorithm in symmetric-key cryptanalysis. Currently, aside from the exhaustive search-based testing method introduced by Canale et al. at CRYPTO 2022, there is no unified model for effectively searching for periodic distinguishers. Although Xiang et al. established a link between periodic functions and truncated differential theory at ToSC 2024, their approach lacks the ability to construct periods using unknown differentials and does not provide automated tools. This limitation underscores the inadequacy of existing methods in identifying periodic distinguishers for complex structures. In this paper, we address the challenge of advancing periodic distinguishers for symmetric-key ciphers. First, we propose a more generalized method for constructing periodic distinguishers, addressing the limitations of Xiang et al.\u27s theory in handling unknown differences. We further extend it to probabilistic periodic distinguishers. As a result, our method can cover a wider range of periodic distinguishers. Second, we introduce a novel symbolic representation to simplify the search for periodic distinguishers, and propose the first fully automated SMT-based search model, which efficiently addresses the challenges of manual searching in complex structures. Based on our method, we have achieved new quantum distinguishers with the following round configurations: 10 rounds for GFS-4F, 10 rounds for LBlock, 10 rounds for TWINE, and 16 rounds for Skipjack-B, improving the previous best results by 1, 2, 2, and 3 rounds, respectively. Our model also identifies the first 7/8/9-round periodic distinguishers for SKINNY. Compared with existing distinguishers (Hadipour et al., CRYPTO 2024) with the same round in the classical setting, our distinguishers achieve lower data complexity
Pirouette: Query Efficient Single-Server PIR
Get PDFPrivate information retrieval (PIR) allows a client to query a public database privately and serves as a key building block for privacy-enhancing applications. Minimizing query size is particularly important in many use cases, for example when clients operate on low-power or bandwidth-constrained devices. However, existing PIR protocols exhibit large query sizes: to query records, the smallest query size of 14.8KB is reported in Respire [Burton et al., CCS\u2724]. Respire is based on fully homomorphic encryption (FHE), where a common approach to lower the client-to-server communication cost is transciphering. When combining the state-of-the-art transciphering [Bon et al., CHES\u2724] with Respire, the resulting protocol (referred to as T-Respire) has a 336B query size, while incurring a 16.2x times higher server computation cost than Respire.
Our work introduces a novel alternative to transciphering for reducing the client-to-server communication: the client transmits only one component of a high-precision LWE ciphertext, from which we design a modular procedure to extract the inputs for the subsequent homomorphic computation. The efficiency of this approach is demonstrated by our Pirouette protocol, which achieves a query size of just 36B. This represents a 9.3x reduction compared to T-Respire and a 420x reduction to Respire. For queries over records, the single-core server computation in Pirouette is only 2x slower than Respire and 8.1x faster than T-Respire, and the server computation is highly parallelizable. Furthermore, Pirouette requires no database-specific hint for clients, and its variant PirouetteH enables additional tradeoffs among query size, throughput, and offline communication, demonstrating the flexibility of our design
Recovering S-Box Design Structures and Quantifying Distances between S-Boxes using Deep Learning
Get PDFAt ASIACRYPT’19, Bonnetain et al. demonstrated that an S-box can be distinguished from a permutation chosen uniformly at random by quantifying the distances between their behaviors. In this study, we extend this approach by proposing a deep learning-based method to quantify distances between two different S-boxes and evaluate similarities in their design structures. First, we introduce a deep learning-based framework that trains a neural network model to recover the design structure of a given S-box based on its cryptographic table. We then interpret the decision-making process of our trained model to analyze which coefficients in the table play significant roles in identifying S-box structures. Additionally, we investigate the inference results of our model across various scenarios to evaluate its generalization capabilities. Building upon these insights, we propose a novel approach to quantify distances between structurally different S-boxes. Our method effectively assesses structural similarities by embedding S-boxes using the deep learning model and measuring the distances between their embedding vectors. Furthermore, experimental results confirm that this approach is also applicable to structures that the model has never seen during training. Our findings demonstrate that deep learning can reveal the underlying structural similarities between S-boxes, highlighting its potential as a powerful tool for S-box reverse-engineering
Publicly Verifiable Generalized Secret Sharing Schemes and Their Applications
Get PDFGeneralized secret sharing (GSS) enables flexible access control in distributed systems by allowing secrets to be shared across arbitrary monotone access structures. However, its adoption in transparent and trustless environments is hindered due to the reliance on trusted participants and secure communication channels. This reliance restricts GSS\u27s ability to provide flexible control in the presence of adversaries. In this paper, we propose publicly verifiable generalized secret sharing (PVGSS), a scheme that allows to distribute a secret using generalized access structures while enabling non-interactive public verifiability of participant honesty. PVGSS scheme offers significant potential to advance the fields of blockchain and applied cryptography, such as attribute-based cryptosystem, fine-grained MPC and on-chain secret escrow. Intuitively, we first build two GSS schemes by leveraging recursive Shamir secret sharing and linear secret sharing scheme. Then, we encrypt GSS shares and generate the corresponding non-interactive zero-knowledge proofs. Furthermore, we innovatively apply the GSS reconstruction algorithm to show all encrypted shares bind to the dealer\u27s secret, with only verification complexity, where is the number of leaf nodes in the access structure . To exemplify the practical applicability, we implement a decentralized exchange (DEX) protocol, where fairness and accountable arbitration are considered. Our benchmarks on the BN128 curve demonstrate the computational efficiency of PVGSS schemes, while Ethereum gas cost analysis confirms the viability of the DEX implementation
Secret-Key PIR from Random Linear Codes
Get PDFPrivate information retrieval (PIR) allows to privately read a chosen bit from an -bit database with bits of communication. Lin, Mook, and Wichs (STOC 2023) showed that by preprocessing into an encoded database , it suffices to access only bits of per query. This requires , and even larger server circuit size.
We consider an alternative preprocessing model (Boyle et al. and Canetti et al., TCC 2017), where the encoding depends on a client\u27s short secret key. In this secret-key PIR (sk-PIR) model we construct a protocol with communication, for any constant , from the Learning Parity with Noise assumption in a parameter regime not known to imply public-key encryption. This is evidence against public-key encryption being necessary for sk-PIR.
Under a new conjecture related to the hardness of learning a hidden linear subspace of with noise, we construct sk-PIR with similar communication and encoding size in which the server is implemented by a Boolean circuit of size . This is the first candidate PIR scheme with such a circuit complexity
GIGA Protocol: Unlocking Trustless Parallel Computation in Blockchains
Get PDFThe scalability of modern decentralized blockchain systems is constrained by the requirement that the participating nodes execute the entire chains transactions without the ability to delegate the verification workload across multiple actors trustlessly. This is further limited by the need for sequential transaction execution and repeated block validation, where each node must re-execute all transactions before accepting blocks, also leading to delayed broadcasting in many architectures.
Consequently, throughput is limited by the capacity of individual nodes, significantly preventing scalability.
In this paper, we introduce GIGA, a SNARK-based protocol that enables trustless parallel execution of transactions, processing non-conflicting operations concurrently, while preserving security guarantees and state consistency. The protocol organizes transactions into non-conflicting batches which are executed and proven in parallel, distributing execution across multiple decentralized entities. These batch proofs are recursively aggregated into a single succinct proof that validates the entire block.
As a result, the protocol both distributes the execution workload and removes redundant re-execution from the network, significantly improving blockchain throughput while not affecting decentralization.
Performance estimates demonstrate that, under the same system assumptions (e.g., consensus, networking, and virtual machine architecture) and under high degrees of transaction parallelism (i.e., when most transactions operate on disjoint parts of the state), our protocol may achieve over a 10000x throughput improvement compared to popular blockchain architectures that use sequential execution models, and over a 500x improvement compared to blockchain architectures employing intra-node parallelization schemes.
Furthermore, our protocol enables a significant increase in transaction computational complexity, unlocking a wide range of use cases that were previously unfeasible on traditional blockchain architectures due to the limited on-chain computational capacity.
Additionally, we propose a reward mechanism that ensures the economic sustainability of the proving network, dynamically adjusting to computational demand while fostering competition among provers based on cost-efficiency and reliability