Muaf kullanıcılarla en uygun yayın şifrelenmesi

ABSTRACTOPTIMAL BROADCAST ENCRYPTION WITH FREERIDERSMurat AkM.S. in Computer EngineeringSupervisor: Assist. Prof. Dr. Ali Aydın SelşukcSeptember, 2006Broadcast encryption schemes allow a center to broadcast encrypted mes-sages so that each particular message can only be decrypted by a set of privilegedreceivers designated for it. The standard technique is to distribute keys to all re-ceivers at the beginning and to use only the necessary keys to encrypt the messagefor each particular broadcast. The number of encryptions needed constitutes thetransmission cost in broadcast encryption schemes. The most efficient scheme interms of transmission cost published so far is the subset difference (SD) scheme. Itis possible to reduce the transmission overhead of a broadcast encryption schemeby allowing a number of free riders to be able to decrypt the message althoughthey are not privileged. However, unless the free riders are chosen cleverly, thecost may even increase. In this thesis, we deal with the problem of choosing agiven number of free riders effectively to reduce the transmission overhead in SDscheme. We first present three greedy algorithms. First algorithm has a fastexecution, the second one is slower but has lower transmission overhead, and thelast one has a trade-off between running time and transmission cost. Then wepresent two algorithms which find the minimum transmission overhead possiblegiven a free rider quota. The experiments we conduct show that the transmissioncost can be significantly reduced.Keywords: Broadcast Encryption, Free Riders.iii