본문 바로가기
KERD
논문KCI 등재

UOWHF 구성방법: 최적의 키길이를 가지는 새로운 병렬 도메인 확장기

Construction of UOWHF: New Parallel Domain Extender with Optimal Key Size

장동훈|이원일
한국정보보호학회 (Korea Institute Of Information Security And Cryptology)|2004.04|정보보호학회논문지 (Journal of The Korea Institute of Information Security and Cryptology)|제14권 제2호|pp. 57-68

0

조회

0

다운로드

0

인용

0

참고문헌

주제분류컴퓨터학

초록

본 논문에서는 UOWHF의 도메인을 확장하기 위한 새로운 병렬 처리 알고리즘을 제안한다. 제시되는 알고리즘은 non-complete -ary tree에 기반을 두고 있으며 현재까지 최적의 키 길이를 가진 유일한 알고리즘인 Shoup의 알고리즘과 동일한 최적의 키 길이를 가진다. 또한 Sarkar의 결과[7]를 이용하여 본 논문에서 제시되는 알고리즘이 Shoup의 알고리즘과 함께 Sarkar가 제시한 도메인 확장 알고리즘들의 커다란 집합 중에서 가장 최적화된 키 길이를 가짐을 증명한다. 그러나 제안 알고리즘의 병렬처리능력은 complete tree에 기반한 구성 방법들 보다 약간 비효율적이다. 그러나 만약 이 점점 커진다면 알고리즘의 병렬처리능력도 complete tree에 기반한 방법들에 가까워진다.

Abstract

We present a new parallel algorithm for extending the domain of a UOWHF. Our algorithm is based on non-complete -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 [8], 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 is getting larger then the parallelizability of the construction is also getting near to that of complete tree based constructions.

참고문헌 (11)

  1. "Collision- resistant hashing", 1294, pp.470~484 (1997)
  2. "A design principle for hash functions Advances in Cryptology - Crypto'89 Lecture Notes in Computer Sciences", 435, pp.416~427 (1989), Springer-Verlag
  3. "Advances in Cryptology - Crypto'89 Lecture Notes in Computer Sciences", 435, pp.428~446 (1989), Springer-Verlag
  4. "Hash functions", 2045, pp.166~181 (2001)
  5. "A New Tree based Domain Extension of UOWHF"
  6. "Universal one-way hash functions and their cryptographic applications", pp.33~43 (1989), Proceed- ings of the Twenty First Annual ACM Symposium on Theory of Computing, ACM Press
  7. "Construction of UOWHF", Cryptology ePrint Archive
  8. "Domain Extenders for UOWHF A Generic Lower Bound on Key Expansion and a Finite Binary Tree Algorithm", Cryptology ePrint Archive
  9. "A composition theorem for universal one-way hash functions", 1807, pp.445~452 (2000)
  10. "Finding collisions on a one-way street can secure hash func- tions be based on general assump- tions?", 1403, pp.334~345 (1998)
  11. "Finding collisions on a one-way street", 1403, pp.334~345 (1998)

관련 논문AI추천

Security Properties of Domain Extenders for Cryptographic Hash FunctionsBart Mennink, Bart Preneel, Elena Andreeva한국정보처리학회 · JIPS(Journal of Information Processing Systems)2010 · 제6권 제4호Pairing을 이용한 트리 기반 그룹키 합의 프로토콜김용대, 이상원, 천정희한국정보보호학회 · 정보보호학회논문지2003 · 제13권 제3호계층적 키 트리를 사용한 모바일 환경에 효율적인 그룹키 합의 프로토콜조석향한국컴퓨터정보학회 · 한국컴퓨터정보학회논문지2018 · 제23권 제2호블록암호 기반 키유도함수의 증명가능 안전성강주성, 염지선, 이옥연한국정보보호학회 · 정보보호학회논문지2010 · 제20권 제4호공개 파라메터 키 크기를 줄인 새로운 이산대수문제박영호, 오상호, 주학수한국정보보호학회 · 정보보호학회논문지2003 · 제13권 제2호광역 파이프 해쉬 함수에 기반한 안전하고 효율적인 비밀분산김희도, 원동호한국정보처리학회 · 정보처리학회논문지C2006 · 제13권 제7호

이 간행물의 다른 논문 (7건)

신뢰할 수 없는 DRM 클라이언트 시스템 하에서 키 보호를 위한 Secure Storage Device의 연구황성운, 권태경, 이기정, 윤기송pp. 3-13정수의 분해를 이용한 ElGamal형 서명기법의 안전성 분석김동렬, 이익권pp. 15-22n-Gram 색인화와 Support Vector Machine을 사용한 스팸메일 필터링에 대한 연구서정택, 서정우, 문종섭, 손태식pp. 23-33P2P 환경의 자기 평판 관리 시스템김태성, 진승헌, 윤효진, 이인석, 김우환, 천정희, 추경균, 조남수pp. 35-47인증된 양자 키 분배 프로토콜양형진, 홍창호, 이화연, 이덕진, 임종인pp. 49-55
원문 보기