Apply a new product of durations in security

Bài báo này giới thiệu một cấu trúc đại số trên các khoảng và ứng dụng nó để thiết kế giao thức Zero-knowledge với độ tin cậy cao nhưng dễ dàng triển khai. Độ phức tạp tấn công giao thức là hàm mũ và độ phức tạp triển khai giao thức là tuyến tính theo là độ dài khóa.
Nội dung trích xuất từ tài liệu:
Apply a new product of durations in securityJournal of Computer Science and Cybernetics, V.29, N.2 (2013), 155–164APPLY A NEW PRODUCT OF DURATIONS IN SECURITYBUI VU ANH1 , PHAN TRUNG HUY21 University2 Hanoiof Science, VNU; Email: vuanh@vnu.edu.vnUniversity of Science and Technology; Email: huypt-fami@mail.hut.edu.vnTóm t t. Khi cần đánh giá tính xác thực của một thông tin, giao thức Zero-knowledge là một giảipháp thường được lựa chọn. Nó được dùng trong các giải pháp về thăm dò tính riêng tư hay bảo mật.Giao thức thường có hai bên tham gia: một bên cần chứng minh cho bên còn lại một khẳng định làđúng mà không để lộ thông tin gì ngoại trừ sự trung thực. Hai bên có thể thoả thuận về cách hỏi vàtrả lời với nhau (vì thế gọi là giao thức). Có hai cách thực hiện giao thức: chứng thực không tươngtác (hỏi và trả lời một lần) và chứng thực tương tác (hỏi và trả lời nhiều lần). Tùy theo ứng dụng,việc chứng thực có thể chỉ yêu cầu xác thực thông tin của một phía hay của cả hai phía. Bài báo nàygiới thiệu một cấu trúc đại số trên các khoảng và ứng dụng nó để thiết kế giao thức Zero-knowledgevới độ tin cậy cao nhưng dễ dàng triển khai. Độ phức tạp tấn công giao thức là hàm mũ và độ phứctạp triển khai giao thức là tuyến tính theo là độ dài khoá.Tkhóa. Khoảng, Zero-knowledge, giao thức, tích khoảng, cấu trúc đại số.Abstract. Whenever we need to conduct a privacy assessment, Zero-knowledge protocol is the onethat we can consider. It is used in consulting for privacy and security solutions. In this protocol, thereare often two parties: one party has to prove to the other that a statement is true, without revealing anything accepting the veracity. They have an agreement on the way of asking and answeringquestions. There are two ways to use the protocol: one-time checking and interactive. Some applications require only one-side proof or both-side proof. This paper introduces an algebraic structure ofdurations and its application to design a Zero-knowledge protocol with high reliability and easy toimplement. The complexity for cracking this protocol is O(2n × (2n)!) and for implementing is O(n)where n is the length of the key.Key words. Duration, Zero-knowledge, protocol, product of durations, algebraic structure.1.INTRODUCTIONMany applications are used with requirements on time which form of durations. In thispaper, we introduce a new product on durations. This product is proved to be a weak association. Applying this property, we can applied them in substantiating information problems.Substantiation protocol chosen is Zero-knowledge. This protocol does only authentication.In Zero-knowledge system, there are two parties, called as a prover and a verifier. Theprover has some valuable information (or some secret) want to exchange, the verifier needsthat information (or secret) and wants to have. Once both sites believe in each other, theexchange must be processed and this phase does not belong to the Zero-knowledge system.This proof only takes responsibility for the honest prover to prove that he has a valuableinformation without losing the privacy to make the verifier believe (protocol). For the systems156BUI VU ANH, PHAN TRUNG HUYwith lower security or under some circumstances, ones can use non-interactive methods [9],concurrent [8] or multi prover interactive [6] methods for this protocol.A proof is called a Zero-knowledge if it satisfies three properties [9]:- Completeness : if the statement is true then the honest verifier will be convinced of this factby an honest prover.- Soundness : if the statement is false, no cheating prover can convince the honest verifier thatit is true, except with some small probability.- Zero-knowledge : if the statement is true, no cheating verifier learns anything other than thisfact.In order to do these, Zero-knowledge systems uses some NPH problems such as findingHamiltonian circle, and three-color problems on graphs as traps [?, 2, 3, 4]. If anyone who hasthe information to solve the problems, he can find solutions easily. Otherwise, it is impossible.In [1], duration algebraic structure have been studied and issued some applications. In thisresearch, we put forward a new application of Zero-knowledge protocol.2.2.1.AN ALGEBRAIC STRUCTURE OF DURATIONSDefinitionLet D = {[l, u] | l, u ∈ Z, l ≤ u} 1 be a set of durations. For d1 , d2 ∈ D, d1 ∩ d2 = ∅ iff d1overlaps d2 . A value t is said to belong to d = [l, u] if l ≤ t ≤ u, denoted as t ∈ d. If there is nosuch t, the duration is empty and denoted as ∅. A new type of product between two durationsis defined as follows:Definition 2.1. Given d1 , d2 ∈ D, d1 = [l1 , u1 ], d2 = [l2 , u2 ]. The duration product of d1and d2 is given by:d1d2 =[l1 , u2 ] if d1 ∩ d2 = ∅∅(not defined) otherwiseThis product in D is closed because it is a continuous duration with two end points thatare also integer numbers, but it is not commutative.d1d2 =[l1 , u2 ] if d1 ∩ d2 = ∅∅otherwised2d1 =[l2 , u1 ] if d1 ∩ d2 = ∅∅otherwiseWe will explain the meaning of this product later when we make a connection to theduration automata. To investigate the associative property of this product, we need somefollowing basic results.Theorem 2.1. If d1 , d2 , d3 ∈ D and d1 ∩d2 = ∅, d2 ∩d3 = ∅ then d1 (d2 d3 ) = (d1 d2 ) d3 .Proof. Suppose d1 = [l1 , u1 ], d2 = [l2 , u2 ], d3 = [l3 , u3 ]. For two durations, there are 4 casesof non-empty intersection. Because we only consider the relationship between (d1 , d2 ) and(d2 , d3 ), there are 24 = 16 cases in total. This theorem can be proved by directly checkingthese 16 cases.1In general cases, we can use Q or R157APPLY A NEW PRODUCT OF DURATIONS IN SECURITYssa, [l1 , u1 ]a1 a2 · · · an , [l1 , u1 ]a , [l2 , u2 ]rrtb1 b2 · · · bm , [l2 , u2 ]tFigure 2.1. Products of two d-labels and two d-stringsTheorem 2.2. Let d1 , d2 , d3 be durations in D. ...