보안의 기초
보안의 기초는 암호학의 엄격한 수학적 기반을 제공합니다. 즉, 보안이 무엇을 의미하는지에 대한 정확한 정의, 보안이 의존하는 난해성 가정, 그리고 체계가 안전함을 증명하는 환원(reduction)을 포함합니다.
Definition
보안의 기초는 보안 목표를 정확하게 명시하고 암호화 구성이 이를 엄격하게 달성함을 입증하는 데 사용되는 정의적 프레임워크, 계산적 가정 및 증명 기법을 포함합니다.
Scope
이 영역은 암호학을 예술이 아닌 과학으로 만드는 이론을 다룹니다. 여기에는 공식적인 보안 정의와 공격자 모델, 계산적 난해성 가정, 증명 가능한 보안의 환원 기반 방법론, 그리고 무작위성과 유사 무작위성의 중심 역할이 포함됩니다. '보안'이 어떻게 정의되고 입증되는지를 다룹니다. 이러한 아이디어를 구현하는 구체적인 기본 요소와 프로토콜은 제외되며, 이는 암호학 중심 영역에서 다루어집니다.
Sub-topics
Core questions
- 암호화 체계가 '안전하다'는 것이 공식적으로 무엇을 의미하는가?
- 공격자의 능력과 목표는 정확한 모델에서 어떻게 포착되는가?
- 보안은 어떤 입증되지 않았지만 그럴듯한 난해성 가정에 의존하는가?
- 환원은 체계를 해독하는 것이 어려운 문제를 해결할 것임을 어떻게 증명하는가?
- 무작위성과 유사 무작위성이 암호학의 기초가 되는 이유는 무엇인가?
Key concepts
- 보안 정의
- 공격자 모델
- 의미론적 보안 및 구별 불가능성
- 계산적 난해성 가정
- 환원
- 일방향 함수
- 유사 무작위성
- 무시할 수 있는 확률
- 계산적 보안 대 정보 이론적 보안
Key theories
- 의미론적 보안 및 구별 불가능성
- Goldwasser와 Micali는 암호화 보안을 의미론적 보안으로 정의했습니다. 즉, 암호문은 평문에 대해 계산적으로 유용한 정보를 전혀 드러내지 않으며, 이는 암호문 구별 불가능성과 동등함이 입증되어 모호한 직관을 정확하고 달성 가능한 목표로 대체했습니다.
- 환원에 의한 증명 가능한 보안
- 체계는 이를 해독하는 효율적인 공격자가 가정된 어려운 문제를 해결하는 알고리즘으로 전환될 수 있음을 보여주는 환원에 의해 안전함이 증명됩니다. 따라서 보안은 가정에 조건부이지만 엄격합니다.
Clinical relevance
기초적인 관점은 현대 암호학이 신뢰받을 수 있는 이유입니다. 즉, 설계자들은 체계가 공격에 저항하기를 바라는 대신, 정확하게 명시된 공격자 모델 하에서 체계를 해독하는 것이 잘 연구된 문제만큼 어렵다는 것을 증명합니다. 이 방법론은 모든 표준화된 기본 요소 및 프로토콜의 보안 주장의 기반이 되며, 규제 기관 및 표준 기관이 어떤 체계를 승인할지 안내하고, 임시적이고 입증되지 않은 설계가 왜 비난받는지 설명합니다.
Evidence & guidelines
증명 가능한 보안 분석은 이제 암호화 표준화에서 필수적으로 요구됩니다(AES, SHA-3 및 양자 후 체계에 대한 NIST 경쟁은 모두 보안 증명 및 환원을 중요하게 평가했습니다). 기계 검증 증명(EasyCrypt) 및 표준화된 모델(랜덤 오라클, 표준 모델)은 엄격성을 제공하지만, 이상화된 가정에 대한 논쟁은 지속됩니다. 보안이 오직 휴리스틱에만 의존하는 구성은 권장되지 않습니다.
History
암호학은 1980년대 초 Goldwasser와 Micali가 확률적 암호화와 의미론적 보안(1982-1984)을 도입하여 최초의 정확한 정의와 증명을 제시하면서 엄격한 과학이 되었습니다. Yao와 Blum-Micali는 유사 무작위성을 공식화했으며, 환원 기반 방법론은 1980년대와 1990년대에 걸쳐 확산되었고, Goldreich의 '암호학의 기초'에서 통합되었습니다. 이러한 정의적 혁명은 현대 암호학을 이전의 코드 제작과 구별합니다.
Key figures
- Shafi Goldwasser
- Silvio Micali
- Oded Goldreich
- Andrew Yao
- Manuel Blum
Related topics
Seminal works
- goldwasser1984
- goldreich2001
- katz2020
Frequently asked questions
- '증명 가능하게 안전하다'는 것은 실제로 무엇을 의미하는가?
- 이는 명시된 공격자 모델 하에서 체계를 해독하는 것이 해결 불가능하다고 여겨지는 어떤 문제를 해결하는 것만큼 어렵다는 수학적 증명이 있다는 것을 의미합니다. 이는 절대적인 보장이 아닙니다. 보안은 난해성 가정과 현실에 충실한 모델에 조건부입니다.
- 왜 입증되지 않은 난해성 가정에 의존해야 하는가?
- 대부분의 유용한 암호학은 무조건적으로 안전하다고 증명될 수 없습니다. 그렇게 한다면 P 대 NP와 같은 주요 미해결 문제가 해결될 것입니다. 대신, 보안은 수십 년간의 실패한 공격으로 그 난이도가 뒷받침되는 소수의 오랫동안 연구된 문제(인수분해, 이산 로그, 격자)로 환원됩니다.