More Like this

1. Oblivious Accumulators

   https://doi.org/10.1007/978-3-031-57722-2_4  

   Baldimtsi, F.; Karantaidou, I.; Raghuraman, S. (April 2024, Public Key Cryptography (PKC))
2. Oblivious Single Access Machines - A New Model for Oblivious Computation

   Appan, Ananya; Heath, David; Ren, Ling (December 2024, ACM Digital Library)
3. Oblivious Digital Tokens

   Liskij, M; Ding, X; Tsudik, G; Basin, D (August 2025, Usenix Security Symposium)
4. Optimal oblivious reconfigurable networks

   https://doi.org/10.1145/3519935.3520020  

   Amir, Daniel; Wilson, Tegan; Shrivastav, Vishal; Weatherspoon, Hakim; Kleinberg, Robert; Agarwal, Rachit (June 2022, ACM SIGACT Symposium on Theory of Computing)

   Oblivious routing has a long history in both the theory and practice of networking. In this work we initiate the formal study of oblivious routing in the context of reconfigurable networks, a new architecture that has recently come to the fore in datacenter networking. These networks allow a rapidly changing bounded-degree pattern of interconnections between nodes, but the network topology and the selection of routing paths must both be oblivious to the traffic demand matrix. Our focus is on the trade-off between maximizing throughput and minimizing latency in these networks. For every constant throughput rate, we characterize (up to a constant factor) the minimum latency achievable by an oblivious reconfigurable network design that satisfies the given throughput guarantee. The trade-off between these two objectives turns out to be surprisingly subtle: the curve depicting it has an unexpected scalloped shape reflecting the fact that load-balancing becomes more difficult when the average length of routing paths is not an integer because equalizing all the path lengths is not possible. The proof of our lower bound uses LP duality to verify that Valiant load balancing is the most efficient oblivious routing scheme when used in combination with an optimally-designed reconfigurable network topology. The proof of our upper bound uses an algebraic construction in which the network nodes are identified with vectors over a finite field, the network topology is described by either the elementary basis or a sequence of Vandermonde matrices, and routing paths are constructed by selecting columns of these matrices to yield the appropriate mixture of path lengths within the shortest possible time interval. 

   more » « less
5. Hop-constrained oblivious routing

   https://doi.org/10.1145/3406325.3451098  

   Ghaffari, Mohsen; Haeupler, Bernhard; Zuzic, Goran (June 2021, Symposium on Theory of Computing (STOC))

   null (Ed.)

   We prove the existence of an oblivious routing scheme that is poly(logn)-competitive in terms of (congestion + dilation), thus resolving a well-known question in oblivious routing. Concretely, consider an undirected network and a set of packets each with its own source and destination. The objective is to choose a path for each packet, from its source to its destination, so as to minimize (congestion + dilation), defined as follows: The dilation is the maximum path hop-length, and the congestion is the maximum number of paths that include any single edge. The routing scheme obliviously and randomly selects a path for each packet independent of (the existence of) the other packets. Despite this obliviousness, the selected paths have (congestion + dilation) within a poly(logn) factor of the best possible value. More precisely, for any integer hop-bound h, this oblivious routing scheme selects paths of length at most h · poly(logn) and is poly(logn)-competitive in terms of congestion in comparison to the best possible congestion achievable via paths of length at most h hops. These paths can be sampled in polynomial time. This result can be viewed as an analogue of the celebrated oblivious routing results of R'acke [FOCS 2002, STOC 2008], which are O(logn)-competitive in terms of congestion, but are not competitive in terms of dilation. 

   more » « less