일방향 함수 (one-way function)
쉽게 풀면
일방향 함수는 계란을 깨서 스크램블 에그를 만드는 것에 비유되곤 한다. 계란을 깨는 것(정방향 계산)은 쉽지만, 스크램블 에그를 다시 원래의 온전한 계란으로 되돌리는 것(역방향 계산)은 사실상 불가능하다. 현대 암호학의 거의 모든 구성 요소(암호화, 해시 함수, 전자 서명 등)는 이런 일방향 함수의 존재를 전제로 안전성을 논한다. 흥미롭게도 일방향 함수가 실제로 존재하는지는 아직 수학적으로 증명되지 않았으며, 이는 P≠NP 추측과도 깊이 관련되어 있다.
왜 중요한가
일방향 함수는 현대 암호학 전체의 이론적 토대가 되는 개념으로, 이것이 존재한다고 가정할 수 있어야 비로소 안전한 암호화·해시함수·전자서명·비밀번호 저장 방식 등을 수학적으로 설계하고 그 안전성을 논증할 수 있습니다. 그래서 이론 컴퓨터과학과 암호학 논문에서는 특정 암호 체계의 안전성을 "어떤 문제가 일방향 함수로서 성립한다"는 가정으로 환원해 증명하는 방식이 표준적인 서술 틀로 자리잡고 있습니다.
논문에서는 이렇게 쓰입니다
암호 시스템의 안전성 증명이 어떤 계산적 가정에 기반하는지 명시할 때 사용된다.
실무 보안 시스템 설계 논문에서는 해시함수의 일방향성이라는 성질을 비밀번호 보호 같은 구체적인 응용에 어떻게 활용하는지를 설명합니다.
이론 computer science 논문에서는 특정 수학적 난제가 일방향 함수의 후보로서 갖는 성질을 복잡도 이론 관점에서 형식적으로 다룹니다.
조금 더 깊게 보면
암호학에서 실제로 쓰이는 안전성 증명은 대개 일방향 함수의 존재를 무조건적으로 증명하는 대신, 소인수분해나 이산로그 문제처럼 오랫동안 효율적인 풀이법이 발견되지 않은 난제들이 일방향 함수로 작동한다고 가정한 뒤, 만약 이 암호 체계가 뚫린다면 그 난제도 효율적으로 풀 수 있다는 식의 환원(reduction) 논증을 사용합니다. 또한 단순 일방향 함수보다 더 강한 성질인 트랩도어 일방향 함수(비밀 정보를 알면 역산이 쉬워지는 함수)는 공개키 암호의 핵심 구성요소로 별도로 다뤄지며, 양자컴퓨터의 발전에 따라 기존에 안전하다고 여겨지던 일부 후보 함수들의 안전성이 재검토되는 것도 최근 암호학 연구의 주요 흐름 중 하나입니다.
주의할 점
일방향 함수의 존재는 엄밀하게 증명된 수학적 사실이 아니라 아직 반증되지 않은 가정이며, 현재까지의 계산 능력으로 역산이 어렵다는 것을 경험적으로 관찰한 것에 가깝다.