BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Ran Gelles

Ran Gelles appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Data Structures and Algorithmsquant-phCryptography and SecurityDistributed, Parallel, and Cluster ComputingInformation Theorymath.IT

Catalog footprint

What is connected

16works
6topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2023arXiv

Beeping Shortest Paths via Hypergraph Bipartite Decomposition

Constructing a shortest path between two network nodes is a fundamental task in distributed computing. This work develops schemes for the construction of shortest paths in randomized beeping networks between a predetermined source node and an arbitrary set of destination nodes. Our first scheme constructs a (single) shortest path to an arbitrary destination in $O (D \log\log n + \log^3 n)$ rounds with high probability. Our second scheme constructs multiple shortest paths, one per each destination, in $O (D \log^2 n + \log^3 n)$ rounds with high probability. Our schemes are based on a reduction of the above shortest path construction tasks to a decomposition of hypergraphs into bipartite hypergraphs: We develop a beeping procedure that partitions the (polynomially-large) hyperedge set of a hypergraph $H = (V_H, E_H)$ into $k = Θ(\log^2 n)$ disjoint subsets $F_1 \cup \cdots \cup F_k = E_H$ such that the (sub-)hypergraph $(V_H, F_i)$ is bipartite in the sense that there exists a vertex subset $U \subseteq V$ such that $|U \cap e| = 1$ for every $e \in F_i$. This procedure turns out to be instrumental in speeding up shortest path constructions under the beeping model.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Distributed Computations in Fully-Defective Networks

We address fully-defective asynchronous networks, in which all links are subject to an unlimited number of alteration errors, implying that all messages in the network may be completely corrupted. Despite the possible intuition that such a setting is too harsh for any reliable communication, we show how to simulate any algorithm for a noiseless setting over any fully-defective setting, given that the network is 2-edge connected. We prove that if the network is not 2-edge connected, no non-trivial computation in the fully-defective setting is possible. The key structural property of 2-edge-connected graphs that we leverage is the existence of an oriented (non-simple) cycle that goes through all nodes [Robbins, 1939]. The core of our technical contribution is presenting a construction of such a Robbins cycle in fully-defective networks, and showing how to communicate over it despite total message corruption. These are obtained in a content-oblivious manner, since nodes must ignore the content of received messages.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Efficient Multiparty Interactive Coding for Insertions, Deletions and Substitutions

In the field of interactive coding, two or more parties wish to carry out a distributed computation over a communication network that may be noisy. The ultimate goal is to develop efficient coding schemes that can tolerate a high level of noise while increasing the communication by only a constant factor (i.e., constant rate). In this work we consider synchronous communication networks over an arbitrary topology, in the powerful adversarial insertion-deletion noise model. Namely, the noisy channel may adversarially alter the content of any transmitted symbol, as well as completely remove a transmitted symbol or inject a new symbol into the channel. We provide efficient, constant rate schemes that successfully conduct any computation with high probability as long as the adversary corrupts at most $\varepsilon /m$ fraction of the total communication, where $m$ is the number of links in the network and $\varepsilon$ is a small constant. This scheme assumes the parties share a random string to which the adversarial noise is oblivious. We can remove this assumption at the price of being resilient to $\varepsilon / (m\log m)$ adversarial error. While previous work considered the insertion-deletion noise model in the two-party setting, to the best of our knowledge, our scheme is the first multiparty scheme that is resilient to insertions and deletions. Furthermore, our scheme is the first computationally efficient scheme in the multiparty setting that is resilient to adversarial noise.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Noisy Beeping Networks

We introduce noisy beeping networks, where nodes have limited communication capabilities, namely, they can only emit energy or sense the channel for energy. Furthermore, imperfections may cause devices to malfunction with some fixed probability when sensing the channel, which amounts to deducing a noisy received transmission. Such noisy networks have implications for ultra-lightweight sensor networks and biological systems. We show how to compute tasks in a noise-resilient manner over noisy beeping networks of arbitrary structure. In particular, we transform any algorithm that assumes a noiseless beeping network (of size $n$) into a noise-resilient version while incurring a multiplicative overhead of only $O(\log n)$ in its round complexity, with high probability. We show that our coding is optimal for some tasks, such as node-coloring of a clique. We further show how to simulate a large family of algorithms designed for distributed networks in the CONGEST($B$) model over a noisy beeping network. The simulation succeeds with high probability and incurs an asymptotic multiplicative overhead of $O(B\cdot Δ\cdot \min(n,Δ^2))$ in the round complexity, where $Δ$ is the maximal degree of the network. The overhead is tight for certain graphs, e.g., a clique. Further, this simulation implies a constant overhead coding for constant-degree networks.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Optimal Short-Circuit Resilient Formulas

We consider fault-tolerant boolean formulas in which the output of a faulty gate is short-circuited to one of the gate's inputs. A recent result by Kalai et al. (FOCS 2012) converts any boolean formula into a resilient formula of polynomial size that works correctly if less than a fraction $1/6$ of the gates (on every input-to-output path) are faulty. We improve the result of Kalai et al., and show how to efficiently fortify any boolean formula against a fraction $1/5$ of short-circuit gates per path, with only a polynomial blowup in size. We additionally show that it is impossible to obtain formulas with higher resilience and sub-exponential growth in size. Towards our results, we consider interactive coding schemes when noiseless feedback is present; these produce resilient boolean formulas via a Karchmer-Wigderson relation. We develop a coding scheme that resists up to a fraction $1/5$ of corrupted transmissions in each direction of the interactive channel. We further show that such a level of noise is maximal for coding schemes with sub-exponential blowup in communication. Our coding scheme takes a surprising inspiration from Blockchain technology.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Coding for interactive communication correcting insertions and deletions

We consider the question of interactive communication, in which two remote parties perform a computation while their communication channel is (adversarially) noisy. We extend here the discussion into a more general and stronger class of noise, namely, we allow the channel to perform insertions and deletions of symbols. These types of errors may bring the parties "out of sync", so that there is no consensus regarding the current round of the protocol. In this more general noise model, we obtain the first interactive coding scheme that has a constant rate and resists noise rates of up to $1/18-\varepsilon$. To this end we develop a novel primitive we name edit distance tree code. The edit distance tree code is designed to replace the Hamming distance constraints in Schulman's tree codes (STOC 93), with a stronger edit distance requirement. However, the straightforward generalization of tree codes to edit distance does not seem to yield a primitive that suffices for communication in the presence of synchronization problems. Giving the "right" definition of edit distance tree codes is a main conceptual contribution of this work.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Reversed Space Attacks

Many quantum key distribution (QKD) schemes are based on sending and measuring qubits -- two-dimensional quantum systems. Yet, in practical realizations and experiments, the measuring devices at the receiver's (Bob) site commonly do not measure a two-dimensional system but rather a quantum space of a larger dimension. Such an enlargement sometimes results from imperfect devices. However, in various QKD protocols such enlargement exists even in the ideal scenario when all devices are assumed to be perfect. This issue is common, for instance, in QKD schemes implemented via photons, where the parties' devices are based on Mach-Zehnder interferometers, as these inherently enlarge the quantum space in use. We show how space enlargement at Bob's site exposes the implemented protocol to new kinds of attacks, attacks that have not yet been explicitly pinpointed nor rigorously analyzed. We name these the "reversed space attacks". A key insight in formalizing our attacks, is the idea of taking all states defining Bob's (large) measured space and reversing them in time in order to identify precisely the space that an eavesdropper may attack. We employ such attacks on two variants of intereferometric-based QKD recently experimented by several groups, and show how to get full information on the qubit sent by Alice, while inducing no errors at all. The technique we develop here has subsequently been used in a closely related work (Boyer, Gelles, and Mor, Physical Review A, 2014) to demonstrate a (weaker variant of) reversed-space attack on both interferometric-based and polarization-based QKD.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Adaptive Protocols for Interactive Communication

How much adversarial noise can protocols for interactive communication tolerate? This question was examined by Braverman and Rao (IEEE Trans. Inf. Theory, 2014) for the case of "robust" protocols, where each party sends messages only in fixed and predetermined rounds. We consider a new class of non-robust protocols for Interactive Communication, which we call adaptive protocols. Such protocols adapt structurally to the noise induced by the channel in the sense that both the order of speaking, and the length of the protocol may vary depending on observed noise. We define models that capture adaptive protocols and study upper and lower bounds on the permissible noise rate in these models. When the length of the protocol may adaptively change according to the noise, we demonstrate a protocol that tolerates noise rates up to $1/3$. When the order of speaking may adaptively change as well, we demonstrate a protocol that tolerates noise rates up to $2/3$. Hence, adaptivity circumvents an impossibility result of $1/4$ on the fraction of tolerable noise (Braverman and Rao, 2014).

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Maximal Noise in Interactive Communication over Erasure Channels and Channels with Feedback

We provide tight upper and lower bounds on the noise resilience of interactive communication over noisy channels with feedback. In this setting, we show that the maximal fraction of noise that any robust protocol can resist is 1/3. Additionally, we provide a simple and efficient robust protocol that succeeds as long as the fraction of noise is at most 1/3 - ε. Surprisingly, both bounds hold regardless of whether the parties send bits or symbols from an arbitrarily large alphabet. We also consider interactive communication over erasure channels. We provide a protocol that matches the optimal tolerable erasure rate of 1/2 - εof previous protocols (Franklin et al., CRYPTO '13) but operates in a much simpler and more efficient way. Our protocol works with an alphabet of size 4, in contrast to prior protocols in which the alphabet size grows as epsilon goes to zero. Building on the above algorithm with a fixed alphabet size, we are able to devise a protocol for binary erasure channels that tolerates erasure rates of up to 1/3 - ε.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Attacks on Fixed Apparatus Quantum Key Distribution Schemes

We consider quantum key distribution implementations in which the receiver's apparatus is fixed and does not depend on his choice of basis at each qubit transmission. We show that, although theoretical quantum key distribution is proven secure, such implementations are totally insecure against a strong eavesdropper that has one-time (single) access to the receiver's equipment. The attack we present here, the "fixed-apparatus attack" causes a potential risk to the usefulness of several recent implementations.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

How to Catch L_2-Heavy-Hitters on Sliding Windows

Finding heavy-elements (heavy-hitters) in streaming data is one of the central, and well-understood tasks. Despite the importance of this problem, when considering the sliding windows model of streaming (where elements eventually expire) the problem of finding L_2-heavy elements has remained completely open despite multiple papers and considerable success in finding L_1-heavy elements. In this paper, we develop the first poly-logarithmic-memory algorithm for finding L_2-heavy elements in sliding window model. Since L_2 heavy elements play a central role for many fundamental streaming problems (such as frequency moments), we believe our method would be extremely useful for many sliding-windows algorithms and applications. For example, our technique allows us not only to find L_2-heavy elements, but also heavy elements with respect to any L_p for 0<p<2 on sliding windows. Thus, our paper completely resolves the question of finding L_p-heavy elements for sliding windows with poly-logarithmic memory for all values of p since it is well known that for p>2 this task is impossible. Our method may have other applications as well. We demonstrate a broader applicability of our novel yet simple method on two additional examples: we show how to obtain a sliding window approximation of other properties such as the similarity of two streams, or the fraction of elements that appear exactly a specified number of times within the window (the rarity problem). In these two illustrative examples of our method, we replace the current expected memory bounds with worst case bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Security and Composability of Randomness Expansion from Bell Inequalities

The nonlocal behavior of quantum mechanics can be used to generate guaranteed fresh randomness from an untrusted device that consists of two nonsignalling components; since the generation process requires some initial fresh randomness to act as a catalyst, one also speaks of randomness expansion. Colbeck and Kent proposed the first method for generating randomness from untrusted devices, however, without providing a rigorous analysis. This was addressed subsequently by Pironio et al. [Nature 464 (2010)], who aimed at deriving a lower bound on the min-entropy of the data extracted from an untrusted device, based only on the observed non-local behavior of the device. Although that article succeeded in developing important tools towards the acquired goal, it failed in putting the tools together in a rigorous and correct way, and the given formal claim on the guaranteed amount of min-entropy needs to be revisited. In this paper we show how to combine the tools provided by Pironio et al., as to obtain a meaningful and correct lower bound on the min-entropy of the data produced by an untrusted device, based on the observed non-local behavior of the device. Our main result confirms the essence of the improperly formulated claims of Pironio et al., and puts them on solid ground. We also address the question of composability and show that different untrusted devices can be composed in an alternating manner under the assumption that they are not entangled. This enables for superpolynomial randomness expansion based on two untrusted yet unentangled devices.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Position-Based Quantum Cryptography: Impossibility and Constructions

In this work, we study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Potent Tree Codes and their applications: Coding for Interactive Communication, revisited

We study the fundamental problem of reliable interactive communication over a noisy channel. In a breakthrough sequence of papers published in 1992 and 1993, Schulman gave non-constructive proofs of the existence of general methods to emulate any two-party interactive protocol such that: (1) the emulation protocol takes a constant-factor longer than the original protocol, and (2) if the emulation protocol is executed over a noisy channel, then the probability that the emulation protocol fails is exponentially small in the total length of the protocol. Unfortunately, Schulman's emulation procedures either only work in a model with a large amount of shared randomness, or are non-constructive in that they rely on the existence of good tree codes. The only known proofs of the existence of good tree codes are non-constructive, and finding an explicit construction remains an important open problem. Indeed, randomly generated tree codes are not good tree codes with overwhelming probability. In this work, we revisit the problem of reliable interactive communication, and obtain the following results: We introduce a new notion of goodness for a tree code, and define the notion of a potent tree code. We believe that this notion is of independent interest. We prove the correctness of an explicit emulation procedure based on any potent tree code. We show that a randomly generated tree code (with suitable constant alphabet size) is a potent tree code with overwhelming probability. Furthermore we are able to partially derandomize this result using only O(n) random bits, where $n$ is the depth of the tree. These results allow us to obtain the first fully explicit emulation procedure for reliable interactive communication over noisy channels with a constant communication overhead, and exponentially small failure probability.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

Semi-Quantum Key Distribution

Secure key distribution among two remote parties is impossible when both are classical, unless some unproven (and arguably unrealistic) computation-complexity assumptions are made, such as the difficulty of factorizing large numbers. On the other hand, a secure key distribution is possible when both parties are quantum. What is possible when only one party (Alice) is quantum, yet the other (Bob) has only classical capabilities? Recently, a semi-quantum key distribution protocol was presented (Boyer, Kenigsberg and Mor, Physical Review Letters, 2007), in which one of the parties (Bob) is classical, and yet, the protocol is proven to be completely robust against an eavesdropping attempt. Here we extend that result much further. We present two protocols with this constraint, and prove their robustness against attacks: we prove that any attempt of an adversary to obtain information (and even a tiny amount of information) necessarily induces some errors that the legitimate parties could notice. One protocol presented here is identical to the one referred to above, however, its robustness is proven here in a much more general scenario. The other protocol is very different as it is based on randomization.

0 citations0 reviewsNo code linkedOpen access