在向量空间上的防欺诈秘密分享方案

Designs,CodesandCryptography,16,75–85(1999)c°1999KluwerAcademicPublishers,Boston.ManufacturedinTheNetherlands.DetectionofCheatersinVectorSpaceSecretSharingSchemes*CARLESPADR¶[e-mail]¶ANS¶[e-mail]@mat.upc.esDepartamentdeMatem`aticaAplicadaiTelem`atica,UniversitatPolit`ecnicadeCatalunya,M`odulC3,CampusNord,c/JordiGirona,1-3,08034Barcelona,SpainCommunicatedby:D.JungnickelReceivedAugust21,1996;RevisedApril8,1998;AcceptedApril16,1998Abstract.AperfectsecretsharingschemeisamethodofdistributingsharesofasecretamongasetPofparticipantsinsuchawaythatonlyqualifiedsubsetsofPcanreconstructthesecretfromtheirsharesandnon-qualifiedsubsetshaveabsolutelynoinformationonthevalueofthesecret.Inasecretsharingscheme,someparticipantscouldlieaboutthevalueoftheirsharesinordertoobtainsomeillicitbenefit.Therefore,thesecurityagainstcheatingisanimportantissueintheimplementationofsecretsharingschemes.Twonewsecretsharingschemesinwhichcheatersaredetectedwithhighprobabilityarepresentedinthispaper.Thefirstonehasinformationrateequalto1=2andcanbeimplementednotonlyinthresholdstructures,butinamoregeneralfamilyofaccessstructures.Weprovethattheinformationrateofthisschemeisalmostoptimalamongallschemeswiththesamesecurityrequirements.Thesecondschemeweproposeisathresholdschemeinwhichcheatersaredetectedwithhighprobabilityeveniftheyknowthesecret.Theinformationrateisinthiscase1=3.Inbothschemes,theprobabilityofcheatingsuccessfullyisafixedvaluethatisdeterminedbythesizeofthesecret.Keywords:secretsharingschemes,detectionofcheaters,unconditionalysecurityinsecretsharing,informationrate1.IntroductionAsecretsharingschemeisamethodofdistributingsharesofasecretamongasetPofparticipantsinsuchawaythatonlyqualifiedsubsetsofPcanreconstructthesecretfromtheirshares.Suchaschemeissaidtobeperfectifthesubsetsthatarenotqualifiedtoreconstructthesecrethaveabsolutelynoinformationonit.Theaccessstructure,¡½2P,ofasecretsharingschemeisthefamilyofqualifiedsubsets.Forexample,theaccessstructureofa(r;n)-thresholdschemeconsistsofallthesubsetswithatleastrofnparticipants.ThresholdschemeswerethefirstsecretsharingschemesandhavebeenindependentlyintroducedbyBlakley[2]andShamir[15]in1979.Thereexiststhepossibilitythatsomeparticipantslieaboutthevalueoftheirsharesinordertoobtainsomeillicitbenefit.Therefore,thesecurityagainstcheatingisanimportantissueintheimplementationofsecretsharingschemes.Weareinterestedhereinuncon-ditionalsecurity,thatis,theprobabilityofcheatingsuccessfullymustnotdependonthecomputationalresourcesavailabletotheparticipants.*ApreviousversionofthispaperappearedinProceedingsofPRAGOCRYPT’96.ThisworkwaspartiallysupportedbyCICYTunderprojectTIC97-0963.76PADR¶O,S¶AEZANDVILLARTheunconditionalsecurityofthresholdschemeshasbeenconsideredbyseveralauthorsunderdifferentassumptions.IntheschemesproposedbyRif`a-Coma[14]andOgataandKurosawa[13],cheatersaredetectedwithhighprobabilityiftheydonotknowthevalueofthesecret.TompaandWoll’sscheme[19]isunconditionallysecureagainstcheatingevenifacoalitionofparticipantswhoknowthesecrettriestodeceiveanhonestparticipantaboutthevalueofthesecret.TheschemeproposedbyRif`a-Comausesrationalinterpolationinsteadofpolynomialinterpolation.TheschemeproposedbyOgataandKurosawa,whichhasoptimalinformationrate,usesplanardifferencesets.TompaandWoll’sschemeisamodificationofShamir’sschemeconsideringonlypartofthesecretsaslegalvaluesofit.Inotherschemes[1,7,9],cheatersarenotonlydetected,butalsoidentifiedwithhighprobability,eveniftheyknowthesecret.Asfarasweknow,allunconditionallysecureschemesproposeduntilnowarethresholdschemes.Sincethesecurityofasystemdegradeswiththeamountofinformationthatmustbekeptsecret,anotherimportantrequirementinthedesignofsecretsharingschemesisthesizeofthesharesgiventotheparticipants.Whenitisrequiredthatnonqualifiedsubsetsobtainnoinformationonthesecret,thesizeofthesharesmustbeatleastthesizeofthesecret[12].Theinformationrateofasecretsharingschemeistheratiobetweenthelength(inbits)ofthesecretandthemaximumlengthofthesharesgiventotheparticipants.Asecretsharingschemeissaidtobeidealifitsinformationrateisequaltoone,whichisthemaximumpossiblevalue.Severalauthorsgaveupperandlowerboundstotheinformationrateofsecretsharingschemesrealizingdifferentaccessstructures[3,4,6,8].Classicalidealschemesareveryvulnerabletocheatingandtheydonotconsentthedetec-tionofcheaters.Unconditionalsecurityagainstcheatingisattainedbyaddingredundantinformationtothesharesgiventotheparticipants.Carpentieri,DeSantisandVaccaro[10]foundalowerboundforthesizeofsharesinathresholdschemeinrelationtoitssecurity.Thisboundincreasesastheprobabilityofcheatingwithoutbeingdetecteddecreases.Be-sides,thesizeofsharesintheschemesthatmakepossibletheidentificationofcheatersismuchlargerthaninthosethatonlydetectthem.Inthispaperweconsidertheproblemoffindingperfectsecretsharingschemesuncondi-tionallysecureagainstcheatingandhavinginformationrateashighaspossible.Weshallsupposetheexistenceoftwodifferentkindsofcheaters:1.Participantswhodonotknowthesecretandcheattodeceivetheotherparticipantsand,ifitisposs