Security of meta-He digital signature scheme based on factoring and discrete logarithms

To enhance the security of signature schemes, Pon et al., recently, investigated all eight variants of the He’s digital signature scheme. The security of the proposed schemes is based on the difficulties of simultaneously solving the factoring and discrete logarithm problems with almost the same sizes of arithmetic modulus. This paper shows that the all eight variants of the He’s digital signature scheme, as well as two more variants, are not secure if attackers can solve discrete logarithm problems. Moreover, the attackers can easily forge signatures of the most optimal signature schemes of the generalized He’ signature schemes even though they can solve neither discrete logarithm problems nor factoring.     

Comment on traceability on RSA-based partially signature with low computation

Recently, Chien et al. proposed RSA-based partially blind signature with low computation for mobile and smart-card applications. Hwang et al. claimed that Chien et al.’s scheme cannot meet the untraceability property of the blind signature later. In this paper, we show that Hwang et al.’s claim is incorrect and Chien et al.’s scheme is still satisfy the untraceability property.     

On the discrete logarithm problem for prime-field elliptic curves

In recent years several papers have appeared that investigate the classical discrete logarithm problem for elliptic curves by means of the multivariate polynomial approach based on the celebrated summation polynomials, introduced by Semaev in 2004. With a notable exception by Petit et al. in 2016, all numerous papers on the subject have investigated only the composite-field case, leaving apart the laborious prime-field case. In this paper we propose a variation of Semaev's original approach that reduces to only one the relations to be found among points of the factor base, thus decreasing drastically the necessary Groebner basis computations. Our proposal holds for any finite field but it is particularly suitable for the prime-field case, where it outperforms both the original Semaev's method and the specialised algorithm by Petit et al..     

Some baby-step giant-step algorithms for the low hamming weight discrete logarithm problem

In this paper, we present several baby-step giant-step algorithms for the low hamming weight discrete logarithm problem. In this version of the discrete log problem, we are required to find a discrete logarithm in a finite group of order approximately , given that the unknown logarithm has a specified number of 1's, say , in its binary representation. Heiman and Odlyzko presented the first algorithms for this problem. Unpublished improvements by Coppersmith include a deterministic algorithm with complexity , and a Las Vegas algorithm with complexity

.

We perform an average-case analysis of Coppersmith's deterministic algorithm. The average-case complexity achieves only a constant factor speed-up over the worst-case. Therefore, we present a generalized version of Coppersmith's algorithm, utilizing a combinatorial set system that we call a splitting system. Using probabilistic methods, we prove a new existence result for these systems that yields a (nonuniform) deterministic algorithm with complexity . We also present some explicit constructions for splitting systems that make use of perfect hash families.

     

Slope packings and coverings,and generic algorithms for the discrete logarithm problem

We consider the set of slopes of lines formed by joining all pairs of points in some subset S of a Desarguesian affine plane of prime order p. If all the slopes are distinct and non‐infinite, we have a slope packing; if every possible non‐infinite slope occurs, then we have a slope covering. We review and unify some results on these problems that can be derived from the study of Sidon sets and sum covers. Then we report some computational results, we have obtained for small values of p. Finally, we point out some connections between slope packings and coverings and generic algorithms for the discrete logarithm problem in prime order (sub)groups. Our results provide a combinatorial characterization of such algorithms, in the sense that any generic algorithm implies the existence of a certain slope packing or covering, and conversely. © 2002 Wiley Periodicals, Inc. J Combin Designs 11: 36–50, 2003; Published online in Wiley InterScience ( www.interscience.wiley.com ). DOI 10.1002/jcd.10033     

A new path-based cutting plane approach for the discrete time-cost tradeoff problem

Determining discrete time-cost tradeoffs in project networks allows for the control of the processing time of an activity via the amount of non-renewable resources allocated to it. Larger resource allocations with associated higher costs reduce activities’ durations. Given a set of execution modes (time-cost pairs) for each activity, the discrete time-cost tradeoff problem (DTCTP) involves selecting a mode for each activity so that either: (i) the project completion time is minimized, given a budget, or (ii) the total project cost is minimized, given a deadline, or (iii) the complete and efficient project cost curve is constructed over all feasible project durations. The DTCTP is a problem with great applicability prospects but at the same time a strongly N P{\mathcal N}\,P-hard optimization problem; solving it exactly has been a real challenge. Known optimal solution methodologies are limited to networks with no more than 50 activities and only lower bounds can be computed for larger, realistically sized, project instances. In this paper, we study a path-based approach to the DTCTP, in which a new path-based formulation in activity-on-node project networks is presented. This formulation is subsequently solved using an exact cutting plane algorithm enhanced with speed-up techniques. Extensive computational results reported for almost 5,000 benchmark test problems demonstrate the effectiveness of the proposed algorithm in solving to optimality for the first time some of the hardest and largest instances in the literature. The promising results suggest that the algorithms may be embedded into project management software and, hence, become a useful tool for practitioners in the future.     

基于身份的动态数字签名方案

数字签名是解决信息安全问题的重要途径,用于鉴别用户身份.随着计算机、网络的发展,安全的用户数字签名显得尤为重要.目前,现代的数字签名技术正向智能化、密码化、多因素、大容量和快速响应方向发展.结合数论中的中国剩余定理及RSA公钥体制,提出了一种基于身份的动态数字签名方案.     

A new exact discrete linear reformulation of the quadratic assignment problem

The quadratic assignment problem (QAP) is a challenging combinatorial problem. The problem is NP-hard and in addition, it is considered practically intractable to solve large QAP instances, to proven optimality, within reasonable time limits. In this paper we present an attractive mixed integer linear programming (MILP) formulation of the QAP. We first introduce a useful non-linear formulation of the problem and then a method of how to reformulate it to a new exact, compact discrete linear model. This reformulation is efficient for QAP instances with few unique elements in the flow or distance matrices. Finally, we present optimal results, obtained with the discrete linear reformulation, for some previously unsolved instances (with the size n = 32 and 64), from the quadratic assignment problem library, QAPLIB.     

Improvement on Hwang et al.’s generalization of proxy signature schemes based on elliptic curves

Hwang et al. proposed their generalization of proxy signature schemes based on elliptic curves. However, two attacks are proposed to show that their schemes have serious security flaws. By the first attack, an adversary can forge an illegal proxy signature that verifiers cannot actually find out the original signers of proxy signatures. The second attack is used to change proxy signatures into multi-signatures belonging to the group that actually generates the proxy signatures. To overcome these flaws, our improvement on Hwang et al.’s scheme is also proposed.     

A new discrete chaotic map based on the composition of permutations

In this paper a new one-dimensional discrete chaotic map based on the composition of permutations is presented. Proposed map is defined over finite set and represents fully digital approach which is significantly different from previous ones. Dynamical properties of special case of proposed map are analyzed. Analyzed map does not have fixed points and exhibits chaotic behavior.     

A new Branch and Bound method for a discrete truss topology design problem

Our paper considers a classic problem in the field of Truss Topology Design, the goal of which is to determine the stiffest truss, under a given load, with a bound on the total volume and discrete requirements in the cross-sectional areas of the bars. To solve this problem we propose a new two-stage Branch and Bound algorithm. In the first stage we perform a Branch and Bound algorithm on the nodes of the structure. This is based on the following dichotomy study: either a node is in the final structure or not. In the second stage, a Branch and Bound on the bar areas is conducted. The existence or otherwise of a node in this structure is ensured by adding constraints on the cross-sectional areas of its incident bars. In practice, for reasons of stability, free bars linked at free nodes should be avoided. Therefore, if a node exists in the structure, then there must be at least two incident bars on it, unless it is a supported node. Thus, a new constraint is added, which lower bounds the sum of the cross-sectional areas of bars incident to the node. Otherwise, if a free node does not belong to the final structure, then all the bar area variables corresponding to bars incident to this node may be set to zero. These constraints are added during the first stage and lead to a tight model. We report the computational experiments conducted to test the effectiveness of this two-stage approach, enhanced by the rule to prevent free bars, as compared to a classical Branch and Bound algorithm, where branching is only performed on the bar areas.     

A counterexample to questions on the integrality property of virtual signature

Wall (1961), defined the virtual Euler Characteristic χ(Γ) of an arbitrary group Γ of finite homological type as , where Γ′ is any torsion free subgroup of finite index in Γ. Analogous to virtual Euler Characteristic, we define the Virtual signature of an oriented virtual Poincare Duality group, a rational number. We show that two of Ken Brown's results on questions regarding the integrality property of virtual Euler Characteristics when formulated in the Virtual signature case is false.     

A fixed-point algorithm for blind source separation with nonlinear autocorrelation

This paper addresses blind source separation (BSS) problem when source signals have the temporal structure with nonlinear autocorrelation. Using the temporal characteristics of sources, we develop an objective function based on the nonlinear autocorrelation of sources. Maximizing the objective function, we propose a fixed-point source separation algorithm. Furthermore, we give some mathematical properties of the algorithm. Computer simulations for sources with square temporal autocorrelation and the real-world applications in the analysis of the magnetoencephalographic recordings (MEG) illustrate the efficiency of the proposed approach. Thus, the presented BSS algorithm, which is based on the nonlinear measure of temporal autocorrelation, provides a novel statistical property to perform BSS.     

A new bound for the quadratic assignment problem based on convex quadratic programming

We describe a new convex quadratic programming bound for the quadratic assignment problem (QAP). The construction of the bound uses a semidefinite programming representation of a basic eigenvalue bound for QAP. The new bound dominates the well-known projected eigenvalue bound, and appears to be competitive with existing bounds in the trade-off between bound quality and computational effort. Received: February 2000 / Accepted: November 2000?Published online January 17, 2001     

A discrete method based on distance measure in linguistic space and its application for CMADM problem

ABSTRACT

Owing to the complexity of decision environment, not all the attributes in multiple attribute decision making are quantitative. There are also some qualitative attributes, which are related to the integration of multiple attribute decision making (MADM) and linguistic multiple attribute decision making (LMADM). The specific method for composite multiple attribute decision making (CMADM) problems is crucial for decision maker (DM) to make scientific decision. In this paper, the Technique for Order Preference by Similarity to an Ideal Solution (TOPSIS) method is extended to a Composite Technique for Order Preference by Similarity to an Ideal Solution (CTOPSIS) method to solve the CMADM problems. As the basis of the CTOPSIS method, the distance measure model in linguistic space and in n-dimension linguistic space is generated based on the non-linear mapping. Based on the distance measure in linguistic space, a standard deviation method is taken to get the attribute weight. At the same time, the distance measure models are proposed based on the distance measure in n-dimension linguistic space, which are used to calculate the distance between the alternatives and the positive and negative idea points separately. Furthermore, a CTOPSIS method is generated to solve the CMADM problems. Finally, a numerical example is illustrated to explain the process. And the result shows that the CTOPSIS method is quite practical and more approximate to the real decision making situation.     

InterQuad: An interactive quad tree based procedure for solving the discrete alternative multiple criteria problem

In this paper an interactive procedure based upon a data structure called a quad tree is developed for solving the discrete alternative multiple criteria problem. Called InterQuad, the procedure has been designed with large discrete alternative problems in mind. InterQuad takes advantage of the ability of a quad tree to identify, store, and retrieve nondominated criterion vectors. Then, the user interacts with the nondominated criterion vectors stored in the quad tree in a fashion similar to that of the Combined Tchebycheff/Aspiration Criterion Vector Procedure of Steuer, Silverman and Whisman.     

A modified variable neighborhood search for the discrete ordered median problem

This paper presents a modified Variable Neighborhood Search (VNS) heuristic algorithm for solving the Discrete Ordered Median Problem (DOMP). This heuristic is based on new neighborhoods’ structures that allow an efficient encoding of the solutions of the DOMP avoiding sorting in the evaluation of the objective function at each considered solution. The algorithm is based on a data structure, computed in preprocessing, that organizes the minimal necessary information to update and evaluate solutions in linear time without sorting. In order to investigate the performance, the new algorithm is compared with other heuristic algorithms previously available in the literature for solving DOMP. We report on some computational experiments based on the well-known N-median instances of the ORLIB with up to 900 nodes. The obtained results are comparable or superior to existing algorithms in the literature, both in running times and number of best solutions found.     

A fully discrete stabilized finite-element method for the time-dependent Navier-Stokes problem

A fully discrete stabilized finite-element method is presentedfor the two-dimensional time-dependent Navier–Stokes problem.The spatial discretization is based on a finite-element spacepair (X_h, M_h) for the approximation of the velocity and thepressure, constructed by using the Q₁ – P₀ quadrilateralelement or the P₁ – P₀ triangular element; the time discretizationis based on the Euler semi-implicit scheme. It is shown thatthe proposed fully discrete stabilized finite-element methodresults in the optimal order error bounds for the velocity andthe pressure.     

A Tikhonov regularization method for Cauchy problem based on a new relaxation model

In this paper, we consider a Cauchy problem of recovering both missing value and flux on inaccessible boundary from Dirichlet and Neumann data measured on the remaining accessible boundary. Associated with two mixed boundary value problems, a regularized Kohn-Vogelius formulation is proposed. With an introduction of a relaxation parameter, the Dirichlet boundary conditions are approximated by two Robin ones. Compared to the existing work, weaker regularity is required on the Dirichlet data. This makes the proposed model simpler and more efficient in computation. A series of theoretical results are established for the new reconstruction model. Several numerical examples are provided to show feasibility and effectiveness of the proposed method. For simplicity of the statements, we take Poisson equation as the governed equation. However, the proposed method can be applied directly to Cauchy problems governed by more general equations, even other linear or nonlinear inverse problems.     

A new algorithm for geometric programming based on the linear structure of its dual problem

In this article, we present an algorithm for the resolution of a nonlinear optimization problem, concretely the posynomial geometric programming model. The solution procedure that we develop extends the condensation techniques for geometric programming, allowing us to find the optimal solutions to the dual geometric problems that we get from the interior of the corresponding feasible regions, in the line that interior point methods for linear programming work, which leads us to obtain considerable computational advantages with respect of the classical solution procedures.