로널드 리베스트

1. 개요

로널드 리베스트는 컴퓨터 과학자이자 암호학자이며, 알고리즘 설계 및 선거 보안 분야에 기여했다. 예일 대학교에서 수학 학사 학위를, 스탠퍼드 대학교에서 컴퓨터 과학 박사 학위를 받았다. RSA 암호 시스템을 공동 개발하고, MD4, MD5, RC2, RC4, RC5, RC6 등 다양한 암호 및 알고리즘을 설계했다. 또한, 알고리즘 교과서인 《알고리즘 입문》의 공동 저자이며, MIT 컴퓨터 과학 및 인공지능 연구소에서 암호 및 정보 보안 그룹을 창립했다. 미국 공학 한림원, 미국 국립 과학원 회원이며, 튜링상 등을 수상했다.

2. 교육

리베스트는 뉴욕 주스케넥터디에서 태어났다. 1969년 예일 대학교에서 수학 학사 학위를 취득했고, 1974년 스탠퍼드 대학교에서 로버트 W. 플로이드의 지도하에 컴퓨터 과학 철학 박사 학위를 받았다.

3. 경력

리베스트는 MIT 계산 이론 그룹 및 MIT CSAIL의 암호 및 정보 보안 그룹의 창립 멤버이다.

RSA 데이터 시큐리티(현재 RSA 시큐리티를 형성하기 위해 시큐리티 다이내믹스와 합병됨), 베리사인, 페퍼코인의 창립자였다.

뉴욕 주스케넥터디에서 태어났으며, 1969년 예일 대학교에서 수학 학사 학위를 취득했고, 1974년 스탠퍼드 대학교에서 컴퓨터 과학 Ph.D.를 취득했다. 알고리즘 교과서로 유명한 알고리즘 입문(1990)의 저자 중 한 명이다(다른 저자는 토머스 H. 코멘, 찰스 E. 레이서슨, 클리퍼드 스타인). 그의 전 박사 과정 학생으로는 애브림 블룸, 베니 코르, 샐리 골드만, 버트 칼리스키, 안나 리샨스카야, 론 핀터, 로버트 샤피르, 앨런 셔먼, 모나 싱이 있다.

4. 연구

리베스트는 암호학, 알고리즘 설계, 머신 러닝의 계산 복잡성, 선거 보안 등 다양한 분야에 크게 기여했다.

4.1. 암호학

RSA 암호 시스템은 1978년 리베스트, 아디 샤미르, 레너드 애들먼이 발표하여 현대 암호학에 혁명을 일으킨 최초의 공개 키 암호 방식이다. 같은 해에 리베스트, 애들먼, 마이클 데르토조스는 동형 암호화와 그 응용 프로그램을 처음으로 공식화했다.

리베스트는 샤피 골드와서, 실비오 미칼리와 함께 1988년 GMR 공개 서명 방식을 발명했고, 2001년에는 샤미르 및 야엘 타우만 칼라이와 함께 링 서명을 발명했다. 그는 MD4(1990년) 및 MD5(1992년) 암호 해시 함수와 RC2, RC4, RC5, RC6 등 대칭 키 블록 암호를 설계했다.

또한, 리베스트는 chaffing and winnowing, 익명 키 교환 인증을 위한 연동 프로토콜, LCS35, 키 와이튼닝, Peppercoin 시스템 등 다양한 암호학 분야에 기여했다.

4.2. 알고리즘

1973년, 리베스트는 매뉴얼 블룸, 로버트 플로이드, 본 프랫, 로버트 타잔과 함께 무작위화를 사용하지 않고 선형 시간을 달성한 최초의 선택 알고리즘인 중위수의 중위수 방법을 발표했다. 이 알고리즘은 알고리즘 강좌에서 흔히 가르쳐진다. 리베스트는 또한 거의 최적의 비교 횟수를 달성하는 무작위 선택 알고리즘인 플로이드-리베스트 알고리즘의 공동 개발자이기도 하다.

1974년 박사 학위 논문에서는 문서에서 부분 단어를 빠르게 일치시키기 위한 해시 테이블의 사용에 대해 연구했으며, 이후 이 연구를 저널 논문으로 발표했다. 같은 시기에 자기 조직화 목록에 대한 연구는 온라인 알고리즘에 대한 경쟁적 분석의 개발에 중요한 전조가 되었다. 1980년대 초, 그는 2차원 빈 포장 문제와 VLSI 설계의 채널 라우팅에 대한 연구도 발표하여 많은 인용을 받았다.

그는 토머스 H. 코르멘, 찰스 E. 레이서슨, 클리퍼드 스타인과 함께 알고리즘에 대한 표준 교과서인 알고리즘 소개(일명 CLRS)의 공동 저자이다. 1990년에 처음 출판되었으며, 2022년에 최신판(4판)이 출간되었다.

4.3. 머신 러닝

리베스트는 알고리즘 설계, 머신 러닝의 계산 복잡성 등 다양한 분야에 기여했다.

의사 결정 트리 학습 문제에서 리베스트와 로랑 이야필은 이진 값을 갖는 질문을 통해 일련의 객체를 식별하는 최적의 의사 결정 트리를 찾는 것이 NP-완전임을 증명했다. 이는 스무고개와 같은 게임에서 질문의 기댓값을 최소화하는 의사 결정 트리를 찾는 문제에 해당한다.

리베스트는 애브림 블룸과 함께 매우 간단한 인공 신경망의 경우에도 주어진 분류 작업을 올바르게 해결할 수 있는 가중치를 찾아 네트워크를 훈련시키는 것이 NP-완전일 수 있음을 보여주었다.

이러한 부정적인 결과에도 불구하고, 리베스트는 의사 결정 목록, 의사 결정 트리 및 유한 오토마타를 효율적으로 추론하는 방법을 발견했다.

4.4. 선거 보안

로널드 리베스트는 최근 선거 보안에 대한 연구를 진행해왔다. 특히, 소프트웨어 독립성 원칙에 기반하여 연구를 진행했는데, 이는 투표 시스템에 사용된 소프트웨어의 숨겨진 변경 사항이 선거 결과의 변경을 초래할 수 없도록, 선거의 보안은 물리적 기록에 기반해야 한다는 것이다.

이 분야에서 리베스트의 연구는 다음과 같다:

* 믹스넷의 견고성 향상
* ThreeBallot 종이 투표 기반의 종단간 감사 가능한 투표 시스템 발명 (2006년, 공개 도메인에 공개)
* 광학 스캔 투표 시스템을 위한 Scantegrity 보안 시스템 개발

그는 기술 지침 개발 위원회(Election Assistance Commission's Technical Guidelines Development Committee)의 위원이었다.

5. 수상 및 영예

미국 공학 한림원, 미국 국립 과학원, 계산 기계 협회, 국제 암호 연구 협회, 미국 예술 과학 아카데미 회원이다. 2000년 아디 샤미르, 레온 애들먼과 함께 IEEE 고지 코바야시 컴퓨터 및 통신상과 보안 컴퓨팅 평생 공로상을 수상했다. 튜링상도 공동 수상했다. 로마 라 사피엔차 대학교에서 명예 학위를 받았으며, 2005년에는 MITX 평생 공로상을 받았다. 2007년 마르코니 펠로우로 선정되었고, 2008년 5월 29일에는 칼턴 칼리지에서 체슬리 강연을 했다. 2015년 6월에는 MIT 연구 석좌 교수로 임명되었다.

6. 주요 저서

* 토머스 H. 코르멘, 찰스 E. 레이서슨과 공저, 알고리즘 소개 초판. MIT Press 및 McGraw-Hill. ISBN^영어
* 토머스 H. 코르멘, 찰스 E. 레이서슨, 클리퍼드 스타인과 공저, 알고리즘 소개 2판. MIT Press 및 McGraw-Hill. ISBN^영어
* 토머스 H. 코르멘, 찰스 E. 레이서슨, 클리퍼드 스타인과 공저, 알고리즘 소개 3판. MIT Press. ISBN^영어

7. 개인사

그의 아들은 기업가이자 회사 공동 창업자인 크리스 리베스트이다.