PROBLEM

KristinAnderson,FredrikClaesson,JacobL¨ofvenberg,andIngemarIngemarsson

DepartmentofElectricalEngineering,Link¨opingsuniversitet,SE-58183Link¨oping,Sweden

{krian,fcl,jacob,i2}@isy.liu.se

ABSTRACT

Inthispaperweconsiderthesubsetdifferenceschemeforbroadcastencryptionandcountthenumberofrequiredbroadcasttransmissionswhenusingthisscheme.Thesub-setdifferenceschemeorganizesreceiversinatreestruc-tureandwenotethatisomorphictreesyieldthesamenum-berofrequiredbroadcasttransmissions.Basedontheiso-morphismthetreescanbepartitionedintoclasses.

Wesuggesttousethevastamountoftoolsavailablefromthetheoryofgroupstoanalyzethesubsetdifferenceschemeandthereforeweformulatethemappingsbetweenisomorphictreesusingconceptsfromgrouptheory.Fi-nallyweidentifysomeresearchissuesforfurtherstudyoftheperformanceofthesubsetdifferenceschemeusinggrouptheory.

1.THEBROADCASTENCRYPTION

PROBLEM

Weconsiderascenarioinwhichoneormoresenderswanttosecurelytransmitamessagetoaselectedsubsetofre-ceivers,calledtheprivilegedset,usingabroadcastchan-nel.Two-waycommunicationisnotallowedonthechan-nel.Thisproblemisknownasthebroadcastencryptionproblem.Anexampleofsuchascenarioisthedistribu-tionofdigitaltelevisionwherethedistributorswantonlythepayingsubscriberstobeabletodecryptandviewtheirbroadcasts.

AnotherapplicationareaisinmilitaryorcivilianTETRA-likenetworkswhereitisnecessarytobeabletosendvoice/videoortextmessagestogroupsofuserswhilemaintainingconfidentialitysothatnooutsidercanaccesstheinformation.Wewouldalsoliketobeabletorevokeuserswhohavebecomeuntrusted.Inaciviliansituationtheadversarycouldbeacriminalwantingtoeavesdroponthecommunicationbetweenthepoliceunitswhilethecriminalisattempingabankrobbery.Efficientbroadcastencryptionsolutionswouldmakeitpossibletorevokecor-ruptuserterminalsandsendfurthercommunicationonlytothetrustedusers.

Therearesomesimplesolutionstothebroadcasten-cryptionproblemwhichillustratethenecessaryconsider-ations.Theproblemcanbesolvedbydistributingonekeytoeachuserandencryptingthetransmission,orratherasessionkeyforthetransmission,oncewitheachkeyofthereceiversintheprivilegedset.Thiswillcauseamessageexpansionproportionaltothenumberofreceiversintheprivilegedsetandisingeneralabadsolution.Itisalsopossibletodistributeonekeyperpossibleprivilegedsetandencrypteachtransmissionwiththekeyassociatedto

thecurrentprivilegedset.Thisyieldsnomessageexpan-sionbutinsteadresultsinanenormousamountofkeystostoreforbothsendersandreceivers.

Morecomplexsolutionsofteninvolvetreestructureswhereeachreceiverisassociatedwithaleafina,oftenbinary,tree.Thetreestructurerequireseachusertostorelesskeysasallkeyscanbegeneratedfromjustafewthatmustbestored.Inshort,thisisachievedbycreatingthekeysusingone-wayfunctionswhichmapakeyataninter-nalnodeinthetreeontotwonewkeyswhichareassoci-atedwiththeleftandrightchildoftheparentnode.

2.THESUBSETDIFFERENCESCHEME

Thesubsetdifference(SD)schemeforsolvingthebroad-castencryptionproblemwasintroducedbyNaor,Naor,andLotspiechin[7].Thesubsetdifferenceschemehasbeenstudiedandimproveduponbymanyothers,includ-ingHalevyandShamirin[6],andthebasicidea,thekeystructure,hasproventoperformverywell.WewillnotdescribetheentireSDschemehere,onlypointoutthoseaspectsconsideredinthispaper.ForafullexplanationoftheSDschemewereferto[7].

IntheSDschemetheusers(receivers)areorganizedasleavesinacompletebinarytree.WecallsuchatreeanSDtree.

Foranygiventransmissiontheuserswillbedividedintotwosets,thosewhoarecurrentlyintheprivilegedset,andthosewhoarecurrentlyinthenon-privilegedset,i.e.thecomplementoftheprivilegedset.

IntheSDschemethereareencryptionkeysassociatedwithusersetsofaspecifickind,namelytheleavesofcom-pletesubtreeswithacompletesubtreecutout,calledSDsubsets.Thecollectionofsubsetsusedtotransmittotheprivilegedsetofusersiscalledthecover.EachSDsub-setinthecovercorrespondstoonebroadcasttransmission,encryptedwiththekeyofthatsubset.

3.ISOMORPHICTREES

WewilldiscusspropertiesoftheSDtreesandthereforeweneedtorestatesomedefinitionsregardingtrees.Definition1.Abinarytreeisanorderedtreesuchthat:[1]

•eachchildcanbedistinguishedeitherasaleftchildorarightchild.

•novertexhasmorethanoneleftnormorethanonerightchild.

Inthispaperwewillonlydealwithcompletebinarytreeswhereeachinternalnodehasexactlytwochildren.Definition2.Twotreesaresaidtobeisomorphicifitispossibletomaponetreeontotheotherbypermutingtheorderofthechildrenofvertices.[1]

Allpermutationsofleftandrightchildren(includingthesubtreesrootedatthesenodes)canalsobeconsideredper-mutationsofthedescendantleaves,whichisthewaywewilldescribesuchpermutations.Eachsuchexchangeoftheorderoftwosiblingsubtreeswillbecalledatreeshift.Wecallapermutationthatisamappingbetweentwoiso-morphictreesanisomorphismpreservingtreeactionoranallowedpermutation.Eachallowedpermutationconsistsofoneormoretreeshifts.WenotethatthenumberoftransmissionsintheSDscheme,whichaswehaveseeninSection1isaveryimportantparameter,isthesameforisomorphictrees.Inotherwords,performinganallowedpermutationonanSDtreewillnotchangethenumberoftransmissionsneededbytheSDalgorithm.

Ifwepartitionthesetofalltreesofagivenheightintoisomorphismclasses,thenallSDtreesinthesameclasswillrequireequalcoversize.TheseclassesprovidethebasisforacharacterisationofallpossibleSDtreesandwillbefurtherinvestigatedinthenextsection.

3.1.Example:IsomorphicTrees

Figure1givesanexampleofsomeisomorphictrees,thatis,treesthatcanbemappedtoeachotherusingonlyal-lowedpermutations.Tree(a)cane.g.bemappedtotree(b)bytheallowedpermutation(56),switchingtheor-deroftheleftandrightsubtreesofthenodeatpositiona.Tree(c)canbemappedtotree(d)bytheallowedper-mutation(15)(26)(37)(48)(57)(68)(13)(24)(34)=(17)(28)(3546).1Thismeansswitchingtheorderofthesutreesofthenodesatpositionsa,b,c,andd,inthatorder.Notethatwhenthefirsttreeshifthasbeenper-formed,thepositionsofthenodeswillhavechanged.Theswitchingshouldbeperformedatthepositionsmarkedinthefigure,notnecessarilyatthenodesoriginallyinthesepositions.

3.2.IsomorphismClasses

ForsmalltreesitisfeasibletodescribeallpossibleSDtreesandpartitiontheminisomorphismclasses.Theparti-tionTthenconsistsofT1,T2,...,Tk,whereeachTicon-sistsofSDtreesthatyieldthesamecoversize.However,itisstillanopenquestionhowtosystematicallydescribethepartitionintoisomorphismclassesforarbitrarilyhighSDtreeswithoutperformingacompleteenumeration.3.2.1Numberofisomorphismclasses

Thenumberofisomorphismclassesforsomeheightsh,wheretheheightofatreeisgivenbythenumberoflevelswithinternalnodesinthetree,canbefoundinTable1andisgivenbythefollowingrecursiveexpression:

󰀂ah=ah−1(ah−1+1)

a2

2(1)

0=1We

usecyclenotationforpermutationsandapplythepermutations

inorderfromlefttoright.

a1234(a)

56781234(b)

5678acbd1234(c)

56781234(d)

5678Figure1.Fourisomorphictrees.Theleavesofonecolorrepre-sentnon-privilegedusersandtheleavesoftheothercolorrepre-sentprivilegedusers.Thesetreescanallbemappedontoeachotherusingonlyallowedpermutations

Table1.Numberofisomorphismclassesfortreeheightsuptoh=5.

hNumberof

isomorphismclasses,ah

02132632142315

26796

Thisexpressionhasalsoappearedin[3]inanothercon-text.However,wehavefoundnoobviousconnectionbe-tweentheproblemsconsideredin[3]andtheoneconsid-eredinthispaper.

4.APPLYINGGROUPTHEORETICCONCEPTSTOTHESDSCHEME

GrouptheoryofferssomepowerfultoolsthatwewouldliketobeabletousewhenconsideringtheSDschemeandanalyzingitsperformance.Asitturnsout,theallowedpermutationsdiscussedinSection3canbedescribedasagroupandthuswecanusemuchofthewelldevelopedtheoryaboutgroups.Wewillnowexplainwhatwemeanbythegroupofallowedpermutations.Wefirstnotethataprivilegedtupleofonesandzeros,p=representtheusersnotinthe󰀃setcanbeidentifiedbyap0,p1,...,pn−1privilegedset.To󰀁,wheretheonesrepresenttheusersintheprivilegedsetandthezerosemphasizethatthetuplesrepresentsetsofuserswewillcallthemusertuples.

Thenwerecallthesymmetricgroup,Sn,consistingofallpermutationsofnelementswiththegroupoperationbeingthecompositionoftwopermutations.Thepermuta-tionsinSncanactontheusertuplesandthuspermutetheusers,equivalentlytothewaytheleavesoftheSDtreeswerepermutedinSection3.However,notallpermuta-tionsinSnareallowedpermutations.

AsstatedinSection3theallowedpermutationsaretheoneswhichonlyconsistofexchangesoftheorderinoneormorepairsofsiblingsubtrees,treeshifts.Itcanbeshownthattheallowedpermutationsactingonusertuplesoflengthnformagroupundercomposition,asubgrouptoSn.Wewilldenotethegroupofallowedpermutationsact-ingonusertuplesoflength2hbyGhastheycorrespondtosequencesoftreeshiftsintheSDtreesofheighth.AgroupHissaidtobegeneratedbycertainelementsh1,...,hk∈Hifthegroupcanbeformedbycombiningtheseelementsinallpossiblewaysusingthegroupopera-tionandgettingastheresultallelementsinthegroup.ThisisdenotedH=󰀆h1,,...,hk󰀇.Thegroupofallowedper-mutations,Gh,canbegeneratedbythepermutationscor-respondingtosimpleexchangesofsiblingsubtrees,treeshifts,attheleftmostsiblingpaironeachlevelofthetree.AsanexamplewelistthefirstsuchexchangesinTable2wherewealsogiveageneralexpressionforthesegenerat-ingpermutations.

Thegroupofallowedpermutationsoftreeheighthcan

Table2.Generatorsofthegroupofallowedpermutationsfortreeheightsuptoh=4andthegeneralexpression.hGenerators1g1=(12)2g1=(12),g2=(13)(24)3

g1=(12),

g2=(13)(24),

g3=(15)(26)(37)(48)4

g1=(12),

g2=(13)(24),

g3=(15)(26)(37)(48),

g4=(19)(210)(311)(412)(513)(614)(715)(816)Ingeneral:

h

gi−11i=(12+1)(22i−+2)...(2i−12i)fori=1,...,h

g3g2g112345678Figure2.Permutationsg1,g2,andg3aregeneratorsofthegroupG3ofallowedpermutations.Forinstance,thepermutationg1=(12)canbeseenastheoperationofchangingtheorderoftheleftandrightsubtreesoftheblacknodemarkedwithg1.

thusbeexpressedasGh=󰀆g1,g2,...,gh󰀇.Thesegen-eratorscanbeshowninatreerepresentation,asinFig.2.Inthefigureablacknoderepresentsapermutationthatexchangestheorderoftheleftandrightsubtreesofthatnode.

UsingthegeneratorsofGhandcompositionsofthemwecangenerateanytreeshift.Thetreeshiftscanbecom-binedtoformall22h

−1elementsofthegroupGhofal-lowedpermutations.

4.1.IsomorphismClassesintheGroupContext

Theusertupleshaveaone-to-onecorrespondencetotheSDtreesandthereforewecanthinkoftheisomorphismclassesasconsistingofeitherSDtreesorusertuples.Astheallowedpermutationsareisomorphismpreservingbydefinition,wecanstatethatifpisausertupleinaniso-morphismclass,Ti,andanyelementg∈Ghactsonpthentheresultingusertuple,gp,isalsoinTi.

Werecallthedefinitionofatransitivegroupasstatedforexamplein[4].

Definition3.ApermutationgroupG⊆SnistransitiveonasetAifthegroupactionistransitive,i.e.foranyelementsx,y∈Athereisagroupelementg∈Gsuchthatx=gy.

ThegroupGhistransitiveoneachisomorphismclass

TiandthusallelementsinTicanbederivedbyapplyingallowedpermutationstoanyusertupleinTi.

OneinterestingrelationisnotedwhenweconsidertheconjugacyclassesinGh,whicharetheclassesofelementsgGhg−1whereg∈Gh.Thatis,theelementsresultingfromconjugatingoneelementg∈GhwithallelementsinGh.Thesequenceofsizesoftheconjugacyclassesis2,5,20,230,26795forthetreeheightsh=1,2,3,4,5whichisexactlyonelessthanthenumberofisomorphismclassesforthesametreeheights(seeTable1).Thissug-geststhattheconjugacyclasseshavesomeconnectiontotheisomorphismclassesandmightprovetobeausefulrelationwhenfurtheranalyzingthepropertiesoftheiso-morphismclasses.Forinstance,wenotedinSection3.2thatitwouldbeinterestingtosystematicallydescribethepartitionofSDtreesintoisomorphismclassesforanar-bitraryheight,h.Thisremainsaresearchproblemwhichmightbepossibletosolveusinggrouptheoretictools,per-hapsbyconsideringtheconjugacyclasses.

WenowremindthatwhatweareinterestedinisthecoversizegeneratedwhenusingtheSDscheme.Thecoversizeisconstantforallusertuplesineachisomor-phismclass,althoughseveralisomorphismclassesmayhavethesamecoversize.From(1)andTable1weknowthatforsmallSDtreesthenumberofisomorphismclassesismanageablebutasthenumberofisomorphismclassesgrowsrapidlywiththeheightofthetreeitisinfeasibletousecompleteenumerationofallclassesforhighertrees.Insteaditisnecessarytostudywhichpropertiesoftheiso-morphismclassesthatareimportantforthecoversizetobeabletodescribetherelationbetweentheisomorphismclassesandthecoversize.

4.2.RelationtoGroupCodes

Itcanbenotedthatifweweretointroduceadistancemea-sureonthesetofusertuplesforwhichthepermutationgroupelementsaredistancepreserving,thenwecancon-siderusertuplesascodewordsofagroupcode.GroupcodeswereintroducedbySlepianin[8]andfurtherin-vestigatedbyForneyin[5]andtheyprovidesomestruc-turethatmaybeadvantageousintheanalysisoftheSDscheme’sperformance.ItisnotobviouswhatdistancemeasuretousealthoughthemostintuitiveisprobablytheHammingdistance.Inpermutationgroupcodesforerrorcorrectionincommunicationsthepermutationdistanceissometimesusedasadistancemeasure.Wemayneedtodefineanotherdistancemeasurewhichismoreusefulinthiscontext.

5.CONCLUSIONS

Wehavenotedthatthesubsetdifferenceschemeforbroad-castencryptionrequiresthesamecoversizeforallSDtreesthatareisomorphictoeachother.BasedonthisfactwepartitionthesetofallSDtreesofheighthintoisomorphismclassesandwehavederivedthenumberofsuchclassesasafunctionofh,see(1).Theisomor-phismclassesareclosedunderallowedpermutationsoftheleavesoftheSDtrees.

Theallowedpermutationsformagroup,Gh,andthuswecanusetoolsfromgrouptheorytoanalyzethebe-

havioroftheSDscheme.ThisgroupisgeneratedbyhpermutationswhichweidentifyinTable2.Thegrouptheoryapproachseemspromisingforinstanceasthereisasimplecorrespondencebetweenthenumberofisomor-phismclassesofeachheighthandthenumberofconju-gacyclassesofGh.

Finallywenotethatifweweretointroduceasuitabledistancemeasurewecouldusethetheoryofgroupcodesandconsidertheusertuplesascodewordsinsuchcodes.Theresultsandresearchissuesdiscussedinthispa-perhavepreviouslybeenpresentedinapreliminaryversionin[2].

REFERENCES

[1]A.V.Aho,J.E.Hopcroft,andJ.D.Ullman.TheDesignandAnaly-sisofComputerAlgorithms.AddisonWesley,1974.[2]K.Anderson,F.Claesson,andI.Ingemarsson.”BroadcastEncryp-tionandGroupCodes”.TechnicalReportLiTH-ISY-R-2605,DeptofElectricalEngineering,Link¨opingsuniversitet,2004.[3]W.H.Cutler.”SubdividingaBoxintoCompletelyIncongruentBoxes”.JournalofRecreationalMathematics,12:104–111,1979.[4]J.D.DixonandB.Mortimer.PermutationGroups,volume163of

GraduateTextsinMathematics.SpringerVerlag,1996.[5]G.D.ForneyJr.”GeometricallyUniformCodes”.IEEETransac-tionsonInformationTheory,37(5):1241–1260,September1991.[6]D.HalevyandA.Shamir.”TheLSDBroadcastEncryption

Scheme”.InAdvancesinCryptology–CRYPTO’02,volume2442ofLectureNotesinComputerScience,pages47–60.SpringerVer-lag,2002.[7]D.Naor,M.Naor,andJ.Lotspiech.”RevocationandTracing

SchemesforStatelessReceivers”.InAdvancesinCryptology–CRYPTO’01,volume2139ofLectureNotesinComputerScience,pages41–62.SpringerVerlag,2001.[8]D.Slepian.”GroupCodesfortheGaussianChannel”.TheBell

SystemTechnicalJournal,pages575–602,April1968.