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

TAÏP CHÍ KHOA HOÏC ÑAÏI HOÏC SAØI GOØN Soá 1 (26) - Thaùng 1/2015 15 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 T o 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 Trước hết, chúng tôi mô tả ngắn gọn bài toán so khớp bí mật hồ sơ DNA được các tác giả đề cập đến trong [BKKT]. DNA của một người S bất kỳ được đặc trưng bằng cặp giá trị gọi là ồ s DNA: trong đó nhận các giá trị trong một tập nhỏ, chứa không hơn giá trị các số nguyên.Vấn đề kiểm tra hồ sơ DNA được mô tả như sau:(*)(**)(***)(****)(*****) So trùng DNA. Giả sử một server lưu trữ các hồ sơ DNA dưới dạng mã hóa. Ta (*)PGS.TS, Trường Đại học Sài Gòn (**)CN, Trường Đại học Khoa học Tự nhiên TP.HCM (***)ThS, Trường Đại học Khoa học Tự nhiên TP.HCM (****)CN, Trường Đại học Vinh (*****)PGS.TS, Trường Đại học Khoa học Tự nhiên TP.HCM cần kiểm tra xem hồ sơ DNA của người S có nằm trong cơ sở dữ liệu của server hay không, nhưng lại không muốn cho server biết được hồ sơ DNA của S. Kiểm tra huyết thống. Hai người S và T muốn kiểm tra xem có cùng quan hệ huyết thống hay không, nhưng cả hai đều không muốn để lộ thông tin về hồ sơ DNA cho người kia biết. Biết điều kiện để hai người có cùng huyết thống là: Trong [BKKT] các tác giả đã giải quyết các vấn đề trên bằng mã đồng cấu (homomorphic encryption), một loại mã bảo toàn các phép toán trên các cấu trúc đại số của bản rõ và bản mã. Trong bài báo này chúng tôi đề xuất một cách giải bài toán trên dựa trên lý thuyết cặp ghép Weil trên đường cong elliptic. 16 2. CÁCH TIẾP CẬN BẰNG CẶP GHÉP WEIL 2.1. Sơ lược về đường c ng elliptic và cặp g ép Weil Định nghĩa 2.1. Cho là một trường có đặc số khác và cho trước thỏa Một đường cong elliptic trên là tập hợp các điểm thỏa mãn phương trình cùng với một điểm ở vô cùng, ký hiệu là . Khi đó tập các điểm trên đường cong với phép cộng điểm được định nghĩa trong [Wa-Theorem 2.1] tạo thành một nhóm giao hoán. Ta ký hiệu nhóm này là . Để cho gọn, với cho trước ta ký hiệu thay vì . Cũng theo luật cộng điểm thì các điểm cấp trên sẽ có dạng . Dựa trên tính chất nhóm này, Neal 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 trên bài toán logarit rời rạc như sau: Bài toán logarit rời rạc trên đường cong elliptic. Giả sử là một trường hữu hạn có đặc số khác và là một đường cong elliptic trên trường . Cho một điểm và , tức nằm trong nhóm cyclic sinh bởi . Liệu có thể tìm trong thời gian đa thức sao cho hay không? Dưới đây là một định lý quan trọng về nhóm -xoắn. Định lý 2.2[Wa-theorem 3.2]. Ký u nhóm - oắ o ó b o ó ạ s ủ , và ỏ . T ì ồ ạ ể ượ ặ sở ủ sao cho: Từ Định lý 2.2 ta có nhận xét sau: Nhận xét 2.3. Nếu thỏa: (i) Bậc của đúng bằng ; (ii) thì chính là cặp cơ sở của Và tính chất của cặp ghép Weil được đề cập qua định lý dưới đây: Định lý 2.4 [Wa-Theorem 3.9, Corollary 3.10]. Ký u ó â ồ ă bậ ủ o . K ó ồ ạ ộ ạ ặ é We ỏ ã : (i) So uy í : , ta có (ii) Vớ thì . (iii) Vớ , thì . (iv) N u ặ sở ủ thì ầ ử s ủ . Trong thực tế việc chọn được cặp điểm cơ sở của nhóm trên một đường cong elliptic bất kỳ vẫn là một bài toán mở. Nhưng trên một lớp đường cong gọi là siêu kỳ dị (supersingular curve) thì ta có thể làm được việc đó. Trong phần dưới ta sẽ đề cập đến cách chọn điểm cơ sở trên một đường cong và cách giải quyết bài toán DNA dựa trên cặp ghép Weil. 17 2.2. Đường c ng siêu ỳ dị Định nghĩa 2.5. Giả sử là một trường có trong đó là một số nguyên tố, khi đó được gọi là siêu k d nếu . Với là một số nguyên tố lớn hơn có dạng , ta xét đường cong: Theo [JK-table 1] đây là đường cong siêu kỳ dị và . Bởi [Scho- Theorem 4.8], hoặc . Ta chứng tỏ: Định lý 2.6. Trước hết ta chứng minh bổ đề sau: Bổ đề 2.7. Đườ o ượ ĩ ở ó duy ấ ộ ể ấ 2. Chứng minh. Theo định nghĩa những điểm cấp trên có dạng với . Để tìm , ta giải phương trình trên trường hữu hạn như sau: Nếu , ta có điểm cấp là . Trong trường hợp còn lại, phương trình sẽ vô nghiệm bởi theo tiêu chuẩn Euler về thặng dư bình phương, phương trình trên chỉ có nghiệm khi và chỉ khi hoặc . Do đó chỉ có duy nhất một điểm cấp là Chứng minh Định lý 2.6. Theo bổ đề trên, nếu thì sẽ có nhiều hơn một điểm cấp 2, do đó , và Định lý 2. được chứng minh. Thuật toán xác suất chọn phần tử sinh trong nhóm cyclic sẽ diễn ra khá nhanh bởi theo tính chất của nhóm cyclic, xác suất chọn đúng phần tử sinh trong một lần chọn là trong đó là hàm Euler. Khi là một số nguyên tố lớn thì xác suất này rất gần , bởi vì khi đó sẽ có cùng cấp với qua đánh giá [Cha-Chapter 6, theorem 21]. Gọi B là phần tử sinh của , giả sử trong đó là một số lẻ, đặt thì sẽ có cấp đúng bằng . Xét ánh xạ: trong đó là nghiệm “phức” của phương trình trên (Bổ đề 2.7 chứng tỏ rằng chính là mở rộng trường bậc của ). Dễ thấy rằng là một song ánh và theo [HPS-Proposition 5.51], là một đồng cấu nhóm, do đó là đẳng cấu, tức cũng là một điểm có cấp . Ta có định lý: Định lý 2.8. í ặ sở ủ . Chứng minh. Rõ ràng điều kiện (i) của Nhận xét 2.3 được thỏa mãn. Ta chứng minh điều kiện (ii), tức . Thật vậy, giả sử: 18 Vì và nằm trong mở rộng bậc của nên chỉ xảy ra nếu , tức . Tuy nhiên điều này vô lý vì là điểm có cấp lẻ, do đó nhóm cyclic sinh bởi nó không thể chứa một phần tử có cấp chẵn, là . Như vậy điều kiện (ii) của Nhận xét 2.3 cũng được thỏa mãn, và chính là cặp cơ sở của Chú ý rằng Định lý 2. cũng bao hàm một thuật toán xây dựng cặp điểm cơ sở cho nhóm -xoắn . 2.3. Ứng dụng và bài t n s ớp DNA Trọng tâm của lớp bài toán so khớp hồ sơ DNA nêu trong phần 1 chính là việc so khớp những dữ liệu nằm trên một tập có số phần tử nhỏ, và do đó dễ bị vét cạn. Các kỹ thuật mã hóa thông thường được cho là không thể giải quyết được bài toán này, bởi vậy các tác giả trong BKKT đã phải sử dụng mã đồng cấu để tính toán giá trị ngay trên bản mã. Trong phần này, chúng tôi sẽ đề xuất một cách giải quyết khác dựa trên cặp ghép Weil. Bài toán có thể thu về phát biểu đơn giản sau: Bài toán so khớp các dữ liệu nhỏ. Cho là một tập các số nguyên có số phần tử nhỏ, S giữ một số bí mật và T giữ một số bí mật. Thế thì làm sao hai người có thể so sánh liệu có bằng hay không mà không tiết lộ thông tin gì về số mình đang giữ cho nhau? Giao thức so khớp dữ liệu nhỏ. S và T sẽ công bố các thông tin chung: - Số nguyên tố lớn . - Đường cong elliptic . - Cặp cơ sở trong đó theo như phần trước đã mô tả. Bước 1. T chọn hai số ngẫu nhiên thỏa và tính rồi gửi đến cho . Bước 2. S chọn hai số ngẫu nhiên thỏa và tính trong đó là hàm băm MD hoặc SHA3, là cặp ghép Weil cho nhóm - xoắn , và gửi cặp cho . Bước 3. T tính: và kiểm tra xem có bằng hay không. Nếu bằng thì , ngược lại thì . Tính đúng đắn. Vì hàm băm là hàm một chiều nên ta chỉ cần chứng minh: Áp dụng tính chất của cặp ghép Weil ta có: và Do đó: 19 Vì các giá trị rất nhỏ so với và nguyên tố cùng nhau với , nên từ ta có . Tính bảo mật. Vì các hàm băm không để lộ điều gì về tiền ảnh, do đó tính bảo mật của giao thức hoàn toàn phụ thuộc vào vấn đề sau: “Liệu ta có thể phục hồi được giá trị từ bộ ba trong đó hay không, với các giá trị bí mật?” Theo [HPS-tr.320], ta biết rằng biểu diễn một điểm thuộc dưới dạng: trong đó là cặp cơ sở của thậm chí còn khó hơn bài toán logarit rời rạc trên đường cong elliptic. Do đó, mô hình do chúng tôi đề xuất có độ bảo mật không thấp hơn bài toán logarit rời rạc trên đường cong elliptic. 3. KẾT LUẬN Sử dụng tính chất nhóm cyclic của đường cong siêu kỳ dị trên trường trong đó là một số nguyên tố lớn hơn có dạng , chúng tôi đã chỉ ra cách chọn cặp điểm cơ sở cho nhóm - xoắn , trong đó là số nguyên dương lẻ thỏa mãn . Qua đó chúng tôi đã sử dụng tính chất của cặp ghép Weil để xây dựng lời giải cho bài toán so khớp hồ sơ DNA với độ an toàn không thấp hơn bài toán logarit rời rạc trên đường cong elliptic. TÀI LIỆU THAM KHẢO 1. [BKKT] Fons Bruekers; Stefan Katzenbeisser; Klaus Kursawe; Pim Tuyls, 2008; Privacy-Preserving Matching of DNA Profiles, available from eprint.iacr.org, May 8. 2. [Cha] K.Chandrasekharan, 1968; Introduction to Analytic Number Theory, Springer- Verlag. 3. [HPS] Jeffrey Hoffstein; Jill Pipher; Joseph H. Silverman, 2008; An Introduction to Mathematical Cryptography, Springer. 4. [Kob] Neal Koblitz, 1987; Elliptic Curve Cryptosystems, Mathematics of Computation, Volume 48. 5. [JK] Antoine Joux; Kim Nguyen, 2001; Seperating Decision Diffie-Hellman from Diffie-Hellman in cryptographic groups, available from eprint.iacr.org. 20 6. [Mil]V.Miller (1986) ; Uses of elliptic curves in cryptography, Advances in CryptographyProceeding of Crypto’ , Lecture Notes in Computer Science, 218 SpringerVerlag, 417-426. 7. [MOV] Alfred Menezes; Tatsuaki Okamoto; Scott Vanstone, 1991; Reducing Elliptic Curve Logarithms to Logarithms in a Finite Fields, ACM. 8. [Wa] Lawrence C. Washington, 2008; Elliptic Curves: Number Theory and Cryptography, 2 nd edition, Chapman & Hall/CRC. * Ngày nhận bài: 26/11/2014. Biên tập xong: /1/201 . Duyệt đăng: 10/1/201 .