Local differential privacy (LDP) is a variant of differential privacy (DP) that avoids the necessity of a trusted central curator, at the expense of a worse trade-off between privacy and utility. The shuffle model has emerged as a way to provide greater anonymity to users by randomly permuting their messages, so that the direct link between users and their reported values is lost to the data collector. By combining an LDP mechanism with a shuffler, privacy can be improved at no cost for the accuracy of operations insensitive to permutations, thereby improving utility in many analytic tasks. However, the privacy implications of shuffling are not always immediately evident, and derivations of privacy bounds are made on a case-by-case basis. In this paper, we analyze the combination of LDP with shuffling in the rigorous framework of quantitative information flow (QIF), and reason about the resulting resilience to inference attacks. QIF naturally captures (combinations of) randomization mechanisms as information-theoretic channels, thus allowing for precise modeling of a variety of inference attacks in a natural way and for measuring the leakage of private information under these attacks. We exploit symmetries of k-RR mechanisms with the shuffle model to achieve closed formulas that express leakage exactly. We provide formulas that show how shuffling improves protection against leaks in the local model, and study how leakage behaves for various values of the privacy parameter of the LDP mechanism. In contrast to the strong adversary from differential privacy, who knows everyone's record in a dataset but the target's, we focus on an uninformed adversary, who does not know the value of any individual in the dataset. This adversary is often more realistic as a consumer of statistical datasets, and indeed we show that in some situations, mechanisms that are equivalent under the strong adversary can provide different privacy guarantees under the uninformed one. Finally, we also illustrate the application of our model to the typical strong adversary from DP.

Order-Revealing Encryption (ORE) allows deriving the order of two plaintexts to facilitate database functions such as range queries and sorting. Ideally, nothing is observable to an adversary beyond the order of the messages. Unfortunately, Ideal ORE is challenging to implement, and a variation of it has then been developed. This variation, referred to as CLWW ORE, reveals the first differing bit position between every two plaintexts, in addition to the order.We provide a formal leakage analysis of these two ORE variations by applying the information-theoretic quantitative information flow (QIF) framework. We evaluate two threat models: (1) the Bayes scenario in which an adversary wishes to guess the secret entirely and (2) a bucketing scenario in which an adversary is content to simply guess the range of the plaintext. We provide security implications, usage guidelines, and a mitigation technique that improves the security of Ideal ORE. We find that while Ideal and CLWW ORE perform similarly under the Bayes scenario, CLWW ORE is fundamentally insecure under the bucketing scenario.