Abstract
Let X be a set of order n and Y be a set of order m. An (n,m,{w 1, w 2})-separating hash family is a set \(\mathcal {F}\) of N functions from X to Y such that for any \(X_1, X_2 \subseteq X\) with \(X_1\cap X_2=\emptyset\), |X 1| = w 1 and |X 2| = w 2, there exists an element \(f\in \mathcal {F}\) such that \(f(X_1)\cap f(X_2)=\emptyset\). In this paper, we provide explicit constructions of separating hash families using algebraic curves over finite fields. In particular, applying the Garcia–Stichtenoth curves, we obtain an infinite class of explicitly constructed (n,m,{w 1,w 2})–separating hash families with \(N=\mathcal {O}(\log\,n)\) for fixed m, w 1, and w 2. Similar results for strong separating hash families are also obtained. As consequences of our main results, we present explicit constructions of infinite classes of frameproof codes, secure frameproof codes and identifiable parent property codes with length \(N=\mathcal {O}(\log\,n)\) where n is the size of the codes. In fact, all the above explicit constructions of hash families and codes provide the best asymptotic behavior achieving the bound \(N=\mathcal {O}(\log\,n)\), which substantially improve the results in [ 8, 15, 17] give an answer to the fifth open problem presented in [11].
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Barg A, Cohen G, Encheva S, Kabatiansky G, Zémor G (2001) A hypergraph approach to the identifying parent property: the case of multiple parents. SIAM J Discrete Math 14:423–431
Boneh D, Shaw J (1998) Collusion–secure fingerprinting for digital data. IEEE Trans Inform Theor 44:1897–1905
Deng D, Stinson DR, Wei R (2004) The Lovász local lemma and its applications to some combinatorial arrays. Design Code Cryptogr 32:121–134
Garcia A, Stichtenoth H (1996) On the asymptotic behaviour of some towers of function fields over finite fields. J Number Theory 61:248–273
Hollmann HDL, van Lint JH (1998) Linnartz J-P, Tolhuizen LMGM (1998) On codes with identifiable parent property. J Comb Theory Ser A 82:121–133
Li PC, van Rees GHJ, Wei R (2006) Constructions of 2–cover–free families and related separating hash families. J Comb Design Published Online: 21 Apr. 2006
Niederreiter H, Xing C (2002) Rational points on curves over finite fields: theory and applications. Cambridge University Press, Cambridge, MA
Sarkar P, Stinson DR (2001) Frameproof and IPP Codes. In INDOCRYPT 2001. Lect Notes Comput Sci 2247:117–126
Serre J-P (1985) Rational points on curves over finite fields. Lecture Notes, Harvard University
Stichtenoth H, (1993) Algebraic function fields and codes. Springer–Verlag, Berlin
Staddon JN, Stinson DR, Wei R (2001) Combinatorial properties of frameproof and traceability codes. IEEE Trans Inform Theory. 47:1042–1049
Stinson DR (1997) On some methods for unconditionally secure key distribution and broadcast encryption. Design Code Cryptogr 12:215–243
Stinson DR, van Trung T, Wei R (2000) Secure frameproof codes, key distribution patterns, group testing algorithms and related structures. J Statist Plann Inference 86:595–617
Stinson DR, Wei R (2004) Generalized cover-free families. Discrete Math 279:463–477
Stinson DR, Wei R, Zhu L (2000) New constructions for perfect hash families and related structures using combinatorial designs and codes. J Comb Designs 8:189–200
Tonien D, Safavi–Naini R (2003) Explicit construction of secure frameproof codes. Int J Pure App Math 6:343–360
van Trung T, Martirosyan S (2005) New constructions for IPP codes. Design Code Cryptogr 35:227–239
Tsfasman MA, Vlădut SG (1991) Algebraic–geometric codes. Kluwer Academic, Dordrecht
Wang H, Xing C (2001) Explicit constructions of perfect hash families from algebraic curves over finite fields. J Comb Theory Ser A, 93:112–124
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by S. Galbraith.
Rights and permissions
About this article
Cite this article
Liu, L., Shen, H. Explicit constructions of separating hash families from algebraic curves over finite fields. Des Codes Crypt 41, 221–233 (2006). https://doi.org/10.1007/s10623-006-9004-y
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-006-9004-y
Keywords
- Algebraic curve
- Separating hash family
- Strong separating hash family
- Frameproof (FP) code
- Secure frameproof (SFP) code
- Identifiable parent property (IPP) code