Browsing by Author "Tzeng, WG"

Now showing 1 - 20 of 27

A new approach for visual cryptography
(2002-12-01)
Tzeng, WG
;
Hu, CM
;
資訊工程學系
;
Department of Computer Science
Visual cryptography is to encrypt a secret image into some shares (transparencies) such that any qualified subset of the shares can recover the secret "visually." The conventional definition requires that the revealed secret images are always darker than the backgrounds. We observed that this is not necessary, in particular, for the textual images. In this paper, we proposed an improved definition for visual cryptography based on our observation, in which the revealed images may be darker or lighter than the backgrounds. We studied properties and obtained bounds for visual cryptography schemes based on the new definition. We proposed methods to construct visual cryptography schemes based on the new definition. The experiments showed that visual cryptography schemes based on our definition indeed have better pixel expansion in average.
A new graph invariant for graph isomorphism: Probability propagation matrix
(1999-05-01)
King, GH
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
The graph isomorphism problem is to determine whether two given graphs are isomorphic or not. In this paper, we present a new graph invariant, called the probability propagation matrix. By means of this graph invariant, we present a heuristic algorithm for the problem. The algorithm is easy to implement and highly parallelizable.
A practical and secure fault-tolerant conference-key agreement protocol
(2000)
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
When a group of people wants to communicate securely over an open network, they run a conference-key protocol to establish a common conference key K such that all their communications thereafter are encrypted with the key K. In this paper we propose a practical and provably secure fault-tolerant conference-key agreement protocol under the authenticated broadcast channel model. The adversary that attacks our protocol can be either active or passive. An active adversary (malicious participant) tries to disrupt establishment of a common conference key among the honest participants, while a passive adversary tries to learn the conference key by listening to the communication of participants. We show that a passive adversary gets no information (zero knowledge) about the conference key established by the honest participants under the assumption of a variant Diffie-Hellman decision problem. We also show that the honest participants can agree on a common conference key no matter how many participants are malicious.
A public-key traitor tracing scheme with revocation using dynamic shares
(2005-04-01)
Tzeng, WG
;
Tzeng, ZJ
;
資訊工程學系
;
Department of Computer Science
We proposed a new public-key traitor tracing scheme with revocation capability using dynamic shares and entity revocation techniques. Our scheme's traitor tracing and revocation programs cohere tightly. The size of the enabling block of our scheme is independent of the number of receivers. Each receiver holds one decryption key only. The distinct feature of our scheme is that when traitors are found, we can revoke their private keys (up to some threshold z) without updating the private keys of other receivers. In particular, no revocation messages are broadcast and all receivers do nothing. Previously proposed revocation schemes need update existing keys and entail large amount of broadcast messages. Our traitor tracing algorithm works in a black-box way. It is conceptually simple and fully k-resilient, that is, it can find all traitors if the number of them is k or less. The encryption algorithm of our scheme is semantically secure assuming that the decisional Diffie-Hellman problem is hard.
A public-key traitor tracing scheme with revocation using dynamic shares
(2001)
Tzeng, WG
;
Tzeng, ZJ
;
資訊工程學系
;
Department of Computer Science
We proposed a new public-key traitor tracing scheme with revocation capability using the dynamic share and entity revocation techniques. The enabling block of our scheme is independent of the number of subscribers, but dependent on the collusion and revocation thresholds. Each receiver holds one decryption key only. Our traitor tracing algorithm works in a black-box way and is conceptually simple. The distinct feature of our scheme is that when the traitors are found, we can revoke their private keys (up to some threshold z) without updating any private key of the remaining subscribers. Furthermore, we can restore the decryption privilege of a revoked private key later. We can actually increase the revocation capability beyond z with dynamic assignment of shares into the enabling block. This property makes our scheme highly practical. Previously proposed public-key traitor tracing schemes have to update all existing private keys even when revoking one private key only. Our scheme is as efficient as Boneh and Franklin's scheme in many aspects. Our traitor tracing scheme is fully k-resilient such that our traitor tracing algorithm can find all traitors if the number of them is k or less. The encryption algorithm of our scheme is semantically secure assuming that the decisional Diffie-Hellman problem is hard. We also proposed a variant traitor tracing scheme whose encryption algorithm is semantically secure against the adaptive chosen ciphertext attack assuming hardness of the decisional Diffie-Hellman problem.
A secure fault-tolerant conference-key agreement protocol
(2002-04-01)
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
When a group of people want to communicate securely over an open network, they run a conference-key protocol to establish a common conference key K such that all their communications thereafter are encrypted with the key K. In this paper, we propose a provably secure fault-tolerant conference-key agreement protocol under the authenticated broadcast channel model. We show that a passive adversary gets zero knowledge about the conference key established by the honest participants under the assumption of a variant Diffie-Hellman decision problem. We also show that the honest participants can agree on a common conference key no matter how many participants are malicious. Furthermore, we show that even if the broadcast channel is not authenticated, our protocol is secure against impersonators under the random oracle model.
A secure fault-tolerant conference-key agreement protocol (vol 51, pg 373, 2002)
(2002-12-01)
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
A threshold GQ signature scheme
(2003)
Liu, LS
;
Chu, CK
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
We proposed the first threshold CQ signature scheme. The scheme is unforgeable and robust against any adaptive adversary if the base GQ signature scheme is unforgeable under the chosen message attack and computing the discrete logarithm modulo a safe prime is hard. Furthermore, our scheme can achieve optimal resilience by some modification.
A time-bound cryptographic key assignment scheme for access control in a hierarchy
(2002-01-01)
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
The cryptographic key assignment problem is to assign cryptographic keys to a set of partially ordered classes so that the cryptographic key of a higher class can be used to derive the cryptographic key of a lower class. In this paper, we propose a time-bound cryptographic key assignment scheme in which the cryptographic keys of a class are different for each time period, that is, the cryptographic key of class C-1 at time t is K-i,K-t. Key derivation is constrained not only by the class relation, but also the time period. In our scheme, each user holds some secret parameters whose number is independent of the number of the classes in the hierarchy and the total time periods. We present two novel applications of our scheme. One is to broadcast data to authorized users in a multilevel-security way and the other is to construct a flexible cryptographic key backup system.
An access control scheme based on Chinese remainder theorem and time stamp concept
(1996)
Hwang, MS
;
Tzeng, WG
;
Yang, WP
;
資訊工程學系
;
Department of Computer Science
In this paper we propose a new dynamic access control method for the computer system with frequently inserted, deleted and updated users/files. Our method, based on the concepts of the access control matrix, key-lock-pair, time stamp and Chinese remainder theorem, associates each user with a user key and a user lock and each tile with a file key and a file lock Our method can achieve the following four goals. (1) By a simple module operation on the keys and locks of the user and the file, we can reveal the access right of a user to a file. (2) When a user/file is added to the computer system, we only assign a key and a lock to the user/file without affecting the keys and locks of the other users/files in the system. (3) When a user/file is deleted from the computer system, we simply erase the entry of the user/file in the computer system. (4) When the access right of a user to a file is updated, we merely modify the key and lock of the user or the file without affecting the keys and locks of the other users/files in the system. The main contribution of our method is that the action of inserting, deleting a user/file, or updating the access right of a user to a file can be done by modifying only one key and one lock, which could not be achieved simultaneously before.
An efficient solution to the millionaires' problem based on homomorphic encryption
(2005)
Lin, HY
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
We proposed a two-round protocol for solving the Millionaires' Problem in the setting of semi-honest parties. Our protocol uses either multiplicative or additive homomorphic encryptions. Previously proposed protocols used additive or XOR homomorphic encryption schemes only. The computation and communication costs of our protocol are in the same asymptotic order as those of the other efficient protocols. Nevertheless, since multiplicative homomorphic encryption scheme is more efficient than an additive one practically, our construction saves computation time and communication bandwidth in practicality.
Authentication of mobile users in third generation mobile systems
(2001-01-01)
Tzeng, ZJ
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
The goal of the third-generation mobile systems is to provide worldwide operation, enhance service capabilities, and improve performance over the second-generation mobile systems. In this paper, we propose an authentication procedure for third-generation mobile systems. The authentication procedure is a protocol suite consisting of two subprotocols: a certificate-based authentication (CBA) protocol and a ticket-based authentication (TBA) protocol. Only two parties, MS and VLR, are involved in executing our protocol. Our authentication procedure uses both public- and secret-key cryptosystems. Our authentication procedure not only provides uniform authentication across domains, but also reduces computational costs in the process of repeated authentication. We provide firm proof of our procedure's correctness.
Common modulus and chosen-message attacks on public-key schemes with linear recurrence relations
(1999-05-14)
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
We consider the linear recurrence relation V-t(x) = Sigma(i=1)(m) (a(i)x + b(i))Vt-i(x) + cx + f where m greater than or equal to 1, a(i) and b(i), 1 less than or equal to i less than or equal to m, are integers. The RSA and LUC schemes can be defined by this relation. In this paper we show that if the linear recurrence relation has some properties, the public-key scheme based on it cannot withstand the common modulus and chosen-message attacks, no matter what the order in is and what the parameters for a(i) and b(i), 1 less than or equal to i less than or equal to m, are. This implies that the LUC cryptosystem cannot withstand the common modulus attack and the LUC digital signature scheme cannot withstand the chosen-message attack. (C) 1999 Elsevier Science B.V. All rights reserved.
Compatible ideal contrast visual cryptography schemes with reversing
(2005)
Hu, CM
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
Recently, Viet and Kurosawa proposed a VCS with reversing, which is a Visual Cryptography Scheme(VCS) where every participant OF is allowed to change black pixels on the transparency to white pixels and vice-versa. The contrast of their scheme is almost ideal, depending on the number of the reconstruction runs performed. Before long, S. Cimato et al. proposed two VCSs with reversing where the contrast of the reconstructed secret image is ideal. However, both Cimato et al.'s schemes cannot be decrypted solely with the human eye. In this paper we propose a new ideal VCS with reversing which is compatible and requires less stacking and reversing operations compared to all previous schemes. Each participant is required to store only two transparencies to reconstruct the ideal contrast secret image.
Distributed key generation as a component of an integrated protocol
(2002)
Chu, CK
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
In this paper we discuss the security issue of distributed key generation in a distributed threshold protocol. We identify two subtle flaws in the previously proposed discrete-log based distributed key generation protocols. We propose a discrete-log based distributed key generation protocol that meets the necessary security requirements and has no such flaws.
Efficient 1-out-of-n oblivious transfer schemes with universally usable parameters
(2004-02-01)
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
In this paper, we propose efficient and secure (string) oblivious transfer (OT(n)(1)) schemes for any n greater than or equal to 2. We build our OT(n)(1) scheme from fundamental cryptographic techniques directly. The receiver's choice is unconditionally secure and the secrecy of the unchosen secrets is based on the hardness of the decisional Diffie-Hellman problem. Some schemes achieve optimal efficiency in terms of the number of rounds and the total number of exchanged messages for the case that the receiver's choice is unconditionally secure. The distinct feature of our scheme is that the system-wide parameters are independent of n and universally usable, that is, all possible receivers and senders use the same parameters and need no trapdoors specific to each of them. We extend our OT(n)(1) schemes to distributed oblivious transfer schemes. Our distributed OT(n)(1) schemes take full advantage of the research results of secret sharing. For applications, we present a method of transforming any (single-database) PIR protocol into a symmetric PIR protocol by slightly increasing the communication cost only.
Efficient k-out-of-n oblivious transfer schemes. with adaptive and non-adaptive queries
(2005)
Chu, CK
;
Tzeng, WG
;
資訊工程學系
;
Department of Computer Science
In this paper we propose efficient two-round k-out-of-n oblivious transfer schemes, in which R sends O(k) messages to S, and S sends 0(n) messages back to R. The computation cost of R and S is reasonable. The choices of R are unconditionally secure. For the basic scheme, the secrecy of unchosen messages is guaranteed. if the Decisional Diffie-Hellman problem is hard. When k = 1, our basic scheme is as efficient as the most efficient 1-out-of-n oblivious transfer scheme., Our schemes have the nice property of universal parameters, that is each pair of R and S need neither hold any secret key nor perform any prior setup (initialization). The system parameters can be used by all senders and receivers without any trapdoor specification. Our k-out-of-n oblivious transfer schemes are the most efficient ones in terms of the communication cost, in both rounds and the number of messages. Moreover, one of our schemes can be extended in a straightforwaxd way to an adaptive k-out-of-n oblivious transfer scheme, which allows the receiver R to choose the messages one by one adaptively. In our adaptivequery scheme, S sends O(n) messages to R in one round in the commitment phase. For each query of R, only O(1) messages are exchanged and O(1) operations axe performed. In fact, the number k of queries need not be pre-fixed or known beforehand. This makes our scheme highly flexible.
Extracting randomness from multiple independent sources
(2005-06-01)
Lee, CJ
;
Lu, CJ
;
Tsai, SC
;
Tzeng, WG
;
資訊科學與工程研究所
We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches them best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.
Inter-protocol interleaving attacks on some authentication and key distribution protocols
(1999-03-26)
Tzeng, WG
;
Hu, CM
;
資訊工程學系
;
Department of Computer Science
We present a new attack, called the inter-protocol interleaving attack, on authentication and key distribution protocols. The attack enlightens us two things. The first is that when considering attacks against a protocol, we should consider not only the protocol itself, but also the interaction with other protocols. The second is about a warning of "not using the shared secret keys between a server and its clients in any other places" that appears in many security-related communication standards, such as CCITT X.509 and ISO 9798. Our attack provides a concrete example for showing that this warning is necessary. (C) 1999 Elsevier Science B.V. All rights reserved.
On path equivalence of nondeterministic finite automata
(1996-04-08)
Tzeng, WG
;
交大名義發表
;
資訊工程學系
;
National Chiao Tung University
;
Department of Computer Science
Two nondeterministic finite automata (NFAs) are said to be path equivalent if each string is accepted by the two automata via the same number of computation paths. In this paper we show the following. (1) The path equivalence problem for NFAs without lambda-cycles is solvable not only in polynomial sequential time but also in O(log(2)(n)) parallel time using a polynomial number of processors, where n is the total number of states in two NFAs. (2) The path equivalence problem for NFAs with lambda-cycles is PSPACE-complete, hence decidable.