2020 5월 – Pseudorandom Things

삼성의 Galaxy A Quantum, QRNG, and more

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

삼성에서 Galaxy A Quantum이라는 폰이 나온다는 소식. 사실 한국에서 이런 소식이 돈건 한참됐고, 이제 외신까지 뜨고있나보다.

앞선 글에서 말했듯 구글에서 조그마한 양자컴퓨터 만드는데 골골대는데 삼성이 외계인을 고문해서 양자컴퓨터를 폰에 넣었다! 이런건 아니고, 그냥 Galaxy A의 난수생성하는 부분을 QRNG (Quantum random number generator)로 대체했다는 말이다.

이 글에서는 1. 왜 QRNG가 유용한 기술인지, 그리고 더 나아가 2. 양자컴퓨터가 난수에 대한 어떤일을 할 수 있는지 살짝 언급해보고자 한다. 얼마전에 DC 수잘갤에 쓴 글을 다듬어서 씀.

계속 읽기 →

양자 스도쿠, 라틴 방진

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

다들 알다시피 스도쿠는 9*9 격자에서 1,2,…,9를 각 행,렬 그리고 작은 3*3 격자 9개에 모두 한번씩만 등장하게 적는 퍼즐이다. 심심할때 아래 처럼 굉장히 이상한… 스도쿠를 풀어보는데 정말 만든사람도 변태다 싶다 -_-

Buy 3D Sudoku logic puzzles from Any Puzzle Media — 며칠 걸려 겨우 풀었던 스도쿠…

그리고 라틴 방진 (Latin square)는 스도쿠에서 3*3에 대한 조건을 뺀 훨씬 간단한 형태. 근데 얘네의 양자버젼이 존재한다고 한다! 양자 라틴방진은 2015년에 제안되었는데, 신기하게도 몇가지 응용도 있다 -_-!! 하지만 무슨말인지 잘 모르겠으니 패스. 그냥 세팅은 간단하다. 9*9격자의 각 점에 1,…,9의 숫자대신 $\mathbb C^9$ 벡터들을 두되, 각 행/열 (스도쿠라면 3*3 사각형에도)의 벡터들이 orthonormal basis가 되도록 하는것.

그러니까 격자들에 벡터를 두고, 아래 묶인집합들이 항상 ONB가 되도록 하는것.

SudoQ — a quantum variant of the popular game 에서 발췌

이번에 올라온 논문은 스도쿠의 양자버젼은 SudoQ인데, 이런저런 재밌는 관찰이나 추측들이 제시된다. 스도쿠가 non-trivial SAT의 한 예시인데 NP-complete라서 흥미롭다네.. 몰랐던 사실 -_- 이전에 Sinkhorn이라는 방식의 iterative 알고리즘을 통해 스도쿠를 풀수있다고도 한다. 이것도 전혀 몰랐군.. 이런 방식의 알고리즘의 양자버젼을 만들고, 얘의 수렴성도 확인한것같다. (증명이 자명한건지 딱히 안적혀있다..)

이런저런 추측은 다음과 같다.

고전적으로 해가 없는 스도쿠는 SudoQ에서도 해가 없다.
고전적으로 해가 유일한 스도쿠는 SudoQ에서도 해가 그거뿐이다.

하지만 아쉽게도 정말 게임으로 즐길수는 없을거같다. 대신 sudoku code라는 error correction code의 양자버젼으로 쓸수 있을거라는 대안만 제시하고 끝.

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만드는 방식이 지금까지 알려진 형태인 이유들 같은게 그나마 좀 캐쥬얼한 내용인것같은데, 그거도 여기 짧게 설명하긴 쉽지 않아보이고 재미도 없을듯 -_-.

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