Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles

We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier. In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize items such as scratch-off cards, similar to those used in lotteries, or even just simple playing cards. The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by “lay-people” and implementable without the use of computers. Research of R. Gradwohl was supported by US-Israel Binational Science Foundation Grant 2002246. Research of M. Naor was supported in part by a grant from the Israel Science Foundation. Research of B. Pinkas was supported in part by the Israel Science Foundation (grant number 860/06). Research of G.N. Rothblum was supported by NSF grant CNS-0430450 and NSF grant CFF-0635297.     

Classification of semantic relations between nominals

The NLP community has shown a renewed interest in deeper semantic analyses, among them automatic recognition of semantic relations in text. We present the development and evaluation of a semantic analysis task: automatic recognition of relations between pairs of nominals in a sentence. The task was part of SemEval-2007, the fourth edition of the semantic evaluation event previously known as SensEval. Apart from the observations we have made, the long-lasting effect of this task may be a framework for comparing approaches to the task. We introduce the problem of recognizing relations between nominals, and in particular the process of drafting and refining the definitions of the semantic relations. We show how we created the training and test data, list and briefly describe the 15 participating systems, discuss the results, and conclude with the lessons learned in the course of this exercise.     

A cost-effective lexical acquisition process for large-scale thesaurus translation

Thesauri and controlled vocabularies facilitate access to digital collections by explicitly representing the underlying principles of organization. Translation of such resources into multiple languages is an important component for providing multilingual access. However, the specificity of vocabulary terms in most thesauri precludes fully-automatic translation using general-domain lexical resources. In this paper, we present an efficient process for leveraging human translations to construct domain-specific lexical resources. This process is illustrated on a thesaurus of 56,000 concepts used to catalog a large archive of oral histories. We elicited human translations on a small subset of concepts, induced a probabilistic phrase dictionary from these translations, and used the resulting resource to automatically translate the rest of the thesaurus. Two separate evaluations demonstrate the acceptability of the automatic translations and the cost-effectiveness of our approach.

DanNet: the challenge of compiling a wordnet for Danish by reusing a monolingual dictionary

This paper is a contribution to the discussion on compiling computational lexical resources from conventional dictionaries. It describes the theoretical as well as practical problems that are encountered when reusing a conventional dictionary for compiling a lexical-semantic resource in terms of a wordnet. More specifically, it describes the methodological issues of compiling a wordnet for Danish, DanNet, from a monolingual basis, and not—as is often seen—by applying the translational expansion method with Princeton WordNet as the English source. Thus, we apply as our basis a large, corpus-based printed dictionary of modern Danish. Using this approach, we discuss the issues of readjusting inconsistent and/or underspecified hyponymy hierarchies taken from the conventional dictionary, sense distinctions as opposed to the synonym sets of wordnets, generating semantic wordnet relations on the basis of sense definitions, and finally, supplementing missing or implicit information.     

Computer-Forensik in der Praxis

Zusammenfassung  Im Zeitalter der Informationstechnologie und der umfassenden Vernetzung vieler Systeme ben?tigt ein Dieb weder eine Brechstange noch muss er im Schutze der Dunkelheit vorgehen. Vielmehr kann er über das Internet, oder lokale Netzwerke, kommen und gehen wann er will, ohne sich der Gefahr einer Entdeckung und Verhaftung auszusetzen. In vielen F?llen ist ein solcher Einbrecher l?ngst über alle Berge, bevor seine Tat überhaupt bemerkt wird. Trotzdem hinterl?sst er Spuren — deren Aufspürung und Analyse die Aufgabe des Computer-Forensikers ist. Zur Unterstützung dieser Arbeit existiert eine Vielzahl an Open-Source-Werkzeugen, die es durchaus mit ihrer kommerziellen Konkurrenz aufnehmen k?nnen.     

Application of maximum entropy principle for reliability-based design optimization

The maximum entropy principle (MEP) is used to generate a natural probability distribution among the many possible that have the same moment conditions. The MEP can accommodate higher order moment information and therefore facilitate a higher quality PDF model. The performance of the MEP for PDF estimation is studied by using more than four moments. For the case with four moments, the results are compared with those by the Pearson system. It is observed that as accommodating higher order moment, the estimated PDF converges to the original one. A sensitivity analysis formulation of the failure probability based on the MEP is derived for reliability-based design optimization (RBDO) and the accuracy is compared with that by finite difference method (FDM). Two RBDO examples including a realistic three-dimensional wing design are solved by using the derived sensitivity formula and the MEP-based moment method. The results are compared with other methods such as TR-SQP, FAMM + Pearson system, FFMM + Pearson system in terms of accuracy and efficiency. It is also shown that an improvement in the accuracy by including more moment terms can increase numerical efficiency of optimization for the three-dimensional wing design. The moment method equipped with the MEP is found flexible and well adoptable for reliability analysis and design.     

An efficient multiobjective differential evolution algorithm for engineering design

Solving engineering design and resources optimization via multiobjective evolutionary algorithms (MOEAs) has attracted much attention in the last few years. In this paper, an efficient multiobjective differential evolution algorithm is presented for engineering design. Our proposed approach adopts the orthogonal design method with quantization technique to generate the initial archive and evolutionary population. An archive (or secondary population) is employed to keep the nondominated solutions found and it is updated by a new relaxed form of Pareto dominance, called Pareto-adaptive ϵ-dominance (paϵ-dominance), at each generation. In addition, in order to guarantee to be the best performance produced, we propose a new hybrid selection mechanism to allow the archive solutions to take part in the generating process. To handle the constraints, a new constraint-handling method is employed, which does not need any parameters to be tuned for constraint handling. The proposed approach is tested on seven benchmark constrained problems to illustrate the capabilities of the algorithm in handling mathematically complex problems. Furthermore, four well-studied engineering design optimization problems are solved to illustrate the efficiency and applicability of the algorithm for multiobjective design optimization. Compared with Nondominated Sorting Genetic Algorithm II, one of the best MOEAs available at present, the results demonstrate that our approach is found to be statistically competitive. Moreover, the proposed approach is very efficient and is capable of yielding a wide spread of solutions with good coverage and convergence to true Pareto-optimal fronts.     

Reliability-based design optimization of problems with correlated input variables using a Gaussian Copula

The reliability-based design optimization (RBDO) using performance measure approach for problems with correlated input variables requires a transformation from the correlated input random variables into independent standard normal variables. For the transformation with correlated input variables, the two most representative transformations, the Rosenblatt and Nataf transformations, are investigated. The Rosenblatt transformation requires a joint cumulative distribution function (CDF). Thus, the Rosenblatt transformation can be used only if the joint CDF is given or input variables are independent. In the Nataf transformation, the joint CDF is approximated using the Gaussian copula, marginal CDFs, and covariance of the input correlated variables. Using the generated CDF, the correlated input variables are transformed into correlated normal variables and then the correlated normal variables are transformed into independent standard normal variables through a linear transformation. Thus, the Nataf transformation can accurately estimates joint normal and some lognormal CDFs of the input variable that cover broad engineering applications. This paper develops a PMA-based RBDO method for problems with correlated random input variables using the Gaussian copula. Several numerical examples show that the correlated random input variables significantly affect RBDO results.     

Stabilization of geometrically nonlinear topology optimization by the Levenberg–Marquardt method

This paper deals with the design of compliant mechanisms in a continuum-based finite-element representation. Because the displacements of mechanisms are intrinsically large, the geometric nonlinearity is essential for designing such mechanisms. However, the consideration of the geometric nonlinearity may cause some instability in topology optimization. The problem is in the analysis part but not in the optimization part. To alleviate the analysis problem and eventually stabilize the optimization process, this paper proposes to apply the Levenberg–Marquardt method to the nonlinear analysis of compliant mechanisms.     

Optimization of dynamic response using a monolithic-time formulation

The design of systems for dynamic response may involve constraints that need to be satisfied over an entire time interval or objective functions evaluated over the interval. Efficiently performing the constrained optimization is challenging, since the typical response is implicitly linked to the design variables through a numerical integration of the governing differential equations. Evaluating constraints is costly, as is the determination of sensitivities to variations in the design variables. In this paper, we investigate the application of a temporal spectral element method to the optimization of transient and time-periodic responses of fundamental engineering systems. Through the spectral discretization, the response is computed globally, thereby enabling a more explicit connection between the response and design variables and facilitating the efficient computation of response sensitivities. Furthermore, the response is captured in a higher order manner to increase analysis accuracy. Two applications of the coupling of dynamic response optimization with the temporal spectral element method are demonstrated. The first application, a one-degree-of-freedom, linear, impact absorber, is selected from the auto industry, and tests the ability of the method to treat transient constraints over a large-time interval. The second application, a related mass-spring-damper system, shows how the method can be used to obtain work and amplitude optimal time-periodic control force subject to constraints over a periodic time interval. This research was performed while the first author held a National Research Council Research Associateship Award at the Air Force Research Laboratory. An early version of this paper was presented at the 46th AIAA Aerospace Sciences Meeting and Exhibit, Jan 7–10, 2008, Reno, Nevada.