Search

In this paper we present some new complexity results on the routing time of a graph under the routing via matching model. This is a parallel routing model which was introduced by Alon et al. [1]. The model can be viewed as a communication scheme on a distributed network. The nodes in the network can communicate via matchings (a step), where a node exchanges data (pebbles) with its matched partner. Let G be a connected graph with vertices labeled from \(\{1,...,n\}\) and the destination vertices of the pebbles are given by a permutation \(\pi \). The problem is to find a minimum step routing scheme for the input permutation \(\pi \). This is denoted as the routing time \(rt(G,\pi )\) of G given \(\pi \). In this paper we characterize the complexity of some known problems under the routing via matching model and discuss their relationship to graph connectivity and clique number. We also introduce some new problems in this domain, which may be of independent interest.

We construct an indistinguishability obfuscation IO scheme for all polynomial-size circuits from constant-degree graded encoding schemes, assuming the existence of a subexponentially secure pseudo-random generator computable by constant-degree arithmetic circuits, and the subexponential hardness of the Learning With Errors LWE problems. Previously, all candidate general purpose IO schemes rely on polynomial-degree graded encoding schemes.

Secret sharing schemes allow a dealer to distribute a secret piece of information among several parties such that only qualified subsets of parties can reconstruct the secret. The collection of qualified subsets is called an access structure. The best known example is the k-threshold access structure, where the qualified subsets are those of size at least k. When $$k=2$$k=2 and there are n parties, there are schemes where the size of the share each party gets is roughly $$\log n$$logn bits, and this is tight even for secrets of 1 bit. In these schemes, the number of parties n must be given in advance to the dealer. In this work we consider the case where the set of parties is not known in advance and could potentially be infinite. Our goal is to give the $${t}^{th}$$tth party arriving the smallest possible share as a function of t. Our main result is such a scheme for the k-threshold access structure where the share size of party t is $$k-1\cdot \log t + \mathsf {poly}k\cdot o\log t$$k-1i¾?logt+polyki¾?ologt. For $$k=2$$k=2 we observe an equivalence to prefix codes and present matching upper and lower bounds of the form $$\log t + \log \log t + \log \log \log t + O1$$logt+loglogt+logloglogt+O1. Finally, we show that for any access structure there exists such a secret sharing scheme with shares of size $$2^{t-1}$$2t-1.

A public-key encryption scheme is k-circular secure if a cycle ofi¾?k encrypted secret keys $$\mathsf {Enc} _{pk_{1}}sk_{2}, \mathsf {Enc} _{pk_{2}}sk_{3}, \ldots , \mathsf {Enc} _{pk_{k}}sk_{1}$$ is indistinguishable from encryptions of zeros. Circular security has applications in a wide variety of settings, ranging from security of symbolic protocols to fully homomorphic encryption. A fundamental question is whether standard security notions like IND-CPA/CCA imply k-circular security. For the case $$k=2$$, several works over the past years have constructed counterexamples--i.e., schemes that are CPA or even CCA secure but not 2-circular secure--under a variety of well-studied assumptions SXDH, decision linear, and LWE. However, for $$k > 2$$ the only known counterexamples are based on strong general-purpose obfuscation assumptions. In this work we construct k-circular security counterexamples for any $$k \ge 2$$ based on ring-LWE. Specifically:for any constant $$k=O1$$, we construct a counterexample based on n-dimensional plain LWE for $$\mathrm{poly}n$$ approximation factors;for any $$k=\mathrm{poly}\lambda $$, we construct one based on degree-n ring-LWE for at most subexponential $$\exp n^{\varepsilon }$$ factors. Moreover, both schemes are $$k'$$-circular insecure for $$2 \le k' \le k$$. Notably, our ring-LWE construction does not immediately translate to an LWE-based one, because matrix multiplication is not commutative. To overcome this, we introduce a new "tensored" variant of LWE which provides the desired commutativity, and which we prove is actually equivalent to plain LWE.

We show how to construct efficient, unconditionally secure non-malleable codes for bounded output locality. In particular, our scheme is resilient against functions such that any output bit is dependent on at most $$n^{\delta }$$ni¾? bits, where n is the total number of bits in a codeword and $$0\le \delta < 1$$0≤i¾?

We show that homomorphic evaluation of any non-trivial functionality of sufficiently many inputs with respect to any CPA secure homomorphic encryption scheme cannot be implemented by circuits of polynomial size and constant depth, i.e., in the class $$\mathrm {AC}^0$$ . In contrast, we observe that there exist ordinary public-key encryption schemes of quasipolynomial security in $$\mathrm {AC}^0$$ assuming noisy parities are exponentially hard to learn. We view this as evidence that homomorphic evaluation is inherently more complex than basic operations in encryption schemes.

Given a graph G cellularly embedded on a surface Σ of genus g, a cut graph is a subgraph of G such that cutting Σ along G yields a topological disk. We provide a fixed parameter tractable approximation scheme for the problem of computing the shortest cut graph, that is, for any e > 0, we show how to compute a (1 + e) approximation of the shortest cut graph in time f(e, g)n3.

Iterated Even-Mansour scheme IEM is a generalization of the basic 1-round proposal ASIACRYPT '91. The scheme can use one key, two keys, or completely independent keys. Most of the published security proofs for IEM against relate-key and chosen-key attacks focus on the case where all the round-keys are derived from a single master key. Whereas results beyond this barrier are relevant to the cryptographic problem whether a secure blockcipher with key-size twice the block-size can be built by mixing two relatively independent keys into IEM and iterating sufficiently many rounds, and this strategy actually has been used in designing blockciphers for a long-time. This work makes the first step towards breaking this barrier and considers IEM with Interleaved Double independent round-keys: $$\begin{aligned} \text {IDEM}_rk_1,k_2,m=k_i\oplus P_r\ldots k_1\oplus P_2k_2\oplus P_1k_1\oplus m\ldots , \end{aligned}$$ where $$i=2$$ when r is odd, and $$i=1$$ when r is even. As results, this work proves that 15 rounds can achieve full indifferentiability from an ideal cipher with $$O{q^{8}}/{2^n}$$ security bound. This work also proves that 7 rounds is sufficient and necessary to achieve sequential-indifferentiability a notion introduced at TCC 2012 with $$O{q^{6}}/{2^n}$$ security bound, so that $$\text {IDEM}_{7}$$ is already correlation intractable and secure against any attack that exploits evasive relations between its input-output pairs.

We present a $$\lg n + 2 \lg \lg n+3$$ ancestry labeling scheme for trees. The problem was first presented by Kannan et al. [STOC 88'] along with a simple $$2 \lg n$$ solution. Motivated by applications to XML files, the label size was improved incrementally over the course of more than 20 years by a series of papers. The last, due to Fraigniaud and Korman [STOC 10'], presented an asymptotically optimal $$\lg n + 4 \lg \lg n+O1$$ labeling scheme using non-trivial tree-decomposition techniques. By providing a framework generalizing interval based labeling schemes, we obtain a simple, yet asymptotically optimal solution to the problem. Furthermore, our labeling scheme is attained by a small modification of the original $$2 \lg n$$ solution.

In this paper, we construct a fully homomorphic encryption (FHE) scheme over integers with the message space \(\mathbb {Z}_Q\) for any prime \(Q\). Even for the binary case \(Q=2\), our decryption circuit has a smaller degree than that of the previous scheme; the multiplicative degree is reduced from \(O(\lambda (\log \lambda )^2)\) to \(O(\lambda )\), where \(\lambda \) is the security parameter. We also extend our FHE scheme to a batch FHE scheme.

The finite element (FE) method has become the standard numerical calculation scheme for the computer simulation of physical systems [1, 2, 3].

Motivated by the goal of securely searching and updating distributed data, we introduce and study the notion of function secret sharing (FSS). This new notion is a natural generalization of distributed point functions (DPF), a primitive that was recently introduced by Gilboa and Ishai (Eurocrypt 2014). Given a positive integer \(p\ge 2\) and a class \(\mathcal F\) of functions \(f:\{0,1\}^n\rightarrow \mathbb G\), where \(\mathbb G\) is an Abelian group, a \(p\)-party FSS scheme for \(\mathcal F\) allows one to split each \(f\in \mathcal F\) into \(p\) succinctly described functions \(f_i:\{0,1\}^n\rightarrow \mathbb G\), \(1\le i\le p\), such that: (1) \(\sum _{i=1}^p f_i=f\), and (2) any strict subset of the \(f_i\) hides \(f\). Thus, an FSS for \(\mathcal F\) can be thought of as method for succinctly performing an “additive secret sharing” of functions from \(\mathcal F\). The original definition of DPF coincides with a two-party FSS for the class of point functions, namely the class of functions that have a nonzero output on at most one input.

Cylindrical algebraic decomposition (CAD) is a fundamental tool in computational real algebraic geometry and has been implemented in several software. While existing implementations are all based on Collins’ projection-lifting scheme and its subsequent ameliorations, the implementation of CAD in the RegularChains library is based on triangular decomposition of polynomial systems and real root isolation of regular chains. The function in the RegularChains library for computing CAD is called CylindricalAlgebraicDecompose. In this paper, we illustrate by examples the functionality, the underlying theory and algorithm, as well the implementation techniques of CylindricalAlgebraicDecompose. An application of it is also provided.

This work is devoted to the definition of stochastic subdivision schemes adapted to the reconstruction of non-regular data. These schemes are constructed in the framework of the Kriging theory. Thanks to the introduction of a zone-dependent error variance in the Kriging approach, they combine interpolatory and non interpolatory subdivision schemes according to a domain segmentation. Their originality relies on the introduction and coupling of three ingredients: a segmentation of the data, a local prediction according to the characteristics of the different zones and an adaption strategy near segmentation points. The convergence of the corresponding 4-point scheme is analyzed. Its behavior is compared with other subdivision schemes on various numerical experiments.

At Crypto 2013, Coron, Lepoint, and Tibouchi (CLT) proposed a practical Graded Encoding Scheme (GES) over the integers, which has very similar cryptographic features to ideal multilinear maps. In fact, the scheme of Coron et al. is the second proposal of a secure GES, and has advantages over the first scheme of Garg, Gentry, and Halevi (GGH). For example, unlike the GGH construction, the subgroup decision assumption holds in the CLT construction. Immediately following the elegant innovations of the GES, numerous GES-based cryptographic applications were proposed. Although these applications rely on the security of the underlying GES, the security of the GES has not been analyzed in detail, aside from the original papers produced by Garg et al. and Coron et al.

In the classical experimental design setting, an experimenter E has access to a population of $n$ potential experiment subjects $i\in \{1,...,n\}$, each associated with a vector of features $x_i\in R^d$. Conducting an experiment with subject $i$ reveals an unknown value $y_i\in R$ to E. E typically assumes some hypothetical relationship between $x_i$'s and $y_i$'s, e.g., $y_i \approx \beta x_i$, and estimates $\beta$ from experiments, e.g., through linear regression. As a proxy for various practical constraints, E may select only a subset of subjects on which to conduct the experiment. We initiate the study of budgeted mechanisms for experimental design. In this setting, E has a budget $B$. Each subject $i$ declares an associated cost $c_i >0$ to be part of the experiment, and must be paid at least her cost. In particular, the Experimental Design Problem (EDP) is to find a set $S$ of subjects for the experiment that maximizes $V(S) = \log\det(I_d+\sum_{i\in S}x_i\T{x_i})$ under the constraint $\sum_{i\in S}c_i\leq B$; our objective function corresponds to the information gain in parameter $\beta$ that is learned through linear regression methods, and is related to the so-called $D$-optimality criterion. Further, the subjects are strategic and may lie about their costs. We present a deterministic, polynomial time, budget feasible mechanism scheme, that is approximately truthful and yields a constant factor approximation to EDP. In particular, for any small $\delta > 0$ and $\epsilon > 0$, we can construct a (12.98, $\epsilon$)-approximate mechanism that is $\delta$-truthful and runs in polynomial time in both $n$ and $\log\log\frac{B}{\epsilon\delta}$. We also establish that no truthful, budget-feasible algorithms is possible within a factor 2 approximation, and show how to generalize our approach to a wide class of learning problems, beyond linear regression.

We investigate adjacency labeling schemes for graphs of bounded degree $\Delta = O(1)$. In particular, we present an optimal (up to an additive constant) $\log n + O(1)$ adjacency labeling scheme for bounded degree trees. The latter scheme is derived from a labeling scheme for bounded degree outerplanar graphs. Our results complement a similar bound recently obtained for bounded depth trees [Fraigniaud and Korman, SODA 10], and may provide new insights for closing the long standing gap for adjacency in trees [Alstrup and Rauhe, FOCS 02]. We also provide improved labeling schemes for bounded degree planar graphs. Finally, we use combinatorial number systems and present an improved adjacency labeling schemes for graphs of bounded degree $\Delta$ with $(e+1)\sqrt{n} < \Delta \leq n/5$.

We present and analyze a splitting numerical scheme for two non-linear models of mathematical finance. Each of the problems is split into two parts: a hyperbolic equation solved numerically by using a flux limiter technique and a parabolic equation computed by implicit-explicit finite difference scheme. We show that the presented splitting numerical schemes are convergent and positivity preserving. Numerical results are also discussed.

We investigate the common recursive structure of history-dependent dynamic models in science and engineering. We give formal semantics in terms of a hybrid algebraic–coalgebraic scheme, namely course-of-value iteration. This theoretical approach yields categories of observationally equivalent model representations with precise semantic relationships. Along the initial–final axis of these categories, history dependence can appear both literally and transformed into instantaneous state. The framework can be connected to philosophical and epistemological discourse on one side, and to algorithmic considerations for computational modeling on the other.

We analyze an implicit discretization scheme for a class of linear-quadratic optimal control problems without mixed state-control terms. Under the assumption that the optimal control has bang-bang structure we show convergence of the discrete approximation and improve existing error estimates to order \(\mathcal {O}(h)\).

Density functional theory (DFT) has become the leading method in computing the electronic structures and properties from first principles. Its foundation was laid on Hohenberg-Kohn theorems, which proved that there exists a one-to-one correspondence between the ground state electron density ρ0 of a many-body system and its total energy. In practice, DFT is most frequently applied in the framework of Kohn–Sham (KS) scheme, where an approximate exchange-correlation functional has to be chosen. Hence, the success of a DFT calculation critically depends on the quality of the exchange-correlation functional. In this chapter, we first briefly discuss the Hohenberg-Kohn theorems (Sect. 1.1). After introducing the KS scheme, various approximations for the exchange-correlation functionals are presented in Sect. 1.2. These functionals are grouped according to Perdew’s classification of Jacob’s ladder. Finally, some general trends for the functional performances along the Jacob’s ladder are outlined.

In this paper, we propose the Method of Particular Solutions for Solving a Class of Nonlinear Reaction-Diffusion Equations using collocation points and approximating the solution using multiquadrics (MQ) and the Thin Plate Splines (TPS) Radial Basis Function (RBF). The scheme works in a similar fashion as finite-difference methods. The results of numerical experiments are presented, and are compared with analytical solutions to confirm the good accuracy of the presented scheme.

We are interested in monoids and its applications. If every element x in a monoid has a quasi-inverse y in the sense of von Neumann, that satisfies x ·y ·x = x and y ·x ·y = y, the monoid is regular. Our purpose is to use regular monoids to build two abstract algebraic public key cryptosystems: key exchange protocol and public key encryption with keyword search scheme. In addition to illustrating how the two cryptosystems work, we provide instances of these abstract algebraic models and analyse them in terms of cryptanalysis security.

Research on two-order partial differential equation tends to be mature. This paper takes initial-boundary problem of dispersive equation for example. I have followed the way of other scholars and created new methods and got two eight-point difference schemes. I have calculated and contracted their truncation errors and analyzed their stability analysis. Based on the unstable difference scheme, the Matlab program is obtained by the algorithm. Although one of the schemes is unstable, it created a new way and solution for the high-order difference equations theoretically.

We present an analysis of Wiesner’s quantum money scheme, as well as some natural generalizations of it, based on semidefinite programming. For Wiesner’s original scheme, it is determined that the optimal probability for a counterfeiter to create two copies of a bank note from one, where both copies pass the bank’s test for validity, is (3/4) n for n being the number of qubits used for each note. Generalizations in which other ensembles of states are substituted for the one considered by Wiesner are also discussed, including a scheme recently proposed by Pastawski, Yao, Jiang, Lukin, and Cirac, as well as schemes based on higher dimensional quantum systems. In addition, we introduce a variant of Wiesner’s quantum money in which the verification protocol for bank notes involves only classical communication with the bank. We show that the optimal probability with which a counterfeiter can succeed in two independent verification attempts, given access to a single valid n-qubit bank note, is \((3/4+\sqrt{2}/8)^n\). We also analyze extensions of this variant to higher-dimensional schemes.

Sample compression schemes are schemes for “encoding” a set of examples in a small subset of examples. The long-standing open sample compression conjecture states that, for any concept class \(\mathcal{C}\) of VC-dimension d, there is a sample compression scheme in which samples for concepts in \(\mathcal{C}\) are compressed to samples of size at most d.

At CHES 2011 Goubin and Martinelli described a new countermeasure against side-channel analysis for AES based on Shamir's secret-sharing scheme. In the present paper, we exhibit a flaw in this scheme and we show that it is always theoretically broken by a first-order side-channel analysis. As a consequence of this attack, only a slight adaptation of the scheme proposed by Ben-Or et al.at STOC in 1988 can securely process multiplications on data shared with Shamir's technique. In the second part of this paper, we propose an improvement of this scheme that leads to a complexity ${\cal \tilde O}(d^2)$ instead of ${\cal O}(d^3)$, where d is the number of shares per data.

The finite differences scheme for finding a numerical solution of the parabolic equation with double nonlinearity is suggested. For this purpose a special auxiliary problem having some advantages over the main problem is introduced. Some properties of the numerical solution are studied and using the advantages of the proposed auxiliary problem, the convergence of the numerical solution to the exact solution in the sense of mean is proven.

We reconsider the balloon popping problem, an intriguing combinatorial problem introduced in order to bound the competitiveness of ascending auctions with anonymous bidders with respect to the best fixed-price scheme. Previous works show that the optimal solution for this problem is in the range (1.6595,2). We give a new lower bound of $$1.68$$ 1.68 and design an $$O(n^5)$$ O ( n 5 ) algorithm for computing upper bounds as a function of the number of bidders $$n$$ n . Our algorithm provides an experimental evidence that the correct upper bound is a constant smaller than $$2$$ 2 , thus disproving a currently believed conjecture, and can be used to test the validity of a new conjecture we propose, according to which the upper bound would decrease to $$\pi ^2/6+1/4\approx 1.8949$$ ? 2 / 6 + 1 / 4 ? 1.8949 .

In this paper we propose a novel way to construct a diffeomorphic polyaffine model. Each affine transform is defined on a local region and the resulting diffeomorphism encapsulates all the local transforms by a smooth and invertible displacement field. Compared with traditional weighting schemes used in combining local transforms, our new scheme guarantees that the resulting transform precisely preserves the value of each local affine transform. By introducing the trajectory of local regions instead of using regions themselves, the new approach encodes precisely each local affine transform using a diffeomorphism with one or more stationary velocity fields. Experiments show that our new polyaffine model is both accurate and efficient.

In this paper we present a locally one-dimensional LOD splitting method to the two-dimensional Black-Scholes equation, arising in the Hull & White model for pricing European options with stochastic volatility. The parabolic equation degenerates on the boundary xi¾?=i¾?0 and we apply to the one-dimensional subproblems the fitted finite-volume difference scheme, proposed in [8], in order to resolve the degeneration. Discrete maximum principle is proved and therefore our method is positivity-preserving. Numerical experiments are discussed.

One of the means to implement information flow policies is by using a cryptographic approach commonly referred to as key assignment schemes. In this approach, information is made publicly available to users but in an encrypted form. Then, keys are assigned to users such that each key reveals a specified part of the information. Usually the distribution of keys follows a predefined scheme that specifies the ability of users to reveal information. In this paper, we present an algebraic approach based on idempotent commutative semirings to define, specify, and analyse key assignment schemes. Then, we illustrate its usage on two key assignment schemes selected from the literature. Also, we propose amendments to the studied schemes to extend their scopes. The proposed generic algebraic approach enables the verification of security properties at an abstract level in systems that use key assignment schemes. The verification takes into consideration the algebraic properties of schemes, and the considered relationships among the assigned keys. Then, it enables the verification of the secrecy properties of the system through algebraic calculations. All the calculations can be automated using a theorem prover such as Prover9.

This Letter focuses on the function projective synchronization (FPS) of hyperchaotic Liu system and the hyperchaotic New Lorenz system. Within the two systems, we achieved the FPS at the first place through a proper control scheme. Furthermore, by designing the parameter update law, the adaptive function projective synchronization (AFPS) is also achieved. Several numerical simulations are presented to show the feasibility and effectiveness of the method.

The paper presents an O *(1.2312 n )-time and polynomial-space algorithm for the traveling salesman problem in an n-vertex graph with maximum degree 3. This improves the previous time bound for this problem. Our algorithm is a simple branch-and-search algorithm. The only branch rule is designed on a cut-circuit structure of a graph induced by unprocessed edges. To improve a time bound by a simple analysis on measure and conquer, we introduce an amortization scheme over the cut-circuit structure by defining the measure of an instance to be the sum of not only weights of vertices but also weights of connected components of the induced graph.

Survey. The main goal of the Algebraic Approach is the design of a unified scheme for the representation of objects for the purposes of their recognition and the transformation of such representations in the suitable algebraic structures. It makes possible to develop corresponding regular structures ready for analysis by algebraic, geometrical and topological techniques. Development of this line of image analysis and pattern recognition is of crucial importance for automated image mining and application problems solving. It is selected and briefly characterized main aspects of current state of the image analysis algebraization. Special attention is paid to the recent results of the Russian mathematical school.

Inner-product encryption (IPE) provides fine-grained access control and has attractive applications. Agrawal, Freeman, and Vaikuntanathan (Asiacrypt 2011) proposed the first IPE scheme from lattices by twisting the identity-based encryption (IBE) scheme by Agrawal, Boneh, and Boyen (Eurocrypt 2010). Their IPE scheme supports inner-product predicates over R μ , where the ring is R = ℤ q . Several applications require the ring R to be exponentially large and, thus, they set q = 2O(n) to implement such applications. This choice results in the AFV IPE scheme with public parameters of size \(O(\mu n^2 \lg^3{q}) = O(\mu n^5)\) and ciphertexts of size \(O(\mu n \lg^3{q}) = O(\mu n^4)\), where n is the security parameter. Hence, this makes the scheme impractical, as they noted.

We propose a new encryption primitive called Membership Encryption. Let \(\mathcal{P}(\mathbf{G})\) be a privacy-preserving token on a group attribute/identity G, such that given \(\mathcal{P}(\mathbf{G})\) it is hard to know the attributes in G. In this membership encryption, if an encryption takes as input an attribute A and the token \(\mathcal{P}(\mathbf{G})\), the decryption requires holding the membership A ∈ G, i.e., A belongs to this group attribute. Membership encryption is applicable in constructing membership proof \(A\in\mathcal{P}(\mathbf{G})\) with privacy preserving on group attribute and the membership. Membership encryption can be also utilized to construct an efficient two-round K-out-of-N oblivious transfer protocol. In this paper, we construct a provably secure membership encryption where the group token \(\mathcal{P}(\mathbf{G})\) is constant-size with maximum number accountability on attributes. Using our scheme, the proposed oblivious transfer protocol exhibits the nice feature of O(1) communication cost for any K from receiver to sender, and O(N) communication cost from sender to receiver.

In this paper, we propose a numerical scheme to solve a kind of the nonlinear telegraph equation by using the Kansa’s method with Radial Basis Functions (RBFs). From the numerical results of experiments presented in this paper, we can get that the accuracy between the numerical solutions and the analytical solutions are valid. In this paper, we also give the analysis of the parameter c in IMQ radical basis function for the results.

A second order finite volume scheme for numerical solution of Maxwell’s equations with discontinuous dielectric permittivity on prismatic meshes is suggested. The scheme is based on the approaches of Godunov, Lax-Wendoff and Van Leer. The key feature of the scheme is gradient calculation and limitation that guarantee approximation even near dielectric permittivity discontinuities. Numerical tests confirm second order of approximation of the proposed scheme.

A boundary value problem for singularly perturbed differential-difference equation with turning point is considered. Some a priori estimates are obtained on the solution and its derivatives. In general, to tackle such type of problems one encounters three difficulties: (i) due to presence of the turning point, (ii) due to presence of terms containing shifts and (iii) due to presence of the singular perturbation parameter. Due to presence of the singular perturbation parameter the classical numerical methods fail to give reliable numerical results and do not converge uniformly with respect to the singular perturbation parameter. In this paper a parameter uniform finite difference scheme is constructed to solve the boundary-value problem. A parameter uniform error estimate for the numerical scheme so constructed is established. Numerical experiments are carried out to demonstrate the efficiency of the numerical scheme and support the theoretical estimates.

We propose an adaptive finite element method to approximate the solutions to reaction-diffusion systems on time-dependent domains and surfaces. We derive a computable error estimator that provides an upper bound for the error in the semidiscrete (space) scheme. We reconcile our theoretical results with benchmark computations.

In this chapter, we first give a quick review of superconvergence analysis in Sect. 5.1. Then we carry out the superclose analysis for 3-D metamaterial Maxwell’s equations represented by the Drude model. The analysis for a semi-discrete scheme is presented in Sect. 5.2, which is followed by the analysis for two fully-discrete schemes in Sect. 5.3. In Sect. 5.4, a superconvergence result in the discrete l 2 norm is proved. Finally, the superconvergence analysis is extended to the 2-D case in Sect. 5.5.

At first, a difference scheme is obtained for the diffusion equation without source. The difference scheme with high-order and unconditional stability is got by the analysis of the truncation error. Then, the scheme is also achieved for the diffusion equation with source. Finally, the effectiveness of the scheme is verified by using the numerical experiments.

Two different types of generalized Lax-Friedrichs scheme for the convective-diffusion equation ut+aux=euxx( a∈R, e>0) are given and analyzed. For the convection term, both of two schemes use generalized Lax-Friedrichs scheme. For the diffusion term, explicit central difference scheme is used. The propagation of chequerboard mode is considered for two schemes and several numerical examples are presented only for the first scheme , which display how different parameters control oscillations. For low and high frequency modes, applying discrete Fourier analysis , some results have been obtained about stability condition of schemes, and clarify the reasons of oscillations and the interrelation among the amplitude error.

This paper investigates the security of RSA system with short exponents. Let N=pq be an RSA modulus with balanced primes p and q. Denote the public exponent by e and the private exponent by d. Then e and d satisfy ed−1=kφ(N), which is usually called the RSA equation. When e and d are both short, and parameter k is the smallest unknown variable in RSA equation, we prove that there exist two new square root attacks. One attack applies the baby-step giant-step method, the other applies the Pollard's ρ method. We show that if K is a known upper bound of k, then k can be recovered in time $\tilde{O}(\sqrt{K})$ and memory $\tilde{O}(\sqrt{K})$ by using the baby-step giant-step method, and in time $\tilde{O}(\sqrt{K})$ and negligible memory by applying Pollard ρ method. As an application of our new attacks, we present the cryptanalysis on an RSA-type scheme proposed by Sun et al.

Monotone iterative scheme is developed for weakly coupled system of Riemann-Liouville fractional differential equation with integral boundary condition using the method of lower and upper solutions. Two monotone convergent sequences converging to extremal solutions are obtained. Existence and uniqueness of solution of weakly coupled system of Riemann-Liouville fractional differential equations with integral boundary conditions is obtained by applying monotone iterative scheme.

The survey of the various augmented spherical wave (ASW) method starts with an outline of the standard scheme. Within the framework of density functional theory and the (semi-)local approximations it allows for both fast and conceptually simple calculations of the ground state properties of solids. On an introductory level this chapter follows the natural sequence of a self-consistency cycle as usually performed in first principles calculations and explains the main steps comprising the calculation of the basis functions, the electron density, and the effective potential.

Frames have become the field of active research, both in theory and in applications. In the work, the notion of quarter- nary affine pseudoframes is introduced and the notion of a quart-ernary generalized multiresolution structure (GMRS) is introduced. An approach for designing one GMRS of Paley-Wiener subspaces of L 2 (R 4) is provided. The sufficient condition for the existence of a sort of affine pseudoframes with filter banks is obtained by virtue of a generalized multiresolution structure. The pyramid decomposition scheme is obtained based on such a generalized multiresolution structure. A method for designing a sort of affine quarternary dual frames in four-imensional space is proposed.

A ring signature [1] demonstrates that the signer who produced it is among a group A of n people, called a ring. A signer may produce a ring signature on any ring A he is part of, arbitrarily without any setup procedure or the consent of anyone in A. Several extensions of ring signatures have been proposed in literature. Step out ring signatures introduced in [2] address the issue of a ring member proving that she is not the original signer of a message, in case of dispute. First we show that the scheme in [2] has several flaws and design a correct scheme and prove formally the security of the same. Then we use the basic constructs of our scheme to design a protocol for a new problem, which we refer to as threshold discernible ring signatures. In threshold discernible ring signatures, a group B of t members can co-operate to identify the original signer of a ring signature that involved a group A of n alleged signers, where B ⊆ A and n ≥ t. This is the first time that this problem is considered in the literature. We formally prove the security of our scheme in the random oracle model and propose various extensions.

This chapter gives more of the important properties of morphisms, and explains scheme theoretic images, finiteness conditions and the “Sorite”.