Abstract Fully Homomorphic Encryption (FHE) enables arbitrary computations on encrypted data, a paradigm that Multi-Key FHE (MKFHE) extends to the decentralized setting by supporting operations on ciphertexts encrypted under multiple, distinct keys. However, the high computational cost of bootstrapping remains a major bottleneck, especially in the multi-key scenario where blind rotation is the dominant overhead. To address this, we propose a novel and parallel-friendly blind rotation scheme based on the NTRU assumption for efficient MKFHE bootstrapping. Our core technical contribution is a grouped inner product algorithm optimized for automorphism-based blind rotation, which reorganizes hybrid product storage and extends the external product to be compatible with both NTRU and MK-RLWE ciphertexts. Our parallelized algorithm reduces the time complexity from O ( n ) to $$O(\sqrt{n})$$ O ( n ) . Our scheme demonstrates significant improvements over prior MKFHE works in both computational efficiency and storage requirements. At a 100-bit security level with $$k=8$$ k = 8 participants, our scheme achieves a ciphertext bootstrapping time of 0.048 seconds, representing a $$6.8 \times$$ 6.8 × speedup compared to Kwak et al.’s state-of-the-art work. Furthermore, our scheme substantially reduces storage overhead, requiring only 81.5MB for evaluation keys ( $$1.7 \times$$ 1.7 × smaller) and 64KB for re-linearization keys ( $$6.0 \times$$ 6.0 × smaller) relative to Kwak et al.’s implementation.

Abstract Toward practical and client-friendly single-server private information retrieval, we introduce FlashPIR, a scheme achieving both low client overhead and high server throughput. Constructed based on fully homomorphic encryption, our protocol possesses two distinct advantages: First, a majority of the resource-intensive computations can be performed in an offline phase, prior to query reception, significantly reducing the online response time. Second, database updates operate independently of clients, with low client computational overhead remaining nearly constant regardless of the database scale. We conducted comprehensive experiments to evaluate the performance of FlashPIR. The results demonstrate that for database sizes of 256 MB, our scheme achieves a throughput $$2.6\times$$ 2.6 × greater than KsPIR (Luo et al., CCS 2024) and $$18.5\times$$ 18.5 × greater than Spiral (Menon and Wu, S&P 2022).

Private Function Encryption (PFE) enables two parties, one holding a private input$x$and the other in possession of a private function$f$, to compute$f(x)$in such that each party learns nothing substantial beyond$f(x)$. PFE is typically achieved by evaluating Yao's two-party computation protocol over a universal circuit that encodes the private function into a private input. Thus, the efficiency of the PFE protocol highly relies on the size of the underlying universal circuit. A universal circuit (UC) is a general-purpose circuit that can simulate arbitrary circuits (up to a certain size$n$). In 1976, Valiant provided a recursive construction of universal circuits and gave a theoretical construction of UC of asymptotic (multiplicative) size$4.75 n\log n$respectively, which matches the asymptotic lower bound$\Omega (n\log n)$up to some constant factor. More recently, (Kiss et al. 2016) validated the practicality of universal circuits in real-world privacy-preserving applications. Subsequent work by (Günther et al. 2017) and (Alhassan et al. 2020) enhanced UCs’ practicality through hybrid constructions with various optimizations. This work focuses on optimizing the size efficiency of universal circuits. Our contributions are three-fold:•Optimized component:We first optimize the underlying component of Valiant's universal circuits to achieve an asymptotic size of$4.5 n\log n$4.5nlogn.•More efficient framework:We propose an improved framework for constructing universal circuits, under which we give a UC construction of asymptotic size$3n\log n$3nlogn. This improves the previous state-of-the-art construction by 33%, which corresponds to the same fraction of reduction in the communication cost of UC-based PFE protocols.•Tigher lower bound:To complement our constructive results, we show that the (multiplicative) size of the universal circuits is lower bounded by$2n\log n$2nlogn.We implement the 2-way universal circuits and evaluate their performance against other implementations, confirming our theoretical analysis.

In this paper, we initiate the study of the Rank Decoding (RD) problem and Low Rank Parity Check (LRPC) codes with blockwise structure in rank-based cryptosystems. First, we introduce the blockwise errors ($\ell $-errors) where each error consists of$\ell $blocks of coordinates with direct-sum supports, and define the blockwise RD ($\ell $-RD) problem as a natural generalization of the RD problem whose solutions are$\ell $-errors (note that the RD problem is actually a special$\ell $-RD problem with$\ell =1$). We adapt the typical attacks on the RD problem to the$\ell $-RD problem, and find that the blockwise structure does not ease the problem too much: the$\ell $-RD problem is still exponentially hard for appropriate choices of$\ell \gt 1$. Second, we introduce the blockwise LRPC ($\ell $-LRPC) codes as generalizations of the LPRC codes whose parity-check matrices can be divided into$\ell $sub-matrices with direct-sum supports, i.e., the intersection of two subspaces generated by the entries of any two sub-matrices is a null space, and investigate the decoding algorithms for$\ell $-errors. We find that the gain of using$\ell $-errors in decoding capacity outweighs the complexity loss in solving the$\ell $-RD problem, which makes it possible to design more efficient rank-based cryptosystems with flexible choices of parameters. As an application, we show that the two rank-based cryptosystems submitted to the NIST PQC competition, namely, RQC and ROLLO, can be greatly improved by using the ideal variants of the$\ell $-RD problem and$\ell $-LRPC codes. Concretely, for 128-bit security, our RQC has total public key and ciphertext sizes of 2.5 KB, which is not only about 50% more compact than the original RQC, but also smaller than the NIST Round 4 code-based submissions HQC, BIKE, and Classic McEliece.

Abstract The MinRank problem is an NP-complete problem that is prevalent in multivariate cryptography and its goal is to find a non-zero linear combination of given a series of matrices over a ring such that the obtained matrix has a small rank. At Asiacrypt 2001, two Zero-Knowledge Proofs of Knowledge (ZKPoK) for the MinRank problem are proposed, and we call them MRZK and MRZK$^{\dagger }$, respectively. The latter is an improved version of the proof size of the former. However, the efficiency of MRZK$^{\dagger }$ has been open and not analyzed. While the MRZK protocol is secure, it must be repeated many times due to the soundness error $2/3$, which leads to the large proof size. For 128-bit security, the MRZK protocol is executed at least 219 iterations and the proof size is about 32 KB. In this paper, we first show that the efficiency of MRZK$^{\dagger }$ is impractical due to unreasonable parameter size. However, when the parameter size is tuned and the efficiency is improved, an imposter can be efficiently constructed. Then, to alleviate the large proof size of MRZK, inspired by the technique designing ZKPoK (Eurocrypt 2020), we propose a sigma protocol with helper to prove the solution to the MinRank problem. Finally, we transform the sigma protocol with helper into a standard ZKPoK (MRZK$^{\sharp }$) by removing the helper. The MRZK$^{\sharp }$ protocol can achieve any small soundness error and enjoy the proof size of about 15 KB (53% improvement over MRZK).

The module learning with errors (MLWE) problem has attracted significant attention and has been widely used in building a multitude of lattice‐based cryptographic primitives. The hardness of the MLWE problem has been established for several variants, but most of the known results require the seed distribution (i.e., the distribution of matrix A ) to be the uniform distribution. In this paper, we show that under the Module‐N‐th degree Truncated polynomial Ring Units (NTRU) (MNTRU) assumption, the search MLWE problem can still be hard for some distributions that are not (even computationally indistinguishable from) the uniform distribution. Specifically, we show that if the seed distribution is a semiuniform distribution (namely, the seed distribution can be publicly derived from and has a “small difference” to the uniform distribution), then for appropriate settings of parameters, the search MLWE problem is hard under the MNTRU assumption. Moreover, we also show that under the appropriate settings of parameters, the search learning with errors over rings problem with semiuniform seeds can still be hard under the NTRU assumption due to our results for the search MLWE problem with semiuniform seeds being rank‐preserving.

We introduce the abstract framework of decentralized smart contracts system with balance and transaction amount hiding property over account-model blockchain. To build a concrete system with such properties, we utilize a homomorphic public-key encryption scheme and construct a highly efficient non-interactive zero knowledge (NIZK) argument based upon the encryption scheme to ensure the validity of the transactions. Our NIZK scheme is perfect zero knowledge in the common reference string model, while its soundness holds in the random oracle model. Compared to previous similar constructions, our proposed NIZK argument dramatically improves the time efficiency in generating a proof, at the cost of relatively longer proof size.

Correlated oblivious transfer (COT) is a crucial building block for secure multi-party computation (MPC) and can be generated efficiently via OT extension. Recent works based on the pseudorandom correlation generator (PCG) paradigm presented a new way to generate random COT correlations using only communication sublinear to the output length. However, due to their high computational complexity, these protocols are only faster than the classical IKNP-style OT extension under restricted network bandwidth. In this paper, we propose new COT protocols in the PCG paradigm that achieve unprecedented performance. \em With $50$ Mbps network bandwidth, our maliciously secure protocol can produce one COT correlation in $22$ nanoseconds. More specifically, our results are summarized as follows: \beginenumerate \item We propose a semi-honest COT protocol with sublinear communication and linear computation. This protocol assumes primal-LPN and is built upon a recent VOLE protocol with semi-honest security by Schoppmann et al. (CCS 2019). We are able to apply various optimizations to reduce its communication cost by roughly $15\times$, not counting a one-time setup cost that diminishes as we generate more COT correlations. \item We strengthen our COT protocol to malicious security with no loss of efficiency. Among all optimizations, our new protocol features a new checking technique that ensures correctness and consistency essentially for free. In particular, our maliciously secure protocol is only \em $1-3$ nanoseconds slower for each COT. \item We implemented our protocols, and the code will be publicly available at EMP toolkit. We observe at least $9\times$ improvement in running time compared to the state-of-the-art protocol by Boyle et al. (CCS 2019) in both semi-honest and malicious settings under any network faster than $50$ Mbps. \endenumerate With this new record of efficiency for generating COT correlations, we anticipate new protocol designs and optimizations will flourish on top of our protocol.

Recent works on distributed garbling have provided highly efficient solutions for constant-round MPC tolerating an arbitrary number of corruptions. In this work, we improve upon state-of-the-art protocols in this paradigm for further performance gain. First, we propose a new protocol for generating authenticated AND triples, which is a key building block in many recent works. \beginitemize \item We propose a new authenticated bit protocol in the two-party and multi-party settings from bare IKNP OT extension, allowing us to reduce the communication by about $24%$ and eliminate many computation bottlenecks. We further improve the computational efficiency for multi-party authenticated AND triples with cheaper and fewer consistency checks and fewer hash function calls. \item We implemented our triple generation protocol and observe around $4\times$ to $5\times$ improvement compared to the best prior protocol in most settings. For example, in the two-party setting with 10 Gbps network and 8 threads, our protocol can generate more than $4$ million authenticated triples per second, while the best prior implementation can only generate $0.8$ million triples per second. In the multi-party setting, our protocol can generate more than $37000$ triples per second over 80 parties, while the best prior protocol can only generate the same number of triples per second over 16 parties. \enditemize We also improve the state-of-the-art multi-party authenticated garbling protocol. \beginitemize \item We take the first step towards applying half-gates in the multi-party setting, which enables us to reduce the size of garbled tables by $2κ$ bits per gate per garbler, where κ is the computational security parameter. This optimization is also applicable in the semi-honest multi-party setting. \item We further reduce the communication of circuit authentication from $4ρ$ bits to $1$ bit per gate, using a new multi-party batched circuit authentication, where ρ is the statistical security parameter. Prior solution with similar efficiency is only applicable in the two-party setting. \enditemize For example, in the three-party setting, our techniques can lead to roughly a $35%$ reduction in the size of a distributed garbled circuit.

Though the electronic technologies have undergone fast developments in recent years, mobile devices such as smartphones are still comparatively weak in contrast to desktops in terms of computational capability, storage, etc., and are not able to meet the increasing demands from mobile users. By integrating mobile computing and cloud computing, mobile cloud computing (MCC) greatly extends the boundary of the mobile applications, but it also inherits many challenges in cloud computing, e.g., data privacy and data integrity. In this paper, we leverage several cryptographic primitives such as a new type-based proxy re-encryption to design a secure and efficient data distribution system in MCC, which provides data privacy, data integrity, data authentication, and flexible data distribution with access control. Compared to traditional cloud-based data storage systems, our system is a lightweight and easily deployable solution for mobile users in MCC since no trusted third parties are involved and each mobile user only has to keep short secret keys consisting of three group elements for all cryptographic operations. Finally, we present extensive performance analysis and empirical studies to demonstrate the security, scalability, and efficiency of our proposed system.

Summary With the rapid development of cloud computing, cloud storage has become a cost‐effective solution for many users with the demand of data storage. However, there are still two main concerns for users with sensitive/private data: (1) Is it secure to store private data in public cloud storages? (2) Is there an efficient way to share private data with other specified users? In the past years, several papers in the literature have used proxy re‐encryption (PRE) to address these two concerns, where the efficiency of the underlying PRE scheme is usually a bottleneck of the overall performance of cloud storages. In this paper, we dedicate to design a secure and practical PRE scheme for cloud‐based data‐sharing. First, we discuss a ‘pitfall’ in the security proof of several existing PREs. Then, we give a general framework for proving the chosen ciphertext attacks (CCA) security of single‐hop unidirectional PRE schemes. Finally, we propose a practical PRE scheme that is proven secure against CCA under the computational Diffie–Hellman problem in the random oracle model. We evaluate the performance of our PRE scheme both in theoretical comparisons with related schemes and in implementations at several security levels. The results indicate that our scheme can be practical in cloud‐based data‐sharing. Copyright © 2014 John Wiley & Sons, Ltd.

In a decentralized attribute-based encryption (ABE) system, any party can act as an authority by creating a public key and issuing private keys to different users that reflect their attributes without any collaboration. Such an ABE scheme can eliminate the burden of heavy communication and collaborative computation in the setup phase of multiauthority ABE schemes, thus is considered more preferable. Recently in IEEE Transactions Parallel Distributed Systems, Han et al. proposed an interesting privacy-preserving decentralized key-policy ABE scheme, which was claimed to achieve better privacy for users and to be provably secure in the standard model. However, after carefully revisiting the scheme, we conclude that their scheme cannot resist the collusion attacks, hence fails to meet the basic security definitions of the ABE system.

Sahai and Waters [6] proposed Attribute-Based Encryption (ABE) as a new paradigm of encryption algorithms that allow the sender to set a policy describing who can decrypt a particular ciphertext. In this paper, we first propose a ciphertext policy attribute-based encryption (CP-ABE) scheme from lattices, which supports flexible threshold access policies on literal (or boolean) attributes. Then we extend it to support multi-valued attributes without increasing the public key and ciphertext size. Our scheme's master secret key has only one matrix despite of the number of the system's attributes. The security of our schemes is based on the worst-case hardness on lattices.