Cặp ghép Weil và ứng dụng trong vấn đề so khớp bí mật hồ sơ DNA

Bài viết giới thiệu về lớp bài toán so khớp hồ sơ DNA và đề xuất một cách giải quyết dựa trên tính chất của cặp ghép Weil trên đường cong elliptic.
Nội dung trích xuất từ tài liệu:
Cặp ghép Weil và ứng dụng trong vấn đề so khớp bí mật hồ sơ DNATAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 1 (26) - Thaùng 1/2015 CẶP GHÉP WEIL VÀ ỨNG DỤNG TRONG VẤN ĐỀ SO KHỚP BÍ MẬT HỒ SƠ DNA TÔN THẤT TRÍ (*) ĐẶNG TUẤN THƯƠNG(**) ĐẶNG HẢI VÂN(***) NGUYỄN THANH HUYỀN(****) NGUYỄN ĐÌNH THÚC(*****)T M TẮT To b b o y ú ô ớ u ề ớ b o so k ớ ồ s DNA [ KKT] ề uấ ộ ả quy d í ấ ủ ặ é We ườ o e . óa: ườ o e ặ é We b o so k ớ ồ s DNA.ABSTRACT In this paper, we introduce a class of the privacy DNA profiles matching problems[BKKT] and propose an approach via the theory of Weil pairing on elliptic curves. Keywords: elliptic curves, Weil pairing, DNA profiles matching problems.1. VẤN ĐỀ SO KHỚP DNA BÍ MẬT cần kiểm tra xem hồ sơ DNA của người S Trước hết, chúng tôi mô tả ngắn gọn có nằm trong cơ sở dữ liệu của server haybài toán so khớp bí mật hồ sơ DNA được không, nhưng lại không muốn cho servercác tác giả đề cập đến trong [BKKT]. biết được hồ sơ DNA của S. DNA của một người S bất kỳ được đặc Kiểm tra huyết thống. Hai người S vàtrưng bằng cặp giá trị gọi là ồ s DNA: T muốn kiểm tra xem có cùng quan hệ huyết thống hay không, nhưng cả hai đều trong đó nhận các giá trị trong một không muốn để lộ thông tin về hồ sơ DNAtập nhỏ, chứa không hơn giá trị các cho người kia biết. Biết điều kiện để haisố nguyên.Vấn đề kiểm tra hồ sơ DNA người có cùng huyết thống là:được mô tả như sau:(*)(**)(***)(****)(*****) So trùng DNA. Giả sử một server lưu Trong [BKKT] các tác giả đã giảitrữ các hồ sơ DNA dưới dạng mã hóa. Ta quyết các vấn đề trên bằng mã đồng cấu (homomorphic encryption), một loại mã(*) PGS.TS, Trường Đại học Sài Gòn bảo toàn các phép toán trên các cấu trúc đại(**) CN, Trường Đại học Khoa học Tự nhiên số của bản rõ và bản mã. Trong bài báo nàyTP.HCM(***) ThS, Trường Đại học Khoa học Tự nhiên chúng tôi đề xuất một cách giải bài toánTP.HCM trên dựa trên lý thuyết cặp ghép Weil trên(****) CN, Trường Đại học Vinh đường cong elliptic.(*****) PGS.TS, Trường Đại học Khoa học Tự nhiênTP.HCM 15 2. CÁCH TIẾP CẬN BẰNG CẶP o ó b o ó ạ s ủ , vàGHÉP WEIL ỏ . T ì 2.1. Sơ lược về đường c ng elliptic và ồ ạ ểcặp g ép Weil ượ ặ sở ủ sao cho: Định nghĩa 2.1. Cho là một trườngcó đặc số khác và cho trước Từ Định lý 2.2 ta có nhận xét sau:thỏa Một đường cong Nhận xét 2.3. Nếu thỏa:elliptic trên là tập hợp các điểm (i) Bậc của đúng bằng ; thỏa mãn phương trình (ii) thì chính là cặp cơ sở của cùng với một điểm ở vô cùng, ký hiệu Và tính chất của cặp ghép Weil đượclà . Khi đó tập các điểm trên đường cong đề cập qua định lý dưới đây:với phép cộng điểm được định nghĩa trong Định lý 2.4 [Wa-Theorem 3.9,[Wa-Theorem 2.1] tạo thành một nhóm Corollary 3.10]. Ký ugiao hoán. Ta ký hiệu nhóm này là ó â ồ . bậ ủ o .K ó Để cho gọn, với cho trước ta ký ồ ạ ộ ạ ặ é Wehiệu thay vì . Cũng theo luậtcộng điểm thì các điểm cấp trên sẽ ỏ ã :có dạng . (i) So uy í : Dựa trên tính chất nhóm này, Neal , ta cóKoblitz [Kob] và Miller [Mil] đã độc lậpđề xuất ý tưởng về việc xây dựng một hệmã trên đường cong elliptic với độ khó dựa (ii) Vớ thì .trên bài toán logarit rời rạc như sau: (iii) Vớ , thì Bài toán logarit rời rạc trên đường .cong elliptic. Giả sử là một trường hữu (iv) N u ặ sở ủhạn có đặc số khác và là một thì ầ ửs ủ .đường cong elliptic trên trường . Cho Trong thực tế việc chọn được cặp điểmmột điểm và , tức cơ sở của nhóm trên một đường congnằm trong nhóm cyclic sinh bởi . Liệu có elliptic bất kỳ vẫn là một bài toán ...