Decentralized e-voting enables secure and transparent elections without relying on trusted authorities, with blockchain emerging as a popular platform. It has compelling applications in Decentralized Autonomous Organizations (DAOs), where governance relies on voting with blockchain-issued tokens. Quadratic voting (QV), a mechanism that mitigates the dominance of large token holders, has been adopted by many DAO elections to enhance fairness. However, current QV systems deployed in practice publish voters' choices in plaintext with digital signatures. The open nature of all ballots comprises voter privacy, potentially affecting voters' honest participation. Prior research proposes using cryptographic techniques to encrypt QV ballots, but they work in a centralized setting, relying on a trusted group of tallying authorities to administrate an election. However, in DAO voting, there is no trusted third party.

Zero-knowledge proofs (ZKPs) have been used to protect the integrity of machine learning (ML) models. However, existing ZKPs for ML are still inefficient, mainly due to the computational cost of evaluating non-linear functions. In this paper, we propose a ZKP framework for typical non-linear functions in ML, including Sigmoid, Softmax, etc. Compared to the state-of-the-art Hao et al. (USENIX Security ’24), our protocols obtain 115.6-2384.4× and 296.8-4104.7× runtime improvements for prover and verifier, respectively, with a 37.91269.5× reduction in proof size.

Abstract Privacy-preserving deep learning based on secure multi-party computation (MPC) has emerged as a critical research focus in recent years. While existing approaches predominantly employ additive secret sharing with a fixed number of parties, they have yet to fully leverage the more efficient Shamir-based schemes. However, the adoption of Shamir secret sharing faces two key challenges: limitations of decimal computation and signed number representation. Furthermore, current solutions often lack optimization for specific computational modules and rely on conventional methods ill-suited for MPC environments. To address these issues, this paper proposes a fixed-point decimal-supported Shamir secret sharing scheme. A key innovation is our truncation algorithm, which effectively manages the expanded decimal digits resulting from multiplication operations, enabling comprehensive fixed-point arithmetic within the Shamir-based MPC framework. Extensive large-scale simulations validate the accuracy of our truncation method. Moreover, we introduce optimized protocols for two crucial deep learning operations: convolution and Softmax function computation. Our convolution protocol leverages the Winograd algorithm to significantly reduce multiplication gate count, yielding over 50% performance improvement. For Softmax computation, we extend existing two-party protocols to a multi-party Shamir setting, developing the nQSMax algorithm. This algorithm achieves exceptional accuracy exceeding 99% within seconds, requiring only a few iterations.

Abstract Inner product arguments are core building blocks of numerous cryptographic primitives and therefore minimizing their complexity is a central goal in this research area. In this paper, we follow the work of Kim et al. (ASIACRYPT’22) and propose the first inner product argument having sublogarithmic communication complexity and sub-square-root verifier complexity simultaneously. We first devise a new subvector combination method for recursion and utilize an aggregated multi-exponentiation argument to prove some committed group elements are valid. We then modify the commitment keys in inner product arguments to be structured and reduce the verifier complexity by delegating the costly computations to the prover. Compared with the state-of-the-art inner product arguments, our protocol is highly competitive in terms of asymptotic complexity.

Zero-knowledge range proof (ZKRP) asserts that a committed integerVlies in a given range like$[{0, 2^{n}-1}]$without other leakages ofV. It is vital in various privacy-preserving systems. Moving forward, the quest for post-quantum security is still in its infancy; the proof size of state-of-the-art lattice-based ZKRP (Lyubashevsky et al., CCS 20 and Couteau et al., Eurocrypt 21) remains linear inn, directly impacting the long-term sustainability in applications such as immutable ledgers. Confronting this unresolved impasse, we propose SHARP-PQ,i.e., succinct hash-based arbitrary-range proof with post-quantum security. SHARP-PQ offers proof size poly-logarithmic ton, optimized batch proofs, and versatile (new) capabilities. Its success stems from the improved inner product argument and exploitation of homomorphism. Empirically, SHARP-PQ features at least$10\times $smaller proof size for multiple ranges over lattice-based ZKRPs while maintaining competitive prover and verifier times. SHARP-PQ also outperforms ZKRPs directly constructed from hash-based generic zero-knowledge proofs at most$10 \times $.

Abstract Byzantine ordered consensus, introduced by Zhang et al. (OSDI 2020), is a new consensus primitive that additionally guarantees a correctness specification of transaction order, allowing nodes to assign fairly an ordering indicator to the committed transaction. Zhang et al. also presented a concrete Byzantine ordered consensus protocol called Pompē in the partially synchronous network model. However, Pompē cannot prevent an adversary from manipulating message delivery time. In this paper, we present Chronos, the first Byzantine ordered consensus protocol in the asynchronous network model, where an adversary can arbitrarily manipulate message delivery time. To construct Chronos, we propose a variant of asynchronous common subset called signal asynchronous common subset protocol, which guarantees the liveness of Chronos. We implement both Chronos and its baseline HoneyBadgerBFT using Go language and deploy them on 100 Amazon t3.medium instances distributed throughout 10 regions across the world. The experimental results show that Chronos is more efficient than HoneyBadgerBFT for small network, achieving peak throughput of 59 368 tx/s when the batch size is 100 000 and the number of nodes is 4, while the peak of HoneyBadgerBFT is 57 077 tx/s.

Zero-knowledge scalable transparent arguments of knowledge (zk-STARKs) are a promising approach to solving the blockchain scalability problem while maintaining security, decentralization and privacy. However, compared with zero-knowledge proofs with trusted setups deployed in existing scalability solutions, zk-STARKs are usually less efficient. In this paper, we introduce Ligerolight, an optimized zk-STARK for the arithmetic circuit satisfiability problem following the framework of Ligero (ACM CCS 2017) and Aurora (Eurocrypt 2019) based on interactive oracle proof, which could be used for blockchain scalability. Evaluations show that Ligerolight has performance advantages compared with existing zk-STARKs. The prover time is 30% faster than Aurora to generate proof for computing an authentication path of a Merkle tree with 32 leaves. The proof size is about 131KB, one-tenth of Ligero and 50% smaller than Aurora. The verifier time is 2 times as fast as Aurora. Underlying Ligerolight is a new batch zero-knowledge inner product argument, allowing to prove multiple inner product relations once. Using this argument, we build a batch multivariate polynomial commitment with poly-logarithmic communication complexity and verification. This polynomial commitment is particularly efficient when opening multiple points in multiple polynomials at one time, and may be of independent interest in constructing scalability solutions.

Abstract Inner product arguments allow a prover to prove that the inner product of two committed vectors equals a public scalar. They are used to reduce the complexity of many cryptographic primitives, such as range proofs. Range proofs are deployed in numerous applications to prove that a committed value lies in a certain range. As core building blocks, their complexity largely determines the performance of corresponding applications. In this paper, we have optimised the inner product argument with statement including two vector commitments (IPA tvc ) and range proof of Daza et al. (PKC’20), the inner product argument with statement including only one vector commitment (IPA ovc ) of Bünz et al. (S&P′18). For IPA tvc , we reduce the concrete communication complexity by 2 log 2 n field elements, where n is the vector dimension. For range proofs, we reduce the concrete communication and prover complexities by about 2 log 2 m field elements and 11 m field multiplications, respectively, where m is the bit length of range. For IPA ovc , we exponentially reduce the asymptotic verifier complexity from linear to logarithmic. Due to the asymptotic characteristics, our protocols are highly competitive when the vector dimension or bit length of range is large.

Recent Blockchain-based Internet of Vehicles (BIoV) solutions are proposed to provide the capabilities of trust management and incentive distribution for traffic information interaction in decentralized trustless Internet of Vehicles (IoV). However, existing trust management methods in BIoV are designed based on subjective user feedback, which is vulnerable to bad-mouthing and collusion attacks. Besides, these incentive strategies achieve accurate information interaction based on the game theory, yet it is challenging for the practical IoV scenario without completely explicit parameters. To address these issues, we propose TI-BIoV, a traffic information interaction system based on three blockchains for IoV with the nonsubjective trust evaluation and optimal incentive with partial inexplicit parameters. Specifically, a nonsubjective trust mechanism is designed based on the traffic information offset calculated by other related traffic information, which ensures the change of vehicle trust value without any subjective factors. On this basis, a trust-based consensus protocol, which selects entities with high trust values as participants, is given to realize the reliable public audit of transactions. According to traffic information accuracy measurements, we develop a$Q$-learning-based algorithm to encourage vehicles continuously submit accurate traffic information and optimally schedule the incentive for both platform and vehicle via training with incompletely explicit parameters of TI-BIoV. Finally, we analyze the security properties and common attacks of TI-BIoV and implement a prototype. The experimental results show that TI-BIoV achieves reliable consensus with nonsubjective trust evaluation and runs stably for a long time with two-sided incentive strategies.

The PRISM made the research of cryptography against subversion attacks flourish these years. In a subversion attack, surveillants can compromise the security of users’ systems by subverting implementations of cryptographic algorithms. While the scenario of a single‐surveillant has been researched by several works, the multi‐surveillant setting attracted less consideration. The authors have initialised this notion in previous work but assumed the surveillants to be completely isolated. In this study, the authors follow this idea and consider more realistic scenarios of the multi‐surveillant subversion, where surveillants are able to have limited communications. They propose the notions of queryable adversaries and conversational adversaries. In the first setting, adversaries can verify whether output is produced by a subverted implementation from others; in the latter setting, adversaries can have arbitrary conversations with each other without leaking their backdoors. Under the framework of ‘amalgamation and decomposition’, they design randomness generators that are secure against queryable adversaries and conversational adversaries, respectively, by adopting implementations from different sources intentionally. Based on the secure randomness generators, they construct symmetric encryption schemes that match the corresponding security definitions.

The application of cloud storage system has been deployed widely in recent years. A lot of electronic medical records (EMRs) are collected and uploaded to the cloud for scalable sharing among the authority users. It is necessary to guarantee the confidentiality of EMRs and the privacy of EMR owners. To achieve this target, we summarize a series of attack behaviors in the cloud storage system and present the security model against many types of unexpected privacy leakage. Privacy of unassailed EMRs is guaranteed in this model, and the influence of privacy leakage is controlled in a certain scope. We also propose a role-based access control scheme to achieve flexible access control on these private EMRs. One can access medical records only if his/her role satisfies the defined access policy, which implies a fine-grained access control. Theoretical and experimental analyses show the efficiency of our scheme in terms of computation and communication.

We put forth the notion of publicly evaluable pseudorandom functions (PEPRFs), which can be viewed as a counterpart of standard pseudorandom functions (PRFs) in the public-key setting. Briefly, PEPRFs are defined over domain X containing a language L associated with a hard relation [Formula: see text], and each secret key [Formula: see text] is associated with a public key [Formula: see text]. For any [Formula: see text], in addition to evaluate [Formula: see text] using [Formula: see text] as standard PRFs, one is also able to evaluate [Formula: see text] with [Formula: see text], x and a witness w for [Formula: see text]. We consider two security notions for PEPRFs. The basic one is weak pseudorandomness which stipulates a PEPRF cannot be distinguished from a real random function on uniformly random chosen inputs. The strengthened one is adaptive weak pseudorandomness which requires a PEPRF remains weak pseudorandom even when an adversary is given adaptive access to an evaluation oracle. We conduct a formal study of PEPRFs, focusing on applications, constructions, and extensions. ∙ We show how to construct chosen-plaintext secure (CPA) and chosen-ciphertext secure (CCA) public-key encryption (PKE) schemes from (adaptive) PEPRFs. The construction is simple, black-box, and admits a direct proof of security. We provide evidence that (adaptive) PEPRFs exist by showing constructions from injective trapdoor functions, hash proof systems, extractable hash proof systems, as well as a construction from puncturable PRFs with program obfuscation. ∙ We introduce the notion of publicly sampleable PRFs (PSPRFs), which is a relaxation of PEPRFs, but nonetheless imply PKE. We show (adaptive) PSPRFs are implied by (adaptive) trapdoor relations. This helps us to unify and clarify many PKE schemes from seemingly unrelated general assumptions and paradigms under the notion of PSPRFs. ∙ We explore similar extension on recently emerging constrained PRFs, and introduce the notion of publicly evaluable constrained PRFs, which, as an immediate application, implies attribute-based encryption. ∙ We propose a twist on PEPRFs, which we call publicly evaluable and verifiable functions (PEVFs). Compared to PEPRFs, PEVFs have an additional promising property named public verifiability while the best possible security degrades to unpredictability. We justify the applicability of PEVFs by presenting a simple construction of “hash-and-sign” signatures, both in the random oracle model and the standard model.

Abstract In this work, we generalize the paradigm of the hash proof system (HPS) proposed by Cramer and Shoup (EUROCRYPT 2002). In the center of our generalization, we lift a subset membership problem to a distribution‐distinguishing problem. Our generalized HPS clarifies and encompasses all the known public‐key encryption (PKE) schemes that essentially implement the idea of an HPS. Moreover, besides the existing smoothness property, we introduce an additional property named anonymity for HPS. As a natural application, we consider anonymity for PKE in the presence of key leakage and provide a generic construction of leakage‐resilient anonymous PKE from an anonymous HPS. We then extend our generalization to the identity‐based setting. Concretely, we generalize the paradigm of the identity‐based HPS (IB‐HPS) proposed by Boneh et al. (FOCS 2007) and Alwen et al. (EUROCRYPT 2010) and introduce anonymity for it. As an interesting application of the anonymous IB‐HPS, we consider security for PKE with keyword search (PEKS) in the presence of token leakage and provide a generic construction of leakage‐resilient secure PEKS from leakage‐resilient anonymous identity‐based encryption, which in turn is based on anonymous IB‐HPS. Copyright © 2013 John Wiley & Sons, Ltd.

In this paper, we introduce a general paradigm called identity-based extractable hash proof system (IB-EHPS), which is an extension of extractable hash proof system (EHPS) proposed by Wee (CRYPTO'10). We show how to construct identity-based key encapsulation mechanism (IB-KEM) from IB-EHPS in a simple and modular fashion. Our construction provides a generic method of building and interpreting CCA-secure IB-KEMs based on computational assumptions. As instantiations, we realize IB-EHPS from the bilinear Diffie–Hellman assumption and the modified bilinear Diffie–Hellman assumption, respectively. Besides, we carefully investigate the relation between EHPS and IB-EHPS, and indicate possible refinement and generalization of EHPS.

ABSTRACT We consider public key encryption (PKE) schemes with auxiliary input, that is, the adversary is given any computationally uninvertible function of the secret key. Previous result only achieves security under chosen‐plaintext attacks (CPA). In this paper, we construct public key encryption schemes that are secure under chosen‐ciphertext attacks even when the adversary is given any computationally uninvertible function of the secret key as an auxiliary input. We follow the Naor–Yung ‘double encryption’ paradigm and generally transform any chosen‐plaintext attack secure public key encryption into a chosen‐ciphertext attack secure one in the auxiliary input model. Copyright © 2012 John Wiley & Sons, Ltd.