TAILIEUCHUNG - Báo cáo khoa học: "Decoding Running Key Ciphers"

There has been recent interest in the problem of decoding letter substitution ciphers using techniques inspired by natural language processing. We consider a different type of classical encoding scheme known as the running key cipher, and propose a search solution using Gibbs sampling with a word language model. | Decoding Running Key Ciphers Sravana Reddy Department of Computer Science The University of Chicago 1100 E. 58th Street Chicago IL 60637 USA sravana@ Kevin Knight Information Sciences Institute University of Southern California 4676 Admiralty Way Marina del Rey CA 90292 USA knight@ Abstract There has been recent interest in the problem of decoding letter substitution ciphers using techniques inspired by natural language processing. We consider a different type of classical encoding scheme known as the running key cipher and propose a search solution using Gibbs sampling with a word language model. We evaluate our method on synthetic ciphertexts of different lengths and find that it outperforms previous work that employs Viterbi decoding with character-based models. 1 Introduction The running key cipher is an encoding scheme that uses a secret key R that is typically a string of words usually taken from a book or other text that is agreed upon by the sender and receiver. When sending a plaintext message P the sender truncates R to the length of the plaintext. The scheme also relies on a substitution function f which is usually publicly known that maps a plaintext letter p and key letter r to a unique ciphertext letter c. The most common choice for f is the tabula recta where c p r mod 26 for letters in the English alphabet with A 0 B 1 and so on. To encode a plaintext with a running key the spaces in the plaintext and the key are removed and for every 0 i P the ciphertext letter at position i is computed to be Ci f Pi Ri . Figure 1 shows an example encoding using the tabula recta. For a given ciphertext and known f the plaintext uniquely determines the running key and vice versa. Research conducted while the author was visiting ISI. 80 Since we know that the plaintext and running key are both drawn from natural language our objective function for the solution plaintext under some language model is P arg max log Pr P Pr Rp c 1 P where the .

• Báo cáo khoa học
• Decoding Running Key Ciphers
• Sravana Reddy
• Long Papers
• báo cáo khoa học
• báo cáo ngôn ngữ
• ngôn ngữ tự nhiên
• Bài giảng Xử lý ngôn ngữ tự nhiên
• Xử lý ngôn ngữ tự nhiên
• Kỹ thuật lập trình
• Mô hình ngôn ngữ
• Mô hình n gram
• Dịch máy
• Phương pháp dịch máy
• Hiểu ngôn ngữ
• Phân loại tin tự động
• Tạo chí tin học
• Điều khiển học
• Truy vấn ngôn ngữ tự nhiên
• Phép dịch truy vấn ngôn ngữ tự nhiên
• Truy vấn SQL
• Văn phạm ngữ nghĩa
• Xử lý nhập nhằng ngữ nghĩa
• Xử lý ngữ nghĩa
• Phân tích ngữ nghĩa
• Biểu diễn vị từ
• Thuộc tính về sự kiện
• Thuộc tính về sự kiện
• Xử lý ngôn ngữ
• Natural Language Processing
• Ngôn ngữ lập trình
• Nhập nhằng cấu trúc
• Tri thức về ngôn ngữ
• Mô hình ngôn ngữ Google Book N grams
• Mô hình ngôn ngữ KenLM
• Phương pháp làm mịn
• Bài toán PTCP
• Phân tích cú pháp
• Cấu trúc ngữ pháp
• Phân tích cú pháp xác suất
• CKY kết hợp xác suất
• Văn phạm phi ngữ cảnh xác suất
• Hình thái học
• Gán nhãn từ loại
• Ngôn ngữ tự nhiên trong dịch máy
• Hệ thống dịch máy
• Phương pháp xây dựng bảng từ
• Tác từ
• Conditional random fields
• Nhận dạng thực thể có tên
• Đối tượng vật lý trừu tượng
• Phân lớp văn bản
• Biểu diễn nhị phân
• Ma trận từ văn bản
• Wolfram Alpha
• Trích rút thông tin
• Phương pháp Snowball