Ivkov M., Korjik V., Wróblewski J., 1997. On generalized greedy algorithms in broadcast key distribution schemes Proc. of the ISITA'98, pp. 130-133, Mexico City. Also in: Cientifica, vol. 14 (March-April 1999), pp. 21-29. Escuela superior de ingeneria mechanica y electrica, Mexico City 1999.
ABSTRACT
In another work a key distribution scheme for broadcast encryption based on 2-designs was proposed. The connectivity of this scheme is the maximal number of messages that should be broadcasted by the center to the non-compromised users to generate a common key. This value was upper bounded in another work with the use of the greedy algorithm. We propose the generalized greedy algorithm and some randomized modifications of it (a hybrid genetic-greedy algorithm among them) to improve a connectivity of broadcast key distribution schemes. We present the results of simulations for different 2-design matrices to prove this property and to find a computation time when different algorithms are used.
A few methods for row covering problem in special case of reduced 2-design matrices are presented. Experimental results show, that relatively fast randomized weighted greedy algorithm (RWGA) method is efficient for this problem. In some real-time applications we can use suboptimal but fast WGA method. All these methods give better results than simple random covering method. A method using genetic algorithm (ordinal-based GA) gives similar results than RWGA, but is significantly slower.