Contract Signing ProtocolsReal-World Fair ExchangeGeneral SettingWhy is Fair Exchange Difficult?Focus on Contract Signing ProtocolsExample: Stock TradingMany Types of ProtocolsContract Signing with Online TTPFundamental LimitationPartial Intuition for FLP ResultOptimistic Contract SigningCrypto Magic: Signature EscrowsPrivate Contract SignaturesAbuse-Free Contract SigningRole of Trusted Third PartyResolve SubprotocolAbort SubprotocolDesirable PropertiesFairness and TimelinessNo Advantage (Balance)Example of AdvantageGame-Theoretic ModelProtocol as a Game TreeDefine Properties on Game TreesKey Idea (omitting many subtleties)Advantage is Unavoidable (Intuition)Impossibility Result“Abuse-Free”: As Good as It GetsAbuse-Free Contract SigningResolve SubprotocolAbort SubprotocolAttack on AccountabilityRepairing the ProtocolCS 395TContract Signing ProtocolsReal-World Fair ExchangeImmunitydealBoth parties want to sign the dealNeither wants to commit firstGeneral SettingTwo parties agree on the items to exchange, each will release his item if the other releases hisPhysical solution is easy• Sit at a table and exchange items simultaneouslyGeneral problem: how to exchange information fairlyon an asynchronous network?• Both parties succeed or both failWhy is Fair Exchange Difficult?Cannot trust communication channels• Messages may be lost• Attacker may insert additional messagesCannot trust other party in protocol• www.Fly-By-Night.com• Public-key certificate does not certify honestyThere may exist a trustworthy judge ortrusted third party• Use sparingly, only if something goes wrong, otherwise becomes a communication bottleneckFocus on Contract Signing ProtocolsFair exchange of digital signaturesTwo parties want to sign a contract. Contract is known in advance to both parties.• We’ll look at protocols for exchanging signatures, notfor contract negotiation (e.g., auctions)• Multi-party signing is more complicatedThe attacker could be another party on the network or the person you think you want to sign a contract with• In key establishment protocols, usually assume that both parties are honestExample: Stock TradingWilling to sell stock at price XOk, willing to buy at price Xstock brokercustomerSigned contracts are essential as proofs of agreement in case market price changesMany Types of ProtocolsProbabilistic protocols• We looked at Rabin’s and BGMR protocolsGradual-release protocols• Exchange signatures a few bits at a time– Work required to guess remaining bits decreases– Main issue: it should be possible to verifythat the bits received so far are part of a valid signatureFixed-round protocols with trusted third party• Impossibility result: no two-party protocol can be fair– Reason: fair two-party exchange can be used to solve the distributed consensus problem• Need TTP in case one of the parties misbehavesContract Signing with Online TTPA BTTPsignature signaturecontractcontractProblem: TTP is the communication bottleneckCan it be removed?Fundamental Limitation(Very weak) consensus is not solvable if one or more processes can be faulty•Fisher, Lynch, Paterson. “Impossibility of Distributed Consensus with One Faulty Process”. J ACM (1985).Consensus problem in asynchronous setting• Several processes want to agree on value of some bit– Each process has initial 0 or 1, eventually “decides” on 0 or 1• Weak termination: some correct process decides• Agreement: no two processes decide on different values• Very weak validity: there is a run in which the decision is 0 and a run in which the decision is 1Partial Intuition for FLP ResultQuote from paper: The asynchronous commit protocols in current use all seem to have a “window of vulnerability”-an interval of time during the execution of the algorithm in which the delay or inaccessibility of a single process can cause the entire algorithm to wait indefinitely. It follows from our impossibility result that every commit protocol has such a “window,” confirming a widely believed tenet in the folklore.Optimistic Contract SigningI am going to sign the contractA BI am going to sign the contractHere is my signatureHere is my signature Involve trusted third party only if something goes wrong• Declares contract binding if presented with first two messagesCrypto Magic: Signature EscrowsOrdinary escrow: OrdEsc(sigA(m),T)• Similar to {sigA(m)}pk(T)• T can extract sigA(m) if formed correctly• B can’t extract sigA(m) and can’t verify what’s insideVerifiable escrow: VerEsc(sigA(m),T)• T can extract sigA(m) if formed correctly• B can’t extract sigA(m) but can verify that A’s signature is inside and that T will be able to extract itPrivate Contract SignaturesPrivate contract signature PCSX(m,Y,T)is an implementation of verifiable signature escrow• Non-interactive zero-knowledge designated-verifier proof of convertible commitment to a signature with a designated converterCan be created only by X, but Y can simulate it• Therefore, Y cannot use it as proof of X’s participationT can convert PCS into a universally verifiable signature sigX(m)• Y can verify that PCS sent by X can indeed be converted by T into X’s signatureOutsider can’t distinguish X’s private contract signature from Y’s simulation [Garay et al.]Abuse-Free Contract Signing[Garay, Jakobsson, MacKenzie]BPCSA(text,B,T)PCSB(text,A,T)sigA(text)sigB(text)ARole of Trusted Third PartyT can convert PCS to regular signature (“resolve”)• If one of the parties stops communicating, the other party can ask T to convert PCS into signatureT can issue an abort token (“abort”)• Promise not to resolve protocol in futureT acts only when requested by A or B• Decides whether to abort or resolve on a first-come-first-served basisResolve SubprotocolBATr1 = PCSA(text,B,T), sigB(text) aborted?Yes: r2 = sigT(a1)No: resolved := truer2 = sigA(text)store sigB(text)r2PCSA(text,B,T)???PCSB(text,A,T)sigT(a1)sigA(text)orIf A stops communicating,B asks T to convert A’s PCS,but must reveal his own sigAbort SubprotocolA???BTa1=sigA(m1,abort)a2resolved?Yes: a2 = sigB(text)No: aborted := truea2 = sigT(a1)m1= PCSA(text,B,T)sigB(text)sigT(a1)ORA (but not B!) can ask T to abort the protocol (i.e., to promise thatT won’t convert A’s PCS in future) This is not a guarantee that A won’t be able to obtain B’s signature byexecuting
View Full Document
Unlocking...