AncomWiki

추측 작업(Guesswork), 대편차 이론, 및 섀넌 엔트로피

Properties1
description이 논문은 비밀번호 추측의 어려움을 정보 이론적 관점에서 분석한다. 기존 연구가 섀넌 엔트로피와 추측 횟수의 관계를 점근적으로 다뤘다면, 본 연구는 비밀번호 길이가 증가할 때 로그 추측 작업(logarithm of guesswork)이 대편차 원리(Large Deviation Principle, LDP)를 만족함을 보인다. 이를 통해 긴 비밀번호의 추측 작업 분포에 대한 직접적인 추정치를 제공한다. 또한 LDP의 부수 결과로…

7 min read

추측 작업(Guesswork), 대편차 이론, 및 섀넌 엔트로피

Source

  • Evernote/Papers/Guesswork, Large Deviations, and Shannon Entropy.md

Summary

이 논문은 비밀번호 추측의 어려움을 정보 이론적 관점에서 분석한다. 기존 연구가 섀넌 엔트로피와 추측 횟수의 관계를 점근적으로 다뤘다면, 본 연구는 비밀번호 길이가 증가할 때 로그 추측 작업(logarithm of guesswork)이 대편차 원리(Large Deviation Principle, LDP)를 만족함을 보인다. 이를 통해 긴 비밀번호의 추측 작업 분포에 대한 직접적인 추정치를 제공한다. 또한 LDP의 부수 결과로, 로그 추측 작업의 기댓값이 비밀번호 선택 과정의 특정 섀넌 엔트로피(specific Shannon entropy)와 같음을 재확인한다.

Key Points

  • 비밀번호 추측 작업(Guesswork)의 로그값이 비밀번호 길이 증가 시 대편차 원리(LDP)를 따른다.
  • LDP는 긴 비밀번호의 추측 작업 분포를 직접 추정할 수 있게 한다.
  • 로그 추측 작업의 기댓값은 비밀번호 선택 과정의 특정 섀넌 엔트로피와 동일하다(Massey의 관찰을 LDP 관점에서 재해석).
  • 추측 작업의 본질적인 구조가 LDP의 속도 함수(rate function) 형태에 내재되어 있다.

그래프 뷰