As the basic problem that introduces the idea of secure multi-party computation (SMC), millionairesâ problem (MP) is one of the research highlights in the field of SMC. However, most of current protocols for MP are only secure in semi-honest model, which using public key cryptography schemes, and there are few secure schemes in malicious model exist security defects. Therefore, this paper analyzes the Li et al.âs protocol for MP that secure in malicious model. Firstly, we point out several behaviours that can be successfully implemented in Li et al.âs protocol. Secondly, by using the zero-knowledge proof (ZKP) for the equality of discrete logarithm (DL), cut-and-choose method etc. We propose the improved protocol and show how to detect malicious behaviours. Finally, we analyze the correctness and security against malicious behaviours of the improved protocol.
This work proposes the use of blockchain for offline voting. Using the Smart contract feature of the Ethereum blockchain network. The voterâs registration is made. An offline token is generated which is used for offline voting. The offline token and the voting information are sent to the vote counters Smart contact. This is where the votes are counted and results extracted. However if a voter can share the cast vote to another voter who will send the new token to the vote counters. In a situation a vote is submitted by multiple voters, the counter has the ability to identify and count such votes only once.
Our proposed scheme is modified from that of Camenisch et al., yet achieves more efficient than their scheme. In general, a batch verification method is more advantageous and is also able to save more cost than the original scheme, while non-interactive zero knowledge proof requires fewer communication rounds than interactive zero knowledge proof. The proposed scheme employs the simplified small exponents test method for secure and fast batch verification on multiple signature elements, which can remarkably reduce the number of time-consuming pairing operations required by both a prover and a verifier, resulting in greatly improved computational efficiency. By applying non-interactive zero knowledge proof technique, the proposed scheme also decreases the number of communication rounds required between both of them.
Cloud computing can provide users with sufficient computing resources, storage, and bandwidth to meet their needs. Data security and privacy protection are among the new threats faced by users. Searchable encryption is the combination of search technology and encryption technology. Searchable encryption can upload the userâs data to the cloud server after special encryption, and can realize the function of retrieving according to keywords. Comparatively to symmetric searchable encryption (SSE), public key searchable encryption (PEKS) simplifies key management greatly. However, most existing public key authenticated encryption with keyword search (PAEKS) schemes are based bilinear pairing, making them computationally expensive. Apart from this, complex retrieval requirements and the integrity of the results had not been considered. To address these problems, we propose a blockchain-based PAEKS schemes supporting multi-keyword queries and integrity verification. In addition, we provide security proofs for the PAEKS scheme under the decisional oracle Diffie-Hellman (DODH) assumption. This scheme a scheme that requires less storage and computational power than other schemes of the same kind.
By the means of asymptotic security of cryptographic security mechanism we can get knowledge about efficiency and tolerable features against various type of attacks compromised on it. Analytical study about how zero-knowledge proofs can be used with Diffie Hellman problem (DHP) are presented in this research. One of the better algorithms of discrete logarithm problem which is suggested by Henry for zero knowledge proofs is suitable for DHP problem for the robustness analysis of it. The efficiency of discrete logarithm algorithm for DHP problem and integer factorization problem are analyzed and made comparison between them and covariance and correlation between their asymptotic functions is obtained as final result which clearly give us idea about strong relationship between each other and correlation factor between them is high, so they are similar in nature.
Hongjian Yin, E Chen, Yan Zhu, Rongquan Feng · 5 authors
In this paper, we address the problem of secure decision of membership. We present a Zero-Knowledge Dual Membership Proof (ZKDMP) protocol, which can support positive and negative (Pos-and-Neg) membership decisions simultaneously. To do it, two secure aggregation functions are used to compact an arbitrarily-sized subset into an element in a cryptographic space. By using these aggregation functions, a subset can achieve a secure representation, and the representation size of the subsets is reduced to the theoretical lower limit. Moreover, the zeros-based and poles-based secure representation of the subset are used to decide Pos-and-Neg membership, respectively. We further verify the feasibility of combining these two secure representations of the subset, so this result is used to construct our dual membership decision cryptosystem. Specifically, our ZKDMP protocol is proposed for dual membership decisions, which can realize a cryptographic proof of strict Pos-and-Neg membership simultaneously. Furthermore, the zero-knowledge property of our construction ensures that the information of the tested element will not be leaked during the implementation of the protocol. In addition, we provide detailed security proof of our ZKDMP protocol, including positive completeness, negative completeness, soundness and zero-knowledge.
Blockchain technology has been widely applied in numerous industries with its decentralization, verifiability, distributivity, and immutability. However, the identity privacy security of blockchain users is facing serious threats because of the openness of traditional blockchain transaction information. Moreover, numerous traditional cryptographic algorithms used by blockchain transaction networks are difficult to attack quantum computing. In this paper, we propose a new lattice-based blind ring signature scheme in allusion to completely anonymous blockchain transaction systems. There into, the blind ring signature can implement the complete anonymity of user identity privacy in blockchain transactions. Meanwhile, lattice cryptography can availably resist quantum computing attacks. Firstly, the proposed signature scheme has strong computational security based on the small integer solution (SIS) problem and a high sampling success rate by utilizing the techniques of rejection sampling from bimodal Gaussian distribution. Secondly, the proposed signature scheme can satisfy the correctness and security under the random oracle model, including anonymity, blindness, and one-more unforgeability. Thirdly, we construct a blockchain transaction system based on the proposed blind ring signature algorithm, which realizes the completely anonymous and antiquantum computing security of the blockchain usersâ identity privacy. Finally, the performance evaluation results show that our proposed blind ring signature scheme has lower latency, smaller key size, and signature size than other similar schemes.
This paper proposes a protocol for Proof of As-sets of a bitcoin exchange using the Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (ZK-SNARK) without revealing either the bitcoin addresses of the exchange or balances associated with those addresses. The proof of assets is a mech-anism to prove the total value of bitcoins the exchange has the authority to spend using its private keys. We construct a privacy-preserving ZK-SNARK proof system to prove the knowledge of the private keys corresponding to the bitcoin assets of an exchange. The ZK-SNARK toolchain helps to convert an NP-Statement for proving the knowledge of the private keys (known to the exchange) into a circuit satisfiability problem. In this protocol, the exchange creates a Pedersen commitment to the value of bitcoins associated with each address without revealing the balance. The simulation results show that the proof generation time, size, and verification time are efficient in practice.
Mohsen Alambardar Meybodi, Amir Kafshdar Goharshady, M. R. Hooshmandasl, Ali Shakiba
Following the Bitcoin model, many modern blockchains reward their miners in two ways: (i) a base reward for each block that is mined, and (ii) the transaction fees of those transactions that are included in the mined block. The base reward is fixed by the respective blockchain's protocol and is not under the miner's control. Hence, for a miner who wishes to maximize earnings, the fundamental problem is to form a valid block with maximal total transaction fees and then try to mine it. Moreover, in many protocols, including Bitcoin itself, the base reward halves at predetermined intervals, hence increasing the importance of maximizing transaction fees and mining an optimal block. This problem is further complicated by the fact that transactions can be prerequisites of each other or have conflicts (in case of double-spending). In this work, we consider the problem of forming an optimal block, i.e. a valid block with maximal total transaction fees, given a set of unmined transactions. The problem is known to be NP-hard. As such, there is no hope in solving it efficiently for general instances. However, we observe that its real-world instances are quite sparse, i.e. the transactions have very few dependencies and conflicts. Using this fact, and exploiting a well-known graph sparsity parameter, namely pathwidth, we present an exact linear-time parameterized algorithm that is applicable to the real-world instances and obtains optimal results. We also provide an experimental evaluation demonstrating that our approach outperforms current Bitcoin miners in practice, obtaining a significant increase in transaction fee revenues.
The assignment problem is an essential problem in many application fields and frequently used to optimize resource usage. The problem is well understood and various efficient algorithms exist to solve the problem. However, it was unclear what practical performance could be achieved for privacy preserving implementations based on multiparty computation (MPC) by leveraging more efficient solution strategies than MPC based simplex solvers for linear programs. We solve this question by implementing and comparing different optimized MPC algorithms to solve the assignment problem for reasonable problem sizes. Our empirical approach revealed various insights to MPC based optimization and we measured a significant (50x) speedup compared to the known simplex based approach. Furthermore, we also study the overhead introduced by making the results publicly verifiable by means of non-interactive zero-knowledge proofs. By leveraging modern proof systems we also achieve significant speedup for proof and verification times compared to the previously proposed approaches as well as compact proof sizes.
Abstract Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O (1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have âescaped the hegemonyâ of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing $$\text{ SNARG } $$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mspace/><mml:mtext>SNARG</mml:mtext><mml:mspace/></mml:mrow></mml:math> s, as well as resulting new efficiency features. Our contribution is threefold: (1) We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded âadversariesâ in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional âunstructuredâ PCPs. (2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques. (3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as âsingle-ciphertext preprocessing SNARGs.â We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.
We introduce MatRiCT+, a practical private blockchain payment protocol based on âpost-quantumâ lattice assumptions. MatRiCT+builds on MatRiCT due to Esgin et al. (ACM CCSâ19) and, in general, follows the Ring Confidential Transactions (RingCT) approach used in Monero, the largest privacy-preserving cryptocurrency. In terms of the practical aspects, MatRiCT+has 2-18Ă shorter proofs (depending on the number of input accounts, M) and runs 3-11Ă faster (for a typical transaction) in comparison to MatRiCT. A significant advantage of MatRiCT+is that the proof lengthâs dependence on M is very minimal (only O(logM)), while MatRiCT has a proof length linear in M. To support its efficiency, we devise several novel techniques in our design of MatRiCT+to achieve compact lattice-based zeroknowledge proof systems, exploiting the algebraic properties of power-of-2 cyclotomic rings commonly used in practical latticebased cryptography. Along the way, we design a family of âoptimalâ challenge spaces, using a technique we call partition-and-sample, with minimal $\ell_{1}$-norm and invertible challenge differences (with overwhelming probability), while supporting highly-splitting power-of-2 cyclotomic rings. We believe all these results to be widely applicable and of independent interest.
We prove that for every 3-player (3-prover) game $\mathcal G$ with value less than one, whose query distribution has the support $\mathcal S = \{(1,0,0), (0,1,0), (0,0,1)\}$ of hamming weight one vectors, the value of the $n$-fold parallel repetition $\mathcal G^{\otimes n}$ decays polynomially fast to zero; that is, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Following the recent work of Girish, Holmgren, Mittal, Raz and Zhan (STOC 2022), our result is the missing piece that implies a similar bound for a much more general class of multiplayer games: For $\textbf{every}$ 3-player game $\mathcal G$ over $\textit{binary questions}$ and $\textit{arbitrary answer lengths}$, with value less than 1, there is a constant $c = c(\mathcal G)>0$ such that the value of the game $\mathcal G^{\otimes n}$ is at most $n^{-c}$. Our proof technique is new and requires many new ideas. For example, we make use of the Level-$k$ inequalities from Boolean Fourier Analysis, which, to the best of our knowledge, have not been explored in this context prior to our work.
Aarushi Goel, Matthew Green, Mathias Hall-Andersen, Gabriel Kaptchuk
Abstract Set membership proofs are an invaluable part of privacy preserving systems. These proofs allow a prover to demonstrate knowledge of a witness w corresponding to a secret element x of a public set, such that they jointly satisfy a given NP relation, i.e. â( w, x ) = 1 and x is a member of a public set { x 1 , . . . , x đ }. This allows the identity of the prover to remain hidden, eg. ring signatures and confidential transactions in cryptocurrencies. In this work, we develop a new technique for efficiently adding logarithmic-sized set membership proofs to any MPC-in-the-head based zero-knowledge protocol (Ishai et al. [STOCâ07]). We integrate our technique into an open source implementation of the state-of-the-art, post quantum secure zero-knowledge protocol of Katz et al. [CCSâ18].We find that using our techniques to construct ring signatures results in signatures (based only on symmetric key primitives) that are between 5 and 10 times smaller than state-of-the-art techniques based on the same assumptions. We also show that our techniques can be used to efficiently construct post-quantum secure RingCT from only symmetric key primitives.
Abstract Traditional zero-knowledge protocols have been studied and optimized for the setting where a single prover holds the complete witness and tries to convince a verifier about a predicate on the witness, without revealing any additional information to the verifier. In this work, we study the notion of distributed-prover zero knowledge (DPZK) for arbitrary predicates where the witness is shared among multiple mutually distrusting provers and they want to convince a verifier that their shares together satisfy the predicate. We make the following contributions to the notion of distributed proof generation: (i) we propose a new MPC-style security definition to capture the adversarial settings possible for different collusion models between the provers and the verifier, (ii) we discuss new efficiency parameters for distributed proof generation such as the number of rounds of interaction and the amount of communication among the provers, and (iii) we propose a compiler that realizes distributed proof generation from the zero-knowledge protocols in the Interactive Oracle Proofs (IOP) paradigm. Our compiler can be used to obtain DPZK from arbitrary IOP protocols, but the concrete efficiency overheads are substantial in general. To this end, we contribute (iv) a new zero-knowledge IOP Graphene which can be compiled into an efficient DPZK protocol. The (D + 1)-DPZK protocol D-Graphene, with D provers and one verifier, admits O ( N 1 /c ) proof size with a communication complexity of O (D 2 ·( N 1â2 /c + N s )), where N is the number of gates in the arithmetic circuit representing the predicate and N s is the number of wires that depends on inputs from two or more parties. Significantly, only the distributed proof generation in D-Graphene requires interaction among the provers. D-Graphene compares favourably with the DPZK protocols obtained from the state-of-art zero-knowledge protocols, even those not modelled as IOPs.
In this paper we describe protocols which use a standard deck of cards to provide a perfectly sound zero-knowledge proof for Hamiltonian cycles and Flow Free puzzles. The latter can easily be extended to provide a protocol for a zero-knowledge proof of many-to-many k-disjoint path coverings.
Jelle Don, Serge Fehr, Christian Majenz, Christian Schaffner
Commit-and-open Sigma-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes via the Fiat-Shamir transformation. Instantiated with hash-based commitments, the resulting non-interactive schemes enjoy tight online-extractability in the random oracle model. Online extractability improves the tightness of security proofs for the resulting digital-signature schemes by avoiding lossy rewinding or forking-lemma based extraction. In this work, we prove tight online extractability in the quantum random oracle model (QROM), showing that the construction supports post-quantum security. First, we consider the default case where committing is done by element-wise hashing. In a second part, we extend our result to Merkle-tree based commitments. Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic. Our analysis makes use of a recent framework by Chung et al. [arXiv:2010.11658] for analysing quantum algorithms in the QROM using purely classical reasoning. Therefore, our results can to a large extent be understood and verified without prior knowledge of quantum information science.