Secure Lossy Source Coding with Side InformationErsen Ekrem Sennur UlukusDepartment of Electrical and Computer EngineeringUniversity of Maryland, College Park, MD [email protected] [email protected]—We study the problem of secure lossy sourcecoding with side information. In all works on this problem,either the equivocation of the source at the eavesdropper orthe equivocation of the legitimate user’s reconstruction of thesource at the eavesdropper is used as the measure of secrecy.In this work, we propose a new secrecy measure, namely,the relative equivocation of the source at the eavesdropperwith respect to the legitimate user. We argue that this newsecrecy measure is the one that corresponds to the naturalgeneralization of the equivocation in a wiretap channel to thecontext of secure lossy source coding, and discuss its advantagesover the other two secrecy measures. Once we adopt therelative equivocation as the measure of secrecy, we providea single-letter description of the rate, relative equivocation anddistortion region. We specialize this single-letter descriptionto the degraded and reversely degraded cases. Moreover, weinvestigate the relationships between the optimal scheme thatattains this region and the Wyner-Ziv scheme.I. INTRODUCTIONSecure source coding problem has been studied for bothlossless and lossy reconstruction cases in [1]–[16]. Securelossless source coding problem is studied in [1]–[7]. Theseworks, despite the differences in their models, share acommon framework, in which the legitimate user wants toreconstruct the source in a lossless fashion by using theinformation it gets from the transmitter in conjunction withits own side information, while the eavesdropper is keptignorant of the source as much as possible. Secure lossysource coding problem is studied in [8]–[16]. In these works,unlike the ones focusing on secure lossless source coding,the legitimate receiver wants to reconstruct the source in alossy fashion, to within a distortion level.Here, similar to [13]–[16], we also study the problemof secure lossy source coding with side information. Inthis problem, the transmitter wants to describe the sourceto the legitimate user within a distortion level, where thelegitimate user has a side information. Meanwhile, thiscommunication between the transmitter and the legitimateuser needs to be kept secret from the eavesdropper, whoalso has a side information, to the extent possible. In [13]–[16], the security of this communication is measured by theequivocation of the source at the eavesdropper. Indeed, thismeasure of secrecy corresponds to a direct generalization ofthe one used for the wiretap channel in [17], [18], wheresecrecy is measured by the equivocation of the messageThis work was supported by NSF Grants CCF 07-29127, CNS 09-64632,CCF 09-64645 and CCF 10-18185.at the eavesdropper. However, in a wiretap channel, theequivocation of the message at the eavesdropper measuresnot only the confusion of the eavesdropper about the messagebut also the relative confusion of the eavesdropper aboutthe message with respect to the legitimate user. This comesfrom the fact that the legitimate user is able to decode themessage, and hence the equivocation of the message at thelegitimate user is asymptotically zero, making the relativeequivocation and the equivocation asymptotically the same.On the other hand, in the context of secure lossy sourcecoding, there is no such asymptotical equivalence betweenthe equivocation of the source at the eavesdropper and therelative equivocation of the source at the eavesdropper withrespect to the legitimate user. The lack of an asymptoticalequivalence comes from the fact that the legitimate userdoes not reconstruct the source in a lossless fashion, butwithin a distortion, and hence, the legitimate user has anequivocation about the source sequence as well. Based onthis observation, we argue that, indeed, the use of relativeequivocation of the source as the secrecy measure providesthe natural generalization of the equivocation in a wiretapchannel to a secure lossy source coding context.Before adopting the relative equivocation as the secrecymeasure, we next discuss another possible secrecy measurewhich is the equivocation of the legitimate user’s reconstruc-tion of the source at the eavesdropper [19]. We argue thatalthough the equivocation of the reconstructed source is use-ful to measure the confusion of the eavesdropper about thelegitimate user’s reconstruction, from a secrecy point of view,it provides inconsistent results. This inconsistency resultsfrom the fact that although the correlation between the sideinformation of the legitimate user and the eavesdropper doesnot affect the quality of the legitimate user’s reconstructionor the quality of the eavesdropper’s reconstruction, it affectsthe equivocation of the legitimate user’s reconstruction of thesource at the eavesdropper. Hence, for two models differingonly in the correlation between the side information of thelegitimate user and the eavesdropper, the qualities of thelegitimate user’s and the eavesdropper’s reconstructions inboth models would be the same. Hence, the capability ofthe legitimate user and the capability of the eavesdropperto reproduce the source will be the same in both cases.Consequently, both models should have the same amount ofsecrecy. However, the equivocations of the legitimate user’sreconstructions of the source at the eavesdropper in thesetwo models might be different since they depend on thecorrelation between the side information of the legitimateuser and the eavesdropper. Thus, the equivocation of thelegitimate user’s reconstruction at the eavesdropper is aninconsistent measure of secrecy.Once we adopt the relative equivocation as the secrecymeasure, we obtain the single-letter description of the rate,relative equivocation and distortion region for the securelossy source coding problem. To this end, we show thatthe coding scheme proposed in [14], where the same prob-lem is studied when the equivocation of the source at theeavesdropper is used as the secrecy measure, attains therate, relative equivocation and distortion region. This resultimplies that the coding scheme in [14] maximizes not onlythe equivocation of the source at the eavesdropper but alsothe relative equivocation of the source.Next, we specialize the single-letter description we obtainto the degraded and reversely degraded cases. Although thesingle-letter