Advances in Cryptology — ASIACRYPT'94

Assuming a set of v entities and a set B of b key-sharing systems, this paper proposes a way of assigning each entity a subset of B so that any two entities have at least one common key-sharing system with which they can share an h-bit common key. Such an assignment is nothing but a cohesive incidence structure. If an entity is assigned a subset {S0,..., Sr−1} ⊂ B then by the system centers for S0 ..., Sr−1, respectively, the entity is supplied r tamper-resistant modules (TRMs) containing data depending on the entity's identifier and the secret information for the corresponding system. The use of plural TRMs per entity can be sound with respect to the status of micro-electronics. Assume that every key-sharing system in B cannot be completely broken unless at least m TRMs are successfully attacked to infer m pieces of h × m-bit data inside them. Then each entity has r TRMs which contain r×h×m-bit data in total while the minimum number of TRMs to attack for complete breaking is b×m. The gain defined by (minimum number of TRMs to attack)/(total memory per key-bit per entity), is thus b/r. Gain 1 is attained by the (trivial) method using r=b TRMs per entity with b(≥1) key-sharing systems. A larger gain will save memory per entity to yield the same security level measured by the tamper-resistance required for complete breaking. This paper also provides a method to generate desirable assignments yielding gain b/r > 2 with large v exponential in r, by introducing a novel binary operation on incidence structures which preserves cohesiveness and constant-weight properties.