Construction of UOWHF: Two New Parallel Methods

Wonil LEE; Donghoon CHANG; Sangjin LEE; Soohak SUNG; Mridul NANDI

doi:10.1093/ietfec/e88-a.1.49

Construction of UOWHF: Two New Parallel Methods

Wonil LEE, Donghoon CHANG, Sangjin LEE, Soohak SUNG, Mridul NANDI

Full Text Views

0

Cite this

Summary :

We present two new parallel algorithms for extending the domain of a UOWHF. The first algorithm is complete binary tree based construction and has less key length expansion than Sarkar's construction which is the previously best known complete binary tree based construction. But only disadvantage is that here we need more key length expansion than that of Shoup's sequential algorithm. But it is not too large as in all practical situations we need just two more masks than Shoup's. Our second algorithm is based on non-complete l-ary tree and has the same optimal key length expansion as Shoup's which has the most efficient key length expansion known so far. Using the recent result, we can also prove that the key length expansion of this algorithm and Shoup's sequential algorithm are the minimum possible for any algorithms in a large class of "natural" domain extending algorithms. But its parallelizability performance is less efficient than complete tree based constructions. However if l is getting larger, then the parallelizability of the construction is also getting near to that of complete tree based constructions. We also give a sufficient condition for valid domain extension in sequential domain extension.

Publication: IEICE TRANSACTIONS on Fundamentals Vol.E88-A No.1 pp.49-58

Publication Date: 2005/01/01

Publicized

Online ISSN

DOI: 10.1093/ietfec/e88-a.1.49

Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)

Category: Symmetric Key Cryptography

Cite this

Copy

Wonil LEE, Donghoon CHANG, Sangjin LEE, Soohak SUNG, Mridul NANDI, "Construction of UOWHF: Two New Parallel Methods" in IEICE TRANSACTIONS on Fundamentals, vol. E88-A, no. 1, pp. 49-58, January 2005, doi: 10.1093/ietfec/e88-a.1.49.
Abstract: We present two new parallel algorithms for extending the domain of a UOWHF. The first algorithm is complete binary tree based construction and has less key length expansion than Sarkar's construction which is the previously best known complete binary tree based construction. But only disadvantage is that here we need more key length expansion than that of Shoup's sequential algorithm. But it is not too large as in all practical situations we need just two more masks than Shoup's. Our second algorithm is based on non-complete l-ary tree and has the same optimal key length expansion as Shoup's which has the most efficient key length expansion known so far. Using the recent result, we can also prove that the key length expansion of this algorithm and Shoup's sequential algorithm are the minimum possible for any algorithms in a large class of "natural" domain extending algorithms. But its parallelizability performance is less efficient than complete tree based constructions. However if l is getting larger, then the parallelizability of the construction is also getting near to that of complete tree based constructions. We also give a sufficient condition for valid domain extension in sequential domain extension.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e88-a.1.49/_p

Copy

@ARTICLE{e88-a_1_49,
author={Wonil LEE, Donghoon CHANG, Sangjin LEE, Soohak SUNG, Mridul NANDI, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Construction of UOWHF: Two New Parallel Methods},
year={2005},
volume={E88-A},
number={1},
pages={49-58},
abstract={We present two new parallel algorithms for extending the domain of a UOWHF. The first algorithm is complete binary tree based construction and has less key length expansion than Sarkar's construction which is the previously best known complete binary tree based construction. But only disadvantage is that here we need more key length expansion than that of Shoup's sequential algorithm. But it is not too large as in all practical situations we need just two more masks than Shoup's. Our second algorithm is based on non-complete l-ary tree and has the same optimal key length expansion as Shoup's which has the most efficient key length expansion known so far. Using the recent result, we can also prove that the key length expansion of this algorithm and Shoup's sequential algorithm are the minimum possible for any algorithms in a large class of "natural" domain extending algorithms. But its parallelizability performance is less efficient than complete tree based constructions. However if l is getting larger, then the parallelizability of the construction is also getting near to that of complete tree based constructions. We also give a sufficient condition for valid domain extension in sequential domain extension.},
keywords={},
doi={10.1093/ietfec/e88-a.1.49},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Construction of UOWHF: Two New Parallel Methods
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 49
EP - 58
AU - Wonil LEE
AU - Donghoon CHANG
AU - Sangjin LEE
AU - Soohak SUNG
AU - Mridul NANDI
PY - 2005
DO - 10.1093/ietfec/e88-a.1.49
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E88-A
IS - 1
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - January 2005
AB - We present two new parallel algorithms for extending the domain of a UOWHF. The first algorithm is complete binary tree based construction and has less key length expansion than Sarkar's construction which is the previously best known complete binary tree based construction. But only disadvantage is that here we need more key length expansion than that of Shoup's sequential algorithm. But it is not too large as in all practical situations we need just two more masks than Shoup's. Our second algorithm is based on non-complete l-ary tree and has the same optimal key length expansion as Shoup's which has the most efficient key length expansion known so far. Using the recent result, we can also prove that the key length expansion of this algorithm and Shoup's sequential algorithm are the minimum possible for any algorithms in a large class of "natural" domain extending algorithms. But its parallelizability performance is less efficient than complete tree based constructions. However if l is getting larger, then the parallelizability of the construction is also getting near to that of complete tree based constructions. We also give a sufficient condition for valid domain extension in sequential domain extension.
ER -