Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCombinatorial Solutions Providing Improved Security for the Generalized Russian Cards Problem
134
0
0.0
(
0
)
Added by
Colleen Swanson
Publication date
2012
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We present the first formal mathematical presentation of the generalized Russian cards problem, and provide rigorous security definitions that capture both basic and extend
rate research
Read More
In the generalized Russian cards problem, we have a card deck $X$ of $n$ cards and three participants, Alice, Bob, and Cathy, dealt $a$, $b$, and $c$ cards, respectively. Once the cards are dealt, Alice and Bob wish to privately communicate their hands to each other via public announcements, without the advantage of a shared secret or public key infrastructure. Cathy should remain ignorant of all but her own cards after Alice and Bob have made their announcements. Notions for Cathys ignorance in the literature range from Cathy not learning the fate of any individual card with certainty (weak $1$-security) to not gaining any probabilistic advantage in guessing the fate of some set of $delta$ cards (perfect $delta$-security). As we demonstrate, the generalized Russian cards problem has close ties to the field of combinatorial designs, on which we rely heavily, particularly for perfect security notions. Our main result establishes an equivalence between perfectly $delta$-secure strategies and $(c+delta)$-designs on $n$ points with block size $a$, when announcements are chosen uniformly at random from the set of possible announcements. We also provide construction methods and example solutions, including a construction that yields perfect $1$-security against Cathy when $c=2$. We leverage a known combinatorial design to construct a strategy with $a=8$, $b=13$, and $c=3$ that is perfectly $2$-secure. Finally, we consider a variant of the problem that yields solutions that are easy to construct and optimal with respect to both the number of announcements and level of security achieved. Moreover, this is the first method obtaining weak $delta$-security that allows Alice to hold an arbitrary number of cards and Cathy to hold a set of $c = lfloor frac{a-delta}{2} rfloor$ cards. Alternatively, the construction yields solutions for arbitrary $delta$, $c$ and any $a geq delta + 2c$.
The problem of $A$ privately transmitting information to $B$ by a public announcement overheard by an eavesdropper $C$ is considered. To do so by a deterministic protocol, their inputs must be correlated. Dependent inputs are represented using a deck of cards. There is a publicly known signature $(a,b,c)$, where $n = a + b + c + r$, and $A$ gets $a$ cards, $B$ gets $b$ cards, and $C$ gets $c$ cards, out of the deck of $n$ cards. Using a deterministic protocol, $A$ decides its announcement based on her hand. Using techniques from coding theory, Johnson graphs, and additive number theory, a novel perspective inspired by distributed computing theory is provided, to analyze the amount of information that $A$ needs to send, while preventing $C$ from learning a single card of her hand. In one extreme, the generalized Russian cards problem, $B$ wants to learn all of $A$s cards, and in the other, $B$ wishes to learn something about $A$s hand.
The $ell$-deck of a graph $G$ is the multiset of all induced subgraphs of $G$ on $ell$ vertices. In 1976, Giles proved that any tree on $ngeq 6$ vertices can be reconstructed from its $ell$-deck for $ell geq n-2$. Our main theorem states that it is enough to have $ellgeq (8/9+o(1))n$, making substantial progress towards a conjecture of Nydl from 1990. In addition, we can recognise connectedness from the $ell$-deck if $ellgeq 9n/10$, and reconstruct the degree sequence from the $ell$-deck if $ellge sqrt{2nlog(2n)}$. All of these results are significant improvements on previous bounds.
Let $textbf{k} := (k_1,ldots,k_s)$ be a sequence of natural numbers. For a graph $G$, let $F(G;textbf{k})$ denote the number of colourings of the edges of $G$ with colours $1,dots,s$ such that, for every $c in {1,dots,s}$, the edges of colour $c$ contain no clique of order $k_c$. Write $F(n;textbf{k})$ to denote the maximum of $F(G;textbf{k})$ over all graphs $G$ on $n$ vertices. There are currently very few known exact (or asymptotic) results known for this problem, posed by ErdH{o}s and Rothschild in 1974. We prove some new exact results for $n to infty$: (i) A sufficient condition on $textbf{k}$ which guarantees that every extremal graph is a complete multipartite graph, which systematically recovers all existing exact results. (ii) Addressing the original question of ErdH{o}s and Rothschild, in the case $textbf{k}=(3,ldots,3)$ of length $7$, the unique extremal graph is the complete balanced $8$-partite graph, with colourings coming from Hadamard matrices of order $8$. (iii) In the case $textbf{k}=(k+1,k)$, for which the sufficient condition in (i) does not hold, for $3 leq k leq 10$, the unique extremal graph is complete $k$-partite with one part of size less than $k$ and the other parts as equal in size as possible.
Given a graph $G=(V,E)$ and a positive integer $tgeq2$, the task in the vertex cover $P_t$ ($VCP_t$) problem is to find a minimum subset of vertices $Fsubseteq V$ such that every path of order $t$ in $G$ contains at least one vertex from $F$. The $VCP_t$ problem is NP-complete for any integer $tgeq2$ and has many applications in real world. Recently, the authors presented a dynamic programming algorithm running in time $4^pcdot n^{O(1)}$ for the $VCP_3$ problem on $n$-vertex graphs with treewidth $p$. In this paper, we propose an improvement of it and improved the time-complexity to $3^pcdot n^{O(1)}$. The connected vertex cover $P_3$ ($CVCP_3$) problem is the connected variation of the $VCP_3$ problem where $G[F]$ is required to be connected. Using the Cut&Count technique, we give a randomized algorithm with runtime $4^pcdot n^{O(1)}$ for the $CVCP_3$ problem on $n$-vertex graphs with treewidth $p$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
