research.logos.co/assets/js/732c9736.de862e8b.js

"use strict";(self.webpackChunkresearch_logos_co=self.webpackChunkresearch_logos_co||[]).push([[7599],{23310:(s,a,e)=>{e.r(a),e.d(a,{assets:()=>r,contentTitle:()=>m,default:()=>x,frontMatter:()=>t,metadata:()=>n,toc:()=>c});var n=e(79503),i=e(74848),l=e(28453);const t={title:"Vac 101: Transforming an Interactive Protocol to a Noninteractive Argument",date:new Date("2024-10-15T12:00:00.000Z"),authors:"marvin",published:!0,slug:"vac101-fiat-shamir",categories:"research",toc_min_heading_level:2,toc_max_heading_level:5},m=void 0,r={authorsImageUrls:[void 0]},c=[{value:"Introduction",id:"introduction",level:2},{value:"Sigma Protocols",id:"sigma-protocols",level:2},{value:"The Schnorr Protocol",id:"the-schnorr-protocol",level:3},{value:"Chaum-Pedersen protocol",id:"chaum-pedersen-protocol",level:3},{value:"Hash Functions",id:"hash-functions",level:2},{value:"The Fiat-Shamir heuristic",id:"the-fiat-shamir-heuristic",level:2},{value:"Schnorr Protocol with the strong Fiat-Shamir",id:"schnorr-protocol-with-the-strong-fiat-shamir",level:3},{value:"Chaum-Pedersen Protocol with the strong Fiat-Shamir",id:"chaum-pedersen-protocol-with-the-strong-fiat-shamir",level:3},{value:"Improper use of the Fiat-Shamir heuristic",id:"improper-use-of-the-fiat-shamir-heuristic",level:2},{value:"Schnorr protocol with the weak Fiat-Shamir heuristic",id:"schnorr-protocol-with-the-weak-fiat-shamir-heuristic",level:3},{value:"Chaum-Pedersen protocol with the Fiat-Shamir heuristic",id:"chaum-pedersen-protocol-with-the-fiat-shamir-heuristic",level:3},{value:"Conclusion",id:"conclusion",level:2},{value:"References",id:"references",level:3}];function h(s){const a={a:"a",annotation:"annotation",h2:"h2",h3:"h3",li:"li",math:"math",mi:"mi",mn:"mn",mo:"mo",mover:"mover",mrow:"mrow",msub:"msub",msup:"msup",ol:"ol",p:"p",semantics:"semantics",span:"span",strong:"strong",table:"table",tbody:"tbody",td:"td",th:"th",thead:"thead",tr:"tr",ul:"ul",...(0,l.R)(),...s.components};return(0,i.jsxs)(i.Fragment,{children:[(0,i.jsx)(a.p,{children:"In this post, we introduce a common technique used to convert interactive protocols to their noninteractive variant."}),"\n","\n",(0,i.jsx)(a.h2,{id:"introduction",children:"Introduction"}),"\n",(0,i.jsx)(a.p,{children:"The set of interactive protocols form a class of protocols that consist of communication between two parties: the Prover and the Verifier.\nThe Prover tries to convince the Verifier of a given claim.\nFor example, the Prover may want to convince the Verifier that she owns a specific Unspent Transaction Output (UTXO);\nthat is, the Prover possesses the ability to spend the UTXO.\nIn many instances, there is information that the Prover does not wish to reveal to the Verifier.\nIn our example, it is critical that the Prover does not provide the Verifier with the spending key associated with her UTXO.\nIn addition to the Prover's claim and secret data, there is additional data, public parameters, that the claimed statement is expressed in terms of.\nThe public parameters can be thought of as the basis for all similar claims."}),"\n",(0,i.jsxs)(a.p,{children:["In an interactive protocol, the Prover and the Verifier are in active communication.\nSpecifically, the Prover and the Verifier exchange messages so that the Verifier can validate the Prover's claim.\nHowever, this communication is not practical for many applications.\nIt is necessary that any party can verify the Prover's claim in decentralized systems.\nIt is impractical for the Prover to be in active communication with a large number of verifying parties.\nInstead, it is desirable for the Prover to generate a proof on their own that can convince any party.\nTo achieve this, it is necessary for the Prover to generate the Verifier's messages in such a way\nthat the Prover cannot manipulate the Verifier's messages for her benefit.\nThe Fiat-Shamir heuristic ",(0,i.jsx)(a.a,{href:"https://dl.acm.org/doi/10.5555/36664.36676",children:"1"})," is used for this purpose.\nEven though much of our discussion will focus on ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u03a3"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\Sigma"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord",children:"\u03a3"})]})})]}),"-protocols,\nthe Fiat-Shamir heuristic is not limited to ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u03a3"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\Sigma"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord",children:"\u03a3"})]})})]}),"-protocols.\nThe Fiat-Shamir heuristic has been applied to zk-SNARKs, but the security in this setting has been the subject of discussion and research in recent years.\nBlock et al. ",(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2023/1071",children:"2"})," provide the first formal analysis of Fiat-Shamir heuristic in zk-SNARKs."]}),"\n",(0,i.jsx)(a.h2,{id:"sigma-protocols",children:"Sigma Protocols"}),"\n",(0,i.jsxs)(a.p,{children:["A ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u03a3"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\Sigma"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord",children:"\u03a3"})]})})]}),"-protocol is a family of interactive protocols that consists of three publicly transmitted messages between the Prover and the Verifier.\nIn particular, the protocol has the following framework:"]}),"\n",(0,i.jsxs)(a.table,{children:[(0,i.jsx)(a.thead,{children:(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.th,{children:"Prover"}),(0,i.jsx)(a.th,{}),(0,i.jsx)(a.th,{children:"Verifier"})]})}),(0,i.jsxs)(a.tbody,{children:[(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f6"})}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"c"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"o"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"m"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"m"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"i"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"t"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"m"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"t"})]})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{\\mathsf{commitment}}{\\longrightarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.2976em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.2866em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f6"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.711em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathsf mtight",children:"commitment"})})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f5"})}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"c"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"g"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"})]})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{\\mathsf{challenge}}{\\longleftarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.3552em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.3442em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f5"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.7581em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathsf mtight",children:"challenge"})})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f6"})}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"r"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"p"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"o"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"})]})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{\\mathsf{response}}{\\longrightarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.1802em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.1692em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f6"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.7581em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathsf mtight",children:"response"})})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]})]})]}),"\n",(0,i.jsxs)(a.p,{children:["These three messages form the protocol's transcript: ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"c"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"o"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"m"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"m"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"i"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"t"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"m"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"t"})]}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"c"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"l"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"g"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"})]}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"r"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"p"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"o"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"n"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"e"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(\\mathsf{commitment}, \\mathsf{challenge}, \\mathsf{response})"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"commitment"})}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"challenge"})}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"response"})}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]}),".\nThe Verifier uses all three of these messages to validate the Prover's original claim.\nThe Verifier's challenge should be selected uniform random from all possible challenges.\nBased on this selection, a dishonest Prover can only convince the Verifier with a negligible probability."]}),"\n",(0,i.jsx)(a.h3,{id:"the-schnorr-protocol",children:"The Schnorr Protocol"}),"\n",(0,i.jsxs)(a.p,{children:["The Schnorr protocol ",(0,i.jsx)(a.a,{href:"https://link.springer.com/chapter/10.1007/0-387-34805-0_22",children:"3"})," is usually the first ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u03a3"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\Sigma"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord",children:"\u03a3"})]})})]}),"-protocol that one studies.\nAdditionally, the Schnorr protocol can be used as an efficient signature scheme.\nThe Schnorr protocol provides a framework that enables the Prover to convince the Verifier that: for group elements ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]}),",\nthe Prover knows the power to raise ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," to obtain ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]}),".\nSpecifically, the Prover possesses some integer ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"x"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"x"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"x"})]})})]})," so that ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"x"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X = g^x"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8588em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"x"})})]})})})})})]})]})]})]}),".\nCryptographic resources may use either multiplicative or additive notation for groups;\nwe will use multiplicative notation.\nBriefly, the element ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," being combined with itself in multiplicative notation is ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"\u22c5"}),(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mn,{children:"2"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g \\cdot g = g^2"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(a.span,{className:"mbin",children:"\u22c5"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.0085em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.8141em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:"2"})})]})})})})})]})]})]})]}),",\nwhile in additive notation it is ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mn,{children:"2"}),(0,i.jsx)(a.mi,{children:"g"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g + g = 2g"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.7778em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(a.span,{className:"mbin",children:"+"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8389em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord",children:"2"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})]})]}),".\nWe assume that our group is of prime order ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"p"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"p"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"p"})]})})]}),", and is sufficiently large to satisfy the discrete logarithm assumption."]}),"\n",(0,i.jsx)(a.p,{children:"The Schnorr protocol proceeds as follows:"}),"\n",(0,i.jsxs)(a.table,{children:[(0,i.jsx)(a.thead,{children:(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.th,{children:"Prover"}),(0,i.jsx)(a.th,{}),(0,i.jsx)(a.th,{children:"Verifier"})]})}),(0,i.jsxs)(a.tbody,{children:[(0,i.jsxs)(a.tr,{children:[(0,i.jsxs)(a.td,{children:[(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{children:"R"})]}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"t \\in_R \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.7651em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"t"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsxs)(a.span,{className:"mrel",children:[(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3283em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.00773em"},children:"R"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]}),", ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"t"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"T := g^t"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.988em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.7936em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})})})})})]})]})]})]})]}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f6"})}),(0,i.jsx)(a.mi,{children:"T"})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{T}{\\longrightarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.3003em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.2893em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f6"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.711em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.13889em"},children:"T"})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f5"})}),(0,i.jsx)(a.mi,{children:"c"})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{c}{\\longleftarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.1234em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.1124em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f5"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.711em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{children:"R"})]}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c \\in_R \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6891em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsxs)(a.span,{className:"mrel",children:[(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3283em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.00773em"},children:"R"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]})})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mi,{children:"x"}),(0,i.jsx)(a.mi,{children:"c"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"z := t + xc"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6984em",verticalAlign:"-0.0833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"t"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(a.span,{className:"mbin",children:"+"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"x"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})]})]})}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f6"})}),(0,i.jsx)(a.mi,{children:"z"})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{z}{\\longrightarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.1234em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.1124em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f6"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.711em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{}),(0,i.jsxs)(a.td,{children:["output 1 provided ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"z"})]}),(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"="})}),(0,i.jsx)(a.mo,{stretchy:"false",lspace:"0em",rspace:"0em",children:"?"})]})}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mi,{children:"c"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g^z \\stackrel{?}{=} T X^c"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.3474em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.153em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"="})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.5669em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mclose mtight",children:"?"})})})]})]})})})})}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]})]})]})]})]})]})]})]}),"\n",(0,i.jsx)(a.h3,{id:"chaum-pedersen-protocol",children:"Chaum-Pedersen protocol"}),"\n",(0,i.jsxs)(a.p,{children:["A tuple of group elements ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(U,V,W)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]})," is a DH-triple if and only if there exists some ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"x"}),(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"x \\in \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.5782em",verticalAlign:"-0.0391em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"x"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]})," so that ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"x"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"V = g^x"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8588em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"x"})})]})})})})})]})]})]})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mi,{children:"x"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"W = U^x"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"x"})})]})})})})})]})]})]})]}),".\nThe Chaum-Pedersen protocol provides a framework that enables a Prover to convince a Verifier that she possesses such a ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"x"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"x"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"x"})]})})]})," for a claimed DH-triple ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(U,V,W)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]}),".\nThe Chaum-Pedersen protocol proceeds as follows:"]}),"\n",(0,i.jsxs)(a.table,{children:[(0,i.jsx)(a.thead,{children:(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.th,{children:"Prover"}),(0,i.jsx)(a.th,{}),(0,i.jsx)(a.th,{children:"Verifier"})]})}),(0,i.jsxs)(a.tbody,{children:[(0,i.jsxs)(a.tr,{children:[(0,i.jsxs)(a.td,{children:[(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{children:"R"})]}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"t \\in_R \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.7651em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"t"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsxs)(a.span,{className:"mrel",children:[(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3283em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.00773em"},children:"R"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]}),", ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"t"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"T := g^t"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.988em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.7936em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})})})})})]})]})]})]}),", ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"S"}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mi,{children:"t"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"S := U^t"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.05764em"},children:"S"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.7936em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.7936em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})})})})})]})]})]})]})]}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f6"})}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"S"})]})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{T,S}{\\longrightarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.3474em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.3364em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f6"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.7581em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mpunct mtight",children:","}),(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.05764em"},children:"S"})]})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f5"})}),(0,i.jsx)(a.mi,{children:"c"})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{c}{\\longleftarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.1234em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.1124em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f5"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.711em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{children:"R"})]}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c \\in_R \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6891em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsxs)(a.span,{className:"mrel",children:[(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3283em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.00773em"},children:"R"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]})})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mi,{children:"x"}),(0,i.jsx)(a.mi,{children:"c"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"z := t + xc"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6984em",verticalAlign:"-0.0833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"t"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}}),(0,i.jsx)(a.span,{className:"mbin",children:"+"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2222em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"x"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})]})]})}),(0,i.jsx)(a.td,{children:(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"\u27f6"})}),(0,i.jsx)(a.mi,{children:"z"})]})})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\stackrel{z}{\\longrightarrow}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.1234em",verticalAlign:"-0.011em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.1124em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"\u27f6"})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.711em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})})]})]}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.011em"},children:(0,i.jsx)(a.span,{})})})]})})})]})})]})}),(0,i.jsx)(a.td,{})]}),(0,i.jsxs)(a.tr,{children:[(0,i.jsx)(a.td,{}),(0,i.jsx)(a.td,{}),(0,i.jsxs)(a.td,{children:["output 1 provided ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"z"})]}),(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"="})}),(0,i.jsx)(a.mo,{stretchy:"false",lspace:"0em",rspace:"0em",children:"?"})]})}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mi,{children:"c"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g^z \\stackrel{?}{=} T V^c"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.3474em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.153em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"="})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.5669em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mclose mtight",children:"?"})})})]})]})})})})}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]})]})]})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mi,{children:"z"})]}),(0,i.jsx)(a.mo,{children:(0,i.jsxs)(a.mover,{children:[(0,i.jsx)(a.mo,{children:(0,i.jsx)(a.mo,{children:"="})}),(0,i.jsx)(a.mo,{stretchy:"false",lspace:"0em",rspace:"0em",children:"?"})]})}),(0,i.jsx)(a.mi,{children:"S"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mi,{children:"c"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"U^z \\stackrel{?}{=} SW^c"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.153em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:(0,i.jsx)(a.span,{className:"mop op-limits",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsxs)(a.span,{className:"vlist",style:{height:"1.153em"},children:[(0,i.jsxs)(a.span,{style:{top:"-3em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{children:(0,i.jsx)(a.span,{className:"mop",children:"="})})]}),(0,i.jsxs)(a.span,{style:{top:"-3.5669em",marginLeft:"0em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"3em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsx)(a.span,{className:"mclose mtight",children:"?"})})})]})]})})})})}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.05764em"},children:"S"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]})]})]})]})]})]})]})]}),"\n",(0,i.jsx)(a.h2,{id:"hash-functions",children:"Hash Functions"}),"\n",(0,i.jsxs)(a.p,{children:["Cryptographic hash functions serve as the backbone to the Fiat-Shamir heuristic.\nA hash function, ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})})]})})]}),", is a special function that takes in an arbitrary binary string and outputs a binary string of a predetermined fixed length.\nSpecifically,\n",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{stretchy:"false",children:"{"}),(0,i.jsx)(a.mn,{children:"0"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mn,{children:"1"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"}"}),(0,i.jsx)(a.mo,{children:"\u2217"})]}),(0,i.jsx)(a.mo,{children:"\u2192"}),(0,i.jsx)(a.mo,{stretchy:"false",children:"{"}),(0,i.jsx)(a.mn,{children:"0"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mn,{children:"1"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"}"}),(0,i.jsx)(a.mi,{children:"n"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash} : \\{0,1\\}^* \\rightarrow \\{0,1\\}^n"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"{"}),(0,i.jsx)(a.span,{className:"mord",children:"0"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord",children:"1"}),(0,i.jsxs)(a.span,{className:"mclose",children:[(0,i.jsx)(a.span,{className:"mclose",children:"}"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6887em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mbin mtight",children:"\u2217"})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"\u2192"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"{"}),(0,i.jsx)(a.span,{className:"mord",children:"0"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord",children:"1"}),(0,i.jsxs)(a.span,{className:"mclose",children:[(0,i.jsx)(a.span,{className:"mclose",children:"}"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"n"})})]})})})})})]})]})]})]}),"."]}),"\n",(0,i.jsx)(a.p,{children:"The security of cryptographic hash functions will rely on certain tasks being computationally infeasible.\nA task is computationally infeasible provided that there is no deterministic algorithm that can conclude the task in polynomial-time."}),"\n",(0,i.jsx)(a.p,{children:"A cryptographic hash function satisfies the following properties:"}),"\n",(0,i.jsxs)(a.ul,{children:["\n",(0,i.jsxs)(a.li,{children:[(0,i.jsx)(a.strong,{children:"Succinct"}),": The hash function should be easy to compute; the hash ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{mathvariant:"bold",children:"b"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}({\\bf{b}})"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"b"})})})}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]})," can be efficiently computed for any binary string ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"bold",children:"b"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"{\\bf{b}}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"b"})})})})]})})]}),"."]}),"\n",(0,i.jsxs)(a.li,{children:[(0,i.jsx)(a.strong,{children:"Preimage Resistance"}),": It should be computationally infeasible to work backwards given the output of a hash function. Let ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"bold",children:"y"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"{\\bf{y}}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",style:{marginRight:"0.01597em"},children:"y"})})})})]})})]})," be a binary string of length ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"n"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"n"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"n"})]})})]}),".\nIt should be 'impossible' to find some binary string ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"bold",children:"x"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"{\\bf{x}}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4444em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"x"})})})})]})})]})," so that ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"bold",children:"y"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{mathvariant:"bold",children:"x"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"{\\bf{y}} = \\mathsf{Hash}({\\bf{x}})"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",style:{marginRight:"0.01597em"},children:"y"})})})}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"x"})})})}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]}),"."]}),"\n",(0,i.jsxs)(a.li,{children:[(0,i.jsx)(a.strong,{children:"Collision Resistance"}),": It should be difficult to find two strings that hash to the same value.\nIt should be computationally infeasible to find two binary strings ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"bold",children:"x"}),(0,i.jsx)(a.mn,{mathvariant:"bold",children:"1"})]})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"{\\bf{x}_1}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.5944em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"x"})}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathbf mtight",children:"1"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})})})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"bold",children:"x"}),(0,i.jsx)(a.mn,{mathvariant:"bold",children:"2"})]})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"{\\bf{x}_2}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.5944em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"x"})}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathbf mtight",children:"2"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})})})]})})]})," so that ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"bold",children:"x"}),(0,i.jsx)(a.mn,{mathvariant:"bold",children:"1"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"bold",children:"x"}),(0,i.jsx)(a.mn,{mathvariant:"bold",children:"2"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"."})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}({\\bf{x}_1}) = \\mathsf{Hash}({\\bf{x}_2})."})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"x"})}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathbf mtight",children:"1"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})})}),(0,i.jsx)(a.span,{className:"mclose",children:")"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathbf",children:"x"})}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathbf mtight",children:"2"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})})}),(0,i.jsx)(a.span,{className:"mclose",children:")"}),(0,i.jsx)(a.span,{className:"mord",children:"."})]})]})]})]}),"\n"]}),"\n",(0,i.jsxs)(a.p,{children:["A related class of functions is one-way functions.\nA one-way function satisfies the first two conditions of a cryptographic hash function (succinct and preimage resistance).\nAll cryptographic hash functions are a one-way functions.\nHowever, one-way functions do not necessarily satisfy collision-resistance.\nWe will simply refer to cryptographic hash functions as hash functions for the rest of this blog.\nCommonly used hash functions include SHA-256 ",(0,i.jsx)(a.a,{href:"https://www.cs.princeton.edu/~appel/papers/verif-sha.pdf",children:"5"}),",\nKeccak ",(0,i.jsx)(a.a,{href:"https://keccak.team/keccak_specs_summary.html",children:"6"}),", and Poseidon ",(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2019/458",children:"7"}),"."]}),"\n",(0,i.jsx)(a.h2,{id:"the-fiat-shamir-heuristic",children:"The Fiat-Shamir heuristic"}),"\n",(0,i.jsxs)(a.p,{children:["The Fiat-Shamir heuristic is the technique used to convert an interactive protocol to a noninteractive protocol.\nThis is done by replacing each of the Verifier's messages with a hashed value.\nSpecifically, the Prover generates the Verifier's message by evaluating the hash function ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})})]})})]}),"\nwith the concatenation of all public values that appear in the protocol thus far.\nIf ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mn,{children:"0"})]}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mo,{children:"\u2026"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mi,{children:"t"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_0, \\dots, m_t"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"minner",children:"\u2026"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2806em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})})]})," denote the public values in the protocol thus far,\nthen the Verifier's message is computed as ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mn,{children:"1"})]})]}),(0,i.jsx)(a.mo,{children:":"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mn,{children:"0"})]}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mo,{children:"\u22ef"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mi,{children:"t"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_{t+1} := \\mathsf{Hash}(m_0|| \\cdots || m_t)"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.2083em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"}),(0,i.jsx)(a.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:":="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"minner",children:"\u22ef"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2806em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]}),"."]}),"\n",(0,i.jsxs)(a.p,{children:["Since ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})})]})})]})," can be efficiently computed, and the messages ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mn,{children:"0"})]}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mo,{children:"\u2026"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mi,{children:"t"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_0, \\dots, m_t"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"minner",children:"\u2026"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2806em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})})]})," are public, then any verifying party can compute ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mn,{children:"1"})]})]})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_{t+1}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.2083em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"}),(0,i.jsx)(a.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})})]}),".\nCritically, since ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})})]})})]})," is preimage resistant and collision resistant,\nthe Prover cannot manipulate her choices of the messages ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mn,{children:"0"})]}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mo,{children:"\u2026"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsx)(a.mi,{children:"t"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_0,\\dots, m_t"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:"0"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"minner",children:"\u2026"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2806em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})})]})," to influence the message ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mn,{children:"1"})]})]})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_{t+1}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.2083em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"}),(0,i.jsx)(a.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})})]}),".\nHence, verifying parties can trust that ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{children:"m"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"t"}),(0,i.jsx)(a.mo,{children:"+"}),(0,i.jsx)(a.mn,{children:"1"})]})]})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"m_{t+1}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6389em",verticalAlign:"-0.2083em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",children:"m"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3011em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"t"}),(0,i.jsx)(a.span,{className:"mbin mtight",children:"+"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2083em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})})]})," is sufficiently random with respect to the preceding messages."]}),"\n",(0,i.jsx)(a.p,{children:"There are two variants of the Fiat-Shamir heuristic: weak and strong.\nThe weak variant uses all of the publicly traded messages in computing the Verifier's messages but does not include the public parameters.\nHowever, in the strong variant all of the publicly traded messages and public parameters are used to compute the Verifier's messages.\nWe will provide a discussion on issues that can arise from using the weak Fiat-Shamir heuristic."}),"\n",(0,i.jsx)(a.h3,{id:"schnorr-protocol-with-the-strong-fiat-shamir",children:"Schnorr Protocol with the strong Fiat-Shamir"}),"\n",(0,i.jsxs)(a.p,{children:["When the strong Fiat-Shamir heuristic is applied to the Schnorr protocol, the message ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c = \\mathsf{Hash}(g||X||T)"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]}),".\nThis choice of ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]})," provides security since it should be computationally infeasible to find collisions for the outputs of ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})})]})})]}),".\nThus, ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]})," fixes the group elements ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]}),", ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"T"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"T"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"})]})})]}),"."]}),"\n",(0,i.jsxs)(a.p,{children:["The elements that would be omitted in the hash by applying weak Fiat-Shamir heuristic are ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]}),"."]}),"\n",(0,i.jsx)(a.h3,{id:"chaum-pedersen-protocol-with-the-strong-fiat-shamir",children:"Chaum-Pedersen Protocol with the strong Fiat-Shamir"}),"\n",(0,i.jsxs)(a.p,{children:["The message ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mi,{children:"H"}),(0,i.jsx)(a.mi,{children:"a"}),(0,i.jsx)(a.mi,{children:"s"}),(0,i.jsx)(a.mi,{children:"h"}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"S"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c = Hash(g||U||V||W||T||S)"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.08125em"},children:"H"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"a"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"s"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.05764em"},children:"S"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]})," when the Prover applies the strong Fiat-Shamir heuristic to the Chaum-Pedersen protocol.\nThe properties of ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\mathsf{Hash}"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6944em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})})]})})]})," fixes the generator ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," and the Prover's statement ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(U,V,W)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]}),"."]}),"\n",(0,i.jsx)(a.h2,{id:"improper-use-of-the-fiat-shamir-heuristic",children:"Improper use of the Fiat-Shamir heuristic"}),"\n",(0,i.jsx)(a.p,{children:"The Fiat-Shamir heuristic appears to be a fairly straightforward technique to implement.\nHowever, a subtle but serious issue that can occur in the application of the Fiat-Shamir heuristic has been a point of discussion for the past few years.\nThe issue concerns what messages are included in the hash.\nIn particular, are the public parameters used to compute the hash value?"}),"\n",(0,i.jsxs)(a.p,{children:["Bernhard et al. ",(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2016/771.pdf",children:"8"})," provide a discussion of Fiat-Shamir heuristic restricted to ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u03a3"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"\\Sigma"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord",children:"\u03a3"})]})})]}),"-protocols.\nIn particular, Bernhard et al. discuss the pitfalls of the weak Fiat-Shamir heuristic.\nRecall that the strong Fiat-Shamir heuristic requires that the public parameters are included in the calculations of the Verifier's messages while the weak version does not.\nThe inclusion of the public parameters in the hash evaluations fixes these public values for the entire protocol.\nThis means that the Prover cannot retroactively change them."]}),"\n",(0,i.jsxs)(a.p,{children:["The issues with the differences in the variants of the Fiat-Shamir heuristics has persisted since Bernhard et al.'s paper.\nIn recent years, auditors from ",(0,i.jsx)(a.a,{href:"https://www.trailofbits.com/",children:"Trail of Bits"})," and ",(0,i.jsx)(a.a,{href:"https://www.openzeppelin.com/",children:"OpenZeppelin"})," have\nreleased blogs (",(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/",children:"9"}),",\n",(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/14/the-frozen-heart-vulnerability-in-giraults-proof-of-knowledge/",children:"10"}),",\n",(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/15/the-frozen-heart-vulnerability-in-bulletproofs/",children:"11"}),", ",(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/18/the-frozen-heart-vulnerability-in-plonk/",children:"12"}),", ",(0,i.jsx)(a.a,{href:"https://blog.openzeppelin.com/the-last-challenge-attack",children:"13"}),")\nand papers (",(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2023/691",children:"14"}),", ",(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2024/398",children:"15"}),")\ndescribing specific vulnerabilities in zero-knowledge papers and repositories associated with the use of the weak Fiat-Shamir heuristic."]}),"\n",(0,i.jsxs)(a.p,{children:["Trail of Bits coined the term ",(0,i.jsx)(a.strong,{children:"FROZEN Heart"}),' to describe the use of weak Fiat-Shamir heuristic.\nFrozen comes from the phrase "FoRging Of ZEro kNowledge proofs",\nand Fiat-Shamir is the "heart" of transforming an interactive protocol to noninteractive protocol.']}),"\n",(0,i.jsx)(a.p,{children:"Now, we examine how weak Fiat-Shamir affects the Schnorr protocol and Chaum-Pedersen protocol."}),"\n",(0,i.jsx)(a.h3,{id:"schnorr-protocol-with-the-weak-fiat-shamir-heuristic",children:"Schnorr protocol with the weak Fiat-Shamir heuristic"}),"\n",(0,i.jsxs)(a.p,{children:["For Schnorr, we will examine two variants:\nthe first where we only include the Prover's claim ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]})," but not the public parameter ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]}),", and\nthe second where we include the public parameter ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," but not the Prover's claim ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]}),"."]}),"\n",(0,i.jsxs)(a.p,{children:["Since we omit the generator ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"G"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g \\in \\mathbb{G}"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.7335em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6889em"}}),(0,i.jsx)(a.span,{className:"mord mathbb",children:"G"})]})]})]})," from the computation for the message ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]})," in our first approach,\nthen ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c = \\mathsf{Hash}(X||T)"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]}),"."]}),"\n",(0,i.jsxs)(a.p,{children:["Now, a malicious Prover can complete the transcript for the Schnorr protocol by selecting any ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{children:"R"})]}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"z \\in_R \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6891em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsxs)(a.span,{className:"mrel",children:[(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3283em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.00773em"},children:"R"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]}),".\nSince, ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," is not fixed as it was not included in the computation of ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]}),".\nBut, the malicious Prover needs the transcript ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(T,c,z)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]})," to satisfy ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"z"})]}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mi,{children:"c"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g^z = TX^c"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8588em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]})]})]})]}),".\nHence, the malicious Prover can compute the generator ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mi,{children:"c"})]}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:")"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{children:"\u2212"}),(0,i.jsx)(a.mn,{children:"1"})]})]})]}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"."})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g = (TX^c)^{z^{-1}}."})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.2369em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]}),(0,i.jsxs)(a.span,{className:"mclose",children:[(0,i.jsx)(a.span,{className:"mclose",children:")"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.9869em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.8913em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.931em",marginRight:"0.0714em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.5em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size3 size1 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mtight",children:"\u2212"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})})})})})]})})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mord",children:"."})]})]})]})]}),"\n",(0,i.jsxs)(a.p,{children:["In our second approach, we omit the group element ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"G"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X \\in \\mathbb{G}"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.7224em",verticalAlign:"-0.0391em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6889em"}}),(0,i.jsx)(a.span,{className:"mord mathbb",children:"G"})]})]})]})," from the computation for the challenge ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]}),".\nThat is, ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"H"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"a"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"s"}),(0,i.jsx)(a.mi,{mathvariant:"sans-serif",children:"h"})]}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"\u2223"}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c = \\mathsf{Hash}(g||T)"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord",children:(0,i.jsx)(a.span,{className:"mord mathsf",children:"Hash"})}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mord",children:"\u2223\u2223"}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]}),"."]}),"\n",(0,i.jsxs)(a.p,{children:["As with the previous example, the malicious Prover takes a Schnorr transcript ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(T,c,z)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]})," where ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"z"}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mo,{children:"\u2208"}),(0,i.jsx)(a.mi,{children:"R"})]}),(0,i.jsxs)(a.msub,{children:[(0,i.jsx)(a.mi,{mathvariant:"double-struck",children:"Z"}),(0,i.jsx)(a.mi,{children:"p"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"z \\in_R \\mathbb{Z}_p"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6891em",verticalAlign:"-0.15em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsxs)(a.span,{className:"mrel",children:[(0,i.jsx)(a.span,{className:"mrel",children:"\u2208"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.3283em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.00773em"},children:"R"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.15em"},children:(0,i.jsx)(a.span,{})})})]})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.975em",verticalAlign:"-0.2861em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathbb",children:"Z"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsxs)(a.span,{className:"vlist-t vlist-t2",children:[(0,i.jsxs)(a.span,{className:"vlist-r",children:[(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.1514em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.55em",marginLeft:"0em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"p"})})]})}),(0,i.jsx)(a.span,{className:"vlist-s",children:"\u200b"})]}),(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.2861em"},children:(0,i.jsx)(a.span,{})})})]})})]})]})]})]}),".\nIt is necessary for the malicious Prover to find a value ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"X"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"})]})})]})," so that ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"z"})]}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mi,{children:"c"})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g^z = TX^c"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8588em",verticalAlign:"-0.1944em"}}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})]})})})})})]}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]})]})]})]}),".\nThis can be acheived by computing ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"X"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mi,{children:"z"})]}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{children:"\u2212"}),(0,i.jsx)(a.mn,{children:"1"})]})]}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:")"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{children:"\u2212"}),(0,i.jsx)(a.mn,{children:"1"})]})]})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"X = (g^z T^{-1})^{c^{-1}}"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.07847em"},children:"X"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.2369em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})})]})})})})})]}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.8141em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mtight",children:"\u2212"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})})})})})]}),(0,i.jsxs)(a.span,{className:"mclose",children:[(0,i.jsx)(a.span,{className:"mclose",children:")"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.9869em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.8913em"},children:(0,i.jsxs)(a.span,{style:{top:"-2.931em",marginRight:"0.0714em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.5em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size3 size1 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mtight",children:"\u2212"}),(0,i.jsx)(a.span,{className:"mord mtight",children:"1"})]})})]})})})})})]})})})]})})})})})]})]})]})]}),"."]}),"\n",(0,i.jsx)(a.h3,{id:"chaum-pedersen-protocol-with-the-fiat-shamir-heuristic",children:"Chaum-Pedersen protocol with the Fiat-Shamir heuristic"}),"\n",(0,i.jsxs)(a.p,{children:["The Verifier's message ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"c"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mi,{children:"H"}),(0,i.jsx)(a.mi,{children:"a"}),(0,i.jsx)(a.mi,{children:"s"}),(0,i.jsx)(a.mi,{children:"h"}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"S"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c = Hash(T,S)"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.08125em"},children:"H"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"a"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"s"}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"h"}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.05764em"},children:"S"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})]})]})," when weak Fiat-Shamir heuristic is applied.\nThe Prover's triple ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(U,V,W)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]})," and the generator ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," are not fixed by ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]}),".\nAs such, a malicious Prover can generate values for ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"U,V,W"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8778em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"})]})})]}),", and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," that satisfy the Verifier's identity checks.\nIn the case of a malicious Prover, ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"T"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"T"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"S"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"S"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.05764em"},children:"S"})]})})]})," are randomly group elements instead of being computed using a value ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"t"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"t"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6151em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"t"})]})})]})," that the Prover selected.\nThis means a malicious Prover must randomly select the value ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"z"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"z"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.04398em"},children:"z"})]})})]})," as well."]}),"\n",(0,i.jsxs)(a.p,{children:["Given the values that have been fixed so far, each of the Verifier's identities consists of two unknowns.\nHence, it is necessary to select one of these unknowns from each identity so that a malicious Prover can compute the last value.\nFor instances, suppose that the malicious Prover randomly selects ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"V"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"V"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"W"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"W"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"})]})})]}),".\nThe malicious Prover can compute ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"g"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"T"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mi,{children:"c"})]}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:")"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mn,{children:"1"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"/"}),(0,i.jsx)(a.mi,{children:"z"})]})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g = (T V^c)^{1/z}"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.138em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"T"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]}),(0,i.jsxs)(a.span,{className:"mclose",children:[(0,i.jsx)(a.span,{className:"mclose",children:")"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.888em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mtight",children:"1/"}),(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})]})})]})})})})})]})]})]})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{children:"="}),(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"S"}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mi,{children:"c"})]}),(0,i.jsxs)(a.msup,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:")"}),(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mn,{children:"1"}),(0,i.jsx)(a.mi,{mathvariant:"normal",children:"/"}),(0,i.jsx)(a.mi,{children:"z"})]})]})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"V = (SW^c)^{1/z}"})]})})}),(0,i.jsxs)(a.span,{className:"katex-html","aria-hidden":"true",children:[(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.6833em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}}),(0,i.jsx)(a.span,{className:"mrel",children:"="}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.2778em"}})]}),(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1.138em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.05764em"},children:"S"}),(0,i.jsxs)(a.span,{className:"mord",children:[(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.6644em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsx)(a.span,{className:"mord mathnormal mtight",children:"c"})})]})})})})})]}),(0,i.jsxs)(a.span,{className:"mclose",children:[(0,i.jsx)(a.span,{className:"mclose",children:")"}),(0,i.jsx)(a.span,{className:"msupsub",children:(0,i.jsx)(a.span,{className:"vlist-t",children:(0,i.jsx)(a.span,{className:"vlist-r",children:(0,i.jsx)(a.span,{className:"vlist",style:{height:"0.888em"},children:(0,i.jsxs)(a.span,{style:{top:"-3.063em",marginRight:"0.05em"},children:[(0,i.jsx)(a.span,{className:"pstrut",style:{height:"2.7em"}}),(0,i.jsx)(a.span,{className:"sizing reset-size6 size3 mtight",children:(0,i.jsxs)(a.span,{className:"mord mtight",children:[(0,i.jsx)(a.span,{className:"mord mtight",children:"1/"}),(0,i.jsx)(a.span,{className:"mord mathnormal mtight",style:{marginRight:"0.04398em"},children:"z"})]})})]})})})})})]})]})]})]}),".\nThus, the malicious Prover has a claimed statement ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mo,{stretchy:"false",children:"("}),(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{stretchy:"false",children:")"})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"(U,V,W)"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"1em",verticalAlign:"-0.25em"}}),(0,i.jsx)(a.span,{className:"mopen",children:"("}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mclose",children:")"})]})})]})," for generator ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," that passes the Verifier's identities using weak Fiat-Shamir heuristic."]}),"\n",(0,i.jsxs)(a.p,{children:["The omission of any of the values ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsxs)(a.mrow,{children:[(0,i.jsx)(a.mi,{children:"U"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"V"}),(0,i.jsx)(a.mo,{separator:"true",children:","}),(0,i.jsx)(a.mi,{children:"W"}),(0,i.jsx)(a.mo,{separator:"true",children:","})]}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"U,V,W,"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.8778em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.10903em"},children:"U"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.22222em"},children:"V"}),(0,i.jsx)(a.span,{className:"mpunct",children:","}),(0,i.jsx)(a.span,{className:"mspace",style:{marginRight:"0.1667em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.13889em"},children:"W"}),(0,i.jsx)(a.span,{className:"mpunct",children:","})]})})]})," and ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"g"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"g"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.625em",verticalAlign:"-0.1944em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",style:{marginRight:"0.03588em"},children:"g"})]})})]})," in the computation of ",(0,i.jsxs)(a.span,{className:"katex",children:[(0,i.jsx)(a.span,{className:"katex-mathml",children:(0,i.jsx)(a.math,{xmlns:"http://www.w3.org/1998/Math/MathML",children:(0,i.jsxs)(a.semantics,{children:[(0,i.jsx)(a.mrow,{children:(0,i.jsx)(a.mi,{children:"c"})}),(0,i.jsx)(a.annotation,{encoding:"application/x-tex",children:"c"})]})})}),(0,i.jsx)(a.span,{className:"katex-html","aria-hidden":"true",children:(0,i.jsxs)(a.span,{className:"base",children:[(0,i.jsx)(a.span,{className:"strut",style:{height:"0.4306em"}}),(0,i.jsx)(a.span,{className:"mord mathnormal",children:"c"})]})})]})," allows a malicious Prover to forge a proof."]}),"\n",(0,i.jsx)(a.h2,{id:"conclusion",children:"Conclusion"}),"\n",(0,i.jsx)(a.p,{children:"The Fiat-Shamir heuristic is an essential technique to convert an interactive protocol to a variant that does not require communication.\nAdditionally, careful application of this technique is necessary to maintain the integrity of the system."}),"\n",(0,i.jsx)(a.h3,{id:"references",children:"References"}),"\n",(0,i.jsxs)(a.ul,{children:["\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://dl.acm.org/doi/10.5555/36664.36676",children:"How to Prove Yourself: Practical Solutions to Identification and Signature Problems"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"2",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2023/1071",children:"Fiat-Shamir Security of FRI and Related SNARKs"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"3",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://link.springer.com/chapter/10.1007/0-387-34805-0_22",children:"Efficient Identification and Signatures for Smart Cards"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"4",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://link.springer.com/content/pdf/10.1007/3-540-48071-4_7.pdf",children:"Wallet Databases with Observers"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"5",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://www.cs.princeton.edu/~appel/papers/verif-sha.pdf",children:"Verification of a Cryptographic Primitive: SHA-256"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"6",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://keccak.team/keccak_specs_summary.html",children:"Keccak specifications summary"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"7",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2019/458",children:"Poseidon: A New Hash Function for Zero-Knowledge Proof Systems"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"8",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2016/771.pdf",children:"How not to Prove Yourself: Pitfalls of the Fiat-Shamir Heuristic and Applications to Helios"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"9",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/13/part-1-coordinated-disclosure-of-vulnerabilities-affecting-girault-bulletproofs-and-plonk/",children:"Frozen Heart - Part 1"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"10",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/14/the-frozen-heart-vulnerability-in-giraults-proof-of-knowledge/",children:"Frozen Heart - Part 2"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"11",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/15/the-frozen-heart-vulnerability-in-bulletproofs/",children:"Frozen Heart - Part 3"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"12",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://blog.trailofbits.com/2022/04/18/the-frozen-heart-vulnerability-in-plonk/",children:"Frozen Heart - Part 4"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"13",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://blog.openzeppelin.com/the-last-challenge-attack",children:"The Last Challenge Attack Blog"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"14",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2023/691",children:"Weak Fiat-Shamir Attacks on Modern Proof Systems"})}),"\n"]}),"\n"]}),"\n",(0,i.jsxs)(a.li,{children:["\n",(0,i.jsxs)(a.ol,{start:"15",children:["\n",(0,i.jsx)(a.li,{children:(0,i.jsx)(a.a,{href:"https://eprint.iacr.org/2024/398",children:"The Last Challenge Attack"})}),"\n"]}),"\n"]}),"\n"]})]})}function x(s={}){const{wrapper:a}={...(0,l.R)(),...s.components};return a?(0,i.jsx)(a,{...s,children:(0,i.jsx)(h,{...s})}):h(s)}},28453:(s,a,e)=>{e.d(a,{R:()=>t,x:()=>m});var n=e(96540);const i={},l=n.createContext(i);function t(s){const a=n.useContext(l);return n.useMemo((function(){return"function"==typeof s?s(a):{...a,...s}}),[a,s])}function m(s){let a;return a=s.disableParentContext?"function"==typeof s.components?s.components(i):s.components||i:t(s.components),n.createElement(l.Provider,{value:a},s.children)}},79503:s=>{s.exports=JSON.parse('{"permalink":"/rlog/vac101-fiat-shamir","source":"@site/rlog/2024-10-15-vac101-fiat-shamir.mdx","title":"Vac 101: Transforming an Interactive Protocol to a Noninteractive Argument","description":"In this post, we introduce a common technique used to convert interactive protocols to their noninteractive variant.","date":"2024-10-15T12:00:00.000Z","tags":[],"readingTime":10.67,"hasTruncateMarker":true,"authors":[{"name":"Marvin","github":"jonesmarvin8","key":"marvin","page":null}],"frontMatter":{"title":"Vac 101: Transforming an Interactive Protocol to a Noninteractive Argument","date":"2024-10-15T12:00:00.000Z","authors":"marvin","published":true,"slug":"vac101-fiat-shamir","categories":"research","toc_min_heading_level":2,"toc_max_heading_level":5},"unlisted":false,"prevItem":{"title":"Libp2p GossipSub IDONTWANT Message Performance Impact","permalink":"/rlog/gsub-idontwant-perf-eval"},"nextItem":{"title":"zkVM Testing Report: Evaluating Zero-Knowledge Virtual Machines for Nescience","permalink":"/rlog/zkVM-testing"}}')}}]);