심심하지만 여유롭진 않아서 짧게 쓸거임. 이전에 쓴 [암호학적으로 어려운게 뭔지]나 [암호의 안전성]에 관해 쓴글도 심심하면 읽어줘

물리적인 이야기는 잘 모르기도 하고, 별로 관심도 없으니 실제 implementation은 얘기 안하고, 엄청 대충 말할거임.


아래글에서 난수생성 원리를 묻는데, 완전한 난수는 컴터로 만들기 어려움. 좀 철학적인 설명이기도 한데 고전적인 세계는 거의 결정론적으로 해결할수도 있잖아?


그러니까 1) 시간측정하고 온도재고 뭐 그런식으로 난수에 쓰는 짧은 seed라는걸 만들고, 

2) 이를 이용해서 더 긴 난수를 만드는 암호학적 유사난수생성기 (Cryptographically secure pseudorandom number generator, CSPRNG or PRNG)를 이용해서 난수를 만듬.

이거에 관해서는 나중에 더 심심하면 쓸게


PRNG에도 안전성의 정의가 다 있는데, 문제는 이런것들이 다 seed가 uniform random이고, 공격자가 얘를 모를때 = 예측하지 못할때 사용 가능함

근데 예를들어 seed를 시간을 재서 한다고 할때, 우리 컴퓨터가 언제 시간재는함수에 접근하는지를 측정하면 대충 seed의 근사값정도는 예측할수있을거아냐?

이런게 안전성에 굉장히 문제가 됨. 그래서 예측불가능한 uniform random을 만드는게 암호학적으로 중요한 태스크로 생각하고있음.




여기서 양자가 들어온다. 양자에 대해 자세히 설명할 생각은 없고, 컴퓨팅 관점에서 양자데이터는 아주아주 대충 설명해서

(pi,ai)의 쌍으로 이루어져있고, 계산은 pi와 ai가 변하면서 진행됨.

그리고 마지막에 측정(measurement)라는 행위를 해서 결과를 보는데, 이걸 하면 pi의 확률로 ai를 보게된다.


언뜻보면 이게 그냥 확률으로 주어지는 쌍 (pi,ai)랑 다를게 뭔가 싶을텐데, 

보통 우리가 확률적으로 생각하는 대상은 사실은 처음 pi의 확률로 ai가 정해지는 결정론적 대상으로 그거가지고 어쩌구저쩌구 계산을 진행하는건데, 이걸 처음 대상을 확률적으로 본거라고 해석할수 있음.

근데 양자데이터는 그냥 주어진 대상 자체가 확률적인거고, 우리가 측정을 해야만 결정되는거임. 그니까 양자 자체의 본질이 랜덤이랑 관계가 있는거지.


그러면 이거가지고 난수를 어떻게 만드냐? 양자의 가장 기본적인 오퍼레이션이 다음과 같은거임

(1,0) -> (1/2,0) + (1/2,1)

그니까 하나의 0을 이용해서 측정하면 0,1이 1/2확률로 나오는 애를 만들수있는거지.


그러면 n비트 난수를 만들기 위해서는? 위에 과정을 n번 반복하면 되는거지 뭐. 

우리가 아는 물리이해를 바탕으로는 이 결과는 진짜로 uniform random이고, 측정하기 전까지 예측 불가능함.

이걸 요즘에는 폰에 넣는다 뭐라 하면서 갤럭시 퀀텀이 나올거라고 하던데... 자세히는 모름





======================================================================

근데 사실 위에건 양자 조금만 아는사람한테는 당연한 얘기고, 요즘 이론적 얘기에 조금만 더 썰 풀어보자. 완전히 썰임.


Q. 내가 만든 난수가 난수인걸 남한테 증명할수 있을까?

이게 생각보다 골때리는 문제임. 예를들어 내가 그냥 1 1 1 1 1 1 을 보내면 응 아무튼 내가 주사위 던져보니까 전부 1이야~ 라고 주장하면 어케 믿냐?


고전적인 방법으론 쉽지 않음. (Verifiable random function이라는게 있긴 함. 근데 얘는 verify하지 못하는애한테 random으로 보이는 함수고, verify가 가능한 경우에는 아무것도 보장하지 않음. 그리고 다른문제들도 이것저것 있고...)

근데 양자적으로는 이게 된단말야? 대충 방식을 설명하자면, Bell inequality라는게 있음. 이게 뭘 말하냐면,


A,B,E가 실험을 하는데 A랑 B는 interaction이없고, E가 A,B와 interaction을 하면서 A,B가 E에게 원하는 결과를 내는 실험임. 이게 실험을 잘 정하면 

-A,B가 고전적인 일만 하면 원하는 결과를 낼 확률이 p

-A,B가 양자데이터를 미리 공유하고있었으면 원하는 결과를 낼 확률이 p보다 높아질수 있는거임. 어떤 특수한 전략 T로는 최대 q까지.


근데 E가 이걸 요리조리 잘 이용하면, 저 실험을 이용해서 성공확률이 높아질수록 저 양자적 성질을 이용하는, 어떤 랜덤을 만드는 프로토콜을 만들수 있는거임.

그러니까, E입장에서는 A,B가 뭘 했던간에 얻는게 정말로 랜덤인 프로토콜을 만들수 있는거지.

심지어 E는 양자적 일을 할필요도 없음! 

그러니까 고전적 컴퓨터는 두 양자컴퓨터를 대상으로 이런저런 실험을 통해서 믿을수있는 예측 불가능한 uniform random을 얻어올수 있는거임.


사실 다른친구가 댓글에서 레퍼한 논문은 그냥 랜덤을 만드는 실험이 아니라 이렇게 믿을수있는 예측불가능한 랜덤을 만드는 실험임.

당연히 이건 그냥 랜덤을 만드는거 (QRNG)보다 훨씬 어려운 태스크이고, QRNG자체는 더 현실적으로 생각하고있는거같음.



근데 저 프로토콜이 (아무것도 설명 안했지만) 좀 이상함. 왜 난수를 만드는데 양자컴퓨터가 두대나 필요하지?

이게 놀랍게도 엄청 오랫동안 open이였음. 신기하게 2017-2018년에 두 연구팀에게서 각각 풀림.

신기한게, 위 두 양자컴퓨터로 하는 프로토콜은 unconditionally 성립하는거임. 그러니까 그냥 우리가 받아들이는 물리법칙이 참이면 안전한거지.

근데 2017-2018에 발견한 결과들은 둘 다 암호학적인 툴을 쓴다. 좀 더 설명하기 쉬운 결과를 말하면, 다음 trapdoor function을 이용하는거임.


0) 우리는 injective function f_k, g_k를 생각할거임 (k는 키) k는 공개키고, k를 알면 두 함수는 계산하기 쉬움.

1) td라는 "trapdoor"가 있어서, f_k(x1), g_k(x2)에서 x1,x2를 계산하는건 쉬움

2) 얘네는 f_k(x1)=g_k(x2)를 만족하는 x1,x2의 쌍을 찾기 어려운 함수임 (td 없이는). 근데 각 x1, x2에 대해서는 fk(x1)=gk(x2)를 만족하는 x2,x1이 무조건 존재함.


양자계산에 약간 익숙하다고 가정하고.... 양자컴퓨터는 다음과 같이 고전적으로 봤을때는 이상한 연산을 할수있음.

1. 양자컴퓨터가 uniform random \sum |u>를 만든다

2. F(0,x)=f_k(x), F(1,x)=g_k(x)라고 하고, \sum |u,F(u)>를 계산함.

3. 두번째 register를 측정(measure)함. 그러면 우리는 |0,x1,y>+|1,x2,y>를 얻는다. (amplitude를 생략하면)


이게 엄청 이상함. 저기서 구한 x1,x2는 위에 2)에서 찾기 어렵다고 한 애는 맞는데, 양자컴퓨터가 x1,x2를 둘 다 볼수는 없지만 뭔가 중첩된 상태로 얻었잖아?

이게 고전적으로는 안되는거고.. 이게 뭔가 고전적으로는 안되는데 양자적으로는 되는거고, 이걸 이용해서 프로토콜을 만드는거임.

저자들은 이게 proof of quantumness (혹은 quantum supremacy)의 새로운 이그잼플이 될 수 있다고 주장했음. 

다만 실험적으로 증명하기에는 파라미터가 너무 커서 현실적이진 않은데, 

이건 (나중에 쓸지 모르겠지만) 지금 하고 있는 quantum supremacy 실험과는 다르게 verify가 쉽다는 장점을 가지지.




너무 대충쓴거같은데 지쳐서 그만써야겠다. 혹시 궁금한거 있으면 대답해줄게