  We consider Oblivious Shuffling and K-Oblivious Shuffling, a refinement
thereof. We provide efficient algorithms for both and discuss their application
to the design of Oblivious RAM. The task of K-Oblivious Shuffling is to
obliviously shuffle N encrypted blocks that have been randomly allocated on the
server in such a way that an adversary learns nothing about the new allocation
of blocks. The security guarantee should hold also with respect to an adversary
that has learned the initial position of K touched blocks out of the N blocks.
The classical notion of Oblivious Shuffling is obtained for K = N.
  We present a family of algorithms for Oblivious Shuffling. Our first
construction, CacheShuffleRoot, is tailored for clients with $O(\sqrt{N})$
blocks of memory and uses $(4+\epsilon)N$ blocks of bandwidth, for every
$\epsilon > 0$. CacheShuffleRoot is a 4.5x improvement over previous best known
results on practical sizes of N. We also present CacheShuffle that obliviously
shuffles using O(S) blocks of client memory with $O(N\log_S N)$ blocks of
bandwidth.
  We then turn to K-Oblivious Shuffling and give algorithms that require 2N +
f(K) blocks of bandwidth, for some function f. That is, any extra bandwidth
above the 2N lower bound depends solely on K. We present KCacheShuffleBasic
that uses O(K) client storage and exactly 2N blocks of bandwidth. For smaller
client storage requirements, we show KCacheShuffle, which uses O(S) client
storage and requires $2N+(1+\epsilon)O(K\log_S K)$ blocks of bandwidth.
  Finally, we consider the case in which, in addition to the N blocks, the
server stores D dummy blocks whose content is is irrelevant but still their
positions must be hidden by the shuffling. For this case, we design algorithm
KCacheShuffleDummy that, for N + D blocks and K touched blocks, uses O(K)
client storage and $D+(2+\epsilon)N$ blocks of bandwidth.
