Bài giảng đại chúng: Mật mã học hiện đại – Adi Shamir

Bài giảng đại chúng: Mật mã học hiện đại – Adi Shamir

(Nguồn: http://viasm.edu.vn)

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.


– Phần 1: 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.

– Phần 2: Memory-Efficient Algorithms for Finding Needles in Haystacks

(Joint work with Itai Dinur, Orr Dunkelman and Nathan Keller.)

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 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 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.

Cryptography: State of the Science

Delivered by ACM A.M. Turing Laureate Adi Shamir (2002)


Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

%d bloggers like this: