Abstract With the rising volume of transactions on blockchains, signature verification becomes a critical bottleneck of efficiency, hindering scalability and performance. This paper presents a general approach to batch verification of arbitrary signatures on blockchain. By leveraging the memory-friendliness of incremental verifiable computation (IVC) and optimizing for blockchain environments, the proposed scheme can enhance scalability, reduce memory consumption, and ensure compatibility with common devices while supporting an arbitrary number of signature verifications. This approach allows for the concurrent generation of IVC proofs while receiving signatures from other nodes, making it particularly well-suited for low-latency blockchain applications. As a concrete instantiation of our approach, we introduce BEATS (Batch ECDSA Transaction verification Scheme), where the underlying SNARK is instantiated by Spartan with Bulletproof commitment. Our implementation, evaluated on a virtual machine with 8 cores and 16 GB RAM, shows significant performance gains compared to Spartan BP , which is the direct construction using Spartan with Bulletproof commitment to verify a batch of ECDSA. The comparison shows that BEATS speeds up the prover by 3–7 times and the verifier by 48–240 times when handling up to 2 11 ECDSA signatures, the maximum batch size supported by Spartan BP . For larger batches exceeding 2 10 , our scheme outperforms the baseline approach, which verifies ECDSA signatures one by one without any proof system. Our verifier achieved a speedup of 21–174 times compared to the baseline as the batch size grows to 2 20 . Furthermore, BEATS exhibits a remarkably low memory footprint, with peak memory usage remaining below 1 GB.

Local differential privacy (LDP) involves users perturbing their inputs to provide plausible deniability of their data. However, this also makes LDP vulnerable to poisoning attacks. In this paper, we first introduce novel poisoning attacks for ranking estimation. These attacks are intricate, as fake attackers do not merely adjust the frequency of target items. Instead, they leverage a limited number of fake users to precisely modify frequencies, effectively altering item rankings to maximize gains. To tackle this challenge, we introduce the concepts of attack cost and optimal attack item (set), and propose corresponding strategies for kRR, OUE, and OLH protocols. For kRR, we iteratively select optimal attack items and allocate suitable fake users. For OUE, we iteratively determine optimal attack item sets and consider the incremental changes in item frequencies across different sets. Regarding OLH, we develop a harmonic cost function based on the pre-image of a hash to select that supporting a larger number of effective attack items. Lastly, we present an attack strategy based on confidence levels to quantify the probability of a successful attack and the number of attack iterations more precisely. We demonstrate the effectiveness of our attacks through theoretical and empirical evidence, highlighting the necessity for defenses against these attacks. The source code and data have been made available at https://github.com/LDP-user/LDP-Ranking.git.

Abstract The lattice-based cryptographic accumulators, which enable short zero-knowledge arguments of membership, have numerous applications in post-quantum privacy-preserving protocols. However, most efficient quantum-safe zero-knowledge arguments are PCP-based systems and rely on non-falsifiable assumptions. For non-PCP-based constructions using the state-of-the-art techniques on compressing lattice-based zero-knowledge proofs, the concrete size of the resulting proof for accumulators with $2^{32}$ members is at least 500 KB. In this paper, we propose a compact non-PCP zero-knowledge proof for the lattice-based Merkle-tree, which leads to an efficient post-quantum cryptographic accumulator. The complexity of our construction is logarithmic in $l\cdot n_{s}$, where $l$ and $n_{s}$ denote the depth of the underlying Merkle-tree and the size of a node, respectively, and the concrete size is only $143.7\ $KB when $l=32$. In particular, we provide an improved lattice-based Bulletproof with efficient knowledge extraction, which allows large challenge space but small soundness slack. Furthermore, the amortized technique can be applied to the Bulletproof without breaking the knowledge soundness due to our improved knowledge extraction. As a direct application, we present a practical lattice-based ring signature, which can achieve logarithmical signing/verifying computational complexity with the number of the ring, while the state-of-the-art constructions (CRYPTO 21) have linear computational complexity.

We provide a strong security notion for broadcast encryption, called adaptive security in the multichallenge setting (MA-security), where the adversary can adaptively have access to the key generation oracle and the encryption oracle many times (multichallenge). The adversary specially can query for the challenge ciphertexts on different target user sets adaptively, which generalizes the attacks against broadcast encryptions in the real world setting. Our general result shows that the reduction of the adaptive secure broadcast encryption will lose a factor of q in the MA setting, where q is the maximum number of encryption queries. In order to construct tighter MA-secure broadcast encryptions, we investigate Gentry and Water’s transformation and show that their transformation can preserve MA-security at the price of reduction loss on the advantage of the underlying symmetric key encryption. Furthermore, we remove the q -type assumption in Gentry and Water’s semistatically secure broadcast encryption by using Hofheinz-Koch-Striecks techniques. The resulting scheme instantiated in a composite order group is MA-secure with constant-size ciphertext header.