Computationally Secure Pattern Matching in the Presence of Malicious Adversaries

We propose a protocol for the problem of secure two-party pattern matching, where Alice holds a text t∈{0,1}^? of length n, while Bob has a pattern p∈{0,1}^? of length m. The goal is for Bob to (only) learn where his pattern occurs in Alice’s text, while Alice learns nothing. Private pattern matching is an important problem that has many applications in the area of DNA search, computational biology and more. Our construction guarantees full simulation in the presence of malicious, polynomial-time adversaries (assuming the hardness of DDH assumption) and exhibits computation and communication costs of O(n+m) group elements in a constant round complexity. This improves over previous work by Gennaro et al. (Public Key Cryptography, pp. 145–160, 2010) whose solution requires overhead of O(nm) group elements and exponentiations in O(m) rounds. In addition to the above, we propose a collection of protocols for important variations of the secure pattern matching problem that are significantly more efficient than the current state of art solutions: First, we deal with secure pattern matching with wildcards. In this variant the pattern may contain wildcards that match both 0 and 1. Our protocol requires O(n+m) communication and O(1) rounds using O(nm) computation. Then we treat secure approximate pattern matching. In this variant the matches may be approximated, i.e., have Hamming distance less than some threshold, τ. Our protocol requires O(nτ) communication in O(1) rounds using O(nm) computation. Third, we have secure pattern matching with hidden pattern length. Here, the length, m, of Bob’s pattern remains a secret. Our protocol requires O(n+M) communication in O(1) rounds using O(n+M) computation, where M is an upper bound on m. Finally, we have secure pattern matching with hidden text length. Finally, in this variant the length, n, of Alice’s text remains a secret. Our protocol requires O(N+m) communication in O(1) rounds using O(N+m) computation, where N is an upper bound on n.     

On the Amortized Complexity of Zero-Knowledge Protocols

We propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance x and error probability 2^?n was O(|x|n) bits. By using our technique to prove n instances simultaneously, we can bring down the proof size per instance to O(|x|+n) bits for the same error probability while using no computational assumptions. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, interval proofs of the latter, and proofs of plaintext knowledge for various types of homomorphic encryption schemes. We first propose our protocols as Σ-protocols and extend them later to zero-knowledge proofs of knowledge.     

Efficient local stereo matching algorithm based on fast gradient domain guided image filtering

Guided image filtering (GIF) based cost aggregation or disparity refinement stereo matching algorithms are studied extensively owing to the edge-aware preserved smoothing property. However, GIF suffers from halo artifacts in sharp edges and shows high computational costs on high-resolution images. The performance of GIF in stereo matching would be limited by the above two defects. To solve these problems, a novel fast gradient domain guided image filtering (F-GDGIF) is proposed. To be specific, halo artifacts are effectively alleviated by incorporating an efficient multi-scale edge-aware weighting into GIF. With this multi-scale weighting, edges can be preserved much better. In addition, high computational costs are cut down by sub-sampling strategy, which decreases the computational complexity from O(N) to O(N/s²) (s: sub-sampling ratio) To verify the effectiveness of the algorithm, F-GDGIF is applied to cost aggregation and disparity refinement in stereo matching algorithms respectively. Experiments on the Middlebury evaluation benchmark demonstrate that F-GDGIF based stereo matching method can generate more accuracy disparity maps with low computational cost compared to other GIF based methods.     

Adaptive proportional fairness resource allocation for OFDM-based cognitive radio networks

In this paper, we study the resource allocation problem in multiuser Orthogonal Frequency Division Multiplexing (OFDM)-based cognitive radio networks. The interference introduced to Primary Users (PUs) is fully considered, as well as a set of proportional rate constraints to ensure fairness among Secondary Users (SUs). Since it is extremely computationally complex to obtain the optimal solution because of integer constraints, we adopt a two-step method to address the formulated problem. Firstly, a heuristic subchannel assignment is developed based on the normalized capacity of each OFDM subchannel by jointly considering channel gain and the interference to PUs, which approaches a rough proportional fairness and removes the intractable integer constraints. Secondly, for a given subchannel assignment, we derive a fast optimal power distribution algorithm that has a complexity of O(L ² N) by exploiting the problem’s structure, which is much lower than standard convex optimization techniques that generally have a complexity of O((N + K)³), where N, L and K are the number of subchannels, PUs and SUs, respectively. We also develop a simple power distribution algorithm with complexity of only O(L + N), while achieving above 90 % sum capacity of the upper bound. Experiments show that our proposed algorithms work quite well in practical wireless scenarios. A significant capacity gain is obtained and the proportional fairness is satisfied perfectly.     

Variable Step Size Affine Projection Algorithm for Adaptive Multiuser DS-CDMA MMSE Receiver

In this paper, we consider the use of affine projection algorithm (APA) for interference suppression in direct sequence code-division multiple-access (DS-CDMA) system. We first derive the multiuser fixed step-size APA (FSS-APA) algorithm. The computational complexity offered by the APA algorithm is linear in terms of the number of taps with additional terms of O (L ²) and a matrix inversion of dimension L, where L is known as the order of the filter. The value of L is chosen very small as compared to the number of filter-taps N _T . We next propose a novel variable step-size APA (VSS-APA) algorithm, which further improves the performance of the FSS-APA algorithm with very small increase in computational complexity as compared to the FSS-APA. It is demonstrated that the performance of the APA based minimum mean-square error (MMSE) receivers is far superior to that of the normalized least-mean-square (NLMS) based receivers. Though, the recursive-least-square (RLS) algorithm based adaptive receivers offer better performance but at the cost of much higher computational complexity.     

A Fast Algorithm for Wave Propagation from a Plane or a Cylindrical Surface

The newly developed Taylor-Interpolation-FFT (TI-FFT) algorithm dramatically increases the computational speeds for millimeter wave propagation from a planar (cylindrical) surface onto a “quasi-planar” (“quasi-cylindrical”) surface. Two different scenarios are considered in this article: the planar TI-FFT is for the computation of the wave propagation from a plane onto a “quasi-planar” surface and the cylindrical TI-FFT is for the computation of wave propagation from a cylindrical surface onto a “quasi-cylindrical” surface. Due to the use of the FFT, the TI-FFT algorithm has a computational complexity of O(N ²?log₂? N ²) for an N?×?N computational grid, instead of N ⁴ for the direct integration method. The TI-FFT algorithm has a low sampling rate according to the Nyquist sampling theorem. The algorithm has accuracy down to ?80 dB and it works particularly well for narrow-band fields and “quasi-planar” (“quasi-cylindrical”) surfaces.     

Quadri-directional searching algorithm for secret image sharing using meaningful shadows

Contrary to conventional protecting data such as cryptographic techniques which encrypt the data with a secret key, secret sharing takes an approach to ensure well protection of transmitted information by allowing a secret message M to be divided into n pieces. Secret message M can be held by n participants to avoid the secret from incidentally or intentionally being lost. In a secret sharing scheme, secret information leaks from shadows, attack on shadow image, and large shadow image issues which has arisen when developing an algorithm. Although existing algorithms provide remedies for such problems, the computational complexity of existing algorithms is still questionable. Therefore, we propose a low computational complexity Quadri-Directional Searching Algorithm (QDSA) for secret image sharing. Experiment results show that the proposed algorithm ensures that generated shares are of high quality and no secret information is leaked from these shares, thus it guarantees high security of our scheme.     

A new adaptive recursive RLS-based fast-array IIR filter for active noise and vibration control systems

Infinite impulse response filters have not been used extensively in active noise and vibration control applications. The problems are mainly due to the multimodal error surface and instability of adaptive IIR filters used in such applications. Considering these, in this paper a new adaptive recursive RLS-based fast-array IIR filter for active noise and vibration control applications is proposed. At first an RLS-based adaptive IIR filter with computational complexity of order O(n²) is derived, and a sufficient condition for its stability is proposed by applying passivity theorem on the equivalent feedback representation of this adaptive algorithm. In the second step, to reduce the computational complexity of the algorithm to the order of O(n) as well as to improve its numerical stability, a fast array implementation of this adaptive IIR filter is derived. This is accomplished by extending the existing results of fast-array implementation of adaptive FIR filters to adaptive IIR filters. Comparison of the performance of the fast-array algorithm with that of Erikson’s FuLMS and SHARF algorithms confirms that the proposed algorithm has faster convergence rate and ability to reach a lower minimum mean square error which is of great importance in active noise and vibration control applications.     

A pixel-based regularization approach to inverse lithography

Inverse lithography attempts to synthesize the input mask which leads to the desired output wafer pattern by inverting the forward model from mask to wafer. In this article, we extend our earlier framework for image prewarping to solve the mask design problem for coherent, incoherent, and partially coherent imaging systems. We also discuss the synthesis of three variants of phase shift masks (PSM); namely, attenuated (or weak) PSM, 100% transmission PSM, and strong PSM with chrome. A new two-step optimization strategy is introduced to promote the generation and placement of assist bar features. The regularization framework is extended to guarantee that the estimated PSM have only two or three (allowable) transmission values, and the aerial-image penalty term is introduced to boost the aerial image contrast and keep the side-lobes under control. Our approach uses the pixel-based mask representation, a continuous function formulation, and gradient-based iterative optimization techniques to solve the inverse problem. The continuous function formulation allows analytic calculation of the gradient in O(MNlog (MN)) operations for an M × N pattern making it practically feasible. We also present some results for coherent and incoherent imaging systems with very low k₁ values to demonstrate the effectiveness of our approach.     

Analysis of Millimeter Wave Scattering by the Infinite Plane Metallic Grating Using PCG-FFT Technique

In this paper, both fast Fourier transformation (FFT) and preconditioned CG technique are introduced into method of lines (MOL) to further enhance the computational efficiency of this semi-analytic method. Electromagnetic wave scattering by an infinite plane metallic grating is used as the examples to describe its implementation. For arbitrary incident wave, Helmholz equation and boundary condition are first transformed into new ones so that the impedance matrix elements are calculated by FFT technique. As a result, this Topelitz impedance matrix only requires O(N) memory storage for the conjugate gradient FFT method to solve the current distribution with the computational complexity O(N log N) . Our numerical results show that circulate matrix preconditioner can speed up CG-FFT method to converge in much smaller CPU time than the banded matrix preconditioner.     

Accelerating near-field 3D imaging approach for joint high-resolution imaging and phase error correction

The computational complexity and memory requirements of large-scale data seriously affect the application of compressed sensing (CS) in near-field three-dimensional (3-D) imaging system. In addition, as influenced by the measurement environment, the error in echo phase results in imaging defocusing. This paper proposes a CS near-field 3-D imaging approach based on nonuniform fast Fourier transform and phase error correction. It applies the fast Gaussian gridding nonuniform fast Fourier transform technique and Separable Surrogate Functionals with only matrix and vector multiplied to accelerate imaging speed and reduce memory requirements; it adopts the phase error correction technique to realize highly-focused imaging; in addition, a sparse observation approach based on Logistic sequence is proposed in this paper for easy availability of engineering realization for CS imaging. As indicated by numerical analysis and actual measurement in anechoic chamber, the approach proposed in this paper, compared with traditional imaging approaches, has the following advantages: accurate high resolution 3-D image of target can be obtained by applying small amount of observation data (10%); the computational complexity falls from O(LN) to O(3N) and memory occupation quantity drops from O(LN) to O(N); it can effectively perform highly-focused imaging for echo signal with phase error; the measurement matrix designed has better non-coherence and easy availability for engineering realization.

     

Graph Coloring Applied to Secure Computation in Non-Abelian Groups

We study the natural problem of secure n-party computation (in the computationally unbounded attack model) of circuits over an arbitrary finite non-Abelian group (G,?), which we call G-circuits. Besides its intrinsic interest, this problem is also motivating by a completeness result of Barrington, stating that such protocols can be applied for general secure computation of arbitrary functions. For flexibility, we are interested in protocols which only require black-box access to the group G (i.e. the only computations performed by players in the protocol are a group operation, a group inverse, or sampling a uniformly random group element). Our investigations focus on the passive adversarial model, where up to t of the n participating parties are corrupted. Our results are as follows. We initiate a novel approach for the construction of black-box protocols for G-circuits based on k-of-k threshold secret-sharing schemes, which are efficiently implementable over any black-box (non-Abelian) group G. We reduce the problem of constructing such protocols to a combinatorial coloring problem in planar graphs. We then give three constructions for such colorings. Our first approach leads to a protocol with optimal resilience t<n/2, but it requires exponential communication complexity $O({\binom{2 t+1}{t}}^{2} \cdot N_{g})$ group elements and round complexity $O(\binom{2 t + 1}{t} \cdot N_{g})$ , for a G-circuit of size N _g . Nonetheless, using this coloring recursively, we obtain another protocol to t-privately compute G-circuits with communication complexity $\mathcal{P}\mathit{oly}(n)\cdot N_{g}$ for any t∈O(n ^1?? ) where ? is any positive constant. For our third protocol, there is a probability δ (which can be made arbitrarily small) for the coloring to be flawed in term of security, in contrast to the first two techniques, where the colorings are always secure (we call this protocol probabilistic, and those earlier protocols deterministic). This third protocol achieves optimal resilience t<n/2. It has communication complexity O(n ^5.056(n+log?δ ^?1)²?N _g ) and the number of rounds is O(n ^2.528?(n+log?δ ^?1)?N _g ).     

Sliding window adaptive SVD using the unsymmetric householder partial compressor

A fast algorithm for tracking the rank-r SVD-approximant Q(t)P(t)U^T(t) of a sliding window data matrix X(t) of dimension L×N is introduced, where P(t) is a square-root power matrix of dimension r×r with r<min{L,N}. This algorithm is based on the unsymmetric Householder partial compressor and uses a reorthonormalizing Householder transformation for downdating. The concept is numerically self-stabilizing and requires no leakage. The dominant complexity is 4Lr+3Nr multiplications per time update which is the lower bound in complexity for an algorithm of this kind. Applications occur in the area of adaptive array processing and other forms of adaptive processing in finite duration subspaces. A complete algorithm summary is provided. Computer simulations illustrate the operation of the algorithm.     

Fast Array Multichannel 2D-RLS Based OFDM Channel Estimator

In this paper a Fast Array Multichannel Two-Dimensional Recursive Least Square (FAM 2D-RLS) adaptive filter is proposed for estimating an OFDM channel in frequency domain. This filter makes use of the shift structure of the input data vector. Thus the computational cost of the classical RLS filter which is O(M ²) is reduced to O(M) for each iteration where M is the order of the filter. In order to ensure numerical stability in finite precision, we make use of array-based methods for implementing FAM 2D-RLS. The adaptive filters illustrated in the standard literature consist of a weight vector and desired data as a scalar. But in our scenario of OFDM channel estimation the weight is a matrix while the desired data are a vector. Hence the algorithm for the matrix form of FAM-2D RLS and its steady state equations are derived. Numerical stability, steady state and convergence performance are verified using MATLAB simulations.     

Improved TDM switching assignments for variable and fixed burst length

In this paper we present two algorithms for improved satellite‐switched TDM slot assignments of N × N traffic matrices under K transponders/carriers (simultaneous connections), 1?K?N. The first algorithm applies to data switching with variable burst length and achieves optimum transmission time with a significantly lower number of switching configurations than a previously proposed algorithm, while still having the same time complexity (O(N⁴)). Experimental results demonstrate the advantage. The second algorithm applies to the case of fixed burst length and offers a faster complexity of O(L·N²), where L is the minimum transmission time, at the cost of occasionally missing the minimum. Extensive simulations indicate that the difference from the minimum is rare and is at most one. They also show that the presented algorithm even improves a previous one which was proposed for the fixed burst length case and has the same time complexity but uses K=N. Copyright © 2006 John Wiley & Sons, Ltd.     

A Magnetoresistance Induced by a Nonzero Berry Phase in GeTe/Sb2Te3 Chalcogenide Superlattices

The chalcogenide alloy Ge–Sb–Te (GST) has not only been used in rewritable digital versatile discs, but also in nonvolatile electrical phase change memory as a key recording material. Although GST has been believed for a long time not to show magnetic properties unless doped with magnetic impurities, it has recently been reported that superlattices (SLs) with the structure [(GeTe)_L(Sb₂Te₃)_M]_N (where L, M, and N are usually integers) have a large magnetoresistance at room temperature for particular combinations of L and M. Here it is reported that when [(GeTe)_L(Sb₂Te₃)_M]_N chalcogenide SL films are thermally annealed at 470 K and cooled down to room temperature under an external magnetic field accompanied by current pulse injections, a large magnetoresistance change (>2500 Ω) is induced. This study shows that the phenomenon has a strong correlation with the GeTe thickness and the periodic structure of the SL films, and that it is induced by the structural phase transition between electrically nonpolar and polar phases in the GeTe layers in the SLs. This study proposes that the relationship between the polar (ferroelectric) phase and the Berry curvature in the SLs is responsible for the magnetoresistance change.     

结合Fourier变换对称性和随机多分辨率奇异值分解的彩色图像加密

提出一种基于Fourier变换对称性和随机多分辨率奇异值分解(R-MRSVD)的彩色图像加密算法。首先计算归一化明文图像的平均值作为logistic-exponent-sine映射的初值,并生成随机矩阵和位置索引;然后对每个颜色通道分别进行二维离散Fourier变换,根据共轭对称性仅保留一半的频谱系数,并提取实部分量和虚部分量构建实数矩阵;最后对实数矩阵进行R-MRSVD和Josephus置乱操作,得到密文图像。将明文图像的像素特征作为混沌序列的初值,保证算法具有高敏感性和高安全性,同时实值的密文便于存储和传输。对算法的解密图像质量、统计特性、密钥敏感性、抗选择明文攻击、鲁棒性等性能进行测试,仿真结果表明,所提加密算法具有可行性和安全性。     

一种基于新超混沌Chen系统的置乱替代相结合的加密算法

随着多元化媒介和数字化信息网络的急速发展,数码形象加密技术在图形形象的安全保存、传达输送、著作权保护和秘密通信等领域被普遍推广应用。针对现有基于超级混沌的图像加密算法的缺点,提出了一种改进算法,该算法对像素加扰进行优化配置,通过像素置换和加密文本扩散过程,进一步混乱明文图像与加密文本图像的关联效应,从而能缩短超级混沌系统的迭代时间。研究结果表明加密后直方图的像素值分布均匀;密文之间的NPCR值和UACI值分别为99.6521%和33.4321%,表明算法对加密密钥的微小改变具有极强的敏感性;在新超混沌序列量化模式中引入该方法可有效提高操作效率,且该算法无论在安全方面还是有效运用方面都具备良好性能,可在图像安全通信和其他领域广泛使用。     

Operational behaviour of a complex system with two out of M failed components

In this paper, the behaviour of a Complex System comprised of two classes of Components (L₁ and L₂) has been evaluated. Class L₁ consists of N components connected in series in which the failure of anyone component completely breaks down the system as a whole. Class L₂ consists of M identical components connected in parallel redundancy. The system works in a state of reduced efficiency when two out of M components of the class fail. Supplementary Variable Technique and Laplace Transforms have been used to obtain the solution.