ロン・リベスト
ロン・リベスト | |
|---|---|
 2012年のRivest | |
| 生まれる | （1947年5月6日）1947年5月6日 |
| 教育 | イェール大学( BA )スタンフォード大学( MS、PhD ) |
| 知られている | 公開鍵RSA、RC2、RC4、RC5、RC6 MD2、MD4、MD5、MD6、リング署名 |
| 受賞歴 |
|
| 科学者としてのキャリア | |
| フィールド | |
| 機関 | マサチューセッツ工科大学 |
| 論文 | 連想検索アルゴリズムの分析 （1974） |
| 博士課程の指導教員 | ロバート・W・フロイド |
| 博士課程の学生 | |
| Webサイト | 人々 |
ロナルド・リン・リベスト（/ r ɪ ˈ v ɛ s t / ; [ 3 ] [ 4 ] 1947年5月6日生まれ）は、アメリカの暗号学者、コンピュータ科学者であり、その研究はアルゴリズムと組合せ論、暗号、機械学習、選挙の完全性といった分野に及んでいる。彼はマサチューセッツ工科大学（MIT）の研究所教授であり、[ 5 ] MITの電気工学・コンピュータサイエンス学科およびコンピュータサイエンス・人工知能研究所 のメンバーでもある。
リベストは、アディ・シャミール、レン・エイドルマンとともにRSAアルゴリズムの発明者の一人であり、この功績により2002年のACMチューリング賞を受賞しました。また、彼は対称鍵暗号アルゴリズムRC2、RC4、RC5の発明者であり、 RC6の共同発明者でもあります（RCは「リベスト暗号」の略です）。さらに、MD2、MD4、MD5 、 MD6 といった暗号ハッシュ関数も考案しました。
教育
リベストは1969年にイェール大学で数学の学士号を取得し、 1974年にはロバート・W・フロイドの指導のもとスタンフォード大学でコンピュータサイエンスの博士号を取得した。[ 1 ]
キャリア
MIT では、Rivest 氏は計算理論グループのメンバーであり、MIT CSAIL の暗号化および情報セキュリティ グループの創設者です。
リベスト氏は、RSA Data Security（現在は Security Dynamics と合併してRSA Security）、Verisign、およびPeppercoinの創設者です。
彼の元博士課程の学生には、アヴリム・ブルム、ベニー・チョー、サリー・ゴールドマン、バート・カリスキ、アンナ・リシアンスカヤ、マルグリット・ベトケ、ロン・ピンター、ロバート・シャピレ、アラン・シャーマン[ 1 ]、モナ・シン[ 2 ] などがいます。
研究
リベスト氏は特に暗号学の研究で知られています。また、アルゴリズム設計、機械学習の計算複雑性、そして選挙のセキュリティにも多大な貢献をしています。
暗号化
リベストは、アディ・シャミール、レナード・エイドルマンと共同で、1978年にRSA暗号システムを発表した。 [C1]これは、公開鍵暗号として初めて使用可能かつ公に記述された方式を提供し、現代の暗号技術に革命をもたらした。伝えられるところによると、リベストは、シャミールとエイドルマンと学生の家で過越祭を祝い、大量のワインを飲んだ後に、暗号システムの鍵となるアイデアを思いついたという。[ 6 ] [ 7 ] 3人は、「公開鍵暗号を実践で使えるものにするための独創的な貢献」により、 2002年のチューリング賞を受賞した。 [ 8 ]この論文は、その後の多くの暗号プロトコルの架空のヒーローであるアリスとボブを初めて紹介した論文でもある。[ 9 ]同年、リベスト、アドルマン、マイケル・デルトウゾスは、準同型暗号とその安全なクラウドコンピューティングへの応用を初めて考案したが、[C2]このアイデアは、安全な準同型暗号アルゴリズムが最終的に開発されてから40年以上経って初めて実現した。[ 10 ]
リベストは、1988年にシャフィ・ゴールドワッサー、シルビオ・ミカリと共同で発表したGMR公開署名方式[C3] [ 11 ] と、2001年にシャミール、ヤエル・タウマン・カライと共同で発明したグループ署名の匿名化形式であるリング署名[C7]の発明者の一人である。彼は、1990年と1992年にそれぞれ発表されたMD4とMD5の暗号ハッシュ関数[C4] [C5]およびRC2、RC4、RC5、RC6を含む一連の対称鍵ブロック暗号を設計した。[C6] [C8]
リベストの暗号技術への貢献としては、他に、チャフィングとウィノウイング、匿名鍵交換を認証するためのインターロック プロトコル、ムーアの法則による計算速度の予測向上に基づくLCS35などの暗号タイムカプセル、鍵ホワイトニングと、データ暗号化標準をDES-Xに拡張する際のxor-encrypt-xor鍵モードによるその応用、暗号マイクロペイメント用のペッパーコインシステムなどがあります。
アルゴリズム
1973年、リベストと共著者らは、ランダム化を使用せずに線形時間で実行できる最初の選択アルゴリズムを発表しました。[A1] [ 12 ]彼らのアルゴリズムである中央値の中央値法は、アルゴリズムのコースでよく教えられています。[ 13 ]リベストは、ほぼ最適な数の比較を実現するランダム選択アルゴリズムであるフロイド-リベストアルゴリズムの2つの同名アルゴリズムの1つでもあります。 [A2] [ 14 ]
リベストの1974年の博士論文は、ハッシュテーブルを用いて文書内の部分的な単語を高速に照合する手法に関するもので、後に彼はこの研究を学術誌に掲載した。[A3]この頃の自己組織化リストに関する研究[A4]は、オンラインアルゴリズムの競合分析の発展における重要な先駆けの一つとなった。[ 15 ] 1980年代初頭には、2次元ビンパッキング問題[A5]やVLSI設計におけるチャネルルーティング[A6]に関する引用数の多い研究も発表した。
彼は、トーマス・H・コーメン、チャールズ・E・ライサーソン、クリフォード・スタインと共著で、アルゴリズムの標準的な教科書である『アルゴリズム入門』（ CLRSとも呼ばれる）を執筆しています。1990年に初版が出版され、その後4版を重ね、最新版は2022年に出版されました。[A7]
学ぶ
決定木学習の問題において、リベストとローラン・ヒャフィルは、バイナリ値の質問（ 20の質問の社交ゲームのように）を通じてオブジェクトのコレクションのそれぞれを識別し、尋ねられる質問の予想数を最小化する決定木を見つけることがNP完全であることを証明しました。 [L1]リベストはまた、アヴリム・ブルムとともに、非常に単純なニューラルネットワークであっても、与えられた分類タスクを正しく解決できるように重みを見つけることによってネットワークをトレーニングすることがNP完全になり得ることも示しました。[L3]これらの否定的な結果にもかかわらず、彼はまた、決定リスト、[L2]決定木、[L4]および有限オートマトンを効率的に推論する方法も発見しました。[L5]
選挙
リベスト氏の最近の研究における重要なテーマは、ソフトウェア独立性の原則に基づく選挙セキュリティである。これは、選挙のセキュリティは物理的な記録に基づいて構築されるべきであり、投票システムで使用されるソフトウェアへの隠れた変更が選挙結果に検知不能な変更をもたらすことはないという原則である。この分野における彼の研究には、このアプリケーションにおける混合ネットワークの堅牢性の向上、 [V1]、 2006年のThreeBallot紙投票用紙ベースのエンドツーエンドの監査可能な投票システムの発明（民主主義の促進を目的としてパブリックドメインにリリース）、 [V2] [ 8 ] 、そして光学スキャン投票システム用のScantegrityセキュリティシステムの開発が含まれる。[V3]
彼は選挙支援委員会の技術ガイドライン策定委員会の委員であった。[ 16 ]
栄誉と賞
リベストは、米国工学アカデミー、米国科学アカデミーの会員であり、計算機学会、国際暗号研究協会、米国芸術科学アカデミーのフェローでもある。アディ・シャミール、レン・エイドルマンとともに、2000年のIEEE小林幸治コンピュータ・通信賞とセキュアコンピューティング生涯功労賞を受賞した。また、チューリング賞も彼らと共同受賞した。リベストはローマ・ラ・サピエンツァ大学から名誉学位（laurea honoris causa）を授与された。[ 17 ] 2005年には、MITX生涯功労賞を受賞した。リベストは2007年にマルコーニフェローに任命され、2008年5月29日にはカールトン大学でチェスリー講演を行った。彼は2015年6月にMITの研究所教授に任命された。[ 18 ]
選定された出版物
Rivest の出版物には以下のものがあります。
アルゴリズム
| A1. | Blum, Manuel ; Floyd, Robert W. ; Pratt, Vaughan ; Rivest, Ronald L. ; Tarjan, Robert E. (1973). 「選択における時間境界」(PDF) . Journal of Computer and System Sciences . 7 (4): 448– 461. doi : 10.1016/S0022-0000(73)80033-9 . MR 0329916 .以前は「中央値計算の線形時間境界」として STOC 1972 で発表されました。 |
| A2. | フロイド, ロバート W. ;リベスト, ロナルド L. (1975年3月). 「選択における期待時間境界」 . Communications of the ACM . 18 (3): 165–172 . doi : 10.1145/360680.360691 . S2CID 3064709 .また、「アルゴリズム489：最小の要素を見つけるためのアルゴリズムSELECT 」（p.173、doi：10.1145/360680.360694）も参照してください。 |
| A3. | Rivest, Ronald L. (1976). 「部分一致検索アルゴリズム」. SIAM Journal on Computing . 5 (1): 19– 50. doi : 10.1137/0205003 . MR 0395398 .1974 年の第 15 回スイッチングおよびオートマトン理論シンポジウムで以前に発表されました。 |
| A4です。 | Rivest, Ronald (1976). 「自己組織化逐次探索ヒューリスティックスについて」 Communications of the ACM . 19 (2): 63– 67. doi : 10.1145/359997.360000 . MR 0408303 . S2CID 498886 .1974 年の第 15 回スイッチングおよびオートマトン理論シンポジウムで以前に発表されました。 |
| A5. | Baker, Brenda S. ; Coffman, EG Jr. ; Rivest, Ronald L. (1980). 「2次元における直交パッキング」. SIAM Journal on Computing . 9 (4): 846– 855. CiteSeerX 10.1.1.309.8883 . doi : 10.1137/0209064 . MR 0592771 . |
| A6. | Rivest, Ronald L.; Fiduccia, Charles M. (1982). 「"greedy"チャネルルータ」 Crabbe, James S.; Radke, Charles E.; Ofek, Hillel (編). Proceedings of the 19th Design Automation Conference, DAC '82, Las Vegas, Nevada, USA, June 14–16, 1982 . ACM and IEEE. pp. 418– 424. doi : 10.1145/800263.809239 . ISBN 0-89791-020-6。 |
| A7. | トーマス・H・コーメン;チャールズ・E・ライザーソン;リベスト、ロナルド L. (1990)。アルゴリズム入門(第 1 版)。 MIT プレスとマグロウヒル。ISBN 0-262-03141-8。第 2 版、Clifford Stein共著、2001 年。第 3 版、2009 年。第 4 版、2022 年。 |
暗号化
| C1. | Rivest, RL; Shamir, A.; Adleman , L. (1978). 「デジタル署名と公開鍵暗号システムを取得する方法」 . Communications of the ACM . 21 (2): 120– 126. doi : 10.1145/359340.359342 . hdl : 1721.1/ 148910 . MR 0700103. S2CID 2873616 . |
| C2. | Rivest, R.; Adleman, L .; Dertouzos, M. (1978). 「データバンクとプライバシー準同型について」. DeMillo, Richard A. (編). Foundations of Secure Computation . Academic Press. pp. 169– 177. |
| C3. | Goldwasser, Shafi ; Micali, Silvio ; Rivest, Ronald L. (1988). 「適応型選択メッセージ攻撃に対する安全なデジタル署名方式」SIAM Journal on Computing . 17 (2): 281– 308. doi : 10.1137/0217017 . MR 0935341 . S2CID 1715998 .以前は「署名問題に対する「逆説的な」解決策」として FOCS 1984 および CRYPTO 1984 で発表されました。 |
| C4. | Rivest, Ronald L. (1990年10月). MD4メッセージダイジェストアルゴリズム. ネットワークワーキンググループ. doi : 10.17487/RFC1186 . RFC 1186 . |
| C5. | Rivest, Ronald L. (1992年4月). MD5メッセージダイジェストアルゴリズム. ネットワークワーキンググループ. doi : 10.17487/RFC1321 . RFC 1321 . |
| C6. | Rivest, Ronald L. (1998年3月). RC2(r)暗号化アルゴリズムの説明. ネットワークワーキンググループ. doi : 10.17487/RFC2268 . RFC 2268 . |
| C7. | Rivest, Ronald L.; Shamir, Adi ; Tauman, Yael (2001). 「秘密を漏らす方法」. Boyd, Colin (編). Advances in Cryptology – ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9–13, 2001, Proceedings . Lecture Notes in Computer Science. Vol. 2248. Springer. pp. 552– 565. doi : 10.1007/3-540-45682-1_32 . ISBN 978-3-540-42987-6。 |
| C8。 | Rivest, Ronald L. (1994). 「RC5暗号化アルゴリズム」. Preneel, Bart (編). 「高速ソフトウェア暗号化：第2回国際ワークショップ」. ルーヴェン、ベルギー、1994年12月14～16日、議事録. Lecture Notes in Computer Science. Vol. 1008. Springer. pp. 86– 96. doi : 10.1007/3-540-60590-8_7 . ISBN 978-3-540-60590-4。 |
学ぶ
| L1。 | Hyafil, Laurent; Rivest, Ronald L. (1976年5月). 「最適な二分決定木の構築はNP完全である」. Information Processing Letters . 5 (1): 15– 17. doi : 10.1016/0020-0190(76)90095-8 . MR 0413598 . |
| L2。 |
| L3。 | Blum, Avrim ; Rivest, Ronald L. (1992). 「3ノードニューラルネットワークの学習はNP完全である」.ニューラルネットワーク. 5 (1): 117– 127. doi : 10.1016/S0893-6080(05)80010-3 . S2CID 8567973 .以前はNIPS 1988にありました。 |
| L4。 | Quinlan, J. Ross ; Rivest, Ronald L. (1989). 「最小記述長原理を用いた決定木の推論」. Information and Computation . 80 (3): 227– 248. Bibcode : 1989InCo...80..227R . doi : 10.1016/0890-5401(89)90010-2 . MR 0984483 . |
| L5。 | Rivest, Ronald L.; Schapire, Robert E. (1993). 「ホーミングシーケンスを用いた有限オートマトン推論」 .情報と計算. 103 (2): 299– 347. doi : 10.1006/inco.1993.1021 . MR 1216458 .以前、STOC 1989 で発表されました。 |
選挙と投票
| V1。 | ヤコブソン, マルクス; ジュエルズ, アリ; リベスト, ロナルド L. (2002). 「ランダム化部分チェックによる電子投票におけるミックスネットの堅牢化」ボネ, ダン (編).第11回USENIXセキュリティシンポジウム議事録, 米国カリフォルニア州サンフランシスコ, 2002年8月5日～9日. マサチューセッツ州ボストン: USENIX協会. pp. 339– 353. |
| V2。 | Rivest, Ronald L.; Smith, Warren D. (2007年8月). 「3つの投票プロトコル：ThreeBallot、VAV、Twin」(PDF) . 2007 USENIX/ACCURATE 電子投票技術ワークショップ (EVT 07) . マサチューセッツ州ボストン: USENIX Association. |
| V3。 | Chaum, David ; Carback, Richard ; Clark, Jeremy ; Essex, Aleksander ; Popoveniuc, Stefan ; Rivest, Ronald L. ; Ryan, Peter YA ; Shen, Emily ; Sherman, Alan T. (2008). 「Scantegrity II: 不可視インク確認コードを用いた光学スキャン選挙システムのエンドツーエンド検証可能性」(PDF) . Dill, David L.; Kohno, Tadayoshi (編). 2008 USENIX/ACCURATE Electronic Voting Workshop, EVT 2008, 2008年7月28日～29日, サンノゼ, CA, USA, Proceedings . ボストン, マサチューセッツ州: USENIX Association. |
私生活
リベストはゲイル・リベストと結婚しており、映画監督のアレックス・リベストと起業家で会社の共同創設者のクリス・リベストという2人の息子がいる。 [ 19 ]
参照
参考文献
- ^ a b c d e f g h i j k l m数学系譜プロジェクトのロン・リベスト
- ^ a b Singh, Mona (1996).ロボットナビゲーションとタンパク質フォールディングへの応用を目的とした学習アルゴリズム（博士論文）. マサチューセッツ工科大学. hdl : 1721.1/40579 . OCLC 680493381 .
- ^ GhostarchiveとWayback Machineにアーカイブ： RSAカンファレンス（2014年2月25日）。「The Cryptographers' Panel」 – YouTube経由。
- ^ GhostarchiveとWayback Machineにアーカイブ：「Faculty Forum Online: Ron Rivest」。YouTube 。 2015年10月15日。
- ^ディジケス、ピーター（2015年6月29日）「チザム、リベスト、トンプソンがMITの新教授に任命：生物学者、コンピューター科学者、そして音楽家がMIT最高の教授職を授与」 MITニュース、マサチューセッツ工科大学。
- ^ Calderbank, Michael (2007年8月20日). 「RSA暗号システム：歴史、アルゴリズム、素数」(PDF) .
- ^シン、サイモン（2000年）「第5章 アリスとボブが公になる」『コードブック』ロンドン：フォース・エステート（英国）ISBN 978-1-85702-889-8。
- ^ a b「ロナルド（ロン）・リン・リベスト」ACMチューリング賞受賞者。ACM （Association for Computing Machinery） . 2023年4月15日閲覧。
- ^ヘイズ、ブライアン（2012年9～10月）「暗号空間におけるアリスとボブ」コンピューティングサイエンス、アメリカン・サイエンティスト、100（5）、Sigma Xi: 362、doi : 10.1511/2012.98.362、JSTOR 43707638。
- ^ Yi, Xun; Paulet, Russell; Bertino, Elisa (2014).準同型暗号とその応用. Springer Briefs in Computer Science. Springer International Publishing. doi : 10.1007/978-3-319-12229-8 . ISBN 978-3-319-12228-1. S2CID 11182158 .特に47ページを参照してください。「FHEの概念は、プライバシー準同型性という名前でリベストによって導入されました。これらの特性を持つスキームを構築する問題は、2009年にジェントリーが画期的な結果を発表するまで未解決のままでした。」
- ^ Menezes, Alfred J. ; van Oorschot, Paul C. ; Vanstone, Scott A. (1996). 「11.6.4 GMRワンタイム署名方式」(PDF) .応用暗号ハンドブック. CRC Press. pp. 468– 471. ISBN 0-8493-8523-7。
- ^パターソン, マイク(1996). 「選択の進歩」. カールソン, ロルフ G.、リンガス, アンジェイ (編).アルゴリズム理論 – SWAT '96, 第5回スカンジナビアアルゴリズム理論ワークショップ, レイキャビク, アイスランド, 1996年7月3日～5日, Proceedings . レクチャーノート・イン・コンピュータサイエンス. 第1097巻. シュプリンガー. pp. 368– 379. doi : 10.1007/3-540-61422-2_146 . ISBN 978-3-540-61422-7。
- ^ Gurwitz, Chaya (1992). 「中央値探索アルゴリズムの指導について」. IEEE Transactions on Education . 35 (3): 230– 232. Bibcode : 1992ITEdu..35..230G . doi : 10.1109/13.144650 .
- ^ Cunto, Walter; Munro, J. Ian (1989). 「平均事例選択」 . Journal of the ACM . 36 (2): 270– 279. doi : 10.1145/62044.62047 . MR 1072421. S2CID 10947879 .
- ^ Sleator, Daniel D. ; Tarjan, Robert E. (1985). 「リスト更新とページングルールの償却効率」. Communications of the ACM . 28 (2): 202– 208. doi : 10.1145/2786.2793 . MR 0777385. S2CID 2494305 .
- ^ 「TGDCメンバー」 .米国国立標準技術研究所. 2009年5月6日. 2007年6月8日時点のオリジナルよりアーカイブ。
- ^略歴。2011年12月6日時点のオリジナルよりアーカイブ。
- ^ 「チザム、リベスト、トンプソンが新研究所教授に任命」 MITニュース | マサチューセッツ工科大学2015年6月29日。
- ^ Cormen, Rivest他著『アルゴリズム入門』 MIT Press第3版
外部リンク
