An Asymptotic Theorem for Substitution-Resistant Authentication Codes
We prove a Shannon-theoretic theorem for authentication codes resistant against impersonation and substitution. The code construction is based upon block-designs. We conjecture that this construction is asymptotically the best possible.
- PDF / 31,023,340 Bytes
- 388 Pages / 481.89 x 691.654 pts Page_size
- 56 Downloads / 191 Views
Series Editors: The Rectors ofCISM
Sandor Kaliszk:y- Budapest Horst Lippmann - Munich Mahir Sayir - Zurich
The Secretary General of CISM Giovanni Bianchi - Milan
Executive Editor
Carlo Tasso - Udine
The series presents lecture notes, monographs, edited works and proceedings in the field of Mechanics, Engineering, Computer Science and Applied Mathematics. Purpose of the series in to make known in the international scientific and technical community results obtained in some of the activities organized by CISM, the International Centre for Mechanical Sciences.
INTERNATIONAL CENTRE FOR MECHANICAL SCIENCES COURSES AND LECI'URES - No. 339
EUROCODE '92
INTERNATIONAL SYMPOSIUM ON CODING THEORY AND APPLICATIONS
EDITED BY P. CAMION INRIA - ROCQUENCOURT P.CHARPIN INRIA - ROCQUENCOURT S.HARARI UNIVERSITY OF TOULON AND VAR - LA GARDE
SPRINGER-VERLAG WIEN GMBH
Le spese di stampa di questo volume sono in parte coperte da contributi del Consiglio Nazionale delle Ricerche.
This volume contains 47 illustrations.
This work is subject to copyright. Ali rights are reserved, whether the whole or part of the material is j
~
0.
19
Coset Weight Enumerators
Definition 2. A r-partition design on (F", !l) is a partition JF" such that !lo = {0}, !lt = !l and for u, v E {0, 1, ... , r}
1r
= {!l0 , !lt, ... , !lr}
of
= card((h- !l) n !lv)
muv
is a constant for all hE n.... The code C = C(!l) is said to admit the partition design The matrix M = (m ....,) is called the associate matrix of 1r. The regularity number is the least number r such that C admits a r-partition design and the regularity matrix which is unique up to a permutation of the indices {9} is the corresponding associate matrix M.
1r.
n. . },
Geometrically, if E ... = {x E IF" I HxT E then 11" = {Eu} a partition of IF" such that muv = card{y E E., I d(x,y) = 1} is independent of the choice of x in E .... This geometric property of the numbers mu,v means that the associate matrix M doesn't depend on the choice of the parity check matrix H of C. We shall also refer to this partition as a partition design of the surrounding space IF" admitted by the code C = C(!l).
Proposition 1. Let G be a subgroup of GL(k, 2). If G acts transitively on !l, then the set of orbits {!lo = {0}, !lt = !l, ... , n.} under G is a partition design admitted by C = C(!l). Theorem 2. If C admits the r-partition design (1) Aj(h)
1r
= {!l0 , ••• , !lr}
then
= Ai(9) for any h, gEn ... , u E {0, ... , r };
(2) The numbers Aj(u)
= Ai(h),
hEn ... satisfy the recurrence relation r
Ai(u)
=L
m,.,Aj-I(v)
v=O
with u E {0, ... , r }, j
~
1. By definition A 0 (0)
(3) The combinatorial partition
1r0
= 1 and A 0 (u) = 0 for u =f. 0;
defined by the equivalence relation
is coarser than the partition design A, then 1 ~ r;
1r.
If 1 + 1 is the number of distinct rows in
(4) There is a r-partition design 'if with least possible numberr+ 1 of classes which lies between the combinatorial partition (which is not in general a partition design) and the given partition design 1r. The co
