Show simple item record

dc.contributor.advisorKatz, Jonathanen_US
dc.contributor.authorKumaresan, Ranjiten_US
dc.date.accessioned2012-10-11T06:18:51Z
dc.date.available2012-10-11T06:18:51Z
dc.date.issued2012en_US
dc.identifier.urihttp://hdl.handle.net/1903/13265
dc.description.abstractBroadcast and verifiable secret sharing (VSS) are central building blocks for secure multi-party computation. These protocols are required to be resilient against a Byzantine adversary who controls at most t out of the n parties running the protocol. In this dissertation, we consider the design of fault-tolerant protocols for broadcast and verifiable secret sharing with stronger security guarantees and improved round complexity. Broadcast allows a party to send the same message to all parties, and all parties are assured they have received identical messages. Given a public-key infrastructure (PKI) and digital signatures, it is possible to construct broadcast protocols tolerating any number of corrupted parties. We address two important issues related to broadcast: (1) Almost all existing protocols do not distinguish between corrupted parties (who do not follow the protocol) and honest parties whose secret (signing) keys have been compromised (but who continue to behave honestly); (2) all existing protocols for broadcast are insecure against an adaptive adversary who can choose which parties to corrupt as the protocol progresses. We propose new security models that capture these issues, and present tight feasibility and impossibility results. In the problem of verifiable secret sharing, there is a designated player who shares a secret during an initial sharing phase such that the secret is hidden from an adversary that corrupts at most t parties. In a subsequent reconstruction phase of the protocol, a unique secret, well-defined by the view of honest players in the sharing phase, is reconstructed. The round complexity of VSS protocols is a very important metric of their efficiency. We show two improvements regarding the round complexity of information-theoretic VSS. First, we construct an efficient perfectly secure VSS protocol tolerating t < n/3 corrupted parties that is simultaneously optimal in both the number of rounds and the number of invocations of broadcast. Second, we construct a statistically secure VSS protocol tolerating t < n/2 corrupted parties that has optimal round complexity, and an efficient statistical VSS protocol tolerating t < n/2 corrupted parties that requires one additional round.en_US
dc.titleBroadcast and Verifiable Secret Sharing: New Security Models and Round Optimal Constructionsen_US
dc.typeDissertationen_US
dc.contributor.publisherDigital Repository at the University of Marylanden_US
dc.contributor.publisherUniversity of Maryland (College Park, Md.)en_US
dc.contributor.departmentComputer Scienceen_US
dc.subject.pqcontrolledComputer scienceen_US
dc.subject.pquncontrolledBroadcasten_US
dc.subject.pquncontrolledCryptographyen_US
dc.subject.pquncontrolledEfficiencyen_US
dc.subject.pquncontrolledRound Optimal Constructionsen_US
dc.subject.pquncontrolledSecurityen_US
dc.subject.pquncontrolledVerifiable Secret Sharingen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record