Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 2-3/2015

01-12-2015

Perfect hash families of strength three with three rows from varieties on finite projective geometries

Author: Ryoh Fuji-Hara

Published in: Designs, Codes and Cryptography | Issue 2-3/2015

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Let \({\mathcal {F}}\) be a set of functions of \(f : X \rightarrow Y\), where \(|X|=k, \,|Y|=v\) and \(|{\mathcal {F}}|=N\). If for any \(t\)-subset \(C \subseteq X\) there exists at least one function \(f\in \mathcal {F}\) such that \(f|_{C}\) is one-to-one, then \({\mathcal {F}}\) is called a perfect hash family, denoted by PHF\((N; k, v, t)\). In this paper, we construct the simplest nontrivial PHFs of \(t=3\) and \(N=3\) using classic generalized quadrangles, quadrics in PG\((4, q)\) and Hermitian varieties in PG\((4, q^2)\). We obtained PHF\((3; q^2(q+1), q^2, 3)\) and PHF\((3; q^5, q^3, 3)\) for \(q\) a prime power. The curve \(k= v^{5/3}\) is greater than known \(k\) for \(v=q^3,\,q\) a prime power.
previous article Primitive normal bases for quartic and cubic extensions: a geometric approach
next article Enumeration of Kerdock codes of length 64
Literature
1.
Atici M., Magliveras S.S., Stinson D.R., Wei W.D.: Some recursive constructions for perfect hash families. J. Comb. Des. 4, 353–363 (1996).
2.
Blackburn S.R.: Combinatorics and Threshold Cryptography. Combinatorial Designs and Their Applications, pp. 49–70. Chapman and Hall, Boca Raton (1999).
3.
Blackburn S.R., Burmester M., Desmedt Y., Wild P.R.: Efficient Multiplicative Sharing Schemes. Lecture Notes in Computer Science vol. 1070, pp. 107–118. Springer, Berlin (1996).
4.
Colbourn C.J., Martirosyan S.S., Van Trung T., Walker II R.A.: Roux-type constructions for covering arrays of strengths three and four. Des. Codes Cryptogr. 41(1), 33–57 (2006).
5.
De Beule J., Klein A., Metsch K., Storme L.: Partial ovoids and partial spreads of clasical finite polar spaces. Serdica Math. J. 34, 689–714 (2008).
6.
Fiat A., Naor M.: Broadcast Encryption. Lecture Notes in Computer Science. vol. 773, pp. 480–491. Springer-Verlag, Berlin (1994).
7.
Fredman M.L., Komlos J.: On the size of separating systems and families of perfect hash functions. SIAM J. Algebraic Discret. Methods 5, 61–68 (1984).
8.
Hirschfeld J.W.P.: Finite Projective Spaces of Three Dimensions. Oxford Mathematical Monographs, x+316 pp. Oxford Science Publications, New York. ISBN: 0-19-853536-8 (1985).
9.
Mehlhorn K.: On the program size of perfect and universal hash functions. In: Proceedings of the 23rd Annual IEEE Symposium on Foundations of Computer Science, pp. 170–175 (1982).
10.
Metsch K., Storme L.: Maximal partial ovoids and maximal partial spreads in Hermitian generalized quadrangles. J. Comb. Des. 16(2), 101–116 (2008).
11.
Stinson D.R.: Cryptography Theory and Practice. Discrete Mathematics and Its Applications, 3rd edn., xviii+593 pp. Chapman & Hall, Boca Raton. ISBN: 978-1-58488-508-5; 1-58488-508-4 (2006).
12.
Thas K.: Symmetry in Finite Generalized Quadrangles. Frontiers in Mathematics, xxii+214 pp. Birkhäuser Verlag, Basel. ISBN: 3-7643-6158-1 (2004).
13.
Walker II R.A., Colbourn C.J.: Perfect hash families: constructions and existence. J. Math. Cryptol. 1(2), 125–150 (2007).
Metadata
Title
Perfect hash families of strength three with three rows from varieties on finite projective geometries
Author
Ryoh Fuji-Hara
Publication date
01-12-2015
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 2-3/2015
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-015-0052-z

Other articles of this Issue 2-3/2015

Designs, Codes and Cryptography 2-3/2015 Go to the issue

OriginalPaper

Square integer Heffter arrays with empty cells

OriginalPaper

Normal forms of hyperelliptic curves of genus 3

OriginalPaper

The asymptotic existence of DR-BIBDs

OriginalPaper

Batch verifiable computation of outsourced functions

EditorialNotes

Guest Editorial: Special Issue in Honor of Scott A. Vanstone

OriginalPaper

Primitive normal bases for quartic and cubic extensions: a geometric approach

Premium Partner

    Image Credits