Search

Numerous works have been proposed to generate random graphs preserving the same properties as real-life large-scale networks. However, many real networks are better represented by hypergraphs. Few models for generating random hypergraphs exist, and also, just a few models allow to both preserve a power-law degree distribution and a high modularity indicating the presence of communities. We present a dynamic preferential attachment hypergraph model which features partition into communities. We prove that its degree distribution follows a power-law, and we give theoretical lower bounds for its modularity. We compare its characteristics with a real-life co-authorship network and show that our model achieves good performances. We believe that our hypergraph model will be an interesting tool that may be used in many research domains in order to reflect better real-life phenomena.

We prove that a class of graphs with an excluded minor and with the maximum degree sublinear in the number of edges is maximally modular, that is, modularity tends to 1 as the number of edges tends to infinity., 7 pages, 1 figure

We consider the best-choice problem for independent (not necessarily iid) observations $X_1, \cdots, X_n$ with the aim of selecting the sample minimum. We show that in this full generality the monotone case of optimal stopping holds and the stopping domain may be defined by the sequence of monotone thresholds. In the iid case we get the universal lower bounds for the success probability. We cast the general problem with independent observations as a variational first-passage problem for the running minimum process which simplifies obtaining the formula for success probability. We illustrate this approach by revisiting the full-information game (where $X_j$'s are iid uniform-$[0,1]$), in particular deriving new representations for the success probability and its limit by $n \rightarrow \infty$. Two explicitly solvable models with discrete $X_j$'s are presented: in the first the distribution is uniform on $\{j,\cdots,n\}$, and in the second the distribution is uniform on $\{1,\cdots, n\}$. These examples are chosen to contrast two situations where the ties vanish or persist in the large-$n$ Poisson limit., Comment: 22 pages, 9 figures

Real numbers from the interval [0, 1] are randomly selected with uniform distribution. There are $n$ of them and they are revealed one by one. However, we do not know their values but only their relative ranks. We want to stop on recently revealed number maximizing the probability that that number is closest to $\frac{1}{2}$. We design an optimal stopping algorithm achieving our goal and prove that its probability of success is asymptotically equivalent to $\frac{1}{\sqrt{n}}\sqrt{\frac{2}{\pi}}$., Comment: 19 pages, 4 figures

We determine the limit of the expected value and the variance of the protection number of the root in simply generated trees, in P?lya trees, and in unlabelled non-plane binary trees, when the number of vertices tends to infinity. Moreover, we compute expectation and variance of the protection number of a randomly chosen vertex in all those tree classes. We obtain exact formulas as sum representations, where the obtained sums are rapidly converging thus allowing an efficient numerical computation of high accuracy.

The following optimal stopping problem is considered. The vertices of a graph $G$ are revealed one by one, in a random order, to a selector. He aims to stop this process at a time $t$ that maximizes the expected number of connected components in the graph $\tilde{G}_t$, induced by the currently revealed vertices. The selector knows $G$ in advance, but different versions of the game are considered depending on the information that he gets about $\tilde{G}_t$. We show that when $G$ has $N$ vertices and maximum degree of order $o(\sqrt{N})$, then the number of components of $\tilde{G}_t$ is concentrated around its mean, which implies that playing the optimal strategy the selector does not benefit much by receiving more information about $\tilde{G}_t$. Results of similar nature were previously obtained by M. Laso\'n for the case where $G$ is a $k$-tree (for constant $k$). We also consider the particular cases where $G$ is a square, triangular or hexagonal lattice, showing that an optimal selector gains $cN$ components and we compute $c$ with an error less than $0.005$ in each case., Comment: 17 pages, 4 figures

The vertices of thekth power of a directed path withnvertices are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already appeared. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). We give upper and lower bounds for the asymptotic behaviour ofpn,kn1/(k+1), wherepn,kis the probability of success under the optimal algorithm. In order to derive the upper bound, we consider a model in which the selector obtains some extra information about the edges that have already appeared. We give the exact asymptotics of the probability of success under the optimal algorithm in this case. In order to derive the lower bound, we analyse a site percolation process on a sequence of thekth powers of a directed path withnvertices.

In our article, we present several protocols that allow to efficiently construct large groups of users based only on local relations of trust. What is more, our approach proves to need only very small computational and communication overhead. Moreover, we give guarantees that a trusted core of the network is defended, even facing a powerful adversary capable of controlling a vast majority of users. This is non-trivial property in real-life networks, as those are usually modelled using preferential attachment graphs, which are extremely prone to attacks on the hub nodes. We show that using our protocols we can achieve similar robustness as Erdős–Renyí graphs, which, on the contrary, are very resistant against attacks focused on chosen nodes. Our protocols have been tested on graphs representing real-world social networks using high performance computing due to the size of the networks. In addition for some protocols, we provided a formal analysis to prove some phenomena in random graphs following power-law distribution, which we use as a network model. Finally, we explicitly demonstrate how our approach can be used to amplify security offered by some privacy-preserving protocols. We believe however that our results can be also seen as a contribution to fundamental observation about the nature of social networks. These results may help to design protocols, whenever it is necessary to gather a big group of users in highly dynamic or even adversarial settings.

One of the most important assumptions in computer security research is that one can permanently delete some data in such a way that no party can retrieve it. In real-life systems this postulate is realized dependently on the specific device used for storing data. In some cases (e.g., magnetic discs) the deletion/erasing is done by overwriting the data to be erased by new one. Many evidence suggest that such procedure may be not sufficient and the attacker armed with advanced microscopic technology is capable in many cases of retrieving data overwritten even many times. In this paper we present a method that provides provable, permanent and irreversible deletion of stored bits based solely on special encoding and processing of data. More precisely the adversary learns nothing about deleted data whp. The security guarantees hold even if the attacker is capable of getting bit-strings overwritten many times. Moreover, in contrast to some previous research, we do not restrict type of data to be deleted.

In many systems privacy of users depends on the number of participants applying collectively some method to protect their security. Indeed, there are numerous already classic results about revealing aggregated data from a set of users. The conclusion is usually as follows: if you have enough friends to "aggregate" the private data, you can safely reveal your private information. Apart from data aggregation, it has been noticed that in a wider context privacy can be often reduced to being hidden in a crowd. Generally, the problems is how to create such crowd. This task may be not easy in some distributed systems, wherein gathering enough "individuals" is hard for practical reasons. Such example are social networks (or similar systems), where users have only a limited number of semi trusted contacts and their aim is to reveal some aggregated data in a privacy preserving manner. This may be particularly problematic in the presence of a strong adversary that can additionally corrupt some users. We show two methods that allow to significantly amplify privacy with only limited number of local operations and very moderate communication overhead. Except theoretical analysis we show experimental results on topologies of real-life social networks to demonstrate that our methods can significantly amplify privacy of chosen aggregation protocols even facing a massive attack of a powerful adversary. We believe however that our results can have much wider applications for improving security of systems based on locally trusted relations., Comment: Submitted to TrustCom2017

We study the problem of hiding communication: while it is easy to encrypt a message sent from Alice to Bob, it is hard to hide that such a communication takes place. Communiaction hiding is one of the fundamental privacy challenges, especially in case of an adversary having a complete view of the traffic and controlling a large number of nodes.

We consider a generalization of the best choice problem to upward directed graphs. We describe a strategy for choosing a maximal element (i.e., an element with no outgoing edges) when a selector knows in advance only the number n of vertices of the graph. We show that, as long as the number of elements dominated directly by the maximal ones is not greater than c 1 n for some positive constant c 1 and the indegree of remaining vertices is bounded by a constant D , the probability p n of the right choice according to our strategy satisfies lim inf n → ∞ p n n ≥ δ > 0 , where δ is a constant depending on c 1 and D .

We examine the evolution of the best choice algorithm and the probability of its success from a directed path to the linear order of the same cardinality through $k$th powers of a directed path, $1 \leq k < n$. The vertices of a $k$th power of a directed path of a known length $n$ are exposed one by one to a selector in some random order. At any time the selector can see the graph induced by the vertices that have already come. The selector's aim is to choose online the maximal vertex (i.e. the vertex with no outgoing edges). It is shown that the probability of success $p_n$ for the optimal algorithm for the $k$th power of a directed path satisfies $p_n = \Theta(n^{-1/(k+1)})$. We also consider the case when the selector knows the distance in the underlying path between each two vertices that are joined by an edge in the induced graph. An optimal algorithm for this choice problem is presented. The exact probability of success when using this algorithm is given.

We propose a ring signature scheme that creates short signatures for large rings. The scheme allows signers to reuse previously created signatures to enlarge the ring size without expanding the size of signature itself. The relation between signatures is a tree structure in which each signature is a node built upon its predecessors. The set of potential signers of a node grows exponentially with the tree height while the size of the signature may remain even constant. We give the specific example of the scheme built on the top of Schnorr ring signatures. We prove its unconditional anonymity and unforgeability in ROM.

In our paper we modify and extend the line of research initiated in CRYPTO 2006 paper ([5]) on preserving privacy in statistical databases. Firstly we present a simpler approach giving the explicit formulas for the sampling probabilities. We show that in most cases our analysis gives substantially better results than those presented in the original paper. Additionaly we outline how the simplified approach can be used for constructing a protocol of privacy preserving sampling distributed databases.

We consider the following online decision problem. The vertices of a directed path are being observed one by one in some random order by a selector. At time t the selector examines the tth vertex and knows the graph induced by the t vertices that have already been examined. The selector’s aim is to choose the currently examined vertex maximizing the probability that it belongs to some prescribed subset of vertices. The optimal stopping time for a subset consisting of the two top vertices is given. For the path of cardinality n the numerical approximation of the probability of the right choice according to the optimal algorithm is given.