In this thesis we follow two directions: Zero Knowledge Protocols and the Discrete Logarithm Problem. In each direction we present the necessary background and we give a new approach for some parts of the existing protocols. / The new parts are dedicated to the soundness property of the Schnorr Identification Scheme and to the security of the sum+-Protocol. Since both directions are very well-known and studied in the field of cryptography, they are presented with many details so that the new results are easy to follow. / In writing this thesis we have tried to present the material in a specific order and in a manner easy to read even by beginners in cryptography.

No description available.

We show that the long-standing assumption of "no-communication" between the provers of the two-prover model is not sufficiently precise to guarantee the security of a bit commitment scheme against malicious adversaries. Indeed, we show how a simple correlated random variable, which does not allow to communicate, can be used to cheat a simplified version (sBGKW) of the bit commitment scheme of Ben-Or, Goldwasser, Kilian, and Wigderson [BGKW88]. Instead we propose a stronger notion of separation between the two provers which takes into account correlated computations. To emphasize the risk that entanglement still represents for the security of a commitment scheme despite the stronger notion of separation, we present two variations of the sBGKW scheme that can be cheated by quantum provers with probability (almost) one. A complete proof of security against quantum adversaries is then given for the sBGKW scheme. By reduction we also obtain the security of the original BGKW scheme against quantum provers. For the unfamiliar reader, basic notions of quantum processing are provided to facilitate the understanding of the proofs presented.

Thesis (M.S.)--University of North Texas, Dec., 2009. / Title from title page display. Includes bibliographical references.

Zero-knowledge proofs protocols are effective interactive methods to prove a node's identity without disclosing any additional information other than the veracity of the proof. They are implementable in several ways. In this thesis, I investigate the graph isomorphism based zero-knowledge proofs protocol. My experiments and analyses suggest that graph isomorphism can easily be solved for many types of graphs and hence is not an ideal solution for implementing ZKP.

No description available.

The immutability, validity and confidentiality of an audit log is crucial when operating over sensitive data to comply to standard data regulations (e.g., HIPAA). Despite its critical needs, state-of-the-art privacy-preserving audit log schemes (e.g., Ghostor (NSDI '20), Calypso (VLDB '19)) do not fully obtain a high level of privacy, integrity, and immutability simultaneously, in which certain information (e.g., user identities) is still leaked in the log. In this work, we propose Harpocrates, a new privacy-preserving and immutable audit log scheme. Harpocrates permits data store, share, and access operations to be recorded in the audit log without leaking sensitive information (e.g., data identifier, user identity), while permitting the validity of data operations to be publicly verifiable. Harpocrates makes use of blockchain techniques to achieve immutability and avoid a single point of failure, while cryptographic zero-knowledge proofs are harnessed for confidentiality and public verifiability. We analyze the security of our proposed technique and prove that it achieves non-malleability and indistinguishability. We fully implemented Harpocrates and evaluated its performance on a real blockchain system (i.e., Hyperledger Fabric) deployed on a commodity platform (i.e., Amazon EC2). Experimental results demonstrated that Harpocrates is highly scalable and achieves practical performance. / Master of Science / Audit logs are an essential part of data storage systems as they allow to check if the system is working as intended. They are usually maintained on a server, a server with ill intentions can easily modify records of the log and make it appear that the system is working correctly. To store these records in an un-modifiable manner, prior works have leveraged special audit log storing mechanisms for e.g., blockchain due to its immutable nature. However, these works do not focus on the privacy of the records which is a crucial aspect for conforming to certain data regulations like HIPAA. In our work, we propose Harpocrates, an immutable and privacy-preserving audit log platform that supports recording operations (share/access) on sensitive data. Harpocrates leverages blockchain to achieve immutability of the audit log. Harpocrates use specific cryptographic primitives to achieve public verifiability and confidentiality of the audit log. Real world deployment of Harpocrates shows that it is practical and achieves strong security guarantees.

No description available.

We present an Ethash-based blockchain relay that utilizes Off-Chain Computation (OCC) to validate block headers on-chain. Current work compromises on fundamental ideas of the blockchain concept: they either require a centralized entity, require a centralized Trusted Third Party (TTP) or are built on economic assumptions. That way, they try to circumvent the on-chain cost-heavy Ethash computation. We utilize Zero Knowledge Proofs (ZKPs) to outsource the Ethash validation to an Off-Chain Computation Framework (OCCF) and only verify the validity of the OCC on-chain. The required dataset for the Ethash validation is inserted into a merkle tree for computational feasibility. Additionally, we validate multiple block headers in batches to further minimize on-chain costs. The on-chain costs of our batch validation mechanism are minimal and constant since only the proof of an OCC is verified on-chain. Through merkle proofs we enable the efficient inclusion of intermediary block headers for any submitted batch. The OCC is feasible on average consumer hardware specifications. Our prototype verifies 5 block headers in a single proof using the ZoKrates framework. Compared to current approaches we only use 3.3% of the gas costs resulting in a highly scalable alternative that is trustless, distributed and has no economic assumptions. For future work, we propose to distribute the computational overhead of computing Ethash inside a ZKP through an off-chain distribution module. This is because we rely on the concurrent execution of the OCC by at least 36 active participants to catch up with the current state of the relay’s blockchain. / Vi presenterar ett Ethash-baserat blockchain-relä som använder sig av Off-Chain Computation (OCC) att validera blockhuvuden i kedjan. Nuvarande arbete kompromissar med grundläggande idéer om blockchain-konceptet: de kräver antingen en centraliserad enhet, kräver en centraliserad Trusted Third Party (TTP) eller bygger på ekonomiska antaganden. På så sätt försöker de kringgå den kostnadstunga Ethash-beräkningen på kedjan. Vi använda Zero Knowledge Proof (ZKP) för att lägga ut Ethash-valideringen på en Off-Chain Computation Framework (OCCF) och verifiera endast giltigheten av OCC på kedjan. Den nödvändiga datamängden för Ethash-valideringen är infogas i ett merkleträd för beräkningsmöjlighet. Dessutom validerar vi flera blockhuvuden i omgångar för att ytterligare minimera kostnader i kedjan. På-kedjan kostnaderna för vår batchvalideringsmekanism är minimala och konstanta eftersom endast bevis på en OCC verifieras i kedjan. Genom merkle proofs möjliggör vi det effektiva inkludering av mellanliggande blockrubriker för alla inlämnade partier. OCC är genomförbart i genomsnitt konsumenthårdvaruspecifikationer. Vår prototyp verifierar 5 blockhuvuden i ett enda bevis med hjälp av ZoKrates-ramverket. Jämfört med nuvarande tillvägagångssätt vi använder bara 3,3% av gaskostnaderna vilket resulterar i ett mycket skalbart alternativ dvs förtroendelös, distribuerad och har inga ekonomiska antaganden. För framtida arbete, föreslår vi för att distribuera beräkningsoverheaden för beräkning av Ethash inuti en ZKP genom en distributionsmodul utanför kedjan. Detta beror på att vi skulle förlita oss på det samtidiga utförandet av OCC med minst 36 aktiva deltagare för att komma ikapp med det aktuella tillståndet för reläets blockkedja.

Anonymous communications networks help to solve the real and important problem of enabling users to communicate privately over the Internet. However, by doing so, they also introduce an entirely new problem: How can service providers on the Internet---such as websites, IRC networks and mail servers---allow anonymous access while protecting themselves against abuse by misbehaving anonymous users? Recent research efforts have focused on using anonymous blacklisting systems (also known as anonymous revocation systems) to solve this problem. As opposed to revocable anonymity systems, which enable some trusted third party to deanonymize users, anonymous blacklisting systems provide a way for users to authenticate anonymously with a service provider, while enabling the service provider to revoke access from individual misbehaving anonymous users without revealing their identities. The literature contains several anonymous blacklisting systems, many of which are impractical for real-world deployment. In 2006, however, Tsang et al. proposed Nymble, which solves the anonymous blacklisting problem very efficiently using trusted third parties. Nymble has inspired a number of subsequent anonymous blacklisting systems. Some of these use fundamentally different approaches to accomplish what Nymble does without using third parties at all; so far, these proposals have all suffered from serious performance and scalability problems. Other systems build on the Nymble framework to reduce Nymble's trust assumptions while maintaining its highly efficient design. The primary contribution of this thesis is a new anonymous blacklisting system built on the Nymble framework---a nimbler version of Nymble---called Nymbler. We propose several enhancements to the Nymble framework that facilitate the construction of a scheme that minimizes trust in third parties. We then propose a new set of security and privacy properties that anonymous blacklisting systems should possess to protect: 1) users' privacy against malicious service providers and third parties (including other malicious users), and 2) service providers against abuse by malicious users. We also propose a set of performance requirements that anonymous blacklisting systems should meet to maximize their potential for real-world adoption, and formally define some optional features in the anonymous blacklisting systems literature. We then present Nymbler, which improves on existing Nymble-like systems by reducing the level of trust placed in third parties, while simultaneously providing stronger privacy guarantees and some new functionality. It avoids dependence on trusted hardware and unreasonable assumptions about non-collusion between trusted third parties. We have implemented all key components of Nymbler, and our measurements indicate that the system is highly practical. Our system solves several open problems in the anonymous blacklisting systems literature, and makes use of some new cryptographic constructions that are likely to be of independent theoretical interest.