랜덤 오라클 모델 (Random Oracle Model, ROM)

랜덤 오라클 모델(Random Oracle Model, ROM)은 해시 함수를 '모든 새 입력에 대해 완전히 무작위인 값을 돌려주고, 같은 입력에는 항상 같은 값을 돌려주는' 이상적인 함수(랜덤 오라클)로 가정한 채 암호 방식의 안전성을 증명하는 이론적 틀입니다. 1993년 미히르 벨라레와 필립 로가웨이(Phillip Rogaway)가 논문 「Random Oracles are Practical」에서 체계화했습니다.

자세히 알아보기

실제 해시 함수(SHA-256 등)는 짧은 코드로 정의된 결정적 알고리즘이지만, 증명할 때는 모든 참여자가 질의를 통해서만 접근할 수 있는 블랙박스 무작위 함수로 취급합니다. 이렇게 하면 증명 안에서 '공격자가 어떤 값을 해시했는지 관찰'하거나 '해시 출력을 미리 정해 두기(프로그래밍)' 같은 강력한 기법을 쓸 수 있어, 효율적인 방식의 안전성을 비교적 쉽게 증명할 수 있습니다.

RSA-OAEP 암호화, RSA-PSS 서명, 피아트-샤미르 변환으로 만든 슈노르 서명과 EdDSA, BLS 서명, STARK와 많은 SNARK가 ROM에서 안전성이 증명되어 있습니다(Groth16처럼 일반 군 모델(generic group model)에 기대는 체계도 있습니다). 반대로 이런 가정 없이 증명하는 것을 '표준 모델(standard model)' 증명이라 하며, 일반적으로 더 강한 보장으로 평가됩니다.

ROM에는 근본적인 한계가 있습니다. 1998년 란 카네티, 오데드 골드라이히, 샤이 할레비는 ROM에서는 안전하지만 어떤 실제 해시 함수로 바꿔도 안전하지 않은 인위적인 방식이 존재함을 보였습니다. 그래도 실무에서 쓰는 자연스러운 방식들에서는 이런 문제가 나타난 적이 거의 없어, ROM 증명은 '설계에 근본적 결함이 없다'는 강한 근거로 받아들여집니다. 구현할 때는 길이 확장 같은 해시의 구조적 성질이 오라클 가정과 어긋나지 않도록 도메인 구분, 올바른 해시 선택(예: SHA-3, HMAC 구성)에 주의해야 합니다.

블록체인·암호화폐에서는

Bitcoin의 BIP-340 슈노르 서명과 zk 롤업의 증명 시스템은 ROM에서 분석된 피아트-샤미르 변환에 의존하고, Ethereum의 BLS 서명은 메시지를 곡선 위의 점으로 대응시키는 해시 함수를 랜덤 오라클로 보는 ROM 증명에 기대고 있습니다. 블록체인 분야의 '오라클(Chainlink 등 외부 데이터 공급자)'과는 이름만 같을 뿐 전혀 다른 개념이므로 혼동하지 않아야 합니다.

쉽게 말하면

질문을 넣으면 매번 진짜 주사위를 굴려 답하고, 같은 질문에는 기록해 둔 답을 그대로 돌려주는 '완벽한 신탁'이 있다고 가정하고 보안을 따지는 사고 실험입니다.