No label defined (Q4244124)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 1290176
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 1290176 |
Statements
7 June 1999
0 references
perpendicular array
0 references
authentication
0 references
character
0 references
0.934036135673523
0 references
0.8437732458114624
0 references
0.7731614112854004
0 references
A perpendicular array \(\text{PA}_{\lambda}(t,k,v)\) is a family of injective mappings from a \(k\)-set \(K\) into a \(v\)-set \(V\) such that for every \(t\)-set \(A\subset K\) and every \(t\)-set \(B\subset V\) exactly \(\lambda\) of our mappings \(f\) will have \(f(A)=B\). An authentication perpendicular array (short APA) is a perpendicular array satisfying an additional homogeneity condition, which is motivated by the cryptographic theory of authentication. This notion was introduced by D. R. Stinson. In the present paper the focus is on \(\text{APA}_1(2,k,q)\), where \(q\) is a prime power \(\equiv 3\pmod 4\). Identifying the mappings with the rows of an array we can describe an \(\text{APA}_1(2,k,v)\) as an \(({v\choose 2},k)\)-array with entries from a \(v\)-set such that the following are satisfied: (1) For each pair of columns and each unordered pair \(B\) of entries there is exactly one row where \(B\) appears in the given columns. (2) For each pair \(B=\{ x,y\}\) of entries, the restriction of the array to the \({k\choose 2}\) rows where \(x\) and \(y\) both appear has \(x\) (and \(y\)) appearing precisely \((k-1)/2\) times in each column. An \(\text{APA}_1(2,k,v)\) can exist only when \(k\) and \(v\) both are odd. Let \(q\) be a prime power \(\equiv 3\pmod 4\). An \(\text{APAV}(q,k)\) is a subset \(K\subset \text{ef}_q\) of \(k\) elements such that for every \(b\in K\) among the \(a-b\), \(a\in K\), \(a\not=b\) there are \((k-1)/2\) squares and \((k-1)/2\) non-squares. These structures were introduced in \textit{J. Bierbrauer} and \textit{Y. Edel} [Theory of perpendicular arrays, J. Comb. Des. 2, No. 6, 375-406 (1994; Zbl 0824.05011)]. If an \(\text{APAV}(q,k)\) exists, then an \(\text{APA}_1(2,k,q)\) can be constructed. The name APAV was coined in \textit{G. Ge} and \textit{L. Zhu} [Authentication perpendicular arrays \(\text{APA}_1(2,5,v),\) J. Comb. Des. 4, No. 5, 365-375 (1996; Zbl 0913.05028)]. It was proved in [\textit{J. Bierbrauer} and \textit{Y. Edel}, loc. cit.] that an \(\text{APAV}(q,k)\) exists whenever \(k\) is odd and \(q>2^{k(k-1)}\). The proof used cyclotomy. The main result of the present paper is an essential improvement of this bound. The main ingredient in the proof is a famous bound on character values, which is closely related to the Hasse-Weil bound on the number of rational points of algebraic curves (this is Theorem 5.41 of \textit{R. Lidl} and \textit{H. Niederreiter} [Finite fields, Cambridge University Press (1984; Zbl 0554.12010)]). The new bound is strong enough to allow an almost complete solution of the existence question of \(\text{APAV}(q,k)\) when \(k\leq 15\). Small parameter values are dealt with by ad hoc constructions and computer work.
0 references