7417533
Cryptographically resilient functions
This correspondence studies resilient functions which have applications in fault-tolerant distributed computing, quantum cryptographic key distribution, and random sequence generation for stream ciphers. We present a number of new methods for synthesizing resilient functions. An interesting aspect of these methods is that they are applicable both to linear and nonlinear resilient functions. Our second major contribution is to show that every linear resilient function can be transformed into a large number of nonlinear resilient functions with the same parameters. As a result, we obtain resilient functions that are highly nonlinear and have a high algebraic degree.
3234900
On Algebraic Immunity and Annihilators
Algebraic immunity AI(f) defined for a boolean function f measures the resistance of the function against algebraic attacks. Currently known algorithms for computing the optimal annihilator of f and AI(f) are inefficient. This work consists of two parts. In the first part, we extend the concept of algebraic immunity. In particular, we argue that a function f may be replaced by another boolean function fc called the algebraic complement of f. This motivates us to examine AI(fc). We define the extended algebraic immunity of f as AI*(f)= min {AI(f), AI(fc)}. We prove that 0≤AI(f)–AI*(f)≤1. Since AI(f)–AI*(f)= 1 holds for a large number of cases, the difference between AI(f) and AI*(f) cannot be ignored in algebraic attacks. In the second part, we link boolean functions to hypergraphs so that we can apply known results in hypergraph theory to boolean functions. This not only allows us to find annihilators in a fast and simple way but also provides a good estimation of the upper bound on AI*(f).
1705766
Duality between Two Cryptographic Primitives
This paper reveals a duality between constructions of two basic cryptographic primitives, pseudo-random string generators and one-way hash functions. Applying the duality, we present a construction for universal one-way hash functions assuming the existence of one-way permutations. Under a stronger assumption, the existence of distinction-intractable permutations, we prove that the construction constitutes a collision-intractable hash function. Using ideas behind the construction, we propose practical one-way hash functions, the fastest of which compress nearly 2n-bit long input into n-bit long output strings by applying only twice a one-way function.
910354
Content Extraction Signatures
Motivated by emerging needs in online interactions, we define a new type of digital signature called a 'Content Extraction Signature' (CES). A CES allows the owner, Bob, of a document signed by Alice, to produce an 'extracted signature' on selected extracted portions of the original document, which can be verified (to originate from Alice) by any third party Cathy, without knowledge of the unextracted (removed) document portions. The new signature therefore achieves verifiable content extraction with minimal multi-party interaction. We specify desirable functional and security requirements from a CES (including an efficiency requirement: a CES should be more efficient in either computation or communication than the simple multiple signature solution). We propose and analyse four provably secure CES constructions which satisfy our requirements, and evaluate their performance characteristics.
7069478
An Advantage of Low-Exponent RSA with Modulus Primes Sharing Least Significant Bits
Let N = pq denote an RSA modulus of length n bits. Call N an (m - LSbS) RSA modulus if p and q have exactly m equal Least Significant (LS) bits. In Asiacrypt '98, Boneh, Durfee and Frankel (BDF) described several interesting 'partial key exposure' attacks on the RSA system. In particular, for low public exponent RSA, they show how to recover in time polynomial in n the whole secret-exponent d given only the n=4 LS bits of d. In this note, we relax a hidden assumption in the running time estimate presented by BDF for this attack. We show that the running time estimated by BDF for their attack is too low for (m- LSbS) RSA moduli by a factor in the order of 2m. Thus the BDF attack is intractable for such moduli with large m. Furthermore, we prove a general related result, namely that if low-exponent RSA using an (m - LSbS) modulus is secure against poly-time conventional attacks, then it is also secure against poly-time partial key exposure attacks accessing up to 2m LS bits of d. Therefore, if low-exponent RSA using (n=4(1 - ?) - LSbS) moduli for small ? is secure, then this result (together with BDF's result on securely leaking the n=2 MS bits of d) opens the possibility of fast and secure public-server-aided RSA decryption/signature generation.
10818775
Zheng and Seberry’s public key encryption scheme revisited
In this paper, we prove that a slightly modified version of Zheng and Seberry’s public key encryption scheme presented at Crypto ’92 is secure against adaptive chosen ciphertext attacks in the random oracle model, assuming the Gap Diffie–Hellman problem is intractable. A further contribution of this paper is to show that Soldera, Seberry, and Qu’s recent security analysis of Zheng and Seberry’s scheme is in fact flawed.
7580725
Kosha: A Peer-to-Peer Enhancement for the Network File System
The storage needs of modern scientific applications are growing exponentially, and designing economical storage solutions for such applications – especially in Grid environments – is an important research topic. This work presents Kosha, a system that aims to harvest redundant storage space on cluster nodes and user desktops to provide a reliable, shared file system that acts as a large distributed storage. Kosha utilizes peer-to-peer (p2p) mechanisms to enhance the widely-used Network File System (NFS). P2P storage systems provide location transparency, mobility transparency, load balancing, and file replication – features that are not available in NFS. On the other hand, NFS provides hierarchical file organization, directory listings, and file permissions, which are missing from p2p storage systems. By blending the strengths of NFS and p2p storage systems, Kosha provides a low overhead storage solution. Our experiments show that compared to unmodified NFS, Kosha introduces a 3.3% fixed overhead and 4.5% additional overhead as nodes are increased from two to sixteen. For larger number of nodes, the additional overhead increases slowly. Kosha achieves load balancing in distributed directories, and guarantees $99.99\%$ or better file availability.
18589263
Optimization of MPI collective communication on BlueGene/L systems
BlueGene/L is currently the world's fastest supercomputer. It consists of a large number of low power dual-processor compute nodes interconnected by high speed torus and collective networks, Because compute nodes do not have shared memory, MPI is the the natural programming model for this machine. The BlueGene/L MPI library is a port of MPICH2.In this paper we discuss the implementation of MPI collectives on BlueGene/L. The MPICH2 implementation of MPI collectives is based on point-to-point communication primitives. This turns out to be suboptimal for a number of reasons. Machine-optimized MPI collectives are necessary to harness the performance of BlueGene/L. We discuss these optimized MPI collectives, describing the algorithms and presenting performance results measured with targeted micro-benchmarks on real BlueGene/L hardware with up to 4096 compute nodes.
13603559
A new metric based on extended spatial frequency and its application to DWT based fusion algorithms
A new quantitative metric is proposed to objectively evaluate the quality of fused imagery. The measured value of the proposed metric is used as feedback to a fusion algorithm such that the image quality of the fused image can potentially be improved. This new metric, called the ratio of spatial frequency error (rSFe), is derived from the definition of a previous measure termed ''spatial frequency'' (SF) that reflects local intensity variation. In this work, (1) the concept of SF is first extended by adding two diagonal SFs, then, (2) a reference SF (SF"R) is computed from the input images, and finally, (3) the error SF (SF"E) (subtracting the fusion SF from the reference SF), or the ratio of SF error (rSFe=SF"E/SF"R), is used as a fusion quality metric. The rSFe (which can be positive or negative) indicates the direction of fusion error-over-fused (if rSFe>0) or under-fused (if rSFe<0). Thus, the rSFe value can be back propagated to the fusion algorithm (BP fusion), thereby directing further parameter adjustments in order to achieve a better-fused image. The accuracy of the rSFe is verified with other quantitative measurements such as the root mean square error (RMSE) and the image quality index (IQI), as well as with a qualitative perceptual evaluation based on a standard psychophysical paradigm. An advanced wavelet transform (aDWT) method that incorporates principal component analysis (PCA) and morphological processing into a regular DWT fusion algorithm is implemented with two adjustable parameters-the number of levels of DWT decompositions and the length of the selected wavelet. Results with aDWT were compared to those with a regular DWT and with a Laplacian pyramid. After analyzing several inhomogeneous image groups, experimental results showed that the proposed metric, rSFe, is consistent with RMSE and IQI, and is especially powerful and efficient for realizing the iterative BP fusion in order to achieve a better image quality. Human perceptual assessment was measured and found to strongly support the assertion that the aDWT offers a significant improvement over the DWT and pyramid methods.
16622032
AVP: A Highly Efficient Transport Protocol for Low Bit Rate Multimedia Communications
Utilization of Internet communications in distance learning, distributed simulation, and distributed work groups involves multimedia transmission of animation, voice and video clips. Highly compressed audio-video data protocols are required for efficient Internet multimedia communications. Addressing this requirement, a new transport protocol called Audio-Video Protocol (AVP) for highly efficient multimedia communications on the Internet is presented. While providing similar real-time delivery functions as Real-Time Transport Protocol (RTP) and Real-Time Control Protocol (RTCP), AVP adopts a novel audio-based synchronization scheme. This synchronization scheme has two advantages. One is the overhead reduction through eliminating the timestamp in each transmitted data packet. The other is the packet rate reduction by putting multiple audio frames or mixed audio-video frames in a single AVP packet. As a result, the end-to-end media unit delay is reduced while achieving implicit synchronization. Furthermore, AVP provides adaptive quality of service (QoS) by the prioritized packetization scheme. Simulation results are presented to verify the advantages of the AVP protocol.
8560106
Combined spatial and temporal domain wavelet shrinkage algorithm for video denoising
A combined spatial- and temporal-domain wavelet shrinkage algorithm for video denoising is presented in this paper. The spatial-domain denoising technique is a selective wavelet shrinkage method which uses a two-threshold criteria to exploit the geometry of the wavelet subbands of each video frame, and each frame of the image sequence is spatially denoised independently of one another. The temporal-domain denoising technique is a selective wavelet shrinkage method which estimates the level of noise corruption as well as the amount of motion in the image sequence. The amount of noise is estimated to determine how much filtering is needed in the temporal-domain, and the amount of motion is taken into consideration to determine the degree of similarity between consecutive frames. The similarity affects how much noise removal is possible using temporal-domain processing. Using motion and noise level estimates, a video denoising technique is established which is robust to various levels of noise corruption and various levels of motion.