충돌회피 함수 (Collision-Resistant Hash Function, CRHF)는 암호 어플리케이션에서 널리 이용되는 해쉬 함수에 가장 일반적으로 적용되어온 개념이다. 그러나 CRHF는 가정이 강력하여 이 가정을 만족시키도록 설계하는 것이 매우 어렵다. 반면, 유니버셜 일방향 함수 (Universal One-Way Hash Function, UOWHF)는 CRHF보다 약한 가정이며 일부 어플리케이션에서 CRHF 대신 사용될 수 있다는 점에서 일종의 대안으로서 연구되어 왔다. Chapter 2에서는 기존에 제시된 UOWHF들이 소개된다. CRHF와는 달리, UOWHF는 일방향 치환 (One-Way Permutation)과 같은 비교적 약한 프리미티브를 이용하여 구성할 수 있다. 임의의 길이의 해쉬 함수를 만들기 위한 가장 일반적인 방법은 고정된 입력 길이를 갖는 함수를 반복적인 방법으로 확장시키는 것이다. 그러나 UOWHF는 메시지의 길이가 길수록 추가로 요구되는 랜덤 키의 길이가 길어지는 문제점이 있다. Chapter 3에서는 ...
충돌회피 함수 (Collision-Resistant Hash Function, CRHF)는 암호 어플리케이션에서 널리 이용되는 해쉬 함수에 가장 일반적으로 적용되어온 개념이다. 그러나 CRHF는 가정이 강력하여 이 가정을 만족시키도록 설계하는 것이 매우 어렵다. 반면, 유니버셜 일방향 함수 (Universal One-Way Hash Function, UOWHF)는 CRHF보다 약한 가정이며 일부 어플리케이션에서 CRHF 대신 사용될 수 있다는 점에서 일종의 대안으로서 연구되어 왔다. Chapter 2에서는 기존에 제시된 UOWHF들이 소개된다. CRHF와는 달리, UOWHF는 일방향 치환 (One-Way Permutation)과 같은 비교적 약한 프리미티브를 이용하여 구성할 수 있다. 임의의 길이의 해쉬 함수를 만들기 위한 가장 일반적인 방법은 고정된 입력 길이를 갖는 함수를 반복적인 방법으로 확장시키는 것이다. 그러나 UOWHF는 메시지의 길이가 길수록 추가로 요구되는 랜덤 키의 길이가 길어지는 문제점이 있다. Chapter 3에서는 MD 및 TR 확장법이 왜 UOWHF에 적용될 수 없는지를 지적하며, 기존에 제시된 UOWHF 확장법에는 어떤 것들이 있는지 살펴본다. Chapter 4에서는 UOWHF의 order에 대한 개념이 소개된다. higher order UOWHF들이 갖는 성질들이 설명되며, 고계 UOWHF가 일방향 치환으로부터 구성될 수 있음이 보여진다. Chapter 4의 결과에 따르면, 어떤 UOWHF가 설계되어 제안되었을 때, 그것의 order를 알 수 있다면 효율적으로 활용할 수 있다: 고정된 입력길이를 갖는 UOWHF의 order가 r ≥ 0일 때, 그것의 (r + 1)-라운드 MD 확장은 UOWHF이다; 고정된 입력길이 dc, 출력길이 c를 갖는 UOWHF의 order가 (dl −d)/(d −1) 일 때, l-레벨 TR 확장이 UOWHF가 된다. Chapter 5에서는 블록 암호에 기반한 해쉬 함수들에 대한 연구가 소개된다. PGV 해쉬 함수는 rate-1, 싱글 블록 길이를 갖는 64개의 모든 해쉬 함수를 포괄하는 모델이다. 이중 12가지가 기존의 공격에 안전할 것으로 제시되어있으며, 블랙박스 모델에서 안전한 것(collision resistance)으로 증명되는 형태는 추가로 8 가지가 더 발견되었다. 그러나 64 가지의 모든 함수가 쉽게 충돌이 발견되도록 만드는 블록 암호들의 예제가 발표됨에 따라, 블랙 박스 모델에서의 증명이 갖는 한계가 드러났다. Chapter 6에서는 이것에 대한 대안으로서 블록 암호 기반 UOWHF를 고려한다. Naor-Yung의 UOWHF와 일부 PGV 해쉬 함수들을 블록 암호 기반 알고리즘으로 변형시킨 모델을 제시한다.
충돌회피 함수 (Collision-Resistant Hash Function, CRHF)는 암호 어플리케이션에서 널리 이용되는 해쉬 함수에 가장 일반적으로 적용되어온 개념이다. 그러나 CRHF는 가정이 강력하여 이 가정을 만족시키도록 설계하는 것이 매우 어렵다. 반면, 유니버셜 일방향 함수 (Universal One-Way Hash Function, UOWHF)는 CRHF보다 약한 가정이며 일부 어플리케이션에서 CRHF 대신 사용될 수 있다는 점에서 일종의 대안으로서 연구되어 왔다. Chapter 2에서는 기존에 제시된 UOWHF들이 소개된다. CRHF와는 달리, UOWHF는 일방향 치환 (One-Way Permutation)과 같은 비교적 약한 프리미티브를 이용하여 구성할 수 있다. 임의의 길이의 해쉬 함수를 만들기 위한 가장 일반적인 방법은 고정된 입력 길이를 갖는 함수를 반복적인 방법으로 확장시키는 것이다. 그러나 UOWHF는 메시지의 길이가 길수록 추가로 요구되는 랜덤 키의 길이가 길어지는 문제점이 있다. Chapter 3에서는 MD 및 TR 확장법이 왜 UOWHF에 적용될 수 없는지를 지적하며, 기존에 제시된 UOWHF 확장법에는 어떤 것들이 있는지 살펴본다. Chapter 4에서는 UOWHF의 order에 대한 개념이 소개된다. higher order UOWHF들이 갖는 성질들이 설명되며, 고계 UOWHF가 일방향 치환으로부터 구성될 수 있음이 보여진다. Chapter 4의 결과에 따르면, 어떤 UOWHF가 설계되어 제안되었을 때, 그것의 order를 알 수 있다면 효율적으로 활용할 수 있다: 고정된 입력길이를 갖는 UOWHF의 order가 r ≥ 0일 때, 그것의 (r + 1)-라운드 MD 확장은 UOWHF이다; 고정된 입력길이 dc, 출력길이 c를 갖는 UOWHF의 order가 (dl −d)/(d −1) 일 때, l-레벨 TR 확장이 UOWHF가 된다. Chapter 5에서는 블록 암호에 기반한 해쉬 함수들에 대한 연구가 소개된다. PGV 해쉬 함수는 rate-1, 싱글 블록 길이를 갖는 64개의 모든 해쉬 함수를 포괄하는 모델이다. 이중 12가지가 기존의 공격에 안전할 것으로 제시되어있으며, 블랙박스 모델에서 안전한 것(collision resistance)으로 증명되는 형태는 추가로 8 가지가 더 발견되었다. 그러나 64 가지의 모든 함수가 쉽게 충돌이 발견되도록 만드는 블록 암호들의 예제가 발표됨에 따라, 블랙 박스 모델에서의 증명이 갖는 한계가 드러났다. Chapter 6에서는 이것에 대한 대안으로서 블록 암호 기반 UOWHF를 고려한다. Naor-Yung의 UOWHF와 일부 PGV 해쉬 함수들을 블록 암호 기반 알고리즘으로 변형시킨 모델을 제시한다.
Universal one-way hash functions (UOWHFs) have been considered as alternative primitives to collision-resistant hash functions (CRHFs). Since a UOWHF is a weaker primitive than a CRHF, it would be easier to design. In Chapter 2, the construction of UOWHFs is introduced. Unlike CRHFs, UOWHFs can be c...
Universal one-way hash functions (UOWHFs) have been considered as alternative primitives to collision-resistant hash functions (CRHFs). Since a UOWHF is a weaker primitive than a CRHF, it would be easier to design. In Chapter 2, the construction of UOWHFs is introduced. Unlike CRHFs, UOWHFs can be constructed from relatively weak primitives such as one-way permutations. The most popular approach for designing a hash function hashing arbitrary-length messages is to extend a hash function with a fixed input length with an iterative method. However, UOWHFs have the problem of the increase of key length depending on the length of hashed messages. In Chapter 3, we present why MD and TR extensions cannot be used for extending UOWHFs and introduce existing extension methods for UOWHFs. In Chapter 4, the notion of the order of a UOWHF is presented, and the properties and construction of higher order UOWHFs are explained. According to the result in Chapter 4, when a UOWHF is designed and proposed, we can use it efficiently if we check its order: when a UOWHF with fixed input length is of order r ≥ 0, then its (r + 1)-round MD extension is a UOWHF; when a UOWHF with fixed input length dc and output length c and its order is (dl −d)/(d −1), its l-level TR extension is a UOWHF. Finally, we survey the research on block-cipher-based hash functions in Chapter 5, and propose the construction of block-cipher-based UOWHFs in Chapter 6.
Universal one-way hash functions (UOWHFs) have been considered as alternative primitives to collision-resistant hash functions (CRHFs). Since a UOWHF is a weaker primitive than a CRHF, it would be easier to design. In Chapter 2, the construction of UOWHFs is introduced. Unlike CRHFs, UOWHFs can be constructed from relatively weak primitives such as one-way permutations. The most popular approach for designing a hash function hashing arbitrary-length messages is to extend a hash function with a fixed input length with an iterative method. However, UOWHFs have the problem of the increase of key length depending on the length of hashed messages. In Chapter 3, we present why MD and TR extensions cannot be used for extending UOWHFs and introduce existing extension methods for UOWHFs. In Chapter 4, the notion of the order of a UOWHF is presented, and the properties and construction of higher order UOWHFs are explained. According to the result in Chapter 4, when a UOWHF is designed and proposed, we can use it efficiently if we check its order: when a UOWHF with fixed input length is of order r ≥ 0, then its (r + 1)-round MD extension is a UOWHF; when a UOWHF with fixed input length dc and output length c and its order is (dl −d)/(d −1), its l-level TR extension is a UOWHF. Finally, we survey the research on block-cipher-based hash functions in Chapter 5, and propose the construction of block-cipher-based UOWHFs in Chapter 6.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.