국제적으로 인터넷 검열이 증가하고 있다

Hhan댓글 남기기

국제적으로 인터넷의 검열이 증가하고 있음을 밝힐 수 있는 자동화된 툴이 개발되었다는 (ACM TechNews에서 들고 온) 미시간 뉴스의 소식. 미시간 대학의 연구자들은 CensoredPlanet이라는 툴을 개발해 2000여개의 사이트를 20달간 다양한 방식으로 검열이 있는지를 모니터링한 듯 하다. 총 데이터는 200억개정도 된다는 듯. 기존에 비해 훨씬 큰 데이터라고 한다. 논문은 ACM CCS 2020에 얼마전에 발표되었다고. CCS가 이런 논문을 받는건 또 처음 알았네.

기술적인 측면을 제외하면 사실 뻔한 발견들을 자동적으로 밝힌 것 같기도 하다. 사람들이 직접 업데이트를 해주지 않으면 잘 알기 어려운 소식들을 자동적으로 밝히는 데 의의가 있지 않나 생각함. 특히 공개적인 이유 없이 갑자기 차단하는 것도 알게 될 수 있을듯.

대표적인 발견으로는 최근 2년간 15개의 국제적으로 있었던 큰 검열을 발견했고, 그중 10개는 기존에 정확히 리포트가 되어있지 않던 것이라고. 그리고 그 검열에는 Freedom House에 의해 “가장 자유로운 국가”들로 분류되던 노르웨이, 일본 (?), 이탈리아, 인도 (?), 이스라엘, 폴란드 등도 포함되어 있다고 한다.

논문에서 들고온 최근 발견한 검열 사건들.

또한 저자들은 100여개 이상의 국가에서 DNS 검열의 증가 추세를 발견하여, https만으로는 인터넷 검열을 피할 수 없을것이라고 지적하고 있다. 중국과 투르크메니스탄이 가장 심각하다고.

우리나라도 2019년 인터넷 검열 논란 (한글위키 별도 페이지가 없어 불가피하게 나무위키를 링크했다 -_- 나무위키가 역사를 기록하고 있다…)에서 DNS차단이 크게 비판받은 적 있는데, 위 큰 사건의 리스트에서 빠진건 아마 2000개의 사이트와 대한민국에서 차단한 사이트의 교집합이 적었던게 아닐까 싶다.

기존에 OONI나 ICLab등의 사이트도 있다고 해서 들어가보려 했는데 -_- 안랩이 OONI를 유해사이트라고 판단한다. 뭘까…

라마누잔의 “가장 쉬운 공식”

Hhan댓글 한 개

John Baez 교수님의 블로그 Azimuth에 흥미로운 식이 올라와서 한번 요약해본다. 오랜만이 수학글 ㅋ

π는 3보다 약간 크고, e는 3보다 약간 작다. 그 평균은? 기하평균은 다음과 같다.

\sqrt{\pi e}= 2.92228236...

식 자체로는 딱히 흥미로워보이지 않는데, 라마누잔이 1914년 The Journal of the Indian Mathematical Society에 다음 식의 증명을 묻는 퍼즐을 냈다고 한다.

\displaystyle \left(\frac 1 1 + \frac 1 {1\cdot 3} + \frac1{1 \cdot 3 \cdot 5} + \cdots\right) + \frac 1{1+\frac 1{1+\frac 2{1+\frac 3{1+ \frac 4{1+ \frac 5{\ddots}}}}}} = \sqrt{\frac{\pi e}2}

와 그냥 뭔가 싶다 -_-!! 이것이 바로 어릴 때 매료되었던 수학의 아름다움이 아닌가 ㅋㅋㅋ 라마누잔이 하디에게 자신을 처음 소개하는 글에 이 식도 있었다고.

John Baez 교수님은 이 식을 라마누잔의 “가장 쉬운 공식” (Ramanujan’s easiest formula)이라고 불렀다. 이 글에서는 이 식의 간략한 증명을 다루고자 한다.

계속 읽기 →

드론택시가 서울을 날다

Hhan댓글 남기기

드론택시 시험 비행을 했다는 블룸버그지의 소식. 조선일보 기사도 있다. 서울과 대구에서 중국 이항(EHang)사에서 3억원에 구매한 제품인 모양. 생각보다 싼 것 같은데, 시제품이여서 그런게 아닐까 싶다. 실제로는 2인승인데, 안전 등의 문제로 80kg의 쌀포대를 실어 운행해본 모양. 운전자도 없이 아마 자동으로 움직이는 듯하다.

서울의 복잡한 교통상황을 생각하면 굉장히 빠르지만 비싼 교통수단이 될 수 있지 않을까 싶다. 약간 걱정은 많은 드론이 뜰 경우 충돌이나 사고(버드스트라이크 등)의 위험을 관리할 수 있을지. 그리고 이착륙을 할 정류장을 많이 확보할 수 있을지 등이다.

또다른 우려는 왜 중국회사의 제품을 쓰냐는 것인데, 연합뉴스의 우려를 다룬 기사를 보면 한국에는 그런 드론을 만드는 제품이 없다는듯.

난독화 이야기 (2) 가장 좋은 난독화란?

Hhan댓글 남기기

난독화 이야기 (1) 에서 가상 블랙박스 난독화, 즉 임의의 프로그램을 인풋-아웃풋만 알 수 있도록 일종의 “프로그램을 암호화”하는 난독화 기술이 불가능함을 설명했다. 그렇다면 자연스러운 질문은 얼마나 강력한 난독화가 가능한지, 가장 좋은 난독화가 무엇인지에 관한 것이다. 한참 쉬었는데, 난독화에 관한 콴타매거진 기사가 올라와서 다시 돌아와서 조금 더 써봄ㅋ

사실 2001년의 가상 블랙박스 난독화 불가능성 논문에서 이미 제시한 개념이 있다. 바로 구별불가능성 난독화, indistinguishability obfuscation, 소위 “IO”라고 불리는 난독화이다. 구별불가능성 난독화는 두 동등한 프로그램, 즉 크기가 같고 입출력이 같은 프로그램 A와 B를 난독화한 결과 O(A)와 O(B)가 구별 불가능하게 만들어준다.

[정의]구별불가능성 난독화 O는 프로그램 P를 인풋으로 받아 다른 프로그램 O(P)를 아웃풋으로 내는 효율적인 컴파일러로써 다음을 만족한다.

  1. (정확성) P의 입출력을 그대로 보존하여 O(P)(x)=P(x)를 만족한다
  2. (안전성) 크기가 같고 입출력이 같은 프로그램 A,B에 대해 O(A)와 O(B)가 구별 불가능하다.

여기서 구별불가능하다는 것은 임의의 효율적인 알고리즘을 들고와도, X=A 또는 B에 대해 O(X)에서 X가 A인지 B인지 결정할 확률이 맞출 확률이 1/2, 즉 찍는 것에 가깝다는 것.처음 보면 이게 뭔 의미인가 싶다. 나도 그랬다 -_- 하지만 이 정의만으로도 꽤 많은 프로그램의 정보를 숨길 수 있다. 다음 예시를 보자.

은행 등의 앱을 편리하게 이용하기 위해서는 일부 개인정보, 예를 들어 계좌번호와 비밀번호 등을 앱에 저장해놓는 것이 편리하다. 이를 가장 효율적으로 구현하는 방식은 그냥 비밀번호와 계좌번호를 그대로 앱에 저장해놓는 것. 근데 이건 앱을 뜯어볼 수 있으면 비밀번호와 계좌번호를 그대로 볼 수 있고, 바로 개인정보의 유출로 이어진다.

그렇지만 만약 발전한 암호기술을 바탕으로 계좌번호와 비밀번호를 암호화한 상태로 똑같은 태스크를 할 수 있다면? 이 경우에는 앱을 뜯어도 얻을 수 있는 정보가 없다. 바로 IO가 말하는 것은, 이 두 프로그램을 IO로 난독화 한 경우 구별이 불가능하고, 따라서 단순히 구현한 프로그램을 난독화하는 것만으로 프로그램을 뜯어보는 것에 대한 강력한 보안을 얻을 수 있다는 것.

잠깐, 우리는 난독화된 프로그램의 안전성을 논하기 위해 다른 안전한 프로그램을 들고왔다. 이 생각을 천천히 살펴보면 다음과 같은 직관을 얻을 수 있다.

IO를 이용해 난독화한 프로그램은 모든 입출력이 같은 프로그램 중 가장 안전하다!

이런 직관에 착안하여 2007년 골드와서 교수님과 그 제자였던 Guy Rothblum이 Best-possible obfuscation이라는 개념을 제안했다. 즉 난독화된 프로그램이 동등한 프로그램 중 가장 안전해지는 난독화 기술이 무엇인지에 대해 질문을 제시한 것.

저자들의 대답은 다음과 같다.

[정리] 컴파일러 O가 효율적인 IO 방법인 것과 효율적인 Best-possible 난독화인 것은 동치이다.

아주 간단하고 깔끔하다. 이 정리를 조금 더 엄밀하게 말하기 위해 Best-possible obfuscation (BPO)의 정의를 다음과 같이 살짝 정의하자.

[정의] Best-possible 난독화 O는 프로그램 P를 인풋으로 받아 다른 프로그램 O(P)를 아웃풋으로 내는 효율적인 컴파일러로써 다음을 만족한다.

  1. (정확성) P의 입출력을 그대로 보존하여 O(P)(x)=P(x)를 만족한다
  2. (안전성) 임의의 알고리즘 L에 대해서, 그리고 임의의 크기가 같고 입출력이 같은 프로그램 A,B에 대해 다음을 만족하는 효율적인 알고리즘 S가 존재한다:

L(O(A))와 S(B)의 결과 분포가 구별 불가능하다.

정확성은 IO와 정확히 같고, 안전성은 언뜻 봐서는 무슨 뜻인지 꽤 헷갈린다. 대충 그 뜻을 해석해보자면, 난독화 결과 O(A)에서 얻을수 있는 결과는 사실 임의의 다른 동등한 프로그램 B에서 얻을수 있었다는 뜻. 다시 말하면 O(A)에서 유출되는 정보는 다른 모든 동등한 프로그램에서 이미 유출되고 있다는 것.

이제 위 정리는 다음과 같이 증명할 수 있다.

[BPO=>IO] O가 BPO라고 하자. L을 identity, 즉 O(A)의 결과를 그대로 내는 알고리즘이라고 하면 임의의 동등한 두 프로그램 A,B에 대해 (O(A), S(A)), (S(A),O(B))가 각각 구별 불가능하고, 따라서 O(A)와 O(B)도 구별 불가능하다.
[IO=>BPO] O가 IO라고 하자. 임의의 L에 대해 S를 잡아줘야 한다. S(*)=L(O(*))로 정의하면 O(A)와 O(B)가 구별 불가능한 것에서 L(O(A))와 L(O(B))도 구별 불가능.

아주 간단하고 쉽다. 이 논문 이후 난독화의 이론적 연구는 IO가 옳은 목표라는 것에 많이들 동의하게 되었고, 이후 수년간 정체되어 있다가 2013년에 처음으로 그럴듯한 일반적인 난독화 기술이 나온다. 이는 다음 글에서 다룰 예정.

마지막으로 이 논문의 독특한 결과는 다음과 같다.

[정리] P=NP라면 BPO가 존재한다.

암호학적으로는 굉장히 어이없는 결과인게, 암호 시스템이 안전하다는 것은 보통 P≠NP보다도 강력한 결과이다. (즉, 암호가 (다른 가정 없이) 안전하면 P≠NP가 성립한다.) 증명은 자세히는 조금 복잡하고, 대충 아래와 같다.

P=NP라면 임의의 프로그램에 대해 동등한 프로그램 중 "가장 짧은" 프로그램을 효율적으로 찾을 수 있다. 그리고 이 가장 짧은 프로그램은 동등한 두 프로그램 A,B에 대해 같으므로, 이 과정은 IO이고 따라서 BPO이다.

CS대학들의 랭킹 사이트

Hhan댓글 남기기

CSRankings.org이라는 사이트가 있다. 이 사이트에서는 대부분의 대학들의 CS계열 랭킹을 확인할 수 있고, 분야별로 정리해서 볼 수도 있다. FAQ페이지를 보니 US News이나 World Report에서 제공하는 순위는 굉장히 명성(reputation)에 의존하니 좀 더 객관적인, 수치에 기반한 랭킹을 제공하고자 하는듯.

대충 확인해보니 거의 최고의 학회/학술지에 출판한 수로 metric을 주는듯. 정확하게는, 최고 학회에 제출한 페이퍼 하나를 저자 수로 나누어서 카운트하는듯 하다. metric에 citation을 포함하지 않은 것에도 FAQ페이지에 조금 설명이 되어있다.

대충 몇가지 랭킹을 확인하여 알게된 결과는 다음과 같다.

  • 이론계열은 확실히 한국이 약하다. 카이스트/서울대/포스텍 모두 연구자 수도, 논문도 적다. 사실은 미국,유럽+이스라엘 정도가 상위권을 대부분 차지한다.
  • AI계열은 서울대/카이스트도 각각 50/30위권으로 꽤나 연구자도 많고 논문, 연구자도 꽤나 많은듯하다. 이 분야에서 1위는 CMU이다. 2,3위는 칭화대와 베이징대학인데, 카운트되는 연구자 수만 각각 100명가까이 된다 ㅋㅋㅋ
  • 전체 분야는 CMU가 1위인데, 연구자만 160명이 넘는다고 한다 -_-.. 카이스트, 서울대는 각각 19위, 41위.
  • Academia Sinica와 같은 기관이 몇몇 빠져있는 경우도 있는듯.

물론 당연히 재미로만 봐야할 결과. 다만 대학원 지원할때는 꽤나 쓸만한 정보일듯 ㅋㅋㅋ

기침 소리를 통한 COVID-19의 감별

Hhan댓글 남기기

BBC에 보도된 기사에 따르면 COVID-19의 감별을 기침소리로 할 수 있다고 한다! MIT와 하버드의 연구자들이 진행한 연구 결과. MIT News 기사가 비교적 자세한듯.

이 결과에 따르면 2660명의 양성, 2660명의 음성으로 이루어진 총 5320명의 사람들의 핸드폰을 통해 녹음한 기침 소리의 풀에서 4256명의 데이터로 CNN을 통한 학습을 진행해 1064명의 나머지 데이터에 대해 진단을 내려보니 다음과 같은 결과를 얻었다고 한다.

  • 증상이 있는 환자들에게 98.5%의 민감도와 94.2%의 특이도를 (즉, 양성 환자를 98.5%확률로 정확히 판단하고, 음성인 환자를 94.2%의 확률로 정확히 판단) 가지고,
  • 증상이 없는 환자에게도 100%의 민감도와 83.2%의 특이도를 가진다.

그 소리의 차이는 사람이 듣고 판단하기는 어려운듯 하고, 뭔가 푸리에변환을 통해 Mel-Frequency Cepstrum이라는 것으로 변환시켜 CNN으로 학습한듯.

굉장히 신기하다. 이 결과는 IEEE Open Journal of Engineering in Medicine and Biology에 실렸다. 근데 걱정되는 점은 데이터 수가 너무 작은게 아닌가 -_-.. 기계학습을 정말 잘 몰라서 판단이 불가능하다. 저널도 처음 들어보았는데, 이 기사에 따르면 작년에 새로 생긴 IEEE 오픈억세스 저널인듯. 얼마나 믿을 수 있는지는 잘 모르겠지만, (논문에 주장하는대로) 학교 등의 검사가 아주 자주 필요한 곳에서는 유용한 검사로 쓸 수 있을듯하다.

교황이 동성애자간 결합을 지지하다

Hhan댓글 남기기

프란치스코 교황이 이번에 공개적으로 동성애자간 시민결합(Same-Sex Civil Unions)을 옹호하고 나섰다. 뉴욕타임즈 기사와 동아일보의 기사 참조.

개인적으로 남에게 피해를 끼치지 않는 선에서 누가 뭘하든, 어떤 그룹이 서로 동의한 무엇을 하든 (헌법에서 보장하는 수준의) 인간의 기본권을 침해하지 않는다면 타인이 왜 신경쓰나 의문이다. 그치만 한국 사회는 특히 이런 문화(와 최근에는 수없이 많은 것들)에 굉장히 적대적인게 꽤나 안타까울 뿐.

Grover algorithm과 QRAM

Hhan댓글 남기기

쇼어 알고리즘과 더불어 가장 유명한 양자알고리즘 중 하나인 그로버 알고리즘은 흔히 unstructured database search로도 불린다. 즉, 딱히 조건이 없는 N개의 데이터 중 원하는 데이터값의 존재성/위치를 결정하는데 양자적으로 O(√N)번의 데이터 확인으로 충분하다는 말.

그런데, 이게 얼마나 사실일까? 이 글에서는 Grover algorithm에 대한 설명과 의의를 Quantum Random Access Memory, 즉 QRAM과 아주 살짝 엮어서 얘기하고자 한다. 목차는 다음과 같다.

  1. Grover algorithm
  2. unstructured database search
  3. Quantum spatial search
  4. RAM model과 QRAM
계속 읽기 →

경사하강법은 양자적으로도 최적이다

Hhan댓글 남기기

볼록최적화(Convex optimization)의 대표적인 방식으로 유명한 경사하강법(Gradient Descent)이 있다. 이 방법은 f:Rn->R의 함수값 중 일정 범위에서 최솟값을 (정확히는 극값 local minimum을) 찾는 유용한 방법이다. 특히 f가 아래로 볼록인 경우 항상 최솟값을 잘 찾아줌이 알려져 있다.

경사하강법은 굉장히 직관적이라는 장점이 있다. 최적화를 해 나가는 과정에서 각 점의 함수값 f(x)과 기울기(gradient) ∇f(x)만을 계산하고, 다음 점을 찾을 때 현재 점에서 기울기방향으로 조금씩 진행해 나가는 것. 이런식으로 f와 ∇f만을 이용해 최적값을 구하는 문제를 1차 볼록최적화(first-order convex optimization)이라고 한다. 놀랍게도 1차 볼록최적화의 경우 고전적으로 경사하강법이 최적임이 알려져 있다고 한다.

그런데 오늘 올라온 마이크로소프트 팀의 로빈 코타리(Robin Kothari)등의 논문 [1]에 따르면 일반적으로 경사하강법이 양자알고리즘을 고려해도 최적이라고 한다. 정확한 저자들의 결과만 보면 (대충) 다음과 같다.

우선 저자들의 목표는 다음 문제를 푸는 것이다.

[문제 1] 아래로 볼록인 f:Rn->R이 B(0,R)에서 G-Lipschitz continuous이고, x*=argminx∈B(0,R)(f(x))일 때, f(x)≤f(x*)+ε인 x를 함수값 f와 기울기 ∇f를 최소한으로 계산하며 찾는것이다. 양자알고리즘은 해당 값을 양자적으로 계산할 수 있다.

우선 이전에 알려진 결과는 다음과 같다.

정리 1. 사영 경사강하법은 (GR/ε)2번의 함수값과 기울기 계산을 통해 문제 1을 풀 수 있다.

여기서 사영 경사강하법은 B(0,R)으로 나간 경우 B(0,R)으로 사영해버리는 방식으로 진행하는 경사강하법이다.

정리 2. (G,R,ε이 정해졌을 때) 어떤 볼록함수들의 집합이 존재해서, 문제 1을 푸는 임의의 고전알고리즘 (e.g. 에러가 있는, 확률론적..)은 최악의 경우 Ω((GR/ε)2)번의 함수값과 기울기 계산을 해야만 한다.

이 결과는 여러번 다른 방법으로 증명되었다고 한다. 예를 들어 Nemirovsky와 Yudin의 오래된 교과서 [2]에서나, NeurIPS’19에 게제된 논문 [3]에서도 그 결과를 증명했다고. 이 논문에서 이 결과를 새로 증명하기도 하는데, 저자들의 주장으로는증명이 더 간단하고 필요한 f의 정의역의 차원 n이 비교적 작다고.

그리고 저자들의 결과는 정리 2의 양자버젼. 다음과 같다.

정리 3. (G,R,ε이 정해졌을 때) 어떤 볼록함수들의 집합이 존재해서, 문제 1을 푸는 임의의 양자알고리즘은 최악의 경우 Ω((GR/ε)2)번의 함수값과 기울기 계산을 해야만 한다.

다만, 두 정리에서 잡는 함수들의 집합이 좀 다르다. 특히 저자들은 정리 2에서 사용한 함수들의 집합의 경우 양자적으로는 O(GR/ε)번의 계산만 해도 충분함을 보였다고.

전공분야는 아니지만 재미있어보여서 약간 정리해봄 -_-ㅋㅋ 논문도 엄청 어려운것 같지는 않고, 증명 자체는 BBBV97 [4]부터 내려온 스탠다드한 hybrid argument를 쓰는듯 하다. 그치만 그래도 길고 별로 흥미롭지도 않으니 생략.

[1] No quantum speedup over gradient descent for non-smooth convex optimization, arxiv.org
[2] Problem complexity and method efficiency in optimization, Wiley
[3] Complexity of highly parallel non-smooth convex optimization, NeurIPS 2019
[4] Strengths and Weaknesses of Quantum Computing, SIAM Journal on Computing

암호란 무엇인가? (2) 안전성의 모델: 완전한 안전성

Hhan댓글 남기기

꽤나 오래 전 쓴 글 암호란 무엇인가? (1)에서 암호학적으로 어려운 문제와 무시할만한(negligible) 사건/확률에 대해 다루었다.

이 글에서는 좀 더 나아가 가장 이상적으로 안전한 암호의 정의, 그렇게 정의하는 합리적인 이유, 그리고 그 한계에 대해 다루겠다. 이 글에서 다루는 암호와 완전한 안전성의 정의는 정보이론(Information Theory)의 아버지로 불리는 클로드 섀넌(Claude Shannon)의 논문 [2]에서 처음으로 제시되었다. 즉, 저 논문 자체가 암호학의 시초격 논문이다. 또한 그 다른 의미에 대해서는 튜링상, 괴델상을 받은 샤피 골드와서(Shafi Goldwasser), 실비오 미칼리(Silvio Micali)의 Probabilistic encryption [3]에서 제시되었다. 이 논문 이전에도 공개키암호에 대한 논의는 있었지만 [3]에서 처음으로 그 안전성에 대한 엄밀한 정의가 논의되었다. 이 공로와 Interactive proof에 관한 논의에 대한 공로로 두 분이 2012년 튜링상을 수상하였다. 놀랍게도 [3]은 골드와서가 대학원생일때 (!) 썼다고 한다 -_-!!

구체적으로, 이 글에서는 다음과 같은 내용들을 다룰 것이다.

  • 암호의 문법과 공격 모델
  • 완전하게 안전한 암호
  • 완전하게 안전한 암호의 성질
  • One-time pad와 그 한계

물론 이 블로그의 특성상 모든것을 엄밀하게 다루지는 않고, 대략적으로 아이디어를 중심으로 설명한다. 사실 그럴수밖에 없는 부분도 있다 -_-.. 안그러면 몇페이지에 걸쳐 여기 언급되지 않는 대상들을 공부하고 돌아와야함. 아주아주 엄밀한 레퍼런스는 골드리치(Oded Goldreich)의 Foundations of Cryptography [4]를 참조하면 좋다. 내 생각에는 거의 암호학의 성서에 가깝다. 혹은 훨씬 최신의 책은 보네(Dan Boneh)와 쇼프(Victor Shoup)의 책 [5]도 아주 좋다.

더 보기