-
대화형 증명 시스템과 영지식 증명
이전 글에서는 공개 키 암호화 시스템에서 보안을 어떻게 챙겨야 하는가를 다루었습니다. 암호화 알고리즘은 기본적으로 외부의 개입이 없습니다. 그러나 세상에는 다양한 프로토콜이 있고, 둘 이상이 통신하며 내용을 주고 받습니다. 이 글에서는 프로토콜의 보안을 어떻게 챙기고 또 암호화폐로 인해 널리 알려진 속성인 영지식성zero-knowledgeness을 다루고자 합니다. 대화형 증명 시스템 NP Revisited Arthur-Merlin Protocol IP 영지식 알리바바와 동굴 Indistinguishability Revisited Fiat-Shamir Protocol Hamiltonian Cycle 마무리 각주 대화형 증명 시스템 대화형 증명 시스템interactive proof system은 두 개체 증명자prover와 검증자verifier로 이루어져...
-
COVID-19 확산의 분석
COVID-19 확산의 분석 Contents 개요 및 기존 분석들 분석 방향성 분석 결과 및 의의 이후 방향성 참고 개요 및 기존 분석들 COVID-19 사태는 현재 인류에 큰 피해를 주고 있으며, 앞으로 얼마나 더 지속될지 모르고, 후에 유사한 전염병이 다시 나타났을 때, 좀 더 유연하고 의미있는 해결책과 대비책이 존재하면 좋을 것이라고 생각했습니다. 또한 코로나와 같은 사회 경제에 직접적으로 영향을 주게 되는 경우, 어떤 패턴이 존재하고 변화하는지를 알아보는 과정이 흥미로울 것 같아서 분석을 진행해보게 되었습니다. 먼저, 기존의 분석에...
-
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1)
Dynamic MSF with Subpolynomial Worst-case Update Time (Part 1) 그래프에서 최소 스패닝 트리 (Minimum spanning tree)를 구하는 문제는 아주 잘 알려져 있고, 일반적으로 가장 처음 공부하게 되는 그래프 알고리즘에 속하며, 매우 다양한 개념에 응용된다. 그래프의 최소 스패닝 트리는 크루스칼 알고리즘을 통해서 $O(m \log m)$ 에 효율적으로 구할 수 있다. 하지만 그래프에서 간선이 추가되고 제거되는 등의 업데이트가 가해진다면, 이 알고리즘은 매 갱신마다 전체 간선 리스트를 전부 순회해야 하니 더 이상 효율적이지 않게 된다. 이렇게 그래프의 일부가...
-
Codeforces Round #688 개최 후기
개요 Codeforces Round #688 (Div. 2) Announcement Editorial (이전 글) Codeforces Round #620 개최 후기 (이전 글) Codeforces Round #578 개최 후기 올해 초 Codforces에서 개최했던 620번 라운드는 제게는 잊을 수 없는 기분 좋은 추억입니다. 처음으로 단독 출제자를 해본 대회에 무려 14612명이 등록해서 좋은 반응을 이끌어냈었다는 것이 정말 좋았습니다. 그 기분을 다시 느끼고 싶어서 라운드가 종료되고 얼마 지나지 않아 바로 다음 라운드를 준비하기 시작했고,1 12월 4일 22시 05분(KST)부터 2시간 15분에 걸쳐 Codeforces Round #688 (Div....
-
IOI 2020 및 SNUPC 2020 출제후기
SNUPC 2020 출제후기 SNUPC 2020에는 Div.1의 총 9문제중 절반 정도에 해당하는 4문제를 출제하였다. 재미있는 문제를 낼 수 있어서 만족스러웠다. 그리고 imeimi2000, TAMREF 등 여러 출제진 검수진들이 고생해 준 덕분에 문제 데이터와 지문의 퀄리티가 올라가서 성공적인 대회가 될 수 있었던 것 같다. 9문제 중 대부분이 자명하지 않고 아이디어를 필요로 하는 문제들이라서 아직 풀어보지 않은 분들은 시도해 보고 나서 글을 보면 좋을 것 같다. 자세한 풀이는 여기 에 있으니 여기에는 담지 않는다. A. 빈 문자열 만들기 링크...