Abstract Partial orders and directed acyclic graphs are commonly recurring data structures that arise naturally in numerous domains and applications and are used to represent ordered relations between entities in the domains. Examples are task dependencies in a project plan, transaction order in distributed ledgers and execution sequences of tasks in computer programs, just to mention a few. We study the problem of order preserving hierarchical clustering of this kind of ordered data. That is, if we have $$a<b$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mi>a</mml:mi><mml:mo><</mml:mo><mml:mi>b</mml:mi></mml:mrow></mml:math> in the original data and denote their respective clusters by [ a ] and [ b ], then we shall have $$[a]<[b]$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mml:mrow><mml:mo>[</mml:mo><mml:mi>a</mml:mi><mml:mo>]</mml:mo><mml:mo><</mml:mo><mml:mo>[</mml:mo><mml:mi>b</mml:mi><mml:mo>]</mml:mo></mml:mrow></mml:math> in the produced clustering. The clustering is similarity based and uses standard linkage functions, such as single- and complete linkage, and is an extension of classical hierarchical clustering. To achieve this, we develop a novel theory that extends classical hierarchical clustering to strictly partially ordered sets. We define the output from running classical hierarchical clustering on strictly ordered data to be partial dendrograms ; sub-trees of classical dendrograms with several connected components. We then construct an embedding of partial dendrograms over a set into the family of ultrametrics over the same set. An optimal hierarchical clustering is defined as the partial dendrogram corresponding to the ultrametric closest to the original dissimilarity measure, measured in the p -norm. Thus, the method is a combination of classical hierarchical clustering and ultrametric fitting. A reference implementation is employed for experiments on both synthetic random data and real world data from a database of machine parts. When compared to existing methods, the experiments show that our method excels both in cluster quality and order preservation.
Mohammed Almukaynizi, Vivin Paliath, Malay Shah, Malav Shah · 5 authors
With the recent prevalence of darkweb/deepweb (D2web) sites specializing in the trade of exploit kits and malware, malicious actors have easy-access to a wide-range of tools that can empower their offensive capability. In this study, we apply concepts from causal reasoning, itemset mining, and logic programming on historical cryptocurrency-related cyber incidents with intelligence collected from over 400 D2web hacker forums. Our goal was to find indicators of cyber threats targeting cryptocurrency traders and exchange platforms from hacker activity. Our approach found interesting activities that, when observed together in the D2web, subsequent cryptocurrency-related incidents are at least twice as likely to occur than they would if no activity was observed. We also present an algorithmic extension to a previously-introduced algorithm called APT-Extract that allows to model new semantic structures that are specific to our application.
We consider natural ways to extend the notion of Zero-Knowledge (ZK) Proofs beyond decision problems. Specifically, we consider search problems, and define zero-knowledge proofs in this context as interactive protocols in which the prover can establish the correctness of a solution to a given instance without the verifier learning anything beyond the intended solution, even if it deviates from the protocol. The goal of this work is to initiate a study of Search Zero-Knowledge (search-ZK), the class of search problems for which such systems exist. This class trivially contains search problems where the validity of a solution can be efficiently verified (using a single message proof containing only the solution). A slightly less obvious, but still straightforward, way to obtain zero-knowledge proofs for search problems is to let the prover send a solution and prove in zero-knowledge that the instance-solution pair is valid. However, there may be other ways to obtain such zero-knowledge proofs, and they may be more advantageous. In fact, we prove that there are search problems for which the aforementioned approach fails, but still search zero-knowledge protocols exist. On the other hand, we show sufficient conditions for search problems under which some form of zero-knowledge can be obtained using the straightforward way.
Abstract We present an efficient method for answering one-dimensional range and closest-point queries in a verifiable and privacy-preserving manner. We consider a model where a data owner outsources a dataset of key-value pairs to a server, who answers range and closest-point queries issued by a client and provides proofs of the answers. The client verifies the correctness of the answers while learning nothing about the dataset besides the answers to the current and previous queries. Our work yields for the first time a zero-knowledge privacy assurance to authenticated range and closest-point queries. Previous work leaked the size of the dataset and used an inefficient proof protocol. Our construction is based on hierarchical identity-based encryption. We prove its security and analyze its efficiency both theoretically and with experiments on synthetic and real data (Enron email and Boston taxi datasets).
Md Samsuzzaman, Mohamed Tahir Hj A Rahman, Mohammad Tariqul Islam, Rahman Rahman · 6 authors
Semantic web offers a smarter web service which synchronizes and arranges all the data over the web in a disciplined pattern. In data mining over the web, accuracy of selecting necessary data as user demand and pick them for output counts as a major key challenge from long ago. Our approach contributes a complete and automatic mapping of data over web3. 0 through ontology and accesses them by intelligent web agent. The agent offers all possible output related to user request, from which user could find desired information. When a user has insufficient data parameters to search, they can gain knowledge from the relational outputs provided by the agent and thus semantic web mining enables unknown knowledge acquisition or discovery. Here, in this paper we briefly illustrate and discuss the architecture of semantic web, then propose a model for web mining to discover knowledge under a framework of agent, and finally discusses the ways, how agent finds out user query related nodes from ontology.
To understand what makes NP-complete problems so hard, I conduct my research through two approaches: construct problem instances and study how badly the solvers work. A simple way to construct SAT instances is to choose a random truth assignment A, and then choose clauses randomly from among those satisfied by A. However, this method tends to produce problems, since the majority of literals point toward the assignment A. Previously, we proposed a problem generator that cancels this effect by hiding both A and its complement A. While the resulting formulas appear to be just as for the Davis-Putnam-Logemann-Loveland (DPLL) algorithms as random 3-SAT formulas with no hidden assignment, they can be solved by WalkSAT in only polynomial time. Here we propose a new method to cancel the attraction to A, by choosing a clause with t > 0 literals satisfied by A with probability proportional to qt for some q < 1. By varying q, we can generate formulas whose variables have no bias, i.e., which are equally likely to be true or false; we can even cause the formula to deceptively point away from A. We present theoretical and experimental results suggesting that these formulas are exponentially both for DPLL algorithms and for incomplete algorithms such as WalkSAT.
Next, we introduce a new application for constructing hard to SAT instances: Negative Databases (NDBs), a strange type of database that only stores records not in the original database. NDBs offer the promise of preserving the confidentiality of the individual records in a database, while permitting certain restricted queries. NDBs have many applications in the field of data security. Constructing an NDB corresponding to a DB is equivalent to constructing a SAT formula with a set of satisfiable truth assignments as its only satisfiable truth assignments. We present a new approach to construct such formulas, and we are able to show that the formula can only be satisfied by the truth assignments that are very close to one of the hidden assignments. We then demonstrate experimentally that the formulas generated by our scheme are much harder to solve than the formulas generated by the previously suggested prefix algorithm and RNDB algorithm[27, 25], and they are indeed enough to ensure security. We hope that this new approach would create interest in constructing SAT formulas as a way to protect the confidentiality of databases.
Finally, to understand how badly the solvers work, we analyze the behavior of two natural variants of DPLL algorithm for Graph 3-Coloring on sparse random graphs G(n, p = c/n). First, we calculate analytically the probability Pc(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c → c* = 3.847... Then we show that even in the easy phase 1 0, including just above the emergence of the giant component, the expected number of backtracks is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring. In addition, we give experimental evidence and heuristic arguments that this tail takes the form Pc(b) ∼ b-1 up to an exponential cutoff.
Many backtracking algorithms exhibit heavy-tailed distributions, in which their running time is often much longer than their median. We analyze the behavior of two natural variants of the Davis-Putnam-Logemann-Loveland (DPLL) algorithm for Graph 3-Coloring on sparse random graphs G(n,p=c/n). Let P_c(b) be the probability that DPLL backtracks b times. First, we calculate analytically the probability P_c(0) that these algorithms find a 3-coloring with no backtracking at all, and show that it goes to zero faster than any analytic function as c \to c^* = 3.847... Then we show that even in the ``easy'' phase 1 < c < c^* where P_c(0) > 0, including just above the emergence of the giant component, the expected number of backtracks is exponentially large with positive probability. To our knowledge this is the first rigorous proof that the running time of a natural backtracking algorithm has a heavy tail for graph coloring. Moreover, our results show that these algorithms take exponential time, not just below the 3-colorability threshold, but just above the degree c=1 at which the giant component first appears. In addition, we give experimental evidence and heuristic arguments that this tail takes the form P_c(b) ~ b^{-1} up to an exponential cutoff.
Alfredo De Santis, Giovanni Di Crescenzo, Oded Goldreich, Giuseppe Persiano
The input to the Graph Clustering Problem consists of a sequence of integers m 1 ; :::; m t and a sequence of P t i=1 m i graphs. The question is whether the equivalence classes, under the graph isomorphism relation, of the input graphs have sizes which match the input sequence of integers. In this note we show that this problem has a (perfect) zero-knowledge interactive proof system. Keywords: Graph Isomorphism, Zero-Knowledge Interactive Proofs. 1 Introduction The remarkable notion of perfect zero-knowledge proofs was introduced by Goldwasser, Micali and Rackoff [GoMiRa]. A perfect zero-knowledge proof system is a method for a prover to convince a polynomial-time bounded verifier with very high probability that a certain assertion is true without revealing any additional information (in an information-theoretic sense). Not many are the languages which have been shown to have a perfect zero-knowledge proof system; in particular, all of them share number-theoretic or random self-red...
The paper presents a more efficient noninteractive zero knowledge proof system (NIZK) for 3 colorability. The length of the proof is 1/3 and the length of the reference string is 1/4 of those of Blum et al. (1988) respectively. The proposed NIZK is based on the quadratic residuosity assumption.>