外文资料原文1.pdf

Author B Schoenmakers Verifi able Secret Sharing A basic secret sharing scheme is defi ned to resist passive attacks only which means that its security depends on the assumption that all parties involved run the protocols as prescribed by the scheme After taking part in the distribution protocol a non qualifi ed set of participants is not able to deduce part of the secret from their shares In many applications however a secret sharing scheme is also required to withstand active attacks This is accomplished by verifi able secret sharing VSS schemes as fi rst introduced in CGMA85 Specifi cally a VSS scheme is required to withstand the following two types of active attacks a dealer sending inconsistent or incorrect shares to some of the participants during the distribution protocol and participants submitting incorrect shares during the reconstruction protocol Clearly Shamir s threshold scheme is not a VSS scheme since it does not exclude either of these attacks A well known example is Feldman s VSS scheme Fel87 Informally Feldman s scheme runs as follows for the case of t n threshold access structures 1 t n Let g denote a generator of a cyclic group G of order p where p is a large prime p n The distribution protocol and reconstruction protocol for dealer and participants P1 Pn are defi ned as follows Distribution Let s RZpdenote the secret to be distributed by the dealer The dealer chooses a random polynomial in Zp x of the form a x s 1x t 1xt 1 subject to the condition that 0 s The dealer sends share si a i to participant Piin private for i 1 n In addition the dealer broadcasts values Bj g j 0 j t Upon receipt of its share si each participant verifi es the validity of the share by evaluating the following equation gsi t 1 Y j 0 Bi j j 1 Reconstruction Each share sicontributed by participant Pi is verifi ed using Eq 1 The secret s a 0 is then recovered as in Shamir s threshold scheme using t valid shares Because of Eq 1 it is impossible for the dealer to give out inconsistent shares to honest participants The only way the dealer may cheat is by sending incorrect shares to some participants Each participant receiving an incorrect share during the distribution protocol is supposed to fi le a complaint against the dealer If the dealer receives t or more complaints the distribution is said to fail Otherwise the dealer is required to broadcast the correct shares si 1 for all participants Pi who fi led a complaint If the decisional Diffi e Hellmann problem is hard for group G Feldman s VSS scheme is secure against cheating by the dealer and cheating by at most t 1 of the participants as long as 2 t 1 n Another well known example is Pedersen s VSS scheme Ped92 The schemes by Feldman and Pedersen are called non interactive because the distribution protocol does not require any interaction between the dealer and participants nor between participants among each other except for the fi ling of complaints Publicly verifi able secret sharing PVSS schemes as introduced by Stadler Sta96 remove the need for interaction entirely by ensuring that anyone not just the participants is able to verify the shares distributed by the dealer see also FO98 Sch99 YY01 Many examples of interactive VSS schemes can be found in papers presenting protocols for secure multiparty computation see GMW87 BGW88 CCD88 and later papers Typically interactive VSS schemes rely on the use of authentication tags checking vectors or similar ideas For instance the VSS scheme of BGW88 lets the dealer choose a random bivariate polynomial p x y of degree at most t 1 such that s p 0 0 for a secret s The dealer sends each participant Pitwo univariate polynomials of degree at most t 1 ai x p x i and bi y p i y Each participant is supposed to check that ai i bi i Furthermore each pair of participants Piand Pjchecks that ai j bj i An interactive protocol between the dealer and the participants is used to determine whether distribution was successful or not Apart from their use in secure multiparty computation VSS schemes are specifi cally used in the construction of distributed key generation DKG protocols which are in turn a basic tool in threshold cryptography The object of a DKG protocol is to let a group of n parties jointly generate a key consisting of a private key and a public key such that the private key is shared among the n parties see e g Ped91 GJKR99 GJKR03 References BGW88 M Ben Or S Goldwasser and A Wigderson Completeness theorems for non cryptographic fault tolerant distributed computation In Proc 20th Symposium on Theory of Computing STOC 88 pages 1 10 New York 1988 A C M CCD88 D Chaum C Cr epeau and I Damg ard Multiparty unconditionally secure pro tocols In Proc 20th Symposium on Theory of Computing STOC 88 pages 11 19 New York 1988 A C M CGMA85 B Chor S Goldwasser S Micali and B Awerbuch Verifi able secret sharing and achieving simultaneity in the presence of faults In Proc 26th IEEE Symposium on Foundations of Computer Science FOCS 85 pages 383 395 IEEE Computer Society 1985 Fel87 P Feldman A practical scheme for non interactive verifi able secret sharing In Proc 28th IEEE Symposium on Foundations of Computer Science FOCS 87 pages 427 437 IEEE Computer Society 1987 FO98 E Fujisaki and T Okamoto A practical and provably secure scheme for pub licly verifi able secret sharing and its applications In Advances in Cryptology 2 EUROCRYPT 98 volume 1403 of Lecture Notes in Computer Science pages 32 46 Berlin 1998 Springer Verlag GJKR99 R Gennaro S Jarecki H Krawczyk and T Rabin Secure distributed key generation for discrete log based cryptosystems In Advances in Cryptology EUROCRYPT 99 volume 1592 of Lecture Notes in Computer Science pages 295 310 Berlin 1999 Springer Verlag GJKR03 R Gennaro S Jarecki H Krawczyk and T Rabin Secure applications of pedersens distributed key generation protocol In Cryptographers Track RSA 2003 volume 2612 of Lecture Notes in Computer Science pages 373 390 Berlin 2003 Springer Verlag GMW87 O Goldreich S Micali and A Wigderson How to play any mental game or a completeness theorem for protocols with honest majority In Proc 19th Symposium on Theory of Computing STOC 87 pages 218 229 New York 1987 A C M Ped91 T Pedersen A threshold cryptosystem without a trusted party In Advances in Cryptology EUROCRYPT 91 volume 547 of Lecture Notes in Computer Science pages 522 526 Berlin 1991 Springer Verlag Ped92 T P Pedersen Non interactive and information theoretic secure verifi able secret sharing In Advances in Cryptology CRYPTO 91