다니엘 번스타인 교수의 두 번째 미국과의 소송

암호학계에 꽤나 공격적인 어투로 유명한 다니엘 번스타인 (Daniel J. Bernstein)이라는 교수가 있다. 바로 기억나는 것만 해도 공개된 메일링에서 (대략) 상대방의 논문에 대해 “그거 Bullshit인거 너도 알지 않냐” 라는 말과, 학회 초청강연에서 깨진 암호 스킴을 줄줄이 말하면서 공격 논문의 부분을 강단에서 주르륵 읽는 -_- 공격적인 성향이 강하시다. 직접 얘기해본적은 없지만, 학회에서 만난 학생은 굉장히 좋은 사람이라고 하긴 했는데 굉장히 무서운 사람이라고 생각이 든다.

이 사람은 연구도 잘하지만 학계에서는 학계의 방향에 대해 논의하는 논문/평론이나 암호 표준화, 외부적인 활동으로 꽤나 유명하다. 표준은 이름 말해도 알기 어려우니 제끼고, 외부 활동으로의 대표적인 예시가 바로 Bernstein v. United State. 소송사건.

요약하자면 미국에서 암호학 기술의 외부반출을 금지하는 법(위키 페이지)이 있었고, 1992년까지 꽤나 엄격했다고 한다. 이 법에 대해 번스타인 교수가 1995년 학생시절 암호 논문을 출판할 때 소스코드를 함께 동봉하기 위해 소송을 해서 (처음에는 다른 사람들과 함께, 나중에는 혼자서가 된 듯 하다.) 결국은 이겼다고.

번스타인 교수의 홈페이지에 공개된 글에 따르면 이번 소송은 대략 NSA의 정책이 암호학 표준을 망치고 있다..에 관한 것 같다. 사실 여러가지 면으로 NSA/미국 정부가 암호 표준에 영향을 많이 주고, 실제로 이상한 결정을 한 것도 여럿 있어서 그런지 사례를 많이 들어가며 글을 썼다. 대략 DES의 키 길이 문제, DualEC의 백도어에 관한 의혹 등이 대표적인 사례인듯 (잘 몰랐는데, 스노든이 공개한 서류에도 약간 관계되는 내용이 있다고 한다.)

NSA가 의심스러운 행동을 자주 하는거야 사실이지만, 다른 여러 학자들은 번스타인 교수가 최근의 NIST 대양자암호 표준화에 떨어져서 하는 소송이 아니냐는 의견도 좀 있다. 공격적인 비난으로는 이러한 번스타인의 행동이 표준화와 대양자암호로의 변화를 늦추는 요인이 될거라고 ㅋㅋ

STOC의 저자 순서와 인용에 관한 새로운 권고

분야에 따라 다르지만, 내가 몸담고 있는 분야들은 주로 논문의 저자 순서를 (성의) ABC순으로 적는다. 이유는 분야마다 다르겠지만, 특히 이론적 분야에서 ABC순서를 지키는 경우가 많은데, 이 경우 저자중 그 누가 빠져도 이론적인 갭이 생겨 모두의 역할이 중요하니 ABC로 쓴다는 말을 들었던 적이 있다.

하지만 많은 다른 분야에서는 1저자, 2저자를 나누어가면서 저자의 이름 순서를 정하기도 한다. 이에 따라 단순히 성의 알파벳이 느려 손해를 보는 상황이 벌어지기도 한다. 현실적으로는 학교 임용에서 1저자 논문과 2저자 논문 등에 점수를 다르게 매겨 취업에서 손해를 보기도 하고 (엄상일교수님이 서울신문에 관련된 사설을 기고한적이 있다), 학계에서는 다른 논문에 인용되는 경우 A et al. 등으로 뭉뚱그려져 다른 저자들이 충분한 인정을 받지 못하는 경우도 자주 생긴다.

이에 따른 영향인지, 이론적 컴퓨터과학의 가장 큰 학회중 하나인 STOC (Symposium of Theory of Computing)에서 2022년 call for paper 페이지에 다음과 같은 권고가 생겼다.

즉 저자의 순서를 (프로그램 등을 통해) 임의로 정하고, 출판물을 인용할 때 et al.의 표현을 지양하고 최대한 모든 저자를 불러달라는 것. 실제로 주변에서 관련된 불만들을 들은 적이 있으니 (특히 교수님의 성 첫글자가 B, C 등이여서 항상 첫 저자를 뺏겨서) 이러한 경향이 퍼지면 많은 학생의 불만이 조금 해소될 것 같다 ㅋㅋ.

이외에도 사실 나는 전통적인 논문의 저자 표기 방식에 불만이 꽤 있는데, 주로 “성”만 언급하는게 동양인들에게 특히 불이익이 되는듯 하다. 농담삼아 하는 얘기가 한국의 학자 Kim과 Lee는 대체 누구길래 이렇게 많은 논문을 쓰냐, 중국의 Wang, Zhang, 베트남의 Nguyen과 견줄만 하다 -_- 이런 얘기를 하니.. 이 때문인지는 모르겠으나 동양 학자들 중에서는 성을 의도적으로 비틀어 쓰는 경우들이 잦은것 같다. (사실 나도 Han을 Hhan으로 썼다!) 이 문제 자체도 제시된걸 어디선가 봤는데, 지금은 도저히 못찾겠군.

ACM Transactions on Computation Theory의 P=NP 해프닝

이론적 컴퓨터과학은 저널보다 학회에 주로 논문을 내고, 주로 아카이브할만한 가치가 있거나 다른 여러 이유가 있을 때 저널버젼으로 정리해서 내곤 한다. (저널에 새로 실리는 논문이 없는 것은 아니다.) 이러한 저널로 유명한 저널이 Journal of the ACM, Siam Journal on Computing이나 ACM Transactions on Computation Theory (ToCT), Journal of Cryptology 등등이 있다. 그런데, 바로 엊그제 ToCT에 P=NP의 증명을 주장하는 다음과 같은 논문이 실렸다.

3SAT은 NP-complete로 잘 알려진 문제로써, 제목에 따르면 3SAT이 다항식시간에 풀리니 P=NP가 된다. ToCT는 얼마전 글에서 소개했던 Scott Aaronson의 P=NP임을 증명/반증하기 어렵다는 Algebrization이 실려있기도 한, 명백히 피어리뷰가 잘 되는 저널이다!! 이정도의 권위있는 저널에 P=NP의 증명/반증이 실린것은 내가 알기로는 처음이다.

그런데 사실 이건 알고보니 휴먼에러였다 -_- ㅋㅋ 아래는 ToCT의 치프에디터 Ryan O’donnell의 해명 트윗.

즉 이미 Rejection 메일은 갔는데, 행정적 오류로 업로드 되어버렸다고. Ryan Williams의 다른 트윗을 보면 사실 데스크리젝이였다고 한다 -_-ㅋㅋ 결국 다음과 같은 노트가 생기고 곧 내릴듯하다. 페이지가 없어질것 같아서 캡쳐해서 기록용으로 여기 써놓는다 ㅋㅋㅋ

양자컴퓨터와 양자우월성 단신

최근 양자컴퓨터와 양자우월성에 관한 흥미로운 두 논문이 아카이브에 올라왔다. 이전 글들 [글 1, 글 2, 글 3, 글 4, 글 5]보다 훨씬 간단하게 정리해봄. 앞선 글에서 찾을 수 있겠지만, 양자우월성 실험은 고전컴퓨터로 수행하기 어렵거나 굉장히 오랜 시간이 걸리는 일을 양자컴퓨터를 통해 빠르게 수행하는 실험을 말한다. 그러한 일을 찾는것도 꽤나 중요한 문제이고, 현재 실험에서는 랜덤회로샘플링 [관련 지난 글]이나 보손샘플링 [관련 지난 글]을 쓴다.

• 우선 오늘 올라온 논문에 따르면 중국의 여러 팀이 모여 구글의 이전 양자우월성 실험에 쓰였던 Sycamore를 뛰어넘는, 최대 66큐비트까지 다룰 수 있는 새로운 양자컴퓨터 Zuchongzhi를 만들었다고. 이름은 중국의 수학자 조충지에서 따온듯. 이 새로운 컴퓨터를 통해 구글이 진행했던 랜덤회로샘플링을 56큐비트, 20뎁스에 대해 1.9 × 10⁷개의 수를 샘플링했고, 이를 통해 0.0662%의 XEB Fidelity를 얻었다고. 비교대상이였던 과거 구글의 실험은 53큐비트, 20뎁스에 대해 3 × 10⁶개의 수를 샘플링했고, 0.224%의 Fidelity를 얻었다. (지난 글에도 말했지만, 정확한 양자컴퓨터는 100%에 가까운 Fidelity를 얻어야한다! 그만큼 에러가 넘친다는 말.)
  
  고전 시뮬레이션을 통해 비슷한 결과를 얻으려면 27648개의 GPU를 가진 슈퍼컴퓨터 Summit을 이용했을때 Sycamore의 실험은 15.9일, 자신들의 실험은 8.24년이 걸릴것이라고, 지난글에서 다뤘던 Pan과 Zhang의 결과는 일종의 치팅이여서 샘플된 수가 xxx0000처럼 생겨 굉장히 편향되어있고, 확인하기 쉽기때문에 직접 비교의 대상으로는 삼지 않았다고 한다.
  
  개인적인 느낌으로는 당연히 훌륭한 결과지만, Sycamore가 첫 발자국을 찍은 이후로 나온 자연스러운 다음 걸음으로 보임 ㅋ 보손샘플링도 그렇고 양자컴퓨터의 구현측에서 중국이 선두로 나서고 있다는 의미가 큰듯.
  
  
  
• 지난주 올라온 논문은 조금 다르게 양자 문제를 고전 컴퓨터로 푸는것에 대해 다룬다. 특히 여러 입자에 대한 정보가 주어졌을 때 이후 상태를 예측하는 다체 문제(Many-body problem) 등의 문제는 한꺼번에 많은 정보를 다뤄야하기때문에 고전적인 컴퓨터를 사용해서는 푸는것이 어렵다고 알려져 있다. 그런데, 이전 여러 논문 [관련 논문]에서 (고전적) 기계학습의 모델을 잘 설계하고 양자 실험결과를 데이터로 주면 휴리스틱하게 다체 문제를 잘 푼다는 것이 알려졌다고 한다.
  
  이 논문에서는 이러한 다체 문제에 관련된 태스크와 다른 몇몇 태스크가 기계학습을 이용해 잘 풀수 있다는 걸 증명했다고 한다. 즉, 고전적 기계학습이 다체문제를 풀 수 있다는걸 증명했다고 한다. 저자들이 사용한 방식은 특정 양자상태를 고전적으로 기록하는, 최근 발전된 classical shadow라는 툴을 사용했다고. 얘는 물리도 머신러닝도 잘 몰라서 더 자세히 읽기 어렵다..
  
  쓰고보니 얘는 양자컴퓨터와도 양자우월성과도 직접적인 관계는 없구만 -_- 그치만 다체문제의 경우 양자컴퓨터가 잘 풀수 있는 구체적인 예시로 제시되었던 것 같으니, 양자컴퓨터에 대한 작은 회의감을 불러 일으킬수도 있겠다. Classical shadow는 여러번 들어보았는데 아직 제대로 공부를 안해봤다 -_- 물론 머신러닝쪽도 잘 모르니 논문을 읽을 엄두도 안나지만.

2020 ACM Prize in Computing 수상자: Scott Aaronson

2020년 ACM Prize in Computing의 수상자가 Scott Aaronson으로 며칠 전 발표되었다. 사실 벌써 일주일인데 요 근래 정신이 없어서 자꾸 미뤘다 -_-.. 근데 왜 ACM 상들은 헷갈리게 n+1년에 n년 상을 주는걸까 -_- 이 블로그에 소개는 하지 않았지만 2020 튜링상도 발표되었다. 컴파일러쪽에 큰 기여를 하신분들인것 같은데 잘은 몰라서 패스.

여튼 Scott Aaronson은 이 블로그에서 굉장히 자주 소개한 사람이다. 양자컴퓨터와 계산복잡도에 관해 주로 연구하고, 이를 보통(?)사람들에게 쉽게(?) 설명하는 책이나 블로그 글을 자주 쓴다. 당연히 Aaronson의 블로그에도 자신의 수상 결과를 알리는 포스팅도 있다. ACM측에서 밝힌 수상 이유는 대략 다음과 같다.

• 양자우월성을 위해 샘플링 기반의 실험의 이론적 기반을 제시, 특히 최근 실험된 보손샘플링의 이론적 기반 제시 [관련글]
• Avi Wigderson과 함께 P=NP를 증명하는게 어려운 이유인 Algebrization을 제안. 우연의 일치인지 2021년 Wigderson은 아벨상 수상자로 채택되었다 [관련글]
• 양자컴퓨터의 특정 문제 (collision finding)에 관한 한계를 제시
• 공적으로 접근할 수 있는 양자컴퓨터에 대한 소스를 책, 블로그나 여러 톡을 통해 제공

또한 블로그에 소개했던 이런저런 Aaronson에 관한 글은 다음과 같은게 더 있다.

• 큰 숫자들 (Big Numbers)이라는 글을 통해 숫자를 세는 방법과 물리학, 컴퓨터과학을 섞어서 재미있게 설명했다 [링크]
• 거시적인 양자 성질을 관측하기 어려운 이유도 제시했다 [링크]
• 구글의 양자우월성 실험에 관련된 이론적 배경에도 부분적으로 기여하였다 [링크, 관련논문]

또한 언젠가 소개해야지 하면서 아직도 안하고 있는 재미있는 다음과 같은 결과들도 있다.

• 양자상태를 고전적으로 설명하는게 어느정도나 가능한지에 관한 연구들
• Huang의 Sensitivity Conjecture의 증명에 따른 양자 복잡계 이론의 결과
• 시간이 선형적이 아닌 Closed timelike curve와 컴퓨터가 만나면 어떻게 되는지에 대한 연구
• (잘 만들어진) 양자컴퓨터로 효율적으로 계산할 수 있지만, 엄청나게 강력한 파워를 가진 컴퓨터도 고전적으로 계산할 수 없는 문제의 제시
• 양자적으로 굉장히 빨리 풀 수 있는 문제들은 Group 등의 특정한 구조를 가져야 할 것이라는 추측과 증명방향 제시

혹시 언젠가 여유가 된다면 이것들 중 재미있는것들을 포스팅을..-_-

구글의 양자컴퓨터를 통한 Zoom 미팅

Zoom video call is powered by Google’s quantum computer이라는 기사가 Physics world에 올라왔다. 구글 시카모어팀이 Zoom 미팅을 하던 중 발견한 이 결과는 Journal Quantum Advanceds of Computing and Correlation라는 저널에 실렸다고.

좀 더 자세하게, 구글의 양자우월성 실험 [지난글 1,지난글 2]에 사용된 Sycamore를 이용해 Zoom 미팅에서 일종의 “quantum Zoom advantage”를 얻을수 있다고. 이 결과는 워털루대학의 Benedetta Brassard교수가 Zoom 미팅을 할때 어쩌다 Zoom미팅 중 Sycamore에 실행했을 때 발견되었다고 한다.

Brassard가 미팅중 Sycamore에 연결해 대시보드를 확인하며 계산이 어떻게 되어가는지 확인하며 Shor알고리즘에 관한 시덥잔은 농담을 던지던 도중, 11명의 미팅 참가자들은 Sycamore의 53큐비트에 혼란스러운 양자상태로 중첩되었고, 몇몇 사람들은 Brassard의 말을 들을수 있던 반면 몇몇 사람들은 대화가 들리지 않는다고 말했다고.

이는 아마 Sycamore와 Zoom이 연결된 동안 양자역학의 다세계 해석이 일어난것으로 생각된다고 한다. 어떤 의미에서 Brassard가 동시에 여러 회의실에 들어간 것으로 보인다고. Brassard는 여러 화면이 줌에 나타나는 것을 보며 고전세계로 돌아가기 위해 측정, 즉 다른사람의 말에 귀를 기울이고 들었다고 한다.

저자들은 이 현상을 통해 참가자들이 여러 회의실에 동시에 참가하고, 지루한 회의시간을 줄이는 현실에 가장 가까운 양자컴퓨터를 통한 이득을 볼 수 있을것이라고 예측한다고.

---

물론 굉장히 공들인 만우절 기사이다 -_-

2021년의 아벨상 수상자: László Lovász와 Avi Wigderson

아마 이 블로그의 독자들이라면 다른 경로를 통해 들었겠지만, (필즈상과 더불어) 수학의 노벨상이라고도 불리는 2021년 아벨상 수상자가 이론적 컴퓨터과학에 종사한 라슬로 로바스(László Lovász)와 아비 위그더슨(Avi Wigderson)으로 결정되었다. 아벨상 홈페이지와 Quanta 기사가 아주 좋은듯.

Quanta 기사에 인용된 Russell Impagliazzo 교수님의 말에 따르면 로바스는 수학의 입장에서 컴퓨터과학에, 위그더슨은 컴퓨터과학의 입장에서 수학에 영향을 주었다고 한다. 물론 서로 엄청난 영향을 주었지만.

내가 아는 대표적인 업적들을 정리해보면, 우선 로바스 교수님은

• 격자(Lattice)의 꽤 짧은 basis를 찾는 Lenstra-Lenstra-Lovász, 소위 LLL algorithm의 저자이다. 이 알고리즘의 따름정리로 임의의 유리수계수 다항식이 다항식시간 내에 인수분해가 됨을 증명했다. 정수의 소인수분해가 아직도 해결되지 않은 문제이고, 암호의 기반으로 쓰이는 것과 비교하면 좋다. 또한 이 알고리즘은 격자기반 암호나 다른 여러 암호의 분석에 여전히 잘 쓰이고 있다.
• 확률론적인 방법으로 어떤 조합적 대상의 증명을 보이는 확률론적 방법에서, 특히 여러 조건이 dependent할 때 존재성을 보이는 유일한 방법인 Lovász Local Lemma, 또다른 LLL을 제안하고 증명했다. 둘 다 LLL으로 불리는게 꽤 재밌다. 요즘에도 제목에 LLL으로 많이들 나온다 둘 다 -_-..
• 또한 Semidefinite Programming이나 Random walk, 초창기 버전의 PCP 정리에 기여하신듯.

위그더슨 교수님은 좀 더 컴퓨터과학 문제에 많이 접근하셨다. 예를 들어

• 확률론적으로 다항식시간에 해결되는 문제의 집합인 BPP와 결정론적으로 해결되는 P의 관계에 많이 연구했다. 특히 특정한 가정 하에 BPP와 P가 같다는, 다항식 시간의 문제들에는 확률론적 알고리즘이 도움이 되지 않을것이라는 Derandomization에 관한 여러 결과를 냈다.
• P=NP을 증명하는게 어려운 이유중 하나인 Algebrization을 제안하였다.
• 마찬가지로 PCP정리에 기여하시고, 그래프의 Zig-Zag product나 expeander graph, 암호학적으로는 pseudorandomness나 Zero-knowledge proof에 많이 기여하셨다고.

구글의 양자우월성 실험에 대한 반박

오늘 막 중국 두 연구자 Feng Pan과 Pan Zhang이 아카이브에 발표한 결과에 따르면 구글의 양자우월성 실험 [지난글 1, 지난글 2, 지난글 3]이 양자우월성을 보여주지 못한다고 한다. 즉, 고전컴퓨터를 이용한 시뮬레이션으로 양자컴퓨터 실험보다 더 정확한 샘플링 결과를 얻었다는 것. 아직 검증이 되지는 않았지만, 논문에서 주장하는 결과와 논의를 요약하면 다음과 같다.

• 0에 가까울수록 고전컴퓨터에, 1에 가까울수록 (더 좋은) 양자컴퓨터에 가까운 척도가 되는 XEB Fidelity 값이 구글의 실험(0.002)을 압도하는 0.739를 달성했다고 한다. 실험은 60개의 GPU를 이용해 5일간 진행하여 2백만개의 샘플을 얻어냈다고.
• 다만 고전적 알고리즘 자체는 (랜덤 회로의 depth/qubit 수의) 지수적시간이 필요해서 구글의 양자컴퓨터 실험이 더 큰 범위로 된다면 다시 양자우월성을 보일수 있을 것이라고.
• 또한 구글의 실험과 다르게 2백만개의 샘플이 서로 correlated 되어있다는 문제도 있다고 한다. 그치만 별 문제는 아닌듯.

이전 다른 논문이 슈퍼컴퓨터를 이용해 20일정도에 구글의 실험과 비슷한 결과를 얻을 수 있을거라고 했는데, 그거보다 훨씬 좋은 결과인듯. 결과의 참거짓은 모르지만, 다행히 보손샘플링을 이용한 양자우월성 실험 [지난글]이나 여기는 언급하지 않은 불완전한 증명이 주어진 NP문제의 검증에 대한 실험 논문도 있어서 그래도 최소한 에러가 있는 양자컴퓨터는 가까이 있지 않을까 희망해본다 -_-.

플로리다의 정수처리장 사이버 공격

NBC 뉴스에 따르면 플로리다의 한 정수처리장이 해커에 의해 공격당했다고 한다 [짧은 기사, 더 긴 기사].

해커는 정수처리장의 원격조정 아이디를 해킹하여 정수처리 과정에서 수산화나트륨(양잿물!)의 정상 수준의 100여배로 올리라는 명령을 내렸다고. 다행히도 이정도는 죽음에 이를정도는 아니지만, 복통/구토, 메스꺼움이나 위장에 대한 손상을 이르키기에는 충분했다고 한다. 더 다행히도 예비 경보장치가 있어 문제가 생기기 전 관리자들이 이상을 알아차리고 재조정을 했기에 피해자는 없다고 한다.

기사에 따르면 미국은 정수처리 시설이 수만개가 있고, 모두 다른 방식으로 운영되는듯 하다. 이번 공격당한 시설은 컴퓨터 원격제어 프로그램인 TeamViewer를 통해 원격 접속할 수 있었고, 이게 문제가 되었다고. 대부분의 시설이 한두명의 보안관리자만 두고 있다고 한다. 피해를 입은 도시의 경우 도시 전체에 관련 시설의 보안관리자가 한명인듯 -_-.

공격자는 누구인지 알려지지 않았고, NBC뉴스에서는 적대국에서 이러한 식의 공격이 이루어질지 모른다고 경고하고 있다. 지난글에 언급한 것 처럼 세상이 전산화가 되어가면서 정말 사이버펑크화가 되간다고밖에…

화웨이의 가짜 트위터 계정

작년에 시작된 벨기에에서 화웨이를 수익성 있는 통신망 사업에서 배제하는 정책(관련 연합뉴스 기사)이 시행된 이후, 화웨이에서 머신러닝(GAN)으로 생성된 가짜 얼굴을 가진 가짜 트위터 아이디를 생성해 이를 (유럽 지사의 아이디로) 리트윗함으로 정책을 비난/비판했다는 뉴욕타임즈 기사. 한글기사는 찾기 어려운듯하다 -_-.

처음 소식을 들었을 때는 트위터 아이디 수백/수천개로 했나 했는데, 기사에 따르면 확인되는 가짜 아이디는 14개정도인듯하다. 하지만 이렇게 엔터테이닝 목적이 아닌 진짜(?) 가짜 사이버인간을 만들어내서 현실에 영향을 주는것을 보니 우리가 얼마나 사이버펑크의 세계에 가까워졌는지 느껴지는구만 -_-.