Cayley hash functions are a family of cryptographic hash functions constructed from Cayley graphs, with appealing properties such as a natural parallelism and a security reduction to a clean, well-defined mathematical problem. As this problem involves non-Abelian groups, it is a priori resistant to quantum period finding algorithms and Cayley hash functions may therefore be a good foundation for post-quantum cryptography. Four particular parameter sets for Cayley hash functions have been proposed in the past, and so far dedicated preimage algorithms have been found for all of them. These algorithms do however not seem to extend to generic parameters, and as a result it is still an open problem to determine the security of Cayley hash functions in general. In this paper, we study the case of Chiu's Ramanujan graphs. We design a polynomial time preimage attack against the resulting Cayley hash function, showing that these particular parameters like the previous ones are not suitable for the construction. We extend our attacks on hash functions based on similar Cayley graphs as Chiu's Ramanujan graphs. On the positive side, we then suggest some possible ways to construct the Cayley hashes that may not be affected by this type of attacks. Our results contribute to a better understanding of the hard problems underlying the security of Cayley hash functions.

We present a lifting-based lapped transform (L-LT) and a reversible symmetric extension (RSE) in the boundary processing for more effective lossy-to-lossless image coding of data with various qualities from only one piece of lossless compressed data. The proposed dual-DCT-lifting-based LT (D2L-LT) parallel processes two identical LTs and consists of 1-D and 2-D DCT-liftings which allow the direct use of a DCT matrix in each lifting coefficient. Since the DCT-lifting can utilize any existing DCT software or hardware, it has great potential for elegant implementations that are dependent on the architecture and DCT algorithm used. In addition, we present an improved RSE (IRSE) that works by recalculating the boundary processing and solves the boundary problem that the DCT-lifting-based L-LT (DL-LT) has. We show that D2L-LT with IRSE mostly outperforms conventional L-LTs in lossy-to-lossless image coding.

The lifting wavelet transform (WT) has been widely applied to image coding. Recently, the total number of lifting steps has been minimized introducing a non-separable 2D structure so that delay from input to output can be reduced in parallel processing. However the minimum lifting WT has a problem that its upper bound of the rate-distortion curve is lower than that of the standard lifting WT. This is due to the rounding noise generated inside the transform in its integer implementation. This paper reduces the rounding noise introducing channel scaling. The channel scaling is designed so that the dynamic range of signal values is fully utilized at each channel inside the transform. As a result, the signal to noise ratio is increased and therefore the upper bound of the minimum lifting WT in lossy coding is improved.

As three dimensional (3D) discrete wavelet transform (DWT) is widely used for high resolution volumetric data compression, and to further improve the performance of lossless coding, the adaptive directional lifting (ADL) structure based on non-separable 3D DWT with a (5,3) filter is proposed in this paper. The proposed 3D DWT has less lifting steps and better prediction performance compared to the existing separable 3D DWT with fixed filter coefficients. It also has compatibility with the conventional DWT defined by the JPEG2000 international standard. The proposed method shows comparable and better results with the non-separable 3D DWT and separable 3D DWT and it is effective for lossless coding of high resolution volumetric data.

This paper reduces the total number of lifting steps of a two dimensional (2D) discrete wavelet transform (DWT) under the constraint that the DWT has full compatibility with a given separable 2D DWT. In a DWT composed of several lifting steps in cascade, a lifting step must wait for a calculation result of its previous lifting step. Therefore more lifting steps bring about longer latency from the input to the output. In this paper, we reduce the total number of lifting steps of a quadruple lifting DWT which is widely utilized as the 9/7 DWT in the JPEG 2000 international standard for image data compression. Firstly, we introduce basic properties for modification of signal flow structure inside a DWT without changing its output. Secondly, we convert the separable 2D quadruple lifting DWT into the non-separable 2D DWT utilizing the basic properties so that the total number of the lifting steps is reduced. As a result, the lifting steps were reduced to 75[%]. Finally, we evaluate the proposed non-separable 2D DWT in respect of compatibility with the conventional separable 2D DWT.

This paper presents an M-channel (M=2n (n ∈ N)) integer discrete cosine transforms (IntDCTs) based on fast Hartley transform (FHT) for lossy-to-lossless image coding which has image quality scalability from lossy data to lossless data. Many IntDCTs with lifting structures have already been presented to achieve lossy-to-lossless image coding. Recently, an IntDCT based on direct-lifting of DCT/IDCT, which means direct use of DCT and inverse DCT (IDCT) to lifting blocks, has been proposed. Although the IntDCT shows more efficient coding performance than any conventional IntDCT, it entails many computational costs due to an extra information that is a key point to realize its direct-lifting structure. On the other hand, the almost conventional IntDCTs without an extra information cannot be easily expanded to a larger size than the standard size M=8, or the conventional IntDCT should be improved for efficient coding performance even if it realizes an arbitrary size. The proposed IntDCT does not need any extra information, can be applied to size M=2n for arbitrary n, and shows better coding performance than the conventional IntDCTs without any extra information by applying the direct-lifting to the pre- and post-processing block of DCT. Moreover, the proposed IntDCT is implemented with a half of the computational cost of the IntDCT based on direct-lifting of DCT/IDCT even though it shows the best coding performance.

In this paper, we propose a two dimensional (2D) non-separable adaptive directional lifting (ADL) structure for discrete wavelet transform (DWT) and its image coding application. Although a 2D non-separable lifting structure of 9/7 DWT has been proposed by interchanging some lifting, we generalize a polyphase representation of 2D non-separable lifting structure of DWT. Furthermore, by introducing the adaptive directional filteringingto the generalized structure, the 2D non-separable ADL structure is realized and applied into image coding. Our proposed method is simpler than the 1D ADL, and can select the different transforming direction with 1D ADL. Through the simulations, the proposed method is shown to be efficient for the lossy and lossless image coding performance.

This paper presents a new unequal error protection (UEP) image transmission system that incorporates a Lifting Wavelet Transform (LWT) and Reed Solomon (RS) coded cooperation scheme to increase image transmission diversity, as well as save transmission bandwidth. Having a partner to assist direct communication increases the resilience of low frequency subband data against an error-prone fading channel. Low frequency subbands are partitioned into two sets of data and transmitted using the RS coded cooperation scheme. High frequency subbands data are transmitted directly to a base station. Results show that the new UEP image transmission system using LWT based RS coded cooperation scheme achieves diversity gains of around 10 dB, with channel SNR from 10 to 20 dB, compared with the image transmission system with non-cooperative system under slow Rayleigh fading channel for all levels of LWT decomposition. In addition, the new UEP image transmission system using LWT based RS coded cooperation scheme with one level of wavelet decomposition offers around 37.5% bandwidth gain (β), compared with the system without LWT, which incurs a reduction of 3 dB in reconstructed image quality.

In JPEG2000, the Cohen-Daubechies-Feauveau (CDF) 9/7-tap wavelet filter was implemented by using the conventional lifting scheme. However, the filter coefficients remain complex, and the conventional lifting scheme disregards image edges in the coding process. In order to solve these issues, we propose a lifting scheme in two steps. In the first step, we select the appropriate filter coefficients; in the second step, we employ a median operator to regard image edges. Experimental results show that the peak signal-to-noise ratio (PSNR) value of the proposed lifting scheme is significantly improved, by up to 0.75 dB on average, compared to that of the conventional lifting scheme in the CDF 9/7-tap wavelet filter of JPEG2000.

This paper presents a paraunitary filter bank (PUFB) based on a direct lifting structure of a building block and its inverse transform for lossless-to-lossy image coding. Although the conventional lifting-based filter banks (LBFBs), which are constructed by lifting structures with integer coefficients and rounding operations, suffer from degradation of coding performance due to much rounding error generated by cascading lifting structures, our proposals can be applied to any PUFB without losing many ones because building blocks can be applied to every lifting block as it is. It is constructed with very simple structures and many rounding operations are eliminated. Additionally, the number of rounding operations is reduced more by using two-dimensional block transform (2DBT) of separated transform to each building block. As result, even though the proposed PUFBs require a little side information block (SIB), they show better coding performance in lossless-to-lossy image coding than the conventional ones.

Previous vehicle surveillance researches on distributed sensor network focused on overcoming power limitation and communication bandwidth constraints in sensor node. In spite of this constraints, vehicle surveillance sensor node must have signal compression, feature extraction, target localization, noise cancellation and collaborative signal processing with low computation and communication energy dissipation. In this paper, we introduce an algorithm for light-weight wireless sensor node signal processing based on lifting scheme wavelet analysis feature extraction in distributed sensor network.

The line-based method has been one of the most commonly-used methods of hardware implementation of two-dimensional (2D) discrete wavelet transform (DWT). However, data buffer is required between the row DWT processor and the column DWT processor to solve the data flow mismatch, which increases the on-chip memory size and the output latency. Since the incompatible data flow is induced from the intrinsic property of adopted lifting-based algorithm, a decomposed lifting algorithm (DLA) is presented by rearranging the data path of lifting steps to ensure that image data is processed in raster scan manner in row processor and column processor. Theoretical analysis indicates that the precision issue of DLA outperforms other lifting-based algorithms in terms of round-off noise and internal word-length. A memory-efficient and high-performance line-based architecture is proposed based on DLA without the implementation of data buffer. For an N M image, only 2N internal memory is required for 5/3 filter and 4N of that is required for 9/7 filter to perform 2D DWT, where N and M indicate the width and height of an image. Compared with related 2D DWT architectures, the size of on-chip memory is reduced significantly under the same arithmetic cost, memory bandwidth and timing constraint. This design was implemented in SMIC 0.18 µm CMOS logic fabrication with 32 kbits dual-port RAM and 20 K equivalent 2-input NAND gates in a 1.00 mm 1.00 mm die, which can process 512 512 image under 100 MHz.

This paper studies a method for transforming ordinary cryptographic primitives to new harder primitives. Such a method is expected to lead to general schemes that make present cryptosystems secure against the attack of quantum computers. We propose a general technique to construct a new function from an ordinary primitive function f with a help of another hard function g so that the resulting function is to be new hard primitives. We call this technique a lifting of f by g. We show that the lifted function is harder than original functions under some simple conditions.

This paper presents a lifting wavelet coding technique with permutation and coefficient modification processes for coding the structured geometry data of 3-D polygonal mesh model. One promising method for coding 3-D geometry data is based on the structure processing of a 3-D model on a triangle lattice plane, while maintaining connectivity. In the structuring process, each vertex may be assigned to several nodes on the triangular lattice plane. One of the nodes to which a vertex is assigned is selected as a representative node and the others are called expanded nodes. Only the geometry data of the vertices at the representative nodes are required for reconstructing the 3-D model. In this paper we apply a lifting wavelet transform with a permutation process for an expanded node at an even location in each decomposition step and the neighboring representative node. This scheme arranges more representative nodes into the lower frequency band. Also many representative nodes separated from the connective expanded nodes are made to adjoin each other in lower frequency bands, and the correlation between the representative nodes will be reduced by the following decomposition process. A process is added to use the modified coefficients obtained from the coefficients of the adjacent representative nodes instead of the original coefficients in the permutation process. This has the effect of restraining increases in the decomposed coefficients with larger magnitude. Some experiments in which the proposed scheme was applied to structured geometry data of a 3-D model with complex connectivity show that the proposed scheme gives better coding performance and the reconstructed models are more faithful to the original in comparison with the usual schemes.

Two-dimensional discrete wavelet transform (DWT) for processing image is conventionally designed by line-based architectures, which are simple and have low complexity. However, they suffer from two main shortcomings - the memory required for storing intermediate data and the long latency of computing wavelet coefficients. This work presents a new block-based architecture for computing lifting-based 2-D DWT coefficients. This architecture yields a significantly lower buffer size. Additionally, the latency is reduced from N2 down to 3N as compared to the line-based architectures. The proposed architecture supports the JPEG2000 default filters and has been realized in ARM-based ALTERA EPXA10 Development Board at a frequency of 44.33 MHz.

Geometrical properties of the lifting-up technique in support vector machines (SVMs) are discussed here. In many applications, an SVM finds the optimal inhomogeneous separating hyperplane in terms of margins while some of the theoretical analyses on SVMs have treated only homogeneous hyperplanes for simplicity. Although they seem equivalent due to the so-called lifting-up technique, they differ in fact and the solution of the homogeneous SVM with lifting-up strongly depends on the parameter of lifting-up. It is also shown that the solution approaches that of the inhomogeneous SVM in the asymptotic case that the parameter goes to infinity.

This paper presents an efficient VLSI architecture of biorthogonal (9,7)/(5,3) lifting based discrete wavelet transform that is used by lossy or lossless compression of JPEG2000. To improve hardware utilization of RPA (Recursive Pyramid Algorithm) implementation, we make the filter that is responsible for row operations of the first level perform both column operations and row operations of the second and following levels. As a result, the architecture has 66.7-88.9% hardware utilization. It requires 9 multipliers, 12 adders, and 12N line memories for NN image, which is smaller hardware complexity compared to that of other architectures with comparable throughput.

The lifting scheme is an efficient and flexible method for the construction of linear and nonlinear wavelet transforms. In this paper, a novel lossless image coding technique based on the lifting scheme using discrete-time cellular neural networks (DT-CNNs) is proposed. In our proposed method, the image is interpolated by using the nonlinear interpolative dynamics of DT-CNN, and since the output function of DT-CNN works as a multi-level quantization function, our method composes the integer lifting scheme for lossless image coding. Moreover, the nonlinear interpolative dynamics by A-template is used effectively compared with conventional CNN image coding methods using only B-template. The experimental results show a better coding performance compared with the conventional lifting methods using linear filters.

In region-of-interest (ROI) image coding based on wavelet transforms, the tap length of the wavelet filter as well as energy compaction characteristics affect the quality of the restored image. This paper presents a wavelet transform comprised of two wavelet filter sets with different tap lengths. The wavelet filter is switched to the shorter-length set to code a ROI of an image and to the longer-length one for the remaining region, the region of non-interest (RONI). ROI coding examples demonstrate that this switching wavelet transform provides better quality levels than fixed transforms under the same total bits; the quality of the recovered ROI is improved in the lossy coding of both regions while that of the full image is improved in the lossless coding of the ROI.

An efficient VLSI architecture for 1-D lifting DWT is proposed in this paper. To achieve higherhardware utilization and higher throughput, the computations of all resolution levels are folded to both the same high-pass and low-pass filters. Besides, the number of registers in the folded architecture is minimized by using the generalized lifetime analysis. Owing to its regular and flexible structure, the design can be extended easily into different resolution levels, and its area is independent of the length of the 1-D input sequence. Compared with other known architectures, our design requires the least computing time for 1-D lifting DWT.