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).

Abstract Time-release cryptography is a flourishing research area with a long history and has been extensively studied. In this work, we enrich it by introducing a novel concept: a time-release zero-knowledge proof (TRZKP). A TRZKP is a non-interactive zero-knowledge proof that allows one to publish a proof for a given relation $$R_\mathcal {L}$$ R L , such that anyone can only finish the verification after time $$\textbf{T}$$ T by performing a sequential computation. This work formalizes the concept of TRZKP and presents light constructions for the time-release version of any NIZK obtained from a public-coin protocol via Fiat-Shamir transformation. TRZKPs can be applied to provide time-release authentication, for example, they can be employed to construct verifiable timed signatures (VTS), introduced by Thyagarajan et al. (CCS’20). Through both theoretical and practical analysis, our construction has advantages over existing VTS for Fiat-Shamir signatures. Specifically, when instantiated with Shnorr signature, our VTS signing time remains basically unchanged as the delay time grows, and is preferable for longer delay times; our VTS verification time is significantly small (on the level of milliseconds, while existing works on the level of seconds), and our VTS size is 67 times smaller than the state-of-the-art. It also has the time-verifiability property, which ensures the signature is recoverable after the specified time.

Abstract Recent years have seen the widespread adoption of zkSNARKs constructed over small fields, including but not limited to, the Goldilocks field, small Mersenne prime fields, and tower of binary fields. Their appeal stems primarily from their efficacy in proving computations with small bit widths, which facilitates efficient proving of general computations and offers significant advantages, notably yielding remarkably fast proving efficiency for tasks such as proof of knowledge of hash preimages. Nevertheless, employing these SNARKs to prove algebraic statements (e.g., RSA, ECDSA signature verification) presents efficiency challenges, particularly in critical applications like zk-bridges and zkVMs that require verifying standard cryptographic primitives. To address this problem, we first define a new circuit model: arithmetic circuits with additional exponentiation gates . These gates serve as fundamental building blocks for establishing more intricate algebraic relations. Then we present a Hash-committed Commit-and-Prove (HCP) framework to construct Non-interactive Zero-knowledge (NIZK) proofs for the satisfiability of these circuits. Specifically, when proving knowledge of group exponentiations in discrete logarithm hard groups and RSA groups, compared to verifying complex group exponentiations within SNARK circuits, our approach requires proving only more lightweight computations within the SNARK, such as zk-friendly hash functions (e.g., Poseidon hash function). The number of these lightweight computations depends solely on the security parameter. This differentiation leads to substantial speedups for the prover relative to direct SNARK methods, while maintaining competitive proof size and verification cost.

Verifiable Computation over encrypted data (VCoed) has two popular paradigms: SNARK-FHE (applying SNARKs to prove FHE operations) and FHE-SNARK (homomorphically evaluating SNARK proofs). For the existing works, FHE-SNARK has a much better efficiency compared to SNARK-FHE.

Abstract Zero knowledge succinct non-interactive arguments of knowledge protocol (zk-SNARK) is an application oriented variant of zero knowledge proof, which enables a prover to convince a verifier that a statement is true, without revealing any other information beyond the correctness of the statement itself. Due to its powerful capabilities and high efficiency, it has been widely deployed in various blockchain based applications to provide privacy and scalability. While these applications place high demands on small proof size, fast verification and decentralization, currently available zk-SNARK with the shortest proof size and the fastest verification speed is in the common reference string (CRS) model, that is they require the trusted setup. After the pioneering results proposed by Bellare et al. in ASIACRYPT 2016, there have been lots of efforts to construct zk-SNARKs that satisfy subversion zero knowledge (S-ZK) and standard soundness from the zk-SNARK in the CRS model. These constructions could be regarded secure in the bare public key (BPK) model because that the equivalence between S-ZK in the CRS model, and uniform non-black-box zero knowledge in the BPK model has been proved by Abdolmaleki et al. in PKC 2020. Thus, compared to the CRS model, the BPK model better characterizes decentralized blockchain based application such as cryptocurrencies and anonymous credentials. In this study, by leveraging the power of random oracle (RO) model, we proposed the first publicly verifiable non-uniform ZK zk-SNARK scheme in the BPK model maintaining comparable efficiency with its conventional counterpart, which can also be compatible with the well-known transformation proposed by Bitansky et al. in TCC 2013 to obtain an efficient designated-verifier zk-SNARK. We achieve this goal by only adding a constant number of elements into the CRS, and using an unconventional but natural method to transform Groth’s zk-SNARK in EUROCRYPT 2016. In addition, we propose a new speed-up technique that provides a trade-off. Specifically, if a logarithmic number of elements are added into the CRS, according to different circuits, the CRS verification time in our construction could be approximately 9–23% shorter than that in the conventional counterpart.

Abstract In this paper, we construct a 6-round simultaneously resettable sound resettable $$(T, \epsilon )$$ ( T , ϵ ) -zero knowledge protocol for $$\mathsf {NP \cap coNP}$$ NP ∩ coNP in the Public Key model under standard assumptions, comparing with the 27-round simultaneously resettable zero knowledge protocol in the BPK model by Deng et al. in 2011, we have achieved a significant reduction in the round complexity. Our model assumes that both prover and verifier hold public keys, we call it the Public Key model. It is a variation of the traditional BPK model where only the verifier is assumed to hold public keys. In the original BPK model, under the sub-exponential hardness assumption of factoring, we construct a 2-round simultaneously resettable sound resettable $$(T,\epsilon )$$ ( T , ϵ ) -zero knowledge protocol for $$\textsf{NP}$$ NP .

Abstract Round complexity is one of the fundamental problems in zero-knowledge (ZK) proof systems. Non-malleable zero-knowledge (NMZK) protocols are ZK protocols that provide security even when man-in-the-middle adversaries interact with a prover and a verifier simultaneously. It is known that the first constant-round public-coin NMZK arguments for NP can be constructed by assuming the existence of collision-resistant hash functions (Pass, R. and Rosen, A. (2005) New and Improved Constructions of Non-Malleable Cryptographic Protocols. In Gabow, H.N. and Fagin, R. (eds) Proc. 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 2224, 2005, pp. 533542. ACM) and has relatively high round complexity; the first four-round private-coin NMZK arguments for NP can be constructed in the plain model by assuming the existence of one-way functions (Goyal, V., Richelson, S., Rosen, A. and Vald, M. (2014) An Algebraic Approach to Non-Malleability. In 55th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2014, Philadelphia, PA, USA, October 1821, 2014, pp. 4150. IEEE Computer Society and Ciampi, M., Ostrovsky, R., Siniscalchi, L. and Visconti, I. (2017) Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds. In Kalai, Y. and Reyzin, L. (eds) Theory of Cryptography15th Int. Conf., TCC 2017. Lecture Notes in Computer Science, Baltimore, MD, USA, November 1215, 2017, Part I, Vol. 10677, pp. 711742. Springer). In this paper, we present a six-round public-coin NMZK argument of knowledge system assuming the existence of collision-resistant hash functions and a three-round private-coin NMZK argument system from multi-collision resistance of hash functions assumption in the keyless setting.

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.

Dual receiver encryption (DRE) is an important cryptographic primitive introduced by Diament et al. at CCS’04, which allows two independent receivers to decrypt a same ciphertext to obtain the same plaintext. This primitive is quite useful in designing combined public key cryptosystems and denial of service attack-resilient protocols. In this paper, we obtain some results as follows. Using weak lattice-based programmable hash functions (wLPHF) with high min-entropy (Crypto’16), we give a generic IND-CCA secure DRE construction in the standard model. Furthermore, we get a concrete DRE scheme by instantiating a concrete wLPHF with high min-entropy. For DRE notion in the identity-based setting, identity-based DRE (IB-DRE), basing on lattice-based programmable hash functions (LPHF) with high min-entropy, we give a framework of IND-ID-CPA secure IB-DRE construction in the standard model. When instantiating with concrete LPHFs with high min-entropy, we obtain five concrete IB-DRE schemes.

Concurrent non-malleable zero-knowledge ( CNMZK ) considers the concurrent execution of zero-knowledge protocols in a setting even when adversaries can simultaneously corrupt multiple provers and verifiers. As far as we know, the round complexity of all the constructions of CNMZK arguments for NP is at least ω (log n ). In this paper, we provide the first construction of a constant-round concurrent non-malleable zero-knowledge argument for every language in NP . Our protocol relies on the existence of families of collision-resistant hash functions , one-way permutations and indistinguishability obfuscators . As an additional contribution, we study the composition of two central notions in zero knowledge, the simultaneously resettable zero-knowledge and non-malleable zero-knowledge , which seemingly have stronger proved security guarantees. We give the first construction of a constant-round simultaneously-resettable non-malleable zero-knowledge . To the best of our knowledge, this is the first study to combine the two security concepts described above together in the zero-knowledge protocols.

Android is a modern and popular software platform for smart phones. To manage information and features on smart phones, Android employs intent-based mechanism for inter-application or intra-application communication and provides a permission-based security model that requires each application to explicitly request permissions in its manifest file. However, misconfiguration defined in manifest files and that embedded in application code may result in vulnerabilities due to developer confusion and general misuse of the features provided by Android. In this paper, we propose a logic-programming-based approach to analyze smart phones and discover misconfiguration vulnerabilities in Android manifest file and application code. To enable misconfiguration vulnerability analysis and detection, we develop a static technique to extract security related information from application code, and employ logic predicates to describe various vulnerabilities. Based on this approach, we developed a tool called SADroid to systematically analyze and detect misconfiguration vulnerabilities in Android smart phones. Our results with two representative phones show that the inherent weakness of Android permission model and developers' programming errors make Android vulnerable to some attacks.

The pointer analysis finds out what a pointer points to in a program. This analysis is useful in static program analysis, bug detection, source navigations and so on. We propose an approach to generate new constraints for one points-to and we use the constraints to refine it. The constraints can be used to refine other program analysis as well. This new constraints are based on the sequencings among the edges on a CFL-path. We propose algorithms to compute the sequencing relations for a CFL-path. Based on the news constraints, we propose a method to check the context-sensitivity of a points to by checking whether there is a trace of the C program satisfying the sequencing relations. We implement our approach in a proto-type tool called TCPA to evaluate the efficiency of our approach. Our approach can be useful in static program analysis, source code bug detection and source code understanding.

Canetti, Goldreich, Goldwasser, and Micali (STOC 2000) introduced the notion of resettable zero-knowledge proofs, where the protocol must be zero-knowledge even if a cheating verifier can reset the prover and have several interactions in which the prover uses the same random tape. Soon afterwards, Barak, Goldreich, Goldwasser, and Lindell (FOCS 2001) studied the closely related notion of resettable soundness, where the soundness condition of the protocol must hold even if the cheating prover can reset the verifier to have multiple interactions with the same verifier's random tape. The main problem left open by this work was whether it is possible to have a single protocol that is simultaneously resettable zero knowledge and resettably sound. We resolve this question by constructing such a protocol. At the heart of our construction is a new non-black-box simulation strategy, which we believe to be of independent interest. This new strategy allows for simulators which "marry'' recursive rewinding techniques (common in the context of concurrent simulation) with non-black-box simulation. Previous non-black-box strategies led to exponential blowups in computational complexity in such circumstances, which our new strategy is able to avoid.