Hhan – 페이지 9 – Pseudorandom Things

CS 논문의 유머러스한 글작성들

2020년 5월 22일2020년 7월 13일Hhan댓글 남기기

수학 논문을 많이 읽지 않아서 정확히는 모르겠지만 -_-.. 수학논문들은 정말 딱 필요한 내용만 적는 경향이 강한것같다. 인트로조차도 expert가 아니면 무슨말인지 한단어도 못알아들을때도 있는것같고..

반면 CS쪽의 논문들은 대부분 결과를 이해하는게 그렇게 어렵지 않아서인지 인트로와 초록을 최대한 재미있고 인상깊게 쓰려고하는것같다. 물론 정말 재미있게 쓰는것들은 대가들이나 할수있는거지만..

그래서 심심해서 이것저것 기억나는 재미있는 부분들을 정리해봄.

계속 읽기 →

New WordPress text editor

2020년 5월 22일Hhan댓글 남기기

워드프레스에서 새로운 편집기를 6월 1일부터 사용할수있다고 한다. 이전 편집기도 많이 안썼고, 조금은 불편하다고 생각했어서 미리 이용하는 기능을 써보기로 함.

이런 저런 ~~기능들~~이 있는것같은데, 이런것들은 다 원래 있던거같고..

폰트사이즈도 조절이 가능한것은 같다. 이전보다 약간은 편해진거같은데 크기가 블럭단위로 바뀌네 -_-..

마크다운도 이용가능하다! 잘은 안쓰지만 아주 편하다고하던데.. 이전에도 지원했나? 혹시 $$$\pi$$$같은 $$$\LaTeX$$$ 마크다운도 지원하나? 아쉽게도 안하는군ㅋ 이전에 사용하던대로 $\LaTeX$ 쓰면 되긴 한다. 여전히 조금 불편하지만. 적절한 css클래스를 추가하면 되는건가?

뭐 결국 이런저런기능 별로 안쓰고 쓰는거만 쓸것같긴 하다. 워낙 귀찮은걸 싫어하니 ㅋㅋㅋ

Playing pool with psi

2020년 5월 20일2020년 6월 26일Hhan댓글 한 개

3Blue1Brown에서 소개되어서 유명해진 충돌을 통해 pi를 계산하는 방법. 유닼님의 블로그에도 소개된적이 있다.

쉽게 말하면 $10^{2n}$ 의 질량을 갖는 공 A와 벽 사이에 $1$ 의 질량을 갖는 공 B를 두고, A를 B방향으로 이동시키면 마찰력이 없고 완전탄성충돌일 때 충돌횟수가 $pi$ 의 소숫점 $n$ 번째 자리까지 정확히 같다는것. 즉, A의 질량이 $M$ 일 때,

(충돌횟수) $= [\pi\sqrt{M}]$

이 된다는 것이다. 이게 Playing pool with \pi라는 논문의 결과.

근데, 혹시 양자알고리즘에 관심이 있다면 Grover algorithm이라는 것을 들어봤을 것이다. Indexing이 되어있는 데이터 $A=\{a_i\}_{1\le i \le N}$ 이 있을때 원하는 데이터 $x$ 를 $A$ 에서 찾는 문제가

고전적으로는 $a_i$ 를 하나하나 다 봐야하니 $\Omega(N)$ 번 데이터를 봐야하지만,
양자컴퓨터로 $\sum |a_i\rangle$ 처럼 데이터를 superposition의 형태로 보는것을 허용하면 데이터에 $\Theta(\sqrt N)$ 번의 접근만으로 원하는 데이터를 충분히 높은 확률로 찾을수 있다는것.

Grover search가 가장 좋은 알고리즘인것도 알려져 있다. 근데 Grover algorithm의 분석을 잘 살펴보면 데이터베이스 접근이

$[\frac 1 4 \pi \sqrt{N-1}]$

번일때 최적이 된다. 이게 신기하게 위의 충돌횟수와 비슷한데, Playing pool with \psi라는 논문에 따르면 이런 유사함이 우연이 아니라, Grover algorithm과 저 충돌 시뮬레이션 사이에 어떤 일종의 isomorphism이 존재한다는것.

(혹시 양자계산에 익숙하지 않은 독자가 있다면.. quantum state는 $\sum_x \alpha_x |x\rangle$ 으로 쓰는데, 사실 이건 $\sum_x |\alpha_x|^2=1$ 이 성립하는 unit vector $(\alpha_1,...,\alpha_N)$ 으로 볼 수 있고, 얘에 대한 Unitary operation만으로 계산을 진행하다 마지막에 measurement를 통해 $x$ 를 각각 $|\alpha_x|^2$의 확률로 얻는것이라고 이해하면…. 아래 설명은 이해할수 있을지도 모른다 -_-..)

Grover algorithm을 아주아주 간략하게 설명하면 다음과 같다.

uniform superposition $|s\rangle = \frac 1 {\sqrt N} \sum_{i=1}^N |i\rangle$ 을 준비한다. 우리가 찾고자하는건 $|x\rangle$ 이라 하자.
$s$ 에 대한 reflection $U_s=2|s\rangle \langle s|-I$ 를 적용한다.
$x$ 에 대한 reflection $U_x=2|x\rangle \langle x| - I$ 를 적용한다. (결과는 $|x\rangle$ 의 계수만 부호가 반대로 바뀐다.)
2,3의 과정을 $T=\frac 1 4 \pi \sqrt{N-1}$ 번 반복하고 measurement를 해서 결과를 본다.

이해가 가지 않을텐데, 설명을 대충한것이니 어쩔수없다 -_-…

여기서 저자가 발견한 isomorphism은 다음과 같다. 우선 충돌 실험에서 공을 A,B 두개만 둘것이 아니라 질량이 모두 같은 $1,...,N$ 번의 번호를 붙인 $N$ 개의 공을 두고, $N-1$ 개의 공을 A위치에 겹쳐서 두고, 하나의 공( $=x$ 번)만 B의 위치에 두자는 것. 그리고 $N$ 개의 공의 현재 속도가 $(v_1,...,v_N)$ 이 될것이다. 근데 운동에너지는 보존되므로

$v_1^2 + ....+v_N^2$

은 상수이고, 이걸 1이라고 둘 수 있다. 이 다음에 이런 quantum state를 생각하자.

$\sum_x v_x |x\rangle$

그러면 공 A가 B와 부딪히는것은 사실 $U_s$ 에 해당하고, B가 벽과 부딪히는것은 $U_x$ 에 해당한다는 것. 특히 $U_x$ 가 $|x\rangle$ 의 부호만 바꿨다는것을 기억하면 꽤나 그럴듯하다.

이런 관점에서 Grover algorithm과 위 충돌실험은 처음 state만 다를뿐, 완전히 같은 실험이라는것. 굉장히 신기하다.

이거 쓰다가 알게되었는데, $\LaTeX$ 코드와 링크삽입이 충돌해서 줄이 바뀌게 되는것같다 -_-…. 어떻게 해결 안되나?

Quantum collision finding for concrete hash functions

2020년 5월 14일2020년 6월 26일Hhan댓글 남기기

지난글에서 얘기했던 컨퍼런스에서 발표된 결과중 간단하게 소개할수 있는게 있어서 한번..

Collision finding problem은 어떤 해쉬함수 $H:[N]\rightarrow[M]$ 에 대해 $H(x_1)=H(x_2)$ 를 만족하는 쌍 $x_1,x_2\in [N]$ 을 찾는 문제이다 ( $N\gg M$ 이라고 가정하자)

만약 이 문제를 임의의 함수 $H$ 에 대해 생각한다면 고전적으로는 시간이 $\sqrt M$ 정도가 필요하다.
반면 양자컴퓨터를 이용하면 BHT algorithm을 이용하면 $\sqrt[3] M$ 정도에 찾을수 있음이 알려져 있다.

그런데 사실 현실의 Hash function은 완전히 random function은 아니고, 특정한 구조를 가진 함수들을 쓴다. 그래서 암호학에서 구체적인 Hash function의 (collision-resistance에 대한) 안전성에 대한 연구의 목표는 위 일반적인 공격(=generic attack)보다 빠른 공격을 찾는게 된다.

실제로 Hash function들은 주로 비슷한 구조의 함수를 여러번 적용하는 형태로 만들어진다. (예를들어 SHA3는 어떤 구조를 12+번정도 반복함) 이런 구조가 적용된 횟수를 라운드라고 하고, 많은 공격에서 실제 구조보다 약간 작은 라운드만 반복했을때를 타겟으로 잡고 연구한다. 이런 공격을 Reduced-round attack이라고 함. 실제 Hash는 알려진 Reduced-round attack의 최대 라운드보다 몇개정도 큰 라운드로 고정해서 사용한다.

최근 학계에서는 Hash function 같은 경우는 여러가지 이유로 양자컴퓨터를 이용한 공격이 아주 드라마틱한 결과를 이끌어낼거라고 생각은 안하는것 같다. 어느정도는 기존에 알려진 공격들의 서브루틴들이 양자알고리즘으로 바뀌었을 때 빨라지는정도로만 안전성이 위협을 받을것이라고 추측하고 있음. 특히 Round는 지금과 똑같이 써도 되지 않을까 막연히 (아무런 논의없이) 가정하고 있는것으로 보인다.

그런데 Hosoyamada Akinori와 Yu Sasaki에 따르면 그 예상이 완전히 옳지는 않다고 한다. Rebound attack이라는 방식이 기존에는 Whirlpool과 AES-MMO라는 두 Hash function을 각각 5,6라운드에 대한 Reduced-round attack이 알려져 있었는데, 이번에 이를 양자컴퓨터를 잘 이용해서 변형하면 6,7라운드에 대해 generic attack보다 빠르게 공격할수 있다고 한다.

즉 Hash function의 양자컴퓨터에 대한 안전성이 generic attack에 대한 공격속도의 증가 말고도 뭔가 구조적인 문제가 조금 더 있을 수 있다는 결론을 얻게된다. 다만 현실적인 공격은 여전히 하는게, 양자컴퓨터도 없고, Whirlpool같은 경우 10라운드를 쓰는데 여전히 그건 한참 남았으니 -_-..

Webinar experience

2020년 5월 12일2020년 5월 20일Hhan댓글 2개

암호 컨퍼런스 하나가 온라인으로 전환되어 진행중이다. Zoom과 Zulip, Youtube를 통해 이루어지는데, 암호컨퍼런스가 최근 보안이슈가 있던 Zoom으로 이루어지는게 조금 웃기네 ㅎㅎ.

형식은 기존과 다르게 25분짜리 동영상 talk을 Youtube에 저장해두고, 컨퍼런스는 각 발표가 10분이내로 정말 간단하게 설명만 한다. 집중도 되고 다양한 분야의 소개도 들을수 있어 좋은듯.

여기 소개할수있는 결과가 있으면 좋을텐데…… Algebraic group model의 현실성이나 Verifiable delay function만드는 방식이 지금까지 알려진 형태인 이유들 같은게 그나마 좀 캐쥬얼한 내용인것같은데, 그거도 여기 짧게 설명하긴 쉽지 않아보이고 재미도 없을듯 -_-.

뭐 기회가 있으면 대략적으로 정리를…

구글의 양자컴퓨터 vs 고전 시뮬레이션, 근황

2020년 5월 9일2020년 7월 5일Hhan댓글 8개

작년 놀라운 결과가 구글에 의해 발표되었다. 최초로 프로그래밍 가능한 양자컴퓨터를 이용해서 고전컴퓨터로는 현실적으로 불가능한 시간이 필요한 태스크를 그들의 53-qubit짜리 양자컴퓨터를 이용해 실험적으로 증명했다는 것.

이 발표 직후에 IBM에서 고전컴퓨터로 불가능하진 않다는 반박을 냈는데, 현존 최고수준의 슈퍼컴퓨터로 며칠이나 걸린다는 거라서… 어떤 의미에서는 양자우월성(Quantum Supremacy)라는 말을 방증하기도 한다.

그러면 이 양자우월성이라는 것을 구글은 어떻게 증명한걸까? 그리고 이후에도 IBM등지에서 다양한 추가 논의를 시도하는 이유는 뭘까? 이 글에서는 이러한 것들에 대해 알아보고자 한다.

2020/7/5 추가: 최근 조사한 것들을 바탕으로, 구글의 양자우월성 증명과 이후 논문들을 모두 설명하도록, 쉽게 읽히도록 새로 정리함.

계속 읽기 →

컴백?

2020년 5월 8일2020년 5월 8일Hhan댓글 남기기

사이트를 이것저것 갈아버렸다.
이제는 좀 더 간략하고 가벼운 글 위주로 써서 유지가능하도록 써야겠음.

The probability that two random integers are relatively prime.

2017년 2월 13일2020년 5월 8일Hhan댓글 한 개

영어공부를 하다 심심해서 오랜만에 기억나는 다음 정리를 다시 한번 증명해봤습니다.

(Theorem) The probability that two random positive integer are relatively prime is $1/\zeta(2)=6/\pi^2$ .

아래의 증명은 (아마도) Niven책[1]에서 처음 본 것 같습니다. 조금 다르더라도 이런 방식의 정의와 증명을 처음 본 건 Niven이 맞으니까 뭐 저기서 인용했다고 칩시다.

계속 읽기 →

A toy problem

2016년 12월 30일2020년 5월 8일Hhan댓글 남기기

얼마전에 (크리스마스날!) 학원 수업 대타를 하루 했습니다. 이제 다시는 학원수업을 하지 않을줄 알았는데.. 오랜만에 올림피아드 문제좀 풀어볼까 하고 잠시 시간을 내어 수업을 했습니다. 그런데 그 전후로 너무 바빠서 생각보다 힘들었습니다..

그날 수업을 위해 준비한 문제중 다음과 같은 문제가 있습니다.

There are $n$ positive integer $a_1,\cdots , a_n$ , need not to be different, in the blackboard. In each “step”, we can erase two numbers $a,b$ and write greatest common divisor and least common multiple of $a,b$ in the blackboard. The “meaningful step” is a step which change the set of integers in the blackboard.

Prove that the possible number of meaningful steps is finite.
Regardless of the way we do steps, if we cannot do any meaningful steps, the possible set of integers in the blackboard is unique.

원래 문제는 1번만 있었는데, 너무 쉬워서 내지 말까 고민했었습니다. 근데 왠지 더이상 할 수 없는 상태가 유일하지 않을까 싶어서 이리저리 고민해보니 적당한 난이도로 해결이 되고, 재미있는 toy problem인 것 같아서 출제했습니다. 풀이는 비밀로 ㅎㅎ.

요즘의 관심사

2016년 12월 15일2020년 5월 8일Hhan댓글 남기기

요즘은 시험기간이여서 글도 많이 쓰지 못하고, 다른 공부도 거의 하지 못합니다. 기말이 있는 과목은 복소다양체(Complex Manifold)와 대수기하학 개론(Introduction to Algebraic Geometry)입니다. 대수기하학 개론은 Take-home exam으로 시험 문제를 일주일간 푸는 시험이고, 복소다양체는 기말 과제로 각자가 정한 주제로 발표하는 시험입니다.

대수기하학 개론에 대해서는 별로 할 말이 없습니다. 재미있긴 한 과목이지만 요즘 다루는 툴이나 이론들이 그렇게 끌리지는 않아서요.. 그래도 Grobner basis는 참 재미있는 툴인 것 같고, 대수기하 과목이 열리면 듣긴 할겁니다 ㅎㅎ

복소다양체의 기말 과제로는 Kenkichi Iwasawa의 “Sheaves for Algebraic Number Fields”를 읽고 발표하기로 결정했는데.. 좀 웃깁니다. 복소다양체보다 정수론을 매일 공부하고 있습니다. 정확하게는 Weiss의 Algebraic Number Theory 책을 읽고 있는데, 지난번의 포스팅도 그 책에서 발견하고 올린겁니다 ㅎㅎ.
재미는 있습니다만 결국 복소다양체에 대해서는 하나도 배우지 못할 것 같습니다.. 수업도 많이 빠졌고.. TeX파일로 정리해서 파일을 제출하고 발표하는 과제이기에 그 파일을 여기 올리거나, 혹은 전후 문제들과 내용들을 간략하게 정리해서 이 블로그에 올릴 수도 있을 것 같습니다.

시험이 끝나고는 Quantum Computation에 대해 공부해보려고 합니다.
일전에 P. Shor의 Quantum polytime에 Factorization과 Discrete Logarithm을 푸는 논문을 예전에 읽은 적이 있는데, 그 때는 대충 이상한 점들도 넘어갔었습니다. 최근에 이것저것 찾아보면서 다시 읽었더니 빈 곳들이 메꿔지는 느낌입니다. 정말로 양자컴퓨터가 실현화 가능할지는 의문이긴 하지만, 그래도 꽤나 재미있는 주제라 약간은 공부해보려 합니다.

-끝-