Paper 2012/520

Optimizing Segment Based Document Protection (Corrected Version)

Miroslaw Kutylowski and Maciej Gebala


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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. It is corrected and generalized version of the article published on the conference SOFSEM'2012.
document protectionaccess rightskey managementkey hierarchydirected acyclic graph
Contact author(s)
maciej gebala @ pwr wroc pl
2012-09-06: received
Short URL
Creative Commons Attribution


      author = {Miroslaw Kutylowski and Maciej Gebala},
      title = {Optimizing Segment Based Document Protection (Corrected Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2012/520},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.