-
Post-Quantum Cryptography
1. Introduction 양자 컴퓨터가 언제 상용화가 가능할지는 예측이 힘들지만 양자 컴퓨터의 개발 이후 영향을 받을 분야는 굉장히 많고 그런 분야들에서는 관련 연구를 활발하게 진행하고 있습니다. 한편 양자 컴퓨터의 이론적 개념은 양자 역학과 컴퓨터 과학에서의 계산 이론 분야의 깊은 이해를 요구하기 때문에 (저를 포함한) 많은 사람들은 양자 컴퓨터의 개념을 매우 피상적으로 알고 있거나 기능을 잘못 이해해서 양자 컴퓨터가 상용화되면 모든 암호 체계가 붕괴된다고 착각하는 경우가 종종 있습니다. 이번 글에서는 양자 컴퓨터 시대를 대비하는 Post-Quantum Cryptography에 대해...
-
Sudoku and Nonogram with z3
서론 이전에 z3와 Boolector를 비교하는 글을 올린 적이 있습니다. (Link) 그런데 정작 z3에 대해서 글이 잘 없어서, 이번에 z3로 퍼즐을 푸는 글을 작성해보게 되었습니다. 스도쿠는 이미 충분히 유명하고, 노노그램은 네모네모 로직이나 피크로스 등을 통해서 많은 분들이 알고 계신 퍼즐이기 때문에 고르게 되었습니다. 이번 글에서는 스도쿠랑 노노그램의 솔버를 하나씩 설명해가면서 작성해보려고 합니다. 본론 Sudoku 스도쿠는 9x9개의 정수를 맞추는 퍼즐 게임입니다. 정수는 모두 1부터 9로 구성되며, 9x9개의 정수 중 몇 개의 값이 고정되어 있습니다. Wikipedia에 있는 sudoku...
-
2020 ICPC Seoul Regional
Result Analysis 이번 서울 리저널에서의 각 대학 별 상위 팀은 다음과 같다. 서울대학교: Let Us Win ICPC WF (World Finals 진출 확정) KAIST: Everybody (World Finals 진출 매우 유력) 고려대학교: 1_Hoeaeng_2_Hawawang (World Finals 진출 예상) 숭실대학교: 181920 (World Finals 진출 가능성 있음) 성균관대학교: we need sleep 올해 서울 리저널은 관전자 입장에서 재밌게 볼 만한 요소가 아주 많은 대회였다. 그래서 관전 포인트도 좀 긴 편이다. 온사이트였으면 재밌었을 것 같은데 참 아쉽다. 서울대학교 내전. 올해 서울대학교는 예년처럼...
-
알고리즘 문제 judge program 만들기
안녕하세요? 저는 이번에 알고리즘 문제의 judge program을 만들어 보았습니다. 소스 코드와 input data, 그리고 output data가 있을 때 각각의 코드마다 어떤 테스트 케이스에서 어떤 결과가 났는지를 출력해주는 프로그램을 목표로 제작하였고, 이 글에서는 제가 만든 프로그램을 어떻게 구현했는지에 대한 간단한 소개를 진행해보도록 하겠습니다. 많은 online judge 사이트, 대표적으로 백준 온라인 저지나 codeforces, sw expert academy 등에서는 많은 문제를 제공하고, 채점 결과와 실행 시간, 메모리 사용량 등도 알 수 있지만 직접 만든 문제나 테스트케이스 등에 대해 확인해보는...
-
공개 키 암호화 시스템과 수학적 안전성
이 글에서는 공개 키 암호화 시스템이 발전해나가면서 같이 논의된 수학적 개념을 살펴보고자 합니다. 특히, 암호문으로부터 평문을 알아낼 수 없다는 막연한 속성을 수학적으로 어떻게 표현하는지 알아보고자 합니다. 목차는 다음과 같습니다. 공개 키 암호화 시스템 배경 지식 공개 키 암호화 시스템의 정의 Diffie-Hellman Key Exchange RSA 암호 One-wayness CPA Semantic Security and Indistinguishability Chosen Ciphertext Attack Random Oracle Model Malleability RSA-OAEP 마무리 각주 공개 키 암호화 시스템 공개 키 암호화 시스템Public Key Cryptosystem, PKC은 W. Diffie와 M....