Stefan Dziembowski

AAAI Conference 2023 Conference Paper

On Manipulating Weight Predictions in Signed Weighted Networks

• Tomasz Lizurej
• Tomasz Michalak
• Stefan Dziembowski

Adversarial social network analysis studies how graphs can be rewired or otherwise manipulated to evade social network analysis tools. While there is ample literature on manipulating simple networks, more sophisticated network types are much less understood in this respect. In this paper, we focus on the problem of evading FGA---an edge weight prediction method for signed weighted networks by Kumar et al. 2016. Among others, this method can be used for trust prediction in reputation systems. We study the theoretical underpinnings of FGA and its computational properties in terms of manipulability. Our positive finding is that, unlike many other tools, this measure is not only difficult to manipulate optimally, but also it can be difficult to manipulate in practice.

FOCS Conference 2008 Conference Paper

Leakage-Resilient Cryptography

• Stefan Dziembowski
• Krzysztof Pietrzak

We construct a stream-cipher S whose implementation is secure even if a bounded amount of arbitrary (adversarially chosen) information on the internal state ofS is leaked during computation. This captures all possible side-channel attacks on S where the amount of information leaked in a given period is bounded, but overall can be arbitrary large. The only other assumption we make on the implementation of S is that only data that is accessed during computation leaks information. The stream-cipher S generates its output in chunks K 1, K 2, .. . and arbitrary but bounded information leakage is modeled by allowing the adversary to adaptively chose a function f l: {0, 1}* rarr {0, 1} lambda before K l is computed, she then gets f l (tau l ) where tau l is the internal state ofS that is accessed during the computation of Kg. One notion of security we prove for S is that Kg is indistinguishable from random when given K 1, .. ., K 1-1, f 1 (tau 1 ), .. ., f l -1(tau l-1 ) and also the complete internal state of S after Kg has been computed (i. e. S is forward-secure). The construction is based on alternating extraction (used in the intrusion-resilient secret-sharing scheme from FOCS'07). We move this concept to the computational setting by proving a lemma that states that the output of any PRG has high HILLpseudoentropy (i. e. is indistinguishable from some distribution with high min-entropy) even if arbitrary information about the seed is leaked. The amount of leakage lambda that we can tolerate in each step depends on the strength of the underlying PRG, it is at least logarithmic, but can be as large as a constant fraction of the internal state of S if the PRG is exponentially hard.

FOCS Conference 2007 Conference Paper

Intrusion-Resilient Secret Sharing

• Stefan Dziembowski
• Krzysztof Pietrzak

We introduce a new primitive called intrusion-resilient secret sharing (IRSS), whose security proof exploits the fact that there exist functions which can be efficiently computed interactively using low communication complexity in k, but not in k-1 rounds. IRSS is a means of sharing a secret message amongst a set of players which comes with a very strong security guarantee. The shares in an IRSS are made artificially large so that it is hard to retrieve them completely, and the reconstruction procedure is interactive requiring the players to exchange k short messages. The adversaries considered can attack the scheme in rounds, where in each round the adversary chooses some player to corrupt and some function, and retrieves the output of that function applied to the share of the corrupted player. This model captures for example computers connected to a network which can occasionally he infected by malicious software like viruses, which can compute any function on the infected machine, but cannot sent out a huge amount of data. Using methods from the bounded-retrieval model, we construct an IRSS scheme which is secure against any computationally unbounded adversary as long as the total amount of information retrieved by the adversary is somewhat less than the length of the shares, and the adversary makes at most k-1 corruption rounds (as described above, where k rounds are necessary for reconstruction). We extend our basic scheme in several ways in order to allow the shares sent by the dealer to be short (the players then blow them up locally) and to handle even stronger adversaries who can learn some of the shares completely. As mentioned, there is an obvious connection between IRSS schemes and the fact that there exist functions with an exponential gap in their communication complexity for k and k-1 rounds. Our scheme implies such a separation which is in several aspects stronger than the previously known ones.

STOC Conference 2002 Conference Paper

Tight security proofs for the bounded-storage model

• Stefan Dziembowski
• Ueli M. Maurer

(MATH) In the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. Assume that a random t -bit string R is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. If s $xi; t , the adversary can store only partial information about R . The legitimate sender Alice and receiver Bob, sharing a short secret key K initially, can therefore potentially generate a very long n -bit one-time pad X with n »| K | about which the adversary has essentially no information, thus at first glance apparently contradicting Shannon's bound on the key size of a perfect cipher.All previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key K had in fact to be longer than the derived one-time pad, or t had to be extremely large ( t ρ ns ), or the adversary was assumed to be able to store only actual bits of R rather than arbitrary s bits of information about R , or the adversary could obtain a non-negligible amount of information about X .In this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model: K is short, X is very long (e.g. gigabytes), t needs to be only moderately larger than s , and the security proof is optimally strong. In fact, we prove that s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal.

STOC Conference 2000 Conference Paper

On the complexity of verifiable secret sharing and multiparty computation

• Ronald Cramer
• Ivan Damgård
• Stefan Dziembowski

CSL Conference 1997 Conference Paper

Bounded-Variable Fixpoint Queries are PSPACE-complete

• Stefan Dziembowski

Abstract We study the complexity of the evaluation of bounded-variable fixpoint queries in relational databases. We exhibit a finite database such that the problem of deciding whether a closed fixpoint formula using only 2 individual variables is satisfied in this database is PSPACE-complete. This clarifies the issues raised by Vardi in [Var95]. We study also the complexity of query evaluation for a number of restrictions of fixpoint logic. In particular we exhibit a sublogic for which the upper bound postulated by Vardi holds.