Shlomi Dolev

Shlomi Dolev, Kazuki Ikeda, Yaron Oz

Quantum energy teleportation (QET) is a process that leverages quantum entanglement and local operations to transfer energy between two spatially separated locations without physically transporting particles or energy carriers. We construct a QET-based quantum key distribution (QKD) protocol and analyze its security and robustness to noise in both the classical and the quantum channels. We generalize the construction to an $N$-party information sharing protocol, possessing a feature that dishonest participants can be detected.

David Denisov, Dan Feldman, Shlomi Dolev et al.

We suggest efficient and provable methods to compute an approximation for imbalanced point clustering, that is, fitting $k$-centers to a set of points in $\mathbb{R}^d$, for any $d,k\geq 1$. To this end, we utilize \emph{coresets}, which, in the context of the paper, are essentially weighted sets of points in $\mathbb{R}^d$ that approximate the fitting loss for every model in a given set, up to a multiplicative factor of $1\pm\varepsilon$. We provide [Section 3 and Section E in the appendix] experiments that show the empirical contribution of our suggested methods for real images (novel and reference), synthetic data, and real-world data. We also propose choice clustering, which by combining clustering algorithms yields better performance than each one separately.

David Denisov, Shlomi Dolev, Dan Felmdan et al.

We study the $k$-means problem for a set $\mathcal{S} \subseteq \mathbb{R}^d$ of $n$ segments, aiming to find $k$ centers $X \subseteq \mathbb{R}^d$ that minimize $D(\mathcal{S},X) := \sum_{S \in \mathcal{S}} \min_{x \in X} D(S,x)$, where $D(S,x) := \int_{p \in S} |p - x| dp$ measures the total distance from each point along a segment to a center. Variants of this problem include handling outliers, employing alternative distance functions such as M-estimators, weighting distances to achieve balanced clustering, or enforcing unique cluster assignments. For any $\varepsilon > 0$, an $\varepsilon$-coreset is a weighted subset $C \subseteq \mathbb{R}^d$ that approximates $D(\mathcal{S},X)$ within a factor of $1 \pm \varepsilon$ for any set of $k$ centers, enabling efficient streaming, distributed, or parallel computation. We propose the first coreset construction that provably handles arbitrary input segments. For constant $k$ and $\varepsilon$, it produces a coreset of size $O(\log^2 n)$ computable in $O(nd)$ time. Experiments, including a real-time video tracking application, demonstrate substantial speedups with minimal loss in clustering accuracy, confirming both the practical efficiency and theoretical guarantees of our method.

Shlomi Dolev, Arseni Kalma

We suggest using Fully Homomorphic Encryption (FHE) to be used, not only to keep the privacy of information but also, to verify computations with no additional significant overhead, using only part of the variables length for verification. This method supports the addition of encrypted values as well as multiplication of encrypted values by the addition of their logarithmic representations and is based on a separation between hardware functionalities. The computer/server performs blackbox additions and is based on the separation of server/device/hardware, such as the enclave, that may deal with additions of logarithmic values and exponentiation. The main idea is to restrict the computer operations and to use part of the variable for computation verification (computation fingerprints) and the other for the actual calculation. The verification part holds the FHE value, of which the calculated result is known (either due to computing locally once or from previous verified computations) and will be checked against the returned FHE value. We prove that a server with bit computation granularity can return consistent encrypted wrong results even when the public key is not provided. For the case of computer word granularity the verification and the actual calculation parts are separated, the verification part (the consecutive bits from the LSB to the MSB of the variables) is fixed across all input vectors. We also consider the case of Single Instruction Multiple Data (SIMD) where the computation fingerprints index in the input vectors is fixed across all vectors.

Philip Derbeko, Shlomi Dolev

The structure and weights of Deep Neural Networks (DNN) typically encode and contain very valuable information about the dataset that was used to train the network. One way to protect this information when DNN is published is to perform an interference of the network using secure multi-party computations (MPC). In this paper, we suggest a translation of deep neural networks to polynomials, which are easier to calculate efficiently with MPC techniques. We show a way to translate complete networks into a single polynomial and how to calculate the polynomial with an efficient and information-secure MPC algorithm. The calculation is done without intermediate communication between the participating parties, which is beneficial in several cases, as explained in the paper.

Shlomi Dolev, Nisha Panwar

Peripheral authentication is an important aspect in the vehicle networks to provide services to only authenticated peripherals and a security to internal vehicle modules such as anti-lock braking system, power-train control module, engine control unit, transmission control unit, and tire pressure monitoring. In this paper a three-way handshake scheme is proposed for a vehicle to a keyfob authentication. A keyfob is a key with a secure hardware that communicates and authenticates the vehicle over the wireless channel. Conventionally, a vehicle to keyfob authentication is realized through a challenge-response verification protocol. An authentic coupling between the vehicle identity and the keyfob avoids any illegal access to the vehicle. However, these authentication messages can be relayed by an active adversary, thereby, can amplify the actual distance between an authentic vehicle and a keyfob. Eventually, an adversary can possibly gain access to the vehicle by relaying wireless signals and without any effort to generate or decode the secret credentials. Hence, the vehicle to keyfob authentication scheme must contain an additional attribute verification such as physical movement of a keyfob holder. Our solution is a two-party and three-way handshake scheme with proactive and reactive commitment verification. The proposed solution also uses a time interval verification such that both vehicle and keyfob would yield a similar locomotion pattern of a dynamic keyfob within a similar observational time interval. Hence, the solution is different from the distance bounding protocols that require multiple iterations for the round-trip delay measurement. The proposed scheme is shown to be adaptable with the existing commitment scheme such as Schnorr identification scheme and Pedersen commitment scheme.

Shlomi Dolev, Peeyush Gupta, Yin Li et al.

Data outsourcing allows data owners to keep their data at \emph{untrusted} clouds that do not ensure the privacy of data and/or computations. One useful framework for fault-tolerant data processing in a distributed fashion is MapReduce, which was developed for \emph{trusted} private clouds. This paper presents algorithms for data outsourcing based on Shamir's secret-sharing scheme and for executing privacy-preserving SQL queries such as count, selection including range selection, projection, and join while using MapReduce as an underlying programming model. Our proposed algorithms prevent an adversary from knowing the database or the query while also preventing output-size and access-pattern attacks. Interestingly, our algorithms do not involve the database owner, which only creates and distributes secret-shares once, in answering any query, and hence, the database owner also cannot learn the query. Logically and experimentally, we evaluate the efficiency of the algorithms on the following parameters: (\textit{i}) the number of communication rounds (between a user and a server), (\textit{ii}) the total amount of bit flow (between a user and a server), and (\textit{iii}) the computational load at the user and the server.\B

Philip Derbeko, Shlomi Dolev, Ehud Gudes et al.

MapReduce is a programming system for distributed processing large-scale data in an efficient and fault tolerant manner on a private, public, or hybrid cloud. MapReduce is extensively used daily around the world as an efficient distributed computation tool for a large class of problems, e.g., search, clustering, log analysis, different types of join operations, matrix multiplication, pattern matching, and analysis of social networks. Security and privacy of data and MapReduce computations are essential concerns when a MapReduce computation is executed in public or hybrid clouds. In order to execute a MapReduce job in public and hybrid clouds, authentication of mappers-reducers, confidentiality of data-computations, integrity of data-computations, and correctness-freshness of the outputs are required. Satisfying these requirements shield the operation from several types of attacks on data and MapReduce computations. In this paper, we investigate and discuss security and privacy challenges and requirements, considering a variety of adversarial capabilities, and characteristics in the scope of MapReduce. We also provide a review of existing security and privacy protocols for MapReduce and discuss their overhead issues.

Shlomi Dolev, Lukasz Krzywiecki, Nisha Panwar et al.

In recent future, vehicles will establish a spontaneous connection over a wireless radio channel, coordinating actions and information. Vehicles will exchange warning messages over the wireless radio channel through Dedicated Short Range Communication (IEEE 1609) over the Wireless Access in Vehicular Environment (802.11p). Unfortunately, the wireless communication among vehicles is vulnerable to security threats that may lead to very serious safety hazards. Therefore, the warning messages being exchanged must incorporate an authentic factor such that recipient is willing to verify and accept the message in a timely manner

Shlomi Dolev, Łukasz Krzywiecki, Nisha Panwar et al.

Vehicular networks are used to coordinate actions among vehicles in traffic by the use of wireless transceivers (pairs of transmitters and receivers). Unfortunately, the wireless communication among vehicles is vulnerable to security threats that may lead to very serious safety hazards. In this work, we propose a viable solution for coping with Man-in-the-Middle attacks. Conventionally, Public Key Infrastructure (PKI) is utilized for a secure communication with the pre-certified public key. However, a secure vehicle-to-vehicle communication requires additional means of verification in order to avoid impersonation attacks. To the best of our knowledge, this is the first work that proposes to certify both the public key and out-of-band sense-able static attributes to enable mutual authentication of the communicating vehicles. Vehicle owners are bound to preprocess (periodically) a certificate for both a public key and a list of fixed unchangeable attributes of the vehicle. Furthermore, the proposed approach is shown to be adaptable with regards to the existing authentication protocols. We illustrate the security verification of the proposed protocol using a detailed proof in Spi calculus.

Shlomi Dolev, Juan Garay, Niv Gilboa et al.

In the problem of swarm computing, $n$ agents wish to securely and distributively perform a computation on common inputs, in such a way that even if the entire memory contents of some of them are exposed, no information is revealed about the state of the computation. Recently, Dolev, Garay, Gilboa and Kolesnikov [ICS 2011] considered this problem in the setting of information-theoretic security, showing how to perform such computations on input streams of unbounded length. The cost of their solution, however, is exponential in the size of the Finite State Automaton (FSA) computing the function. In this work we are interested in efficient computation in the above model, at the expense of minimal additional assumptions. Relying on the existence of one-way functions, we show how to process a priori unbounded inputs (but of course, polynomial in the security parameter) at a cost linear in $m$, the number of FSA states. In particular, our algorithms achieve the following: * In the case of $(n,n)$-reconstruction (i.e. in which all $n$ agents participate in reconstruction of the distributed computation) and at most $n-1$ agents are corrupted, the agent storage, the time required to process each input symbol and the time complexity for reconstruction are all $O(mn)$. * In the case of $(t+1,n)$-reconstruction (where only $t+1$ agents take part in the reconstruction) and at most $t$ agents are corrupted, the agents' storage and time required to process each input symbol are $O(m{n-1 \choose t-1})$. The complexity of reconstruction is $O(m(t+1))$.