This preview shows page 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-108-109-110-111-112-113-114-115-116-117-118-119-120-121-122-123-217-218-219-220-221-222-223-224-225-226-227-228-229-230-231 out of 231 pages.
Practical Aspects of Modern CryptographyFun with Public-KeyInteractive Proofs and Zero KnowledgeTraditional ProofsInteractive ProofsGraph IsomorphismSlide 7Slide 8Zero-Knowledge Interactive ProofZKIP of Graph IsomorphismSlide 11Slide 12Slide 13Slide 14Slide 15Slide 16Fiat-Shamir HeuristicZKIP of Graph Non-IsomorphismSlide 19Slide 20Slide 21Slide 22Proving Something is a SquareSlide 24An Interactive ProofSlide 26Slide 27Slide 28Slide 29Proving KnowledgeSlide 31Slide 32Slide 33Slide 34A Proof of KnowledgeSlide 36Slide 37Slide 38Slide 39Facts About Interactive ProofsApplying Fiat-ShamirAn Non-Interactive ZK ProofSlide 43Slide 44Slide 45Secret SharingSlide 47Secret Sharing – ANDSlide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Secret Sharing – ANDSlide 60Secret Sharing – ORSlide 62Slide 63Slide 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Slide 72Slide 73Slide 74Threshold SchemesSlide 76Shamir’s Threshold SchemeSlide 78Slide 79Slide 80Slide 81Slide 82Slide 83Slide 84Slide 85Slide 86Slide 87Slide 88Slide 89Slide 90Slide 91Slide 92Slide 93Slide 94Slide 95Lagrange InterpolationSolving a Linear SystemVerifiable Secret SharingHomomorphic EncryptionAn Additive HomomorphismSlide 101Slide 102Slide 103Secret Sharing HomomorphismsSlide 105Slide 106Slide 107Threshold EncryptionRecall Diffie-HellmanElGamal EncryptionElGamal Re-EncryptionGroup ElGamal EncryptionThreshold Encryption (ElGamal)Slide 114Slide 115Slide 116A Claim:Slide 118Slide 119Slide 120More specifically …A Web-Based ElectionSlide 123Slide 124But wait …Slide 126Slide 127PrivacySlide 129Slide 130Understanding ElectionsSome Principles of Election ProtocolsSlide 133VerifiabilityRobustnessCoercibilityCurrent Election MethodsSlide 138Slide 139Slide 140Cryptographic VerifiabilitySlide 142Slide 143Cryptographic Voting SystemsThe Encryption PhaseThe Tallying PhaseFundamental Tallying DecisionSlide 148Slide 149A Fundamental Trade-OffSlide 151The Mix-Net ParadigmSlide 153Slide 154Slide 155Slide 156Multiple MixesSlide 158Slide 159A Re-encryption MixSlide 161Multiple Re-encryption MixesSlide 163Slide 164Slide 165Slide 166Constructing a Verifiable MixSlide 168Slide 169Slide 170Slide 171Slide 172Unconditional VerifiabilityMix-Net PropertiesSlide 175The Homomorphic ParadigmSlide 177Slide 178Homomorphic TechniquesSlide 180Slide 181Slide 182Slide 183Slide 184Slide 185Slide 186Slide 187Slide 188Slide 189Slide 190Slide 191Slide 192Slide 193Slide 194Slide 195Slide 196Slide 197Slide 198Slide 199Slide 200Slide 201Slide 202Slide 203Slide 204Slide 205Slide 206Slide 207Slide 208Slide 209Unstructured AuditingAuditingA Fundamental LimitationIn Practice?Slide 215Slide 216PropertiesScorecardSlide 219Slide 220Slide 221Slide 222Slide 223Slide 224Slide 225Slide 226Slide 227Slide 228ConclusionsSlide 230Slide 231Slide 232Practical Aspects of Modern CryptographyJosh BenalohBrian LaMacchiaJohn ManferdelliJanuary 14, 2019Practical Aspects of Modern CryptographyFun with Public-KeyTonight we’ll …•Introduce some basic tools of public-key crypto•Combine the tools to create more powerful tools•Apply these tools to a grand application: doing elections “right”January 14, 2019Practical Aspects of Modern CryptographyInteractive Proofs and Zero Knowledge•There are non-traditional methods of convincing others that something is true without writing down a proof.•These methods can be used to convince others of the veracity of partial information about a secret.January 14, 2019Practical Aspects of Modern CryptographyTraditional Proofs•I want to convince you that something is true.•I write down a proof and give it to you.January 14, 2019Practical Aspects of Modern CryptographyInteractive ProofsWe engage in a dialogue at the conclusion of which you are convinced that my claim is true.January 14, 2019Practical Aspects of Modern CryptographyGraph IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyGraph IsomorphismBECDAJanuary 14, 2019Practical Aspects of Modern CryptographyGraph IsomorphismBECDAACBDEJanuary 14, 2019Practical Aspects of Modern CryptographyZero-Knowledge Interactive ProofG1G2January 14, 2019Practical Aspects of Modern CryptographyZKIP of Graph IsomorphismGenerate, say, 100 additional graphs isomorphic to G1 (and therefore also isomorphic to G2).January 14, 2019Practical Aspects of Modern CryptographyG1G2H1H2H3H100ZKIP of Graph IsomorphismJanuary 14, 2019Practical Aspects of Modern Cryptography•Accept a single bit challenge “L/R” for each of the 100 additional graphs.•Display the indicated isomorphism for each of the additional graphsZKIP of Graph IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyG1G2H1H2H3H100ZKIP of Graph IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyG1G2H1H2H3H100ZKIP of Graph IsomorphismLLRRJanuary 14, 2019Practical Aspects of Modern CryptographyG1G2H1H2H3H100ZKIP of Graph IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyZKIP of Graph Isomorphism•If graphs G1 and G2 were not isomorphic, then the “prover” would not be able to show any additional graph to be isomorphic to both G1 and G2.•A successful false proof would require the prover to guess all 100 challenges in advance: probability 1 in 2100.January 14, 2019Practical Aspects of Modern CryptographyFiat-Shamir Heuristic•Instead of challenge bits being externally generated, they can be produced by applying a one-way hash function to the full set of additional graphs.•This allows a ZKIP to be “published” without need for interaction.January 14, 2019Practical Aspects of Modern CryptographyG1G2ZKIP of Graph Non-IsomorphismJanuary 14, 2019Practical Aspects of Modern Cryptography•A verifier can generate 100 additional graphs, each isomorphic to one of G1 and G2 , and present them to the prover.•The prover can then demonstrate that the graphs are not isomorphic by identifying which of G1 and G2 each additional graph is isomorphic to.ZKIP of Graph Non-IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyG1G2ZKIP of Graph Non-IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyG1G2ZKIP of Graph Non-IsomorphismH1H2H3H100January 14, 2019Practical Aspects of Modern CryptographyG1G2H1H2H3H100ZKIP of Graph Non-IsomorphismJanuary 14, 2019Practical Aspects of Modern CryptographyProving Something is a SquareSuppose I want to convince you that Y is a square modulo N.[There exists an X such that Y = X2 mod
View Full Document
Unlocking...