Apply a new product of durations in security

Chia sẻ: Nguyễn Minh Vũ | Ngày: | Loại File: PDF | Số trang:10

Thêm vào BST

Báo xấu

30
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Apply a new product of durations in security

Journal of Computer Science and Cybernetics, V.29, N.2 (2013), 155–164 APPLY A NEW PRODUCT OF DURATIONS IN SECURITY BUI VU ANH1 , PHAN TRUNG HUY2 1 University 2 Hanoi of Science, VNU; Email: vuanh@vnu.edu.vn University of Science and Technology; Email: huypt-fami@mail.hut.edu.vn Tó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ải phá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ương tá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à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 khoá. T khó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 one that we can consider. It is used in consulting for privacy and security solutions. In this protocol, there are 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 answering questions. 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 of durations and its application to design a Zero-knowledge protocol with high reliability and easy to implement. 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. INTRODUCTION Many applications are used with requirements on time which form of durations. In this paper, 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. The prover has some valuable information (or some secret) want to exchange, the verifier needs that information (or secret) and wants to have. Once both sites believe in each other, the exchange 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 valuable information without losing the privacy to make the verifier believe (protocol). For the systems 156 BUI VU ANH, PHAN TRUNG HUY with 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 fact by an honest prover. - Soundness : if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability. - Zero-knowledge : if the statement is true, no cheating verifier learns anything other than this fact. In order to do these, Zero-knowledge systems uses some NPH problems such as finding Hamiltonian circle, and three-color problems on graphs as traps [?, 2, 3, 4]. If anyone who has the 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 this research, we put forward a new application of Zero-knowledge protocol. 2. 2.1. AN ALGEBRAIC STRUCTURE OF DURATIONS Definition Let D = {[l, u] | l, u ∈ Z, l ≤ u} 1 be a set of durations. For d1 , d2 ∈ D, d1 ∩ d2 = ∅ iff d1 overlaps d2 . A value t is said to belong to d = [l, u] if l ≤ t ≤ u, denoted as t ∈ d. If there is no such t, the duration is empty and denoted as ∅. A new type of product between two durations is defined as follows: Definition 2.1. Given d1 , d2 ∈ D, d1 = [l1 , u1 ], d2 = [l2 , u2 ]. The duration product of d1 and d2 is given by: d1 d2 = [l1 , u2 ] if d1 ∩ d2 = ∅ ∅ (not defined) otherwise This product in D is closed because it is a continuous duration with two end points that are also integer numbers, but it is not commutative. d1 d2 = [l1 , u2 ] if d1 ∩ d2 = ∅ ∅ otherwise d2 d1 = [l2 , u1 ] if d1 ∩ d2 = ∅ ∅ otherwise We will explain the meaning of this product later when we make a connection to the duration automata. To investigate the associative property of this product, we need some following 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 cases of 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 checking these 16 cases. 1 In general cases, we can use Q or R 157 APPLY A NEW PRODUCT OF DURATIONS IN SECURITY s s a, [l1 , u1 ] a1 a2 · · · an , [l1 , u1 ] a , [l2 , u2 ] r r t b1 b2 · · · bm , [l2 , u2 ] t Figure 2.1. Products of two d-labels and two d-strings Theorem 2.2. Let d1 , d2 , d3 be durations in D. If (d1 then (d1 d2 ) d3 = d1 (d2 d3 ). d3 = ∅ and d1 d2 ) (d2 d3 ) = ∅ Proof. By remarking the relationship between left and right bounds of 3 durations d1 = [l1 , u1 ], d2 = [l2 , u2 ], d3 = [l3 , u3 ], we only take care of the order of these li , ui , i = 1..3. Thus, we can choose a representative value in each duration. From logical aspect, there are limited cases, so we can use discrete checking method by regarding li , ui , i = 1..3, as integer numbers in durations. For a duration [l1 , u1 ], there are at most 16 possibilities to put 2 points l2 , u2 (l2 ≤ u2 ) into the intervals defined by l1 and u1 . For each 4 points configuration of intervals defined by l1 , u1 , l2 , u2 with random order (l1 ≤ u1 , l2 ≤ u2 ), we have at most 49 cases to put l3 , u3 into these intervals. Because the role of l1 , l2 , l3 and u1 , u2 , u3 are the same, hence the values of these end points can be considered as integer numbers from 1 to 14. The truth of this theorem can be proved by running a simple program to check for all cases as follow. The results of running a simple program as shown below give us a confirmation for the proof of this theorem Let D = {[l, u] | l, u ∈ [1, 14], l ≤ u, l, u ∈ Z+ } be a set of durations with integer end points and values from 1 to 14. The pseudo code below is to check for associative property of the product of 3 durations as mentioned in the theorem 2.2. Function check() { ok=true; for (d1 ∈ D) and ok for (d2 ∈ D) and ok for (d3 ∈ D) and ok if prod(prod(d1 , d2 ),d3 ) = ∅ and prod(d1 ,prod(d2 , d3 )) = ∅ then if prod(prod(d1 , d2 ),d3 ) = prod(d1 ,prod(d2 , d3 )) then ok=false; return(ok); } Remark: Function prod will return the product of two durations. In the following example, we present the cases that may happen between the product of 3 durations when checking for associative property. Example 2.1. For three durations [2, 5][4, 6][1, 3]: ([2, 5] [4, 6]) [1, 3] = [2, 6] ([4, 6] [1, 3]) [2, 5] = ∅ ([1, 3] [2, 5]) ([1, 2] [4, 6] = [1, 5] [3, 5]) [4, 6] = ∅ [1, 3] = [2, 3] but [2, 5] [2, 5] = ∅ but [4, 6] ([1, 3] [4, 6] = [1, 6] and [1, 3] [4, 6] = ∅ and [1, 2] ([4, 6] [2, 5]) = [4, 6] ([2, 5] ([3, 5] [1, 3]) = [2, 5] [1, 5] = [4, 5] [4, 6]) = [1, 3] [4, 6]) = [1, 2] ∅=∅ [2, 6] = [1, 6] [3, 6] = ∅ 158 BUI VU ANH, PHAN TRUNG HUY We can see that if the products of 3 durations with some associations are defined, then they are equal. A question raises: is the defined product of a given sequence of durations with any association unique? The answer as follows. Theorem 2.3. Suppose d1 = [l1 , u1 ], d2 = [l2 , u2 ], . . . , dn = [ln , un ]. If a product δ of d1 , d2 , . . . , dn with an association is defined then δ = [l1 , un ]. Proof. We will prove by induction on n. - For the case of n = 2, this confirmation is true. - Suppose the confirmation is true for n = k > 2 durations. We denote the product of a sequence of durations for δk associations as δk = [d1 , d2 , . . . dk ]. In case this product is defined, the product is unique, otherwise it is ∅. For xk = d1 d2 . . . dk , di = [li , ui ], i = 1..k , δk = [l1 , uk ]. Suppose d = [l, u] ∈ D, there are 3 possibilities to multiply d with xk . + Left multiply: d xk = [l, u] [l1 , uk ] = [l, uk ], if it is defined. + Right multiply: xk d = [l1 , uk ] [l, u] = [l1 , u] if it is defined. + Middle multiply: Suppose the sequence xk+1 = d1 . . . di d di+1 . . . dk with a product for δk+1 association δk+1 = [d1 . . . di d di+1 . . . dk ] is defined. Because δk+1 is defined, there is at least one separation such that δl = [d1 , . . . , di , d], δr = [di+1 , . . . , dk ] are both defined and dl dr = ∅. δl d = [ll , u], δr = [li+1 , uk ] and dl dr = ∅ ⇒ [ll , u] ∩ [li+1 , uk ] = ∅ ⇒ dl dr = [ll , u] [li+1 , uk ] = [l1 , uk ]. Note that the new duration can be a result of no more than other k durations Corollary 2.1. If δ1 and δ2 are two products of a given sequence d1 , d2 , . . . , dn , which are defined for any two associations then δ1 = δ2 . Corollary 2.2. If the product of a sequence d1 , d2 , . . . , dn for any association is defined, then the result is a continuous duration. Example 2.2. Consider the sequence x = [1, 6][5, 8][2, 4][3, 7]: (([1, 6] [1, 6] [1, 6] [5, 8]) ([5, 8] ([5, 8] [2, 4]) ([2, 4] [2, 4]) [3, 7] = ([1, 8] [3, 7])) = [1, 6] [3, 7] = [1, 6] [2, 4]) ([5, 8] ∅ [3, 7] = [1, 4] [3, 7] = [1, 7] [2, 7]) = [1, 6] [5, 7] = [1, 7] [3, 7]) = ∅ (not defined) Example 2.2 shows that if two products of the same sequence with different associations are defined then they are equal. 2.2. Generating a sequence of durations from a binary string Definition 2.2. Let d1 , d2 , d3 be 3 durations. The triple (d1 , d2 , d3 ) is said to be in - Configuration 0 (left association): iff (d1 d2 ) d3 = ∅ and d1 (d2 d3 ) = ∅. - Configuration 1 (right association): iff (d1 d2 ) d3 = ∅, and d1 (d2 d3 ) = ∅. When we create 3 durations from the duration d, there are 4 other end points we must specify. If r is a vector with 4 dimensions which specifies these ends (such as the length ratios between the three durations), we call r as a division ratio. Fig. 2.2 shows two configurations when dividing duration [0, 1] into 3 durations using standard ratio (all steps are equal to 1 unit). For a duration d = [l, u], dividing by configuration 0 and configuration 1 with standard APPLY A NEW PRODUCT OF DURATIONS IN SECURITY d1 0 0 3 2 d2 4 -3 -1 d3 1 -1 0 1 2 3 4 -1 d1 2 d2 -1 d3 -2 Conf . 0 159 0 1 2 1 3 4 Conf . 1 Figure 2.2. Left-associated and right-associated with standard ratio (1 unit step) ratio gives us (ordered from the first, the second and the third durations): ([l, 3u − 2l], [2u − l, 4u − 3l], [2l − u, u]) and ([l, 2u − l], [4l − 3u, −u], [3l − 2u, u]) Dividing with different ratios will produce different durations, one can choose another ratio in which the constraint l1 < u3 < l2 < u1 for configuration 0 and l3 < u2 < l1 < u3 for configuration 1 must be kept. Ratios that keep constraints above are called suitable division. We note that the product of a durations sequence hides the information from the way taking the product (theorem 2.3). Thus, people who know the product result can hardly know which association has been applied. Due to this characteristic, we will use the association information of durations which will be hidden in a binary sequence k ∈ {0, 1}2n+1 , n ∈ Z + as an authentication key. Having choosen a key k and a duration d, the algorithm below will generate a sequence of durations x for a given suitable division ratio r. Algorithm 1: Generating a sequence of durations for a given key. Input: A key k , a duration d and a suitable division ratio r. Output : A sequence of durations x uniquely corresponding to key k . 1. Read k from left to right. If the first symbol of k is 0, divide d by the conf. 0, otherwise divide by the conf. 1. 2. Read two next symbols ab in k . + If the last used conf. is 0 then if a = 0 then divide the 2nd, otherwise divide the 3rd duration of the previous stage. + If the last used conf. is 1 then if a = 0 then we divide the 1st, otherwise divide the 2nd duration of the previous stage. + If b = 0, use conf. 0, otherwise use the conf. 1 with given ratio r to divide the selected duration. 3. Repeat step 2 until the end of k . Remark: The length of k is always odd by this construction. Example 2.3. Suppose d = [0, 1], a key k = 0110001 and 1 unit step ratio. These are steps: 1. The first symbol of k is 0, starting configuration is 0. We divide d into 3 durations (Fig. 2.3a). 2. Two next symbols are 11, we divide d3 using right associated (Fig. 2.3b). 3. Two next symbols are 00, we divide d31 using left associated (Fig. 2.3c). 4. Two next symbols are 01, we divide d312 using right associated (Fig. 2.3d). The result is x = ([0, 3][2, 4])((([−1, 11]([7, 23]([−17, −1][−9, 15])))[−5, 3])([−7, −3][−5, 1]))