An efficient computational Zero-Knowledge Proof of Knowledge whose security relies on the NP-completeness of the Independent Set Problem is presented here. The proposed algorithm is constructed from a bit commitment scheme based on the hardness of the Discrete Logarithm Problem, which guarantees the fulfillment of soundness, completeness and computational zero-knowledge properties, and allows avoiding the use of the Graph Isomorphism Problem, which is present in every known Zero-Knowledge Proofs for the Independent Set Problem.
Cryptography and Data Security
Complexity and Algorithms in Graphs
Physical Unclonable Functions (PUFs) and Hardware Security
It's essential on algorithm design of designated confirmer signatures to construct proofs satisfying security requirements such as unforgetablility, non-transferability, invisibility and zero-knowledge. A designated confirmer signature protocol (RSA-DCSV) is proposed, based on RSA encryption and signature schemes in forms of RSA extended modular computations. Proofs for a designated verifier are considered. Security analysis on RSA-DCSV is also addressed.
A protocol for zero-knowledge proofs of identity based on ElGamal on conic is proposed in this paper. The solution to a hard puzzle is divided into two parts, and the P (prover) provides one of them according to the V (verifier) 's random bit. The eavesdropper cannot obtain any useful knowledge about the P (prover) 's identity during the process of authentication. No adversary in this protocol can cheat each other or get the privacy of each other. The security of this protocol relies on the discrete logarithm problem on conic over finite fields. Compared with those identification protocols implemented on elliptic, these kinds of identification protocols implemented on conic can be designed and implemented easier. Corresponding to the simple version, a parallel version is presented subsequently. The characteristic of ZKp and security of the simple version is proved. The trait of our identification protocol is given. We also analyzed the "soundness ", the "completeness ", before analyzed the amount of computation in the protocol. A simple solution considering t/sub timeout/ is proposed to prevent a potential leak of our protocol. Some problems need to be solved in the future is brought forward at the end of this paper.
Delegation, whereby an entity gives some of its rights to other entities, is considered the cornerstone of decentralized authorization, and many access control frameworks proposed recently make delegation its central tenet. In these frameworks, delegation is commonly viewed as a transfer between two autonomous agents---the grantor and the grantee. But the situation can be considerably more complex, and more challenging, in the case the grantor belongs to an organization. Generally, employees are not autonomous agents, but their actions are subject to the regulations of their enterprise. In particular, if an employee transfers his rights to another agent, this transfer is subject to the enterprise delegation policies.In delegation frameworks, authorizing a request requires finding a valid chain of credentials that delegates the authority from the source (the local policy of the entity that serves the request) to the requester. Unfortunately, chain discovery is a computationally expensive and time consuming task. It was shown that, in the general case, chain discovery is undecidable, and in more restrictive cases, it is polynomial in the number of credentials available to the server. Verifying compliance with the terms of a delegation policy adds a considerable overhead to request authorization.This paper presents a framework that considerably reduces the time required to authorize a request. In this framework, a delegation chain is condensed into a single credential, called chained delegation certificate (CDC). A CDC attests that the owner has a certain right, and serves as proof that every link in the chain complies with the policy governing delegation of the right in question. When CDCs are used for authorization, a server does not need to verify compliance with the delegation policy, nor does it need to perform the chain discovery step, and therefore requests are served considerably faster.
A distributed conference key distribution system is introduced. The system utilizes secure multi-party computation scheme by virtue of Feldman's (t+1, n) VSS to perform the conference key computation such that a key can be obtained in a distributed fashion in which any key of servers is required to perform the computation. By runing the protocal, every honest user of a given conference can get a common key, even if a minority of servers malfunction or misbehave. This scheme does not rely on any unproven cryptographic assumptions or on the availability of any tamper -proof hardware. By using zero knowledge proof, any corrupted information and incorrect results can be detected. And by distributing the sensitive security information across several servers and never reconstructing and key at a single location, the compromise of a few servers will not compromise the privacy of any key. The scheme is implemented in a distributed environment. By conducting a number of experiments in the fault-free case and various fault scenarios, it is shown that the scheme is practicable and efficient.
Subliminal channel is proposed by Simmons, he showed a method that a message authentication without secrecy channel transferring secret message. Subsequently, subliminal channel is implemented in ElGamal, DSA which based on the difficulty of discrete logarithms. Zero-knowledge proof is an important tool in cryptology, a digital signature scheme based on zero-knowledge proof or “cut and chose” is regarded as resist subliminal channel. The possibility of constructing subliminal channel in these digital signature scheme is analyzed, the security and application of subliminal channel is discussed also.
The need for cryptography has been recognized since ancient times. One of its main goals, private communication in the presence of adversary, is traced back to the ancient Roman empire, whose emperor Julius Ceasar used to communicate to his allies by replacing each letter in his message with the third next letter in the alphabet. Classical cryptography went on until the end of last century focusing on the art of designing and breaking secrecy codes. Modern cryptography has significantly enlarged its scope to the rigorous analysis of any system that is potentially subject to malicious threats and the design of solution that can guarantee the system to withstand such threats. As a consequence, many goals have been added to that of private communication in the presence of adversary, and cryptography has moved from an engineering art built on a number of heuristic techniques to a scientific discipline based on mathematically rigorous design requirements, solution techniques and correctness proofs. We present here an introduction to some basic topics in the foundation of modern cryptography; specifically: one-way functions, pseudo-random generators, pseudo-random functions and zero-knowledge protocols.
It is shown in this paper that a kind of new cryptographic primitive proposed by Zheng in 1997, Signcryption, may be applied to construct distributed cryptographic protocols. In fact, the protocols based on Signcryption have the following two properties: Each message exchanged between two participants can be transferred in short data packet, and messages that carry key materials are unforgeable and non-repudiatable without the involvement of a trusted key distribution center. Firstly, based on the modified signcryption scheme of Zheng and Verifiable Secret Sharing(VSS) idea, this paper gives a kind of threshold signcryption scheme without any trusted center for the first time. Furthermore, this scheme can gain its ends of both threshold signature and threshold encryption simultaneously and the costs is much cheaper. In addition, non-repudiation is also offered. Secondly, by analyzing recent distributed key generation protocols, especially Naor’s idea, it put forward a new protocol mainly based on signcryption, called SC-DKDS. Compared with others, SC-DKDS does not need any additional costs, such as authentication channels, private channels or any complicated zero knowledge proofs. The security proofs of the protocols mentioned above are given in RO(Random Oracle) model.
This paper proposed a protocol for zero-knowledge proof of identity based on ElGamal on conic. It is more appropriate than the traditional identity protocol in distributed environment without trusted third parties. The security of this protocol relies on the discrete logarithm problem on conic over finite fields. Compared with those identification protocols implemented on elliptic curve, this protocol can be designed and implemented easier. And compared with that security lies on disassemble a large number, it runs faster. Corresponding to the simple version, a parallel version is presented subsequently. The characteristic of ZKp and security of the simple version is proved. The "soundness", "completeness", and amount of computation are also analyzed. A simple solution considering t/sub timeout/ is proposed to prevent a potential leak of our protocol.
In 1982, Chaum [21] pioneered the anonymous e-cash which finds many applications in e-commerce. In 1993, Brands [8--10] and Ferguson [30, 31] published on single-term offline anonymous ecash which were the first practical e-cash. Their constructions used blind signatures and were inefficient to implement multi-spendable e-cash. In 1995, Camenisch, Hohenberger, and Lysyanskaya [12] gave the first compact 2 -spendable e-cash, using zero-knowledge-proof techniques. They left an open problem of the simultaneous attainment of O(1)-unit wallet size and efficient coin tracing. The latter property is needed to revoke bad coins from over-spenders. In this paper, we solve [12]'s open problem, and thus enable the first practical compact e-cash. We use a new technique whose security reduces to a new intractability assumption: the Decisional Harmonically-Tipped Diffie-Hellman (DHTDH) Assumption.
Abstract. There is a broad literature on distributed card games over communications networks, collectively known as mental poker. Likein any distributed protocol, avoiding the need for a Trusted Third Party (TTP) in mental poker is highly desirable, because really trusted TTPs are not always available and seldom free. This paper deals with the player dropout problem in mental poker without a TTP. A solution based on zero-knowledge proofs is proposed. While staying TTP-free, our proposal allows the game to continue after player dropout.
Abstract. In undeniable signature schemes, zero-knowledgeness and non-transferability have been identified so far. In this paper, by separating these two notions, we show the first 3-move confirmation and disavowal protocols for Chaum’s undeniable signature scheme which is secure against active and concurrent attacks. Our main observation is that while the signer has one public key and one secret key, there exist two witnesses in the confirmation and disavowal proofs of Chaum’s scheme.
In this paper, we introduce the concept of additive zero knowledge. Essentially, an additive proof can be considered as a proof system involving many provers and one verifier such that the statements of all the provers are proved simultaneously. Our model of additive proofs is presented using constructions of blind group identification, aggregate signatures and chained signatures. The security of our protocols relies on the difficulty of the underlying Diffie-Hellman problem in bilinear maps. As applications, we present a novel method to prevent spam.