Bài giảng đại chúng về Mật mã học hiện đại - Adi Shamir
Địa điểm: Nhà văn hóa Trường ĐH Kinh tế Quốc dân (tức Hội trường A), đường Trần Đại Nghĩa, Hai Bà Trưng, Hà Nội.
Báo cáo viên: GS Adi Shamir
Thời gian: 14:00 - 16:30 Chủ Nhật, 04/12/2016
Tóm tắt:
Đăng ký tham dự:
1) Bài giảng đại chúng, miễn phí, sinh viên và những người làm nghiên cứu đều có thể tham dự, nhưng cần đăng ký để đảm bảo có chỗ ngồi.
2) Chỉ đăng ký nếu gần như chắc chắn sẽ đến dự. Nếu không đi dự được thì xin báo lại qua email để huỷ đăng ký.
3) Đăng ký tham dự: Tại đây.
Nội dung:
- Phần 1 (14h00-15h00): Cryptography: State of the Science
Abstract: This month we are celebrating the 40-th anniversary of the paper "New Directions in Cryptography" which was published by Diffie and Hellman in November 1976. This paper was a turning point in the history of cryptography, and established it for the first time as an academic research area. In this talk I'll survey the main developments of the last 40 years, describe the current state of the field, and try to make some predictions about new cryptographic and cryptanalytic developments.
A more technical talk about my latest research can be an expanded version of my Crypto 2016 talk given three months ago.
- Coffee break (15h00-15h30)
- Phần 2 (15h30-16h30): Memory-Efficient Algorithms for Finding Needles in Haystacks
Abstract: One of the most common tasks in cryptography and cryptanalysis is to find some interesting event (a needle) in an exponentially large collection (haystack) of N=2^n possible events, or to demonstrate that no such event is likely to exist. In particular, we are interested in finding needles which are defined as events that happen with an unusually high probability of p ≫ 1/N in a haystack which is an almost uniform distribution on N possible events. When the search algorithm can only sample values from this distribution, the best known time/memory tradeoff for finding such an event requires O(1/Mp^2) time given O(M) memory.
In this talk I will describe much faster needle searching algorithms in the common cryptographic setting in which the distribution is defined by applying some deterministic function f to random inputs.
Such a distribution can be modeled by a random directed graph with N vertices in which almost all the vertices have O(1) predecessors while the vertex we are looking for has an unusually large number of O(pN) predecessors. When we are given only a constant amount of memory, we propose a new search methodology which we call \textbf{NestedRho}. As p increases, such random graphs undergo several subtle phase transitions, and thus the log-log dependence of the time complexity T on p becomes a piecewise linear curve which bends four times. Our new algorithm is faster than the O(1/p^2) time complexity of the best previous algorithm in the full range of 1/N < p < 1 , and in particular it improves the previous time complexity by a significant factor of \sqrt{N} for any p in the range N^(−0.75) < p < N^(−0.5).
When we are given more memory, we show how to combine the \textbf{NestedRho} technique with the parallel collision search technique in order to further reduce its time complexity. Finally, we show how to apply our new search technique to more complicated distributions with multiple peaks when we want to find all the peaks whose probabilities are higher than p.
Joint work with Itai Dinur, Orr Dunkelman and Nathan Keller.
----
Giới thiệu về GS Adi Shamir
Adi Shamir – ‘S’ trong hệ mã hoá khoá công khai RSA - là người khởi đầu cho nhiều hướng nghiên cứu của mật mã hiện đại.
Ngay sau khi Diffie, Hellman đưa ra khái niệm mật mã hoá khoá công khai vào năm 1976 - dấu mốc cho sự khai sinh của mật mã hiện đại, Rivest, Shamir và Adleman đã công bố một trong những hệ mã hoá khoá công khai đầu tiên vào năm 1977. Hệ mã RSA – lấy theo chữ cái tên của ba ông – hiện vẫn đang được sử dụng rộng rãi trong nhiều ứng dụng của thực tế: bảo mật trong quân đội, giao dịch ngân hàng, trao đổi email v.v
Mật mã hiện đại mở ra nhiều hướng nghiên cứu mới: chữ ký điện tử (đã được nhiều nước cho phép sử dụng với giá trị pháp lý ngang với chữ ký thông thường); các sơ đồ định danh; v.v. Sự ra đời của mật mã hiện đại cũng thúc đẩy sự phát triển của nhiều lĩnh vực nghiên như lý thuyết số tính toán (computational number theory) vì độ an toàn của các sơ đồ như RSA dựa trên độ khó giải của các bài toán số học như phân tích số. Mật mã hiện đại, qua sự nghiên cứu tương tác giữa người bảo vệ an toàn và kẻ tấn công, cũng làm nảy sinh những khái niệm mới trong Khoa học máy tính như chứng minh tương tác (Interactive Proofs) - khái niệm vượt qua phạm vi của những chứng minh thông thường.
Adi Shamir là một trong những người mở đường cho mật mã hiện đại, những công trình của ông mang tính bản lề. Bên cạnh hệ mã RSA, ông còn là người:
- đề xuất sơ đồ chia sẻ bí mật (Shamir Secret Sharing), nơi bí mật được chia sẻ giữa nhiều người và chỉ khi có sự đồng thuận thì bí mật mới được tiết lộ. Đó là nền tảng cho nhiều ứng dụng thực tế, như trong bầu cử điện tử.
- đưa vào khái niệm mã hoá dựa trên danh tính (Identity-based Encryption) năm 1986 và hiện nay đó là một hướng nghiên cứu quan trọng của mật mã.
- bên cạnh lập mã, ông cũng là một người tiên phong trong phá mã. Cùng Eli Biham, ông đề xuất khái niệm phá mã sai phân (Diffrential Cryptanalysis) được sử dụng phổ biến trong việc phá các hệ mã đối xứng.
- ngoài phạm vi mật mã học, Shamir còn có những đóng góp lớn cho lĩnh vực độ phức tạp tính toán. Ông hoàn tất chứng minh IP = PSPACE, lập quan hệ tương đương giữa độ phức tạp theo thời gian của các chứng minh tương tác và độ phức tạp theo không gian của các chứng minh tĩnh cổ điển.
Với những kết quả nền tảng và mở đường, Shamir đã được trao nhiều giải thưởng danh giá, đặc biệt là giải Turing - giải thưởng cao quý nhất trong lĩnh vực Khoa học máy tính.
Mời tất cả các bạn tới dự bài giảng đại chúng của Adi Shamir vào 14h, ngày 4/12 do VIASM tổ chức tại Nhà văn hóa Trường ĐH Kinh tế quốc dân (đi vào cổng Trần Đại Nghĩa). Đây là một dịp để chúng ta được tìm hiểu quá trình phát triển 40 năm của mật mã hiện đại, dẫn dắt bởi một người đã tham gia và chứng kiến toàn bộ sự hình thành và phát triển của nó.
Đăng ký tham dự:
1) Bài giảng đại chúng, miễn phí, sinh viên và những người làm nghiên cứu đều có thể tham dự, nhưng cần đăng ký để đảm bảo có chỗ ngồi.
2) Chỉ đăng ký nếu gần như chắc chắn sẽ đến dự. Nếu không đi dự được thì xin báo lại qua email để huỷ đăng ký.
3) Đăng ký tham dự: Tại đây.