Algorithm portfolios for noisy optimization

Noisy optimization is the optimization of objective functions corrupted by noise. A portfolio of solvers is a set of solvers equipped with an algorithm selection tool for distributing the computational power among them. Portfolios are widely and successfully used in combinatorial optimization. In this work, we study portfolios of noisy optimization solvers. We obtain mathematically proved performance (in the sense that the portfolio performs nearly as well as the best of its solvers) by an ad hoc portfolio algorithm dedicated to noisy optimization. A somehow surprising result is that it is better to compare solvers with some lag, i.e., propose the current recommendation of best solver based on their performance earlier in the run. An additional finding is a principled method for distributing the computational power among solvers in the portfolio.     

On the performance of MaxSAT and MinSAT solvers on 2SAT-MaxOnes

We analyze and compare two solvers for Boolean optimization problems: WMaxSatz, a solver for Partial MaxSAT, and MinSatz, a solver for Partial MinSAT. Both MaxSAT and MinSAT are similar, but previous results indicate that when solving optimization problems using both solvers, the performance is quite different on some cases. For getting insights about the differences in the performance of the two solvers, we analyze their behaviour when solving 2SAT-MaxOnes problem instances, given that 2SAT-MaxOnes is probably the most simple, but NP-hard, optimization problem we can solve with them. The analysis is based first on the study of the bounds computed by both algorithms on some particular 2SAT-MaxOnes instances, characterized by the presence of certain particular structures. We find that the fraction of positive literals in the clauses is an important factor regarding the quality of the bounds computed by the algorithms. Then, we also study the importance of this factor on the typical case complexity of Random-p 2SAT-MaxOnes, a variant of the problem where instances are randomly generated with a probability p of having positive literals in the clauses. For the case p=0, the performance results indicate a clear advantage of MinSatz with respect to WMaxSatz, but as we consider positive values of p WMaxSatz starts to show a better performance, although at the same time the typical complexity of Random-p 2SAT-MaxOnes decreases as p increases. We also study the typical value of the bound computed by the two algorithms on these sets of instances, showing that the behaviour is consistent with our analysis of the bounds computed on the particular instances we studied first.     

Translation-based approaches for solving disjunctive temporal problems with preferences

Disjunctive Temporal Problems (DTPs) with Preferences (DTPPs) extend DTPs with piece-wise constant preference functions associated to each constraint of the form l ≤ x ? y ≤ u, where x,y are (real or integer) variables, and l,u are numeric constants. The goal is to find an assignment to the variables of the problem that maximizes the sum of the preference values of satisfied DTP constraints, where such values are obtained by aggregating the preference functions of the satisfied constraints in it under a “max” semantic. The state-of-the-art approach in the field, implemented in the native DTPP solver Maxilitis, extends the approach of the native DTP solver Epilitis. In this paper we present alternative approaches that translate DTPPs to Maximum Satisfiability of a set of Boolean combination of constraints of the form l?x ? y?u, ? ∈{<,≤}, that extend previous work dealing with constant preference functions only. We prove correctness and completeness of the approaches. Results obtained with the Satisfiability Modulo Theories (SMT) solvers Yices and MathSAT on randomly generated DTPPs and DTPPs built from real-world benchmarks, show that one of our translation is competitive to, and can be faster than, Maxilitis (This is an extended and revised version of Bourguet et al. 2013).     

Verifiable threshold quantum secret sharing with sequential communication

A (t, n) threshold quantum secret sharing (QSS) is proposed based on a single d-level quantum system. It enables the (t, n) threshold structure based on Shamir’s secret sharing and simply requires sequential communication in d-level quantum system to recover secret. Besides, the scheme provides a verification mechanism which employs an additional qudit to detect cheats and eavesdropping during secret reconstruction and allows a participant to use the share repeatedly. Analyses show that the proposed scheme is resistant to typical attacks. Moreover, the scheme is scalable in participant number and easier to realize compared to related schemes. More generally, our scheme also presents a generic method to construct new (t, n) threshold QSS schemes based on d-level quantum system from other classical threshold secret sharing.     

A novel secret image sharing scheme using large primes

A secret image sharing scheme is any method of distributing shares of a secret image amongst a set of peers, such that the secret may be revealed only with participation of all members of a qualified set of peers. Following Shamir’s (t, n)–threshold scheme, we propose a novel lossy/lossless secret image sharing scheme, that improves existing schemes in terms of security and performance. As opposed to the usual convention of representing a digital image by a collection of 8–bit integer values, we consider 8b–bit values where b is a positive integer. This approach accommodates a larger finite field, which in turn produces a less intrusive secret image sharing scheme. Extensive empirical results are presented to demonstrate the efficiency and robustness of the proposed scheme.     

<Emphasis FontCategory="NonProportional">FEMPAR</Emphasis>: An Object-Oriented Parallel Finite Element Framework

FEMPAR is an open source object oriented Fortran200X scientific software library for the high-performance scalable simulation of complex multiphysics problems governed by partial differential equations at large scales, by exploiting state-of-the-art supercomputing resources. It is a highly modularized, flexible, and extensible library, that provides a set of modules that can be combined to carry out the different steps of the simulation pipeline. FEMPAR includes a rich set of algorithms for the discretization step, namely (arbitrary-order) grad, div, and curl-conforming finite element methods, discontinuous Galerkin methods, B-splines, and unfitted finite element techniques on cut cells, combined with h-adaptivity. The linear solver module relies on state-of-the-art bulk-asynchronous implementations of multilevel domain decomposition solvers for the different discretization alternatives and block-preconditioning techniques for multiphysics problems. FEMPAR is a framework that provides users with out-of-the-box state-of-the-art discretization techniques and highly scalable solvers for the simulation of complex applications, hiding the dramatic complexity of the underlying algorithms. But it is also a framework for researchers that want to experience with new algorithms and solvers, by providing a highly extensible framework. In this work, the first one in a series of articles about FEMPAR, we provide a detailed introduction to the software abstractions used in the discretization module and the related geometrical module. We also provide some ingredients about the assembly of linear systems arising from finite element discretizations, but the software design of complex scalable multilevel solvers is postponed to a subsequent work.     

SCARE and power attack on AES-like block ciphers with secret S-box

Despite Kerckhoff's principle, there are secret ciphers with unknown components for diplomatic or military usages. The side-channel analysis of reverse engineering (SCARE) is developed for analyzing secret ciphers. Considering the side-channel leakage, SCARE attacks enable the recovery of some secret parts of a cryptosystem, e.g., the substitution box table. However, based on idealized leakage assumption, most of these attacks have a few limitations on prior knowledge or implementations. In this paper, we focus on AES-like block ciphers with a secret S-box and demonstrate an attack which recovers both the secret key and the secret S-box. On the one hand, the key is recovered under profiled circumstance by leakage analysis and collision attack. On the other hand, the SCARE attack is based on mathematical analysis. It relies on Hamming weight of MixColumns intermediate results in the first round, which can restore the secret S-box. Experiments are performed on real power traces from a software implementation of AES-like block cipher. Moreover, we evaluate the soundness and efficiency of our method by simulations and compare with previous approaches. Our method has more advantages in intermediate results location and the required number of traces. For simulated traces with gaussian noise, our method requires 100000 traces to fully restore the secret S-box, while the previous method requires nearly 300000 traces to restore S-box.     

Secret sharing approach for securing cloud-based pre-classification volume ray-casting

With the evolution in cloud computing, cloud-based volume rendering, which outsources data rendering tasks to cloud datacenters, is attracting interest. Although this new rendering technique has many advantages, allowing third-party access to potentially sensitive volume data raises security and privacy concerns. In this paper, we address these concerns for cloud-based pre-classification volume ray-casting by using Shamir’s (k, n) secret sharing and its variant (l, k, n) ramp secret sharing, which are homomorphic to addition and scalar multiplication operations, to hide color information of volume data/images in datacenters. To address the incompatibility issue of the modular prime operation used in secret sharing technique with the floating point operations of ray-casting, we consider excluding modular prime operation from secret sharing or converting the floating number operations of ray-casting to fixed point operations – the earlier technique degrades security and the later degrades image quality. Both these techniques, however, result in significant data overhead. To lessen the overhead at the cost of high security, we propose a modified ramp secret sharing scheme that uses the three color components in one secret sharing polynomial and replaces the shares in floating point with smaller integers.     

Visual search tree profiling

Understanding how the search space is explored for a given constraint problem – and how it changes for different models, solvers or search strategies – is crucial for efficient solving. Yet programmers often have to rely on the crude aggregate measures of the search that are provided by solvers, or on visualisation tools that can show the search tree, but do not offer sophisticated ways to navigate and analyse it, particularly for large trees. We present an architecture for profiling a constraint programming search that is based on a lightweight instrumentation of the solver. The architecture combines a visualisation of the search tree with various tools for convenient navigation and analysis of the search. These include identifying repeated subtrees, high-level abstraction and navigation of the tree, and the comparison of two search trees. The resulting system is akin to a traditional program profiler, which helps the user to focus on the parts of the execution where an improvement to their program would have the greatest effect.     

Cryptanalysis of a Type of CRT-Based RSA Algorithms

It is well known that the Chinese Remainder Theorem(CRT)can greatly improve the performances of RSA cryptosystem in both running times and memory requirements.However,if the implementation of CRT-based RSA is careless,an attacker can reveal some secret information by exploiting hardware fault cryptanalysis.In this paper,we present some fault attacks on a type of CRT-RSA algorithms namely BOS type schemes including the original BOS scheme proposed by Bl(?)mer,Otto,and Seifert at CCS 2003 and its modified scheme proposed by Liu et al.at DASC 2006.We first demonstrate that if some special signed messages such as m=0,±1 are dealt carelessly,they can be exploited by an adversary to completely break the security of both the BOS scheme and Liu et al.'s scheme.Then we present a new permanent fault attack on the BOS scheme with a success probability about 25%.Lastly,we propose a polynomial time attack on Liu et al.'s CRT-RSA algorithm,which combines physical fault injection and lattice reduction techniques when the public exponent is short.     

Beyond the structure of SAT formulas

Nowadays, many real-world problems are encoded into SAT instances and efficiently solved by modern SAT solvers. These solvers, usually known as Conflict-Driven Clause Learning (CDCL) SAT solvers, include a variety of sophisticated techniques, such as clause learning, lazy data structures, conflict-based adaptive branching heuristics, or random restarts, among others. However, the reasons of their efficiency in solving real-world, or industrial, SAT instances are still unknown. The common wisdom in the SAT community is that these technique exploit some hidden structure of real-world problems.In this thesis, we characterize some important features of the underlying structure of industrial SAT instances. Namely, they are the community structure and the self-similar structure. We observe that most industrial SAT formulas, viewed as graphs, have these two properties. This means that (i) in a graph with a clear community structure, i.e. having high modularity, we can find a partition of its nodes into communities such that most edges connect nodes of the same community; and (ii) in a graph with a self-similar pattern, i.e. being fractal, its shape is kept after re-scalings, i.e., grouping sets of nodes into a single node. We also analyze how these structures are affected by the effects of CDCL techniques during the search.Using the previous structural studies, we propose three applications. First, we face the problem of generating pseudo-industrial random SAT instances using the notion of modularity. Our model generates instances similar to (classical) random SAT formulas when the modularity is low, but when this value is high, our model is also adequate to model realistic pseudo-industrial problems. Second, we propose a method based on the community structure of the instance to detect relevant learnt clauses. Our technique augments the original instance with this set of relevant clauses, and this results into an overall improvement of the efficiency of several state-of-the-art CDCL SAT solvers. Finally, we analyze the classification of industrial SAT instances into families using the previously analyzed structure features, and we compare them to other classifiers commonly used in portfolio SAT approaches.In summary, this dissertation extends the understandings of the structure of SAT instances, with the aim of better explaining the success of CDCL techniques and possibly improve them, and propose a number of applications based on this analysis of the underlying structure of SAT formulas.     

Restricted (<Emphasis Type="Italic">k</Emphasis>, <Emphasis Type="Italic">n</Emphasis>)-threshold quantum secret sharing scheme based on local distinguishability of orthogonal multiqudit entangled states

In this work, we study a restricted (k, n)-threshold access structure. According to this structure, we construct a group of orthogonal multipartite entangled states in d-dimensional system and investigate the distinguishability of these entangled states under restricted local operations and classical communication. Based on these properties, we propose a restricted (k, n)-threshold quantum secret sharing scheme (called LOCC-QSS scheme). The k cooperating players in the restricted threshold scheme come from all disjoint groups. In the proposed protocol, the participants distinguish these orthogonal states by the computational basis measurement and classical communication to reconstruct the original secret. Furthermore, we also analyze the security of our scheme in three primary quantum attacks and give a simple encoding method in order to better prevent the participant conspiracy attack.     

Computing the Level Set Convex Hull

Quasiconvex (QC) functions are functions whose level sets are convex. The quasiconvex envelope (QCE) of a given function, g, is the maximal QC function below g. The QCE provides a level set representation for the convex hull of every level set of a given function. We present a nonlocal line solver for computing the QCE of a given function. The algorithm is based on solving the one dimensional problem on lines, which can be done by a fast marching or sweeping method. Convergence of the algorithm is established.     

Threshold quantum secret sharing based on single qubit

Based on unitary phase shift operation on single qubit in association with Shamir’s (t, n) secret sharing, a (t, n) threshold quantum secret sharing scheme (or (t, n)-QSS) is proposed to share both classical information and quantum states. The scheme uses decoy photons to prevent eavesdropping and employs the secret in Shamir’s scheme as the private value to guarantee the correctness of secret reconstruction. Analyses show it is resistant to typical intercept-and-resend attack, entangle-and-measure attack and participant attacks such as entanglement swapping attack. Moreover, it is easier to realize in physic and more practical in applications when compared with related ones. By the method in our scheme, new (t, n)-QSS schemes can be easily constructed using other classical (t, n) secret sharing.     

分组密码AES-128的差分故障攻击

AES是美国数据加密标准的简称,又称Rijndael加密算法。它是当今最著名且在商业和政府部门应用最广泛的算法之一。AES有三个版本,分别是AES-128,AES-19和AES-AES的分析是当今密码界的一个热点,文中使用差分故障攻击方法对AES进行分析。差分故障攻击假设攻击者可以给密码系统植入错误并获得正确密文和植入故障后密文,通过对两个密文分析比对从而得到密钥。文中提出了对AES-128的两种故障攻击方法,分别是在第8轮和第7轮的开始注入故障。两个分析方法分别需要2个和4个故障对。数据复杂度分别为2^34（2^112）次猜测密钥。     

Security of a semi-quantum protocol where reflections contribute to the secret key

In this paper, we provide a proof of unconditional security for a semi-quantum key distribution protocol introduced in a previous work. This particular protocol demonstrated the possibility of using X basis states to contribute to the raw key of the two users (as opposed to using only direct measurement results) even though a semi-quantum participant cannot directly manipulate such states. In this work, we provide a complete proof of security by deriving a lower bound of the protocol’s key rate in the asymptotic scenario. Using this bound, we are able to find an error threshold value such that for all error rates less than this threshold, it is guaranteed that A and B may distill a secure secret key; for error rates larger than this threshold, A and B should abort. We demonstrate that this error threshold compares favorably to several fully quantum protocols. We also comment on some interesting observations about the behavior of this protocol under certain noise scenarios.     

Decoherence effect on quantum-memory-assisted entropic uncertainty relations

Uncertainty principle significantly provides a bound to predict precision of measurement with regard to any two incompatible observables, and thereby plays a nontrivial role in quantum precision measurement. In this work, we observe the dynamical features of the quantum-memory-assisted entropic uncertainty relations (EUR) for a pair of incompatible measurements in an open system characterized by local generalized amplitude damping (GAD) noises. Herein, we derive the dynamical evolution of the entropic uncertainty with respect to the measurement affecting by the canonical GAD noises when particle A is initially entangled with quantum memory B. Specifically, we examine the dynamics of EUR in the frame of three realistic scenarios: one case is that particle A is affected by environmental noise (GAD) while particle B as quantum memory is free from any noises, another case is that particle B is affected by the external noise while particle A is not, and the last case is that both of the particles suffer from the noises. By analytical methods, it turns out that the uncertainty is not full dependent of quantum correlation evolution of the composite system consisting of A and B, but the minimal conditional entropy of the measured subsystem. Furthermore, we present a possible physical interpretation for the behavior of the uncertainty evolution by means of the mixedness of the observed system; we argue that the uncertainty might be dramatically correlated with the systematic mixedness. Furthermore, we put forward a simple and effective strategy to reduce the measuring uncertainty of interest upon quantum partially collapsed measurement. Therefore, our explorations might offer an insight into the dynamics of the entropic uncertainty relation in a realistic system, and be of importance to quantum precision measurement during quantum information processing.     

Empirical hardness of finding optimal Bayesian network structures: algorithm selection and runtime prediction

Various algorithms have been proposed for finding a Bayesian network structure that is guaranteed to maximize a given scoring function. Implementations of state-of-the-art algorithms, solvers, for this Bayesian network structure learning problem rely on adaptive search strategies, such as branch-and-bound and integer linear programming techniques. Thus, the time requirements of the solvers are not well characterized by simple functions of the instance size. Furthermore, no single solver dominates the others in speed. Given a problem instance, it is thus a priori unclear which solver will perform best and how fast it will solve the instance. We show that for a given solver the hardness of a problem instance can be efficiently predicted based on a collection of non-trivial features which go beyond the basic parameters of instance size. Specifically, we train and test statistical models on empirical data, based on the largest evaluation of state-of-the-art exact solvers to date. We demonstrate that we can predict the runtimes to a reasonable degree of accuracy. These predictions enable effective selection of solvers that perform well in terms of runtimes on a particular instance. Thus, this work contributes a highly efficient portfolio solver that makes use of several individual solvers.     

Quantum secure two-party computation for set intersection with rational players

Recently, Shi et al. (Phys Rev A 92:022309, 2015) proposed quantum oblivious set member decision protocol where two legitimate parties, namely Alice and Bob, play a game. Alice has a secret k, and Bob has a set \(\{k_1,k_2,\ldots k_n\}\). The game is designed towards testing if the secret k is a member of the set possessed by Bob without revealing the identity of k. The output of the game will be either “Yes” (bit 1) or “No” (bit 0) and is generated at Bob’s place. Bob does not know the identity of k, and Alice does not know any element of the set. In a subsequent work (Shi et al in Quant Inf Process 15:363–371, 2016), the authors proposed a quantum scheme for private set intersection (PSI) where the client (Alice) gets the intersected elements with the help of a server (Bob) and the server knows nothing. In the present draft, we extended the game to compute the intersection of two computationally indistinguishable sets X and Y possessed by Alice and Bob, respectively. We consider Alice and Bob as rational players, i.e. they are neither “good” nor “bad”. They participate in the game towards maximizing their utilities. We prove that in this rational setting, the strategy profile ((cooperate, abort), (cooperate, abort)) is a strict Nash equilibrium. If ((cooperate, abort), (cooperate, abort)) is strict Nash, then fairness and correctness of the protocol are guaranteed.     

VMVC: Verifiable multi-tone visual cryptography

Traditional k out of n threshold visual cryptography scheme is proposed to hide a secret image into n shares, where only k or more shares can visually reveal the secret image. Most of the previous state of art approaches on visual cryptography are almost restricted in processing of binary images as secret, which are inadequate for many applications like securely transmission of medical images(Store and Forward Telemedicine), forensic images etc. In this paper, a new Verifiable Multi-toned Visual Cryptography (VMVC) scheme is proposed to securely transmit the confidential images on web. Proposed approach also provides cheating prevention, since each pixel of shares contains a self embedding verifiable bit for integrity test of that pixel. Many existing approaches are suffering from many unnecessary encryption constraints like random shares, codebook requirement, contrast loss etc, which all are successfully addressed in proposed approach. Some comparisons with previously proposed methods are also made. Experimental results and analysis are used to prove the efficiency of proposed approach.