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