Pseudorandom Things

양자컴퓨터도 XEB Fidelity를 더 잘 속일수는 없다

2020년 8월 21일2020년 8월 23일Hhan댓글 한 개

작년 구글의 양자컴퓨터 실험과 그 이후의 고전 시뮬레이션 발전에 대해 지난번 글에서 소개한 바 있다. 다음과 같이 정의되는 XEB Fidelity를 다시 불러오자.

$\displaystyle {F}_C(p):=2^n \sum_{x\in\{0,1\}^n} p(x)q_C(x) -1$

여기서 C는 타겟이 되는 random circuit이고, $p$ 는 테스트하고자하는 확률 분포, $q_C$ 는 C의 결과로 나오는 확률 분포. 이 XEB값은 $p$ 가 유니폼 랜덤이면 Fidelity가 0이 되고, $p=q_C$ 가 되면 (C의 structure때문에) 1이 된다고 한다.

이러한 설명 하에 지난번까지의 양자우월성 실험에 대한 결론은 다음과 같다.

XEB Fidelity는 구글 실험에서 0.00224를 달성한다.
강력한 가정하에, C의 depth d를 키우면 고전컴퓨터는 XEB Fidelity를 (구글 실험보다도) 크게 만들 수 없다.
(구글 실험과 겹치지 않는) 특정한 파라미터에서는 고전컴퓨터가 XEB Fidelity를 1에 가깝게 만들 수는 있다.

그치만 고전컴퓨터는 depth가 클 때 XEB Fidelity가 거의 항상 0에 가깝고, 양자컴퓨터로 구글의 실험을 하면 노이즈가 줄어들수록 XEB Fidelity가 1에 가까워지니 이걸로 “양자우월성”을 증명하겠다는 것이 구글의 전략이였다.

근데 여기서 잠깐 XEB Fidelity의 정의를 살펴보면, 이 값은 굳이 0~1 사이의 값이 될 필요는 없다. 괴상하게 p를 잘 잡으면 1보다 더 커질 수 있는 값이다!

그렇다면 여기서 질문: 양자컴퓨터를 이용하면 XEB Fidelity를 어떻게 잘 “속여서(Fool)” 1보다 더 크게 만들 수 있지 않을까? 예를들어 100이나 d²같은 값으로? 이렇게 하면 XEB Fidelity를 크게 키우는 것에 집중했을 때 (마지막 결과의) 고전컴퓨터를 이용한 시뮬레이션보다 훨씬 큰, 더 강력한 결과가 되지 않을까?

(안타깝게도) 오늘 나온 논문의 결과에 따르면, 그게 안될 가능성이 높다고 한다.

조금 자세하게는 C는 임의의 회로, 즉 uniform random unitary map으로 잡으면 임의의 ε>0에 대해 XEB Fidelity를 1+ε보다 크게 만드는 실험을 하려면

$\displaystyle\frac{2^{n/4}}{poly (n)}$

보다 큰 개수의 샘플이 필요하다고 한다. 그리고 샘플이 $2^{n/3}$ 개 정도 있으면 실제로 XEB Fidelity를 2에 가까운 정도로 크게 만들수 있다고.

그러니까, 신기하게도 구글의 실험에서 한 단순한 실험이 XEB Fidelity를 키우는데에는 어느정도 최적의 알고리즘 중 하나라는것!

다만 해석에는 여지가 약간 있는데, 논문에서 C를 depth가 작은 임의의 회로가 아닌 uniform random unitary map으로 잡았다. 이건 사실 효율적으로는 구현이 불가능한 회로이고, 이론적으로 뭔가를 증명하기가 훨씬 좋은 이상적인 대상이다. 뭐 여튼 구글의 단순한 실험이 XEB Fidelity 값을 최대로 만드는 방식일 것이라는 강력한 근거는 된다 ㅋ.

난독화 이야기 (1) 가상 블랙박스 난독화는 불가능하다

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

한동안 연구 주제로 잡았던 것 중 프로그램을 “읽기 어렵게 만드는” 난독화라는 기술이 있다. 프로그램 난독화 기술은 여러가지 이유로 2013년 정도부터 (이론적) 암호학에서 현재 가장 중요한 주제로 떠올랐다.

특히 구별불가능성 난독화(Indistinguishability Obfuscation)의 존재성이 그 핵심 문제인데, 이를 가장 활발히 풀던 연구자들이 해당 기술이 가능하다고 주장하는 논문을 최근 포스팅했다.

따라서 이를 기념(?)하기 위해 이 방향의 연구의 큰 이야기들을 몇 개의 글로 정리해보고자 한다. 다만 의욕이 항상 없어 다음 이야기가 언제 나올지는 의문 ㅋ

이번 글에서는 프로그램 난독화의 초창기 결과인 2001년의 보아즈 바락(Boaz Barak)등이 증명한 가상 블랙박스 난독화(Virtual Black-box Obfuscation)이 불가능하다는 논문에 대한 이야기를 하고자 한다. 증명이 아주 간단하다!

계속 읽기 →

얼굴 인식 기술을 속일 수 있을까?

2020년 8월 15일2020년 8월 15일Hhan댓글 2개

일전에 얼굴인식 기술이 미국에서, 특히 경찰이 그 완성되지 않은 기술을 사용하는데에 대해 우려가 있다는 글을 포스팅 한 적이 있다. 그 뿐만 아니라 얼굴 인식 기술이 예측하지 못한 방식으로 개인을 추적하고, 그 추적한 정보를 이용해 스토킹을 하거나 개인과 협상하는데에 다양하게 악의적으로 이용할 수 있는 등의 위험성이 크다. 심지어 올해 초의 뉴욕타임즈 글에 따르면 Clearview라는 스타트업은 이미 30조개 이상의 사진을 수집하고 이를 이용해 기술을 개발하고 있다고 한다.

이에 따라 자연스럽게 떠오르는 질문은 얼굴 인식 기술을 어떻게든 무효화 시킬 수 있겠냐는 것. 시카고 대학의 연구자들의 대답은 다음과 같다.

현재의 얼굴 인식 기술은 꽤 강하게 무효화할 수 있다!

USENIX security 2020 학회에 발표된 논문의 저자이 개발한 Fawkes라는 기술을 이용하면 우리가 보는 이미지를 (저자들의 표현에 따르면) “클로킹”시킬 수 있다고 한다. 사람에게는 비슷하지만 현재 얼굴 인식 기술들에게는 꽤나 다르게 보이는 새로운 이미지를 만들 수 있다는 것. 이 클로킹 기술은 심지어 저자들의 소개 페이지에서 다운로드해서 이용 가능하다!

논문에 따르면 Fawkes의 클로킹은 다음과 같은 정도로 얼굴 인식 기술의 무효화를 달성한다.

최신 얼굴 인식 기술을 제공하는 Microsoft Azure, Amazon Rekognition, Face++등의 기술에게 클로킹된 이미지를 학습 데이터로 제공한 경우, 그 학습 모델은 새로운 클로킹 되지 않은 이미지를 잘못 분류할 가능성이 거의 100%에 달한다. 여기서는 Fawkes가 해당 모델의 Feature extractor (FE)를 알고, 정확히 같은 FE를 쓴다고 가정한듯.
얼굴 인식 기술 Fawkes가 알지 못하는 FE를 쓰는 경우나, 모델이 그냥 이미지 자체에서 얼굴인식을 해내는 경우에도 95%이상의 확률로 클로킹되지 않은 이미지를 잘못 분류했다고 한다.
얼굴 인식 기술이 클로킹 되지 않은 이미지도 학습 데이터로 쓰는 경우, 학습데이터중 클로킹된 이미지가 많아지면 많아질수록 얼굴인식이 실패할 확률이 높아졌다고 한다. 특히 클로킹된 이미지와 되지 않은 이미지의 비율이 1:1인 경우정도부터 95%정도의 확률로 잘못 분류하기 시작했다고.

굉장히 흥미롭다! 다만 얼굴 인식 기술이 항상 불가능함을 증명할수는 없는듯. 어찌보면 당연한게, 사람은 구별 가능해야할테니… 자세한 소개는 저자들의 유튜브 영상에잘 설명되어 있다.

Authors’ presentation

그렇다면 여기서 몇 가지 질문이 떠오른다.

특정한 Class의 얼굴인식 기술에 대해 증명 가능한 무효화 기술은 없을까? 예를 들어, 푸리에 변환을 이용한다거나, 특정한 Feature만 쓴다거나.. 이런 것은 암호학적 기술과 결합하면 꽤나 그럴듯한 시나리오처럼 보이는데, 글쎄 -_-…머신러닝을 잘 모르니..
실제 Fawkes된 이미지를 보면 원래 이미지와 약간 달라 보이는데, 조금 궁금한것은 원래 얼굴 인식 기술이 촬영/보정 어플을 적용한 경우에도 잘 작동할까? 그렇다면 촬영/보정 어플을 적용하고 Fawkes를 쓰면 안전성/보정 측면 모두에서 만족할만한 결과가 나올까?

암호학 단신

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

1. 유한체 $\mathbb F_{2^{30750}}$ 위에서의 이산로그가 풀렸다는 소식. 기존의 유한체위의 이산로그 최고기록은 2014년의 $\mathbb F_{2^{9234}}$ 에서의 문제였고, NMBTHRY mailing list 항목에서 확인할 수 있다. 기존 기록은 45 core-year가 필요했고, 이번 기록은 2900 core-year가 들었다고 한다. 지난번 정수위에서의 소인수분해/이산로그 글에서 소개했던 것도 있고, 이런 실험들을 하는 여러 그룹들이 있는가보다.

2. 7월 7일 새로나온 논문에 따르면 소인수분해 등을 푸는데 사용되는 NFS (Number field sieve)의 점근적 시간복잡도가 약간 현실과 맞지 않는다고 한다. 좀 자세히 말하면, NFS의 복잡도는 다음과 같다.

$\exp\left(\sqrt[3]{\frac{64}{9}} (\log N)^{1/3}(\log \log N)^{2/3} (1+o(1))\right)$

여기서 주로 $o(1)$ 항을 0으로 두고 최적화를 진행하는데, 이 $o(1)$ 항이 0에 가까워지려면 $N>\exp(\exp(25))$정도는 되어야 하고, 따라서 지금까지 이를 이용한 최적화가 현실적으로 다양하게 약간 잘못되었을 수 있다고. 이런걸 고려하면 소인수분해를 약간은 더 빨리할 수 있을듯.

3. 암호학적 증명을 컴퓨터로 확인할 수 있다는 소식. 특히 IND-CPA 공개키 암호를 IND-CCA후지사키-오카모토 변환의 대양자 안전성 증명을 컴퓨터로 확인했다는 논문.

논문에 따르면 암호학계의 증명이 틀리는 것은 꽤나 흔한 일이라고 한다. 예를 들어 일전에 소개한 OCB2의 증명이 틀렸다는 소식이나, 더 이전에는 RSA-OAEP라는 산업에서도 굉장히 잘 쓰이는 RSA의 변형의 안전성이 틀렸고, 여러번 수정되었다는 사실 (링크된 위키페이지에도 잘 소개되어있다.), 그리고 난수함수와 난수행렬이 구별이 어렵다는 유명한 PRF/PRP switching lemma의 교과서에도 소개되던 증명이 틀렸다는 사실 등. 그래서 Code-based game-playing proof라는걸 로가웨이와 벨라르가 소개하며 안전성 증명의 컴퓨터 검증의 방향을 제시했고, 그 이후 여러가지 논문이 정말 있었나보다. (이 논문 등) 이번에는 그런 방향을 양자안전성 증명까지 확장한듯. 증명 검증 툴은 Coq정도만 알고있었는데, 생각보다 다양한 것이 있군.

하드웨어와 알고리즘의 발전 중 무엇이 빠를까?

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

컴퓨터 과학과 공학은 최근 수십년간 엄청난 주목을 받고, 특히 문제를 푸는 알고리즘과 그를 실행하는 하드웨어에서 큰 발전을 이루어내고 있다.

알고리즘쪽은 컴퓨터가 풀 수 있는 “효율적인” 문제가 무엇인지에 대답하기 위해 발전하고, 이 블로그의 글중 많은 부분에서 여러 발전을 소개하고있다.

하드웨어 부분에서는 최근까지도 상수년에 2배의 속도가 빨라진다는 무어의 법칙에 거의 따라가며 발전하고 있고, 이 발전은 많은 뉴스기사를 보거나, 당장 우리가 쓰는 컴퓨터를 실행해 봐도 실감할 수 있다.

그렇다면 여기서 질문: 최근의 하드웨어와 알고리즘은 무엇이 더 많이 발전했을까?

물론 일반적으로 두 발전을 비교하는 것은 불가능하다. 특히, 하드웨어는 일반적인 발전정도를 단위연산별로 계측하여 어느정도는 측정할 수 있지만, 알고리즘의 경우에는 어떤 문제를 푸냐에 따라 그 발전정도가 천차만별이다. 심지어 몇몇 문제의 경우는 특수한 경우에 훨씬 잘 풀기도 하고. 지난 글에서 슬쩍 언급했듯이 몇몇 문제는 수십년간 발전이 거의 없는 정도이다.

대신 얼마전 유럽의 연구자들이 Arxiv에 구체적인 문제를 대상으로 비교방식을 제시하는 논문을 포스팅했다. 논문에서는 구체적으로 주어진 식을 만족하는 해가 존재하냐고 묻는 SAT문제를 대상으로 비교를 진행했다. 찾아보니 SAT Competition이 계속 진행되고 있을정도로 활발하게 연구되는 분야이니, 꽤나 괜찮은 대상인듯.

논문의 결과를 간단히 요약하자면 다음과 같다.

여기서 각 항목은 200개의 SAT 인스턴스 중 해결한 인스턴스의 개수를 말하고, 가로축은 서로 다른 SAT-solver 알고리즘들을 뜻하고, 세로축은 1999년과 2019년의 하드웨어, 정확하게는 다음 세팅을 썼다고 한다.

1999년: Pentium III processor (467MHz) + 1.5GB RAM
2019년: Intel Xeon Silver 4112 CPU (2.60GHz) + 128GB RAM

저자들은 Team SW, Team HW를 나누어 각자 구현했다고 한다. 결과에 따르면 다음과 같이 말할수 있다.

SAT문제에 관해서는 알고리즘의 발전이 하드웨어의 발전보다 약간 더 빠르다!

몇가지 관찰이나 세팅은 아래에 정리해둔다.

각 결과들은 200개의 인스턴스중 900초안에 풀리는 인스턴스의 개수를 센 것이다.
인스턴스들은 알려진 벤치마크들로 여러가지 만들어진 것으로, 테스트를 위한 적절한 크기/방법을 골랐다고 한다. 아마 Random SAT등으로 고르면 일부 세팅은 거의 전부 푸는데 다른 세팅은 전혀 못푸는 그런 상황이 벌어졌을듯. 특히 set-asp-gauss라는 벤치마크가 가장 적절하여 이용했다고 한다.
2019년에 가장 좋은 알고리즘으로 알려진 Maple SAT solver가 1999년 하드웨어를 쓴 경우 다른 알고리즘보다 약간 더 못푸는 경우가 발생했다. 저자들도 정확한 이유를 알지는 못하고, 아마 좋은 알고리즘에서 사용한 특정한 자료구조가 현대 하드웨어에 훨씬 적합한게 아닐까.. 같은 추측을 한다.
사실 SAT 알고리즘은 1990년대 후반 등장한 CDCL (Conflict-Driven Clause Learning)이라는 방식을 아직 기반으로 사용하고 있다고 한다. 물론 다양한 발전이 있긴하다! 심지어 CDCL도 DPLL (Davis–Putnam–Logemann–Loveland)이라고 하는 1960년대 알고리즘을 기반으로 발전했다고 한다. 역시 알고리즘의 큰 줄기는 1960년대에 다 나온듯 ㅋㅋㅋ

과거의 알고리즘에 비해 얼마나 좋아졌는지 뭔가 직관적으로 볼 수 있는 결과가 있으면 좋을텐데 좀 아쉽다 ㅋㅋ 여튼 결론은 알고리즘의 연구가 하드웨어연구만큼 중요하다는 것으로 논문은 끝.

깔끔한 문제는 깔끔한 복잡도를 가질까?

2020년 8월 6일2020년 10월 26일Hhan댓글 남기기

이론적 컴퓨터과학의 많은 문제들을 보면, 최근 수십년간 이 학문이 엄청나게 발전했음에도 불구하고 대부분의 문제에서 최적인 알고리즘은 아주 오래전 (수십년 전, 길게는 거의 60년 정도까지!) 발견된 쉬운 알고리즘인 경우가 많다. 좀 발전했다 쳐봤자, 거기에서 조금 나아지는 정도? 구체적인 예들로는 다음과 같은 것들이 있다. O*(X)는 polylogX이나 다른 파라미터들에 대한 비슷한 팩터를 무시한 복잡도. 덧셈, 곱셈등의 복잡도는 대부분의 경우 O(1)로 생각한다.

n개의 점으로 이루어진 그래프에서 모든 쌍들 사이의 최단거리(All pair shortest path)를 모두 구하는 알고리즘은 (가장 일반적인 경우, 즉 대부분의 edge가 있는 경우) 1960년대 Floyd-Warshall 알고리즘의 복잡도인 점의 개수 n에 대해 O(n³)에서 수년 전 Ryan Williams가 발견한 알고리즘이 살짝 나아진 O(n³/exp( $\sqrt {\log n}$ ))정도를 달성하는데에 그친다.
길이가 n인 두 수열에서 같은 부분수열을 찾는 문제(Longest common subsequence, LCS)나 한 주어진 수열에서 특정한 규칙을 따라 다른 주어진 수열로 변화시키는데 최소 몇번의 변환을 해야하는지에 대한 문제(Edit distance)역시 간단한 동적계획법 알고리즘으로 O(n²)의 알고리즘에서 거의 개선되지 않았다. 비슷하게 1980년의 O(n²/log²n)정도가 지금까지 찾은 최고의 알고리즘.
n개의 수의 집합에서 a+b+c=0를 만족하는 쌍 (a,b,c)를 찾는 문제인 3-SUM문제는 아주 간단한 알고리즘인 정렬 후 체크방식인 O(n²)알고리즘보다 나은 방식은 Baran등이 제안한 알고리즘으로 기껏해야 O((nloglogn/logn)²)수준의 굉장히 미묘한 발전이 끝이다.
지난 글에서 말했듯이 외판원 문제(Traveling salesman problem)역시 1960년대 발견된 헬드-카프 알고리즘의 복잡도인 O*(2ⁿ)에서 거의 발전하지 않았다.
또, NP-hard문제의 대명사인 SAT문제를 일반적인 경우에 푸는 최고의 알고리즘도 역시 O*(2ⁿ)수준에 그친다. 물론 SAT문제의 형태를 제한한 3-SAT같은 경우에는 O*((4/3)ⁿ)정도의 알고리즘도 있다.

특히 마지막 두 문제는 NP-hard로 잘 알려진 문제들. 이 문제들을 가장 잘 푸는 방식은 이게 최선일까?

많은 컴퓨터과학자들은 사람들이 좋은 알고리즘을 개발하는 것을 문제의 어려움을 증명하는 것보다 훨씬 잘한다고 생각한다. 즉, 우리가 아는 최선의 알고리즘이 진짜 최선에서 그렇게 벗어나지 않았을 것이라고 믿는다!

이런 생각은 다음과 같은 가설로 구체화된다.

Exponential time hypothesis (ETH)는 n개의 변수에 대한 3-SAT 문제가 어떤 상수 c>1에 대해 O*(cⁿ)의 복잡도를 갖는 알고리즘이 최적이라는 가설이다. 좀 더 강하게, k-SAT의 최적의 복잡도 O*(c_kⁿ)를 만족하는 c_k를 생각하면 $\lim_{k\rightarrow \infty} c_k = 2$ 가 성립할것이라고 말하는 Strong exponential time hypothesis (SETH)도 있다. 최근에는 이것의 양자버젼인 QSETH도 제안되었다. (사실 다들 생각은 하고 있었고, 이걸로 의미있는 결과를 처음으로 얻어냈다.)
비슷하게 3-SUM hypothesis는 임의의 ε>0에 대해 3-SUM을 푸는 O*(n^2-ε) 알고리즘이 없을것이라는 가설이다.

많은 컴퓨터과학자와 나는 SETH가 참이라고 믿는다. 하지만 이를 증명하는것은… 글쎄다. 아마 이러한 관점에서 많은 컴퓨터과학자들이 두 n×n 행렬의 곱이 O*(n²)에 될것이라고 믿는듯 하다. 나는 이것은 아직 그렇게까지 믿지 않는다 -_-ㅋ 이 스택익스체인지에 관련 논의가 있다. 딱히 강력한 근거는 없는듯. 여튼, 이러한 관점에서 컴퓨터과학자들은

깔끔하게 정의된 문제는 깔끔한 복잡도를 갖는다

라고 믿는다. 물론 나도 믿는다 ㅋ

하지만: 지난 TSP에 관한 글에서 언급했듯 네더로프가 증명한 바에 따르면 행렬곱이 O*(n²)복잡도를 달성한다면 이분그래프에 대한 외판원 문제가 O*(1.9999ⁿ)에 풀린다고 한다!

그렇다면 가능성은 다음과 같다.

이분그래프에 대한 TSP는 “깔끔한 문제”가 아니다.
행렬곱은 “깔끔한 문제”가 아니다.
이분그래프에 대한 TSP는 사실 다른 깔끔한 복잡도(e.g. O*((4/3)ⁿ))를 갖는다.
행렬곱이 다른 깔끔한 복잡도를 갖는다.

나는 개인적으로 첫번째 가능성을 지지한다 ㅋㅋㅋ

조금 다른 관점에서, 답을 approximate하게 구하는 것은 어떨까? 예를 들어 TSP의 최적값에 가까운 해를 구하는 알고리즘이나, 선형시간에 LCS에 가까운 해를 찾는것은? 그 가까운의 범위도 깔끔한 값을 가질까?

오랫동안 사람들은 그렇게 믿어온듯 하다. 예를들어 metric TSP, 즉 외판원 문제에서 변들의 길이가 삼각부등식을 만족하는 경우에는 1.5-approximation 다항식 시간 알고리즘이 Christofides–Serdyukov에 의해 알려져 있었고, 이게 최적으로 믿고 있었다. 다음 블로그 글에 한글로도 잘 정리되어 있다.

그리고 LCS는 $\sqrt{n}$ -approximation 선형 알고리즘이 최적이고, 심지어 $n^t$ -approximation 근사는 O*(n^2-2t)에 되었다고 한다.

하지만: 최근 arixv에 올라온 논문에 따르면 metric TSP문제가 다항식시간에 1.49…9-approximation이 가능하다고 한다. 여기서 9는 36개 이하로 있다고 한다 -_- 저자들은 이 결과가 어쩌면 4/3-approximation일수도 있다고 생각하는듯 하다.

그리고, SODA2019에 발표된 결과에 따르면 LCS에 대한 O(n^0.497956)-approximation을 선형시간에 할 수 있다고 한다.

이런, 그렇다면 근사할 수 있는 정도는 깔끔하지 않은것일까? 이건 전혀 모르겠다 -_- 나는 참이라고 믿는데, 최근의 결과들은 그렇지 않다고 주장한다. metric TSP정도는 꽤나 깔끔한 문제처럼 느껴지는데……

실수는 “현실적인 수”일까?

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

주의: 이 글은 꽤나 철학적인 글이고, 나는 이 글에서 다루는 여러 내용에 대해 정확히 알지 못한다.

우리가 현실에서 보는 구체적 수량들, 예를 들어 물질의 질량, 속도, 우리의 키나 몸무게 등 기타 등등이 전부 실수로 이루어져있다. 이는 자연수/정수로, “수량”을 생각하던 초창기 인류의 이해를 넘어 현실을 구체화하는 하나의 방식으로 인류가 받아들인 방식이다.

실수라는게 가끔 생각해보면 조금은 이상하기도 하다. “우리의 키”에 해당하는 값이 어떤 정보를 담을수 있을까? 굉장히 철학적인 질문이다. 이게 무슨말이냐면, 우리의 키는 어떤 자릿수 정도부터는 “임의의 실수”에 가까울거고, 이 수치는 무한히 많은 정보를 담는다. 그런데 아론손의 [큰 숫자들]에도 슬쩍 언급했듯이, 최소한 우리가 볼 수 있는 우주는 유한한 자릿수에 결정되는듯 하다. 어떻게 이런 일이 벌어질 수 있을까?

사실 이런 비슷한 고민은 여러 사람들이 고민을 하곤 하는듯하다. 친구의 페이스북에서 본 적도 있고, 딱히 기억은 안나지만 다른데서도 본 적이 있는듯.

이 질문에 대해 니콜라스 지상(Nicolas Gisin)이라는 스위스의 물리학자가 꽤나 재미있는 대답을 내 놓았다. 바로 (과학철학 저널에 게재된) 이 논문에서 제시한 그의 생각은, 우리가 생각하는 실수는 현실적인 수가 아니고, 현실의 수는 유한한 정보 + “랜덤정보”로 표현된다는 것. 그리고 그 랜덤정보가 시간이 지남에 따라 점점 결정되어 나가는 것이라고 한다. 지상의 다른 논문 (사설에 가까운듯)에 따르면 이러한관점은 직관주의 수학(Intuitionistic Mathematics)와 맞닿아 있다고 한다.

직관주의 수학은 브라우어 고정점 정리(Brouwer fixed point theorem)과 여타 다른 브라우어(Luitzen Egbertus Brouwer)가 주장했다고 한다. 여담인데 이 글을 검색하며 브라우어의 결과를 이것저것 봤는데, Simplicial approximation theorem이나 Tietze extension theorem, Hairy ball theorem등에 대한 기여로 유명한 모양이다. 엄청난 분이셨군 -_-…

여튼 브라우어와 힐베르트가 한 논쟁이 꽤나 유명하다고 하는데, 이 논쟁에서 힐베르트는 형식주의(formalism)를 옹호하였고, 브라우어는 직관주의를 옹호한 모양. 자세한 내용은 모르지만, 현대 수학/물리학의 흐름으로 보았을때는 힐베르트의 형식주의가 압도적으로 승리한듯 ㅋ

지상의 사설에 따르면 비슷한 시기 아인슈타인과 한 철학자 헨리 베르그손(Henry Bergson)의 토론도 꽤 유명한 모양인데, 이 토론의 주제는 “시간이 존재하는가?” 였던 모양. 이 논의는 아인슈타인의 대승이였고, 아인슈타인의 결론은

“There is no such thing as the time (of the philosopher).”
Albert Einstein

였던 모양이다. 허허 -_-

물론 형식주의와 상대성이론 하에서도, 양자물리학의 측정(measurement)을 도입하면 진짜 “랜덤”이 등장하긴 한다. 근데 아직 상대성이론과 양자물리학은 잘 통합되고 있지 않고, 출처를 찾기는 어려운데, 어디선가 로컬하게는 측정 등으로 난수가 등장하지만, 우주 전체는 unitary하게 직인다는 것을 본것도 같은데 -_-…… (사설에서도 이걸 정확한 언급 없이 말하는듯 하다. 저언혀 정확하지 않음 ㅡㅡ!) 그렇다면 사실상 우주에서 진짜 “난수”는 빅뱅정도에 이미 다 결정된거고, 자유의지나 시간의 흐름따위는 허상이고 우리는 그냥 이를 따라간다는 것으로 이해할 수도 있다.

니콜라스 지상이 사설에서 논의하는 바에 따르면, 그 자신이 도입한 실수의 확률론적 표현을 도입하면 시간과 난수라는게 등장해서 그나마 이런 회의론을 접어둘 수 있다는듯.

물리를 잘 몰라서 디테일한 논의를 따라갈수가 없다 ㅠ.ㅠ.. 조금 느끼는 것은 물리학자들은 공부를 하면 할수록 (물리학적 관점의) 철학적인 질문들에 꽤 다가갈수밖에 없는듯 하고, 이것들은 꽤나 흥미로운듯 하다 ㅋㅋ. 특히 실수를 확률론적으로 접근하는 방식은 굉장히 재미있다. 언젠가는 물리를 더 공부하고 싶은데 게을러서 참 -_-….

서평: Quantum Computing Since Democritus

2020년 7월 27일Hhan댓글 남기기

최근 스콧 아론손(Scott Aaronson)의 저작 Quantum Computing Since Democritus (QCSD)를 읽고있다. 아론손은 일전에 번역하여 포스팅했던 큰 숫자들의 저자이기도 하다. 2006년 워털루 대학에서 가르쳤던 렉쳐에서 시작된 책이라고 한다.

QCSD는 양자컴퓨터의 시작부터 (2013년까지의) 현재 근황까지 발전하여 이어진 여러 생각들을 아론손의 아주 잘 정리하고 있다. 다루고 있는 내용은 컴퓨팅에 관한 고전적 이론부터 양자물리학이 왜 이렇게 이루어져야 하는지, 이와 양자컴퓨터가 만났을 때 일어나는 일들이 무엇인지, 양자물리학으로 (컴퓨터과학에) 어떤 이상한 일들이 벌어지는지, 양자컴퓨터와 우주 (예를들어 closed timelike curve)가 만나면 무슨일이 벌어지는지 등을 굉장히 다양하게 소개한다. 심지어는 타임머신, 자유의지, 마음 등 철학적인 주제마저도 넘나들며 논의한다 -_-!!

놀라운게 저런 개념들을 소개하며 아론손 자신이 쓴 논문들과 최근의 가장 화제가 된 논문들 -_-… 을 개념적으로 아주 잘 연관시켜 설명해준다. 예를 들어 “classical proof”와 “quantum proof”가 어떻게 다른지 [논문], 위에 살짝 말한 Closed timelike curve를 컴퓨터가 이용할 수 있을때 고전컴퓨터와 양자컴퓨터가 어떻게 달라지는지 [논문]라던가, 다른 결과로는 IP=PSPACE, 혹은 P≠NP문제가 증명하기 어렵다는 이전의 결과나 아론손 본인의 논문등.

양자컴퓨터의 “성서“를 쓴 미카엘 닐슨(Michael Nielsen)은 다음과 같은 코멘트를 하기도 했다.

“이 책은 우리가 과학의 근본에 대해 궁금한 점들에 대해 알아낸것들의 아름다운 조합이다. 정보란 무엇일까? 계산한다는 것은? 마음과 자유의지라는것은 무엇일까? 아론손은 그의 고유한 문장들을 통해 최근 과학에서 가장 놀라운 발견, 생각-예를 들어 영지식 증명이나 양자컴퓨터, 블랙홀 엔트로피 등-에 대한 지식을 맛있게 조리한다. 강력하게 추천한다.”
Michael Nielsen in Aaronson’s blog comment.

개인적인 생각으로는, 이 책이 정말 저런 지식들을 아름답게 정리하기는 한다. 근데 좀 어렵다! 분량때문이기도 하겠지만, 너무 많은 전문적인 지식을 간략한 설명으로 때우고 설명한다. 교양 서적이라기보다는 준-교양서적. 읽는데 꽤나 노력이 필요하다. 그치만 그 내용은 정말 놀랍고 아름다운 내용들을 담는다. 나도 강력하게 추천한다 ㅋ

혹시 관심이 있으면 아론손의 홈페이지에 책보다 훨씬 짧은 렉쳐노트들이 정리되어 있다. 한번 살펴보는것도 추천. 얼마전 아론손이 새로 쓴 새 서문에서 여러가지 재미있는 이야기도 있다. 2013-2020의 양자컴퓨터 관련 놀라운 결과들도 아주살짝 정리되어있으니 이것도 추천ㅋ.

실제이미지 vs 딥페이크

2020년 7월 24일Hhan댓글 한 개

일전에 디즈니의 머신러닝 기술을 포스팅하며 딥페이크의 악용에 대해 걱정했는데, 역시 연구자들이 이런 일을 생각하지 않았을리 없다 ㅋㅋ. ICML 2020 논문에 대한 정보는 ACM Technews에서 얻고, 나머지는 알아서 조사함.

실제 이미지와 딥페이크 이미지를 사람이 분석하는 것은 꽤 어려운 태스크로 알려져 있다. whichfaceisreal.com이라는 페이지에서 당신의 구별 능력을 테스트할 수 있다. 방금 해봤는데 10번중에 세번 맞았다 -_- 안면인식에 문제가 있나… Wired.com의 기사에 따르면 평균적으로 75%의 정확도를 지닌다는듯. 내 눈에 문제가 있는듯하다 -_-…

여튼 이번 ICML 2020에 발표될 것으로 얼마전 채택된 논문에 따르면, (GAN 계열으로 생성되는) 딥페이크 데이터들에 대한 주기분석 (Frequency Analysis)를 진행하면 아래와 같이 구체적인 차이점이 드러난다고 한다. 저자들의 대학인 RUHR 대학의 홍보페이지에 조금 더 자세한 글도 올라와 있다.
(왜 푸리에분석이 아닐까? -_- 뭔가 기술적으로는 다른가?)

Taken from paper github page

기존에 이미지 자체에서 차이를 찾아내는 논문이 몇몇 있었는데, 주기분석을 전체적으로 분석한 논문은 몇 없었나보다. 이 논문은 꽤 총체적으로 주기분석을 다룬듯 하다. 어찌보면 딥페이크는 이미지 도메인(그냥 우리가 보는 모습)을 흉내내는것이니, 푸리에 도메인에서는 차이점이 드러날 수 있으니 꽤 그럴듯한 분석인듯.

분석 대상으로 삼은 논문들을 몇개 보니 오히려 분석 대상들이 쇼킹하다 ㅋㅋㅋ

주어진 음원 파일을 말하도록 알맞게 동영상의 입모양을 바꾸는 딥페이크 [논문, 유튜브]
목소리를 유지하며 하는말 일부를 편집하는 딥페이크 [논문, 유튜브]
StyleGen으로 유명한 “스타일”을 배우는 딥페이크 [논문, 유튜브, 관련 Zariski님 포스팅]

이 논문의 레퍼런스를 따라가다 다른 신기한 결과들도 여럿 발견했다.

예를들어, 최근 딥페이크 동영상들을 심장박동을 기준으로 분석하면 뭔가 이상한점이 찾아진다는 논문. 근데 심장박동은 어떻게 재려나?

또, 이런 구별 논문들을 보면 그냥 이미지 말고 구별방식까지 다 같이 러닝하면 되지 않는가 하는 의문이 든다. 이 방식은 아니지만, 딥페이크로 학습한 이미지를 살짝만 고치면 다음 이미지와 같이 최근 구별하는 방식들을 피할수있다는 논문도 있다. 별로 방식에는 관심이 없어 읽어보지는 않음 -_-ㅋㅋ

뭔가 해커와 보안전문가의 대결같다 -_- 구별하는 방식을 내놓을 때마다 그걸 막는 딥페이크를 제시하면 되지 않나 싶은데, 머신러닝 전문가가 아니여서 전혀 모르겠구만. 지금 발전하는 방식으로는 수 년 내에는 컴퓨터로도 새로운 아이디어 없이는 구별할 수 없는 딥페이크가 나오지 않을까 싶다. 그러면 또 NSA같은데서 구별 방식을 숨기려나-_-….

한국 자가격리 앱의 보안성 결함

2020년 7월 23일2020년 7월 23일Hhan댓글 2개

뉴욕타임즈지에 따르면 한국에서 사용하고 있는 자가격리 앱에서 사용자의 이름과 현재 위치를 유출시킬 수 있고, 자가격리 앱에 현재 위치를 속일수도 있는 결함이 발견되었다고 한다. 비슷한 안전성 문제가 인도에서도 있었다고 일전 뉴욕타임즈에서 보고된적 있으며, 국제 앰네스티에 따르면 카타르 자가격리 앱도 문제가 있었다고 한다. 대부분의 문제점은 이미 해결되었고, 한국 앱의 경우에는 지난주 앱스토어와 구글플레이에서 이미 업데이트가 된듯.

사실 이런 새로운 형태의 앱에서 정보가 새는건 흔한 일인듯 해서 그렇게 놀랍진 않다 -_- 아카이브나 이프린트를 보면 이런저런 대책을 제공하고 있지만, 당장 급해죽겠는 국가에서 논문을 거들떠나 볼리가 ㅋㅋ..

그것보다 놀라운 것은 ~~한국과~~ 인도의 앱 보안 이슈를 뉴욕타임즈 팀이 밝힌듯 하다는것. 아니 얘네는 기자들 아닌가? 왜이렇게 전문적이지 -_-.. 구독을 해야지 해야지 말만하다 한주 3번인가 되는 free trial로 만족하고 있었는데, 1주 0.5$로 할인하길래 그냥 질렀다. 역시 사람은 전문성이 있어야..

2020/07/23 추가 2: Zariski님이 댓글에서 지적해주신대로 한국 앱의 경우에는 Frédéric Rechtenstein라는 엔지니어가 찾아서 보고했다고 한다. 아래 대학원생분 말고 이분도 정부에 문제제기를 했으니 역시 묵살된듯 ㅋㅋ… 경향신문 기사에서 당사자분의 인터뷰도 했으니 참조.

2020/07/23 추가 1: snulife의 한 글(계정 필요)에 따르면 그냥 코드 자체가 굉장히 문제가 많았다고. 다음과 같은 너무나 간단한 수준의 문제들이 있던듯.

https가 아닌 http회선을 이용함.
암호화 과정에서 비밀키를 소스코드에 포함시키고, 그 비밀번호는 123456789012345678901234567890123456 이였다고 함.
개인인증도 딱히 없어서 다른 사람의 정보도 볼 수 있었다고 함.
컴공 원생이 개발자/담당자에게 이미 문제점을 알고 연락했었는데, 회신을 받지 못했다고 함.

아니 이건 너무한거 아닌가… -_-… K-보안이란…