Paper 2012/520

Optimizing Segment Based Document Protection (Corrected Version)

Miroslaw Kutylowski and Maciej Gebala

Abstract

In this paper we provide a corrected and generalized version of the scheme presented at SOFSEM'2012 in our paper ``Optimizing Segment Based Document Protection'' (SOFSEM 2012: Theory and Practice of Computer Science, LNCS 7147, pp. 566-575). We develop techniques for protecting documents with restricted access rights. In these documents so called \emph{segments} are encrypted. Different segments may be encrypted with different keys so that different user may be given different \emph{access rights}. Hierarchy of access rights is represented by means of a directed acyclic \emph{access graph}. The segments are encrypted with keys - where each key corresponds to one node in the access graph. The main feature of the access graph is that if there is an arch $\overrightarrow{AB}$ in the graph, then all segments labelled with $B$ can be decrypted with the key corresponding to node $A$. We show how to minimize the space overhead necessary for auxiliary keying information stored in the document. We provide an algorithm based on node disjoint paths in the access graph and key derivation based on one-way functions. Our current solution, based on maximal weighted matchings, provides an optimal solution for creating subdocuments, in case when frequency of creating each subdocument is known.