Abstract:Let $G=(V,, E)$ be a given graph with non-negative integral edgecost and delay, $Ssubseteq V$ be a terminal set and $rin S$ bethe selected root. The shallow-light Steiner tree (emph{SLST}) problemis to compute a minimum cost tree spanning the terminals of $S$,such that the delay between $r$ and every other terminal is boundedby a given delay constraint $Dinmathbb{Z}_{0}^{+}$. It is knownthat the emph{SLST} problem is NP-hard and unless $NPsubseteq DTIME(n^{loglog n})$there exists no approximation algorithm with ratio $(1,,gammalog^{2}n)$for some fixed $gamma>0$. Nevertheless,under the same assumption it admits no approximation ratio betterthan $(1,,gammalog|V|)$ for some fixed $gamma>0$ even when $D=2$.This paper first gives an exact algorithm with time complexity$O(3^{t}nD+2^{t}n^{2}D^{2}+n^{3}D^{3})$,where $n$ and $t$ are the numbers of vertices and terminals of thegiven graph respectively. This is a pseudo polynomial time parameterizedalgorithm with respect to the parameterization ``number of terminals''.Later, this algorithm is improved to a parameterized approximationalgorithm with a time complexity $O(3^{t}rac{n^{2}}{epsilon}+2^{t}rac{n^{4}}{epsilon^{2}}+rac{n^{6}}{epsilon^{3}})$and a bifactor approximation ratio $(1+epsilon,,1)$. That is, forany small real number $epsilon>0$, the algorithm computes a Steinertree with delay and cost bounded by $(1+epsilon)D$ and the optimumcost respectively.

Alert Name:
Alerting to:
Authentication email will be sent to your email address in 24 hours
Frequency:
Email Message Format:	Plain text Graphical(HTML)

Complete the form below and we will recommend the selected titles to your friends on your behalf. * Indicates a required field.
Your name*:
Your email address*:
Recipient's name*:
Recipient's email address*:
(multiple recipient's names and email addresses should be separated with semicolons)
Your comments:	I thought you would find the page(s) useful.

Your name:
Your email address:
Recipient's name:
Recipient's email address:
(multiple recipient's names and email addresses should be separated with semicolons)
Your comments:	I thought you would find this page useful.

Disclaimer: This message was sent to your friend using the "Send it to a friend" facility on the Sciencepaper Online’ WWW site, http://www.paper.edu.cn/en. The Sciencepaper Online is not responsible for the content of this email, and anything said in this email does not necessarily reflect the Sciencepaper Online's views.


	1. Parameterized Approximation Algorithms for the Shallow-Light Steiner Tree Problem
	GUO Longkun, LIAO Kewen, SHEN Hong
	Computer Science and Technology 02 June 2015
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:Let $G=(V,, E)$ be a given graph with non-negative integral edgecost and delay, $Ssubseteq V$ be a terminal set and $rin S$ bethe selected root. The shallow-light Steiner tree (emph{SLST}) problemis to compute a minimum cost tree spanning the terminals of $S$,such that the delay between $r$ and every other terminal is boundedby a given delay constraint $Dinmathbb{Z}_{0}^{+}$. It is knownthat the emph{SLST} problem is NP-hard and unless $NPsubseteq DTIME(n^{loglog n})$there exists no approximation algorithm with ratio $(1,,gammalog^{2}n)$for some fixed $gamma>0$. Nevertheless,under the same assumption it admits no approximation ratio betterthan $(1,,gammalog\|V\|)$ for some fixed $gamma>0$ even when $D=2$.This paper first gives an exact algorithm with time complexity$O(3^{t}nD+2^{t}n^{2}D^{2}+n^{3}D^{3})$,where $n$ and $t$ are the numbers of vertices and terminals of thegiven graph respectively. This is a pseudo polynomial time parameterizedalgorithm with respect to the parameterization ``number of terminals''.Later, this algorithm is improved to a parameterized approximationalgorithm with a time complexity $O(3^{t}rac{n^{2}}{epsilon}+2^{t}rac{n^{4}}{epsilon^{2}}+rac{n^{6}}{epsilon^{3}})$and a bifactor approximation ratio $(1+epsilon,,1)$. That is, forany small real number $epsilon>0$, the algorithm computes a Steinertree with delay and cost bounded by $(1+epsilon)D$ and the optimumcost respectively.
	TO cite this article:GUO Longkun, LIAO Kewen, SHEN Hong . Parameterized Approximation Algorithms for the Shallow-Light Steiner Tree Problem[OL].[ 2 June 2015] http://en.paper.edu.cn/en_releasepaper/content/4640692


	2. Buyer-seller watermarking protocols suitable for probabilistic privacy homomorphisms
	ZENG Peng
	Computer Science and Technology 10 November 2014
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:A common limitation of some recently proposed watermarking protocols lies in the requirement of deterministic privacy homomorphisms which would result in an inevitable contradiction between the security and the robustness of watermarks. The present paper provides afix to two important buyer-seller watermarking protocols by removingthis limitation. In addition, the improved protocols solve thesecure verification problem existing in the original ones.
	TO cite this article:ZENG Peng. Buyer-seller watermarking protocols suitable for probabilistic privacy homomorphisms[OL].[10 November 2014] http://en.paper.edu.cn/en_releasepaper/content/4617972

Saved Papers

Saved Papers


	3. Security Enhancement to a User Authentication Scheme for Multi-Server Environment
	ZENG Peng
	Computer Science and Technology 29 October 2014
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:User authentication schemes for multi-server setting allow a remote user to obtain services from multiple servers without the need to separately register with every individual server.In general, user authentication schemes for a multi-server environment should provide the following properties: single registration,low computation, no need for verification table, mutual authentication and key agreement, and security.Recently Wang, Juang, and Lei proposed a privacy-preservation user authentication scheme based on the quadratic residue and claimed the scheme meets all five requirements.In this paper, we demonstrate that their scheme is, unfortunately, vulnerable to a previously unpublished parallel-session attack.In other words, this attack enables a malicious user to impersonate legitimate users and obtain services from participating application servers without the victims' knowledge.We then show how the flaw in Wang emph{et al.}'s scheme can be fixed.
	TO cite this article:ZENG Peng. Security Enhancement to a User Authentication Scheme for Multi-Server Environment[OL].[29 October 2014] http://en.paper.edu.cn/en_releasepaper/content/4615680


	4. Generalized Format-preserving Encryption for Character Data
	Ma Haoyu,Liu Zheli,Jia Chunfu,Yuan Ke
	Computer Science and Technology 04 May 2013
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:We studied format-preserving encryption (FPE) for character data, for solutions that encipher character strings while preserving both their lengths and memory consumptions. By clustering characters into multiple sets according to the number of bytes they are encoded, we managed to establish mixed-radix numeral systems for character data. Under such systems, we proposed a basic method for character data that exploits existing FPEs, as well as a generalized character FPE scheme using Feistel-based construction, where a customized ``dynamic modular addition'' is used to ensure the feasibility the scheme. Our work showed a new way of designing encryption methods for arbitrary message spaces, which involves no tradeoff between efficacy and efficiency.
	TO cite this article:Ma Haoyu,Liu Zheli,Jia Chunfu, et al. Generalized Format-preserving Encryption for Character Data[OL].[ 4 May 2013] http://en.paper.edu.cn/en_releasepaper/content/4540303


	5. Symmetric Bayesian-Nash Equilibrium of Simultaneous Vickrey Auctions with Perfect Substitutes
	Bu Tianming,Qi Qi
	Computer Science and Technology 08 January 2013
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:This paper studies the model that there are two simultaneous one-round sealed-bid second-price/Vickrey auctions. Each auction sells on eidentical object. For each bidder, there is no extra beneﬁt from winning more than one object. This model is in spired by the similar phenomenon appears pervasively on eBay which is the world’s largest online marketplace for businesses and consumers to auction oﬀ goods through it. The paper focuses on the buyers’s trategic behavior in this model. The symmetric Bayesian-Nash equilibria under several constraints are characterized. In addition, the expected total revenue under the symmetric Bayesian-Nash equilibrium of simultaneous Vickrey auctions is analyzed.
	TO cite this article:Bu Tianming,Qi Qi. Symmetric Bayesian-Nash Equilibrium of Simultaneous Vickrey Auctions with Perfect Substitutes[OL].[ 8 January 2013] http://en.paper.edu.cn/en_releasepaper/content/4509967


	6. Parallel hash function using DM-based integer-valued chaotic maps network
	Liao Dong,Wang Xiaomin
	Computer Science and Technology 10 December 2012
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:A parallel hash function using DM-based integer-valued chaotic maps network is proposed which combines the advantage of both chaotic system and DM scheme. And the algorithm has avoided the flaw of the forgery attack of the exiting parallel hash functions. The algorithm can be used to calculate hash values of 128, 160, 192, 256, 384 and 512 bits with little difference in performance for the different hash values. The message is partitioned into message blocks with fixed length and each message block is processed by the integer-valued chaotic maps network in parallel. The final hash value is generated with a sponge-like construction， which confuses the mixed result of all the outputs of the integer-valued chaotic maps network. The hash function is mainly implemented by extend integer-valued tent maps and can work in a parallel mode, which guarantees good security and high efficiency. Theoretical and simulation results show that the proposed hash algorithm has strong diffusion and confusion capability and good collision resistance. These properties make it a good candidate for hash on platforms that support parallel processing.
	TO cite this article:Liao Dong,Wang Xiaomin. Parallel hash function using DM-based integer-valued chaotic maps network[OL].[10 December 2012] http://en.paper.edu.cn/en_releasepaper/content/4500967


	7. Conditionally Anonymous Ring Signature \ Scheme without Random Oracles
	Zeng Shengke,Qin Zhiguang,Lu Qing
	Computer Science and Technology 08 February 2012
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:Compared to the original ring signature scheme, conditionally anonymous ring signature allows to revoke the anonymity of the actual signer without the group manager's help, i.e., in case of dispute, the actual signer can be traced through signer's confirmation or the non-signers' disavowal. However, the previous conditionally anonymous ring signature schemes rely on random oracles, in the other words, the security of such schemes depend on the randomness of the hash functions. In order to improve the security, this paper proposes a ring signature scheme with traceability without random oracles in the common reference string model.
	TO cite this article:Zeng Shengke,Qin Zhiguang,Lu Qing. Conditionally Anonymous Ring Signature \ Scheme without Random Oracles[OL].[ 8 February 2012] http://en.paper.edu.cn/en_releasepaper/content/4463457


	8. Advanced Framework for Iterative Hash Functions---C-hash
	Zhimin Li,Bo Yang,Lin Li,Shihui Zheng,Yixian Yang,Zhang Zhihui
	Computer Science and Technology 14 November 2007
	Show/Hide Abstract \| Cite this paper︱Full-text: PDF (0 B)

	Abstract:In this paper, we study the cryptanalytical techniques to perform Joux multi-collision, Kelsey and Schneier generic long message second preimage attack and Kelsey and Kohno herding attack on the Merkle-Damgard construction as well as its variants with XOR-linear/additive checksums and propose an advanced Merkle-Damgard construction, C-hash, by changing the feedback addition value, which can add the computation complexity of the generic attacks, compared with Merkle-Damgard construction and its variants.
	TO cite this article:Zhimin Li,Bo Yang,Lin Li, et al. Advanced Framework for Iterative Hash Functions---C-hash[OL].[14 November 2007] http://en.paper.edu.cn/en_releasepaper/content/16347

	Check out RSS, or use RSS reader to subscribe this item