🥳#call4reading #OpenAccess

✍️Deterministic Search on Complete #Bipartite Graphs by Continuous-Time #QuantumWalk #by Honghong Lin and Yun Shang

🔗10.2478/qic-2024-0001

#quantumcounting #quantumwalk

'Variational Estimators of the Degree-corrected Latent Block Model for Bipartite Networks', by Yunpeng Zhao, Ning Hao, Ji Zhu.

http://jmlr.org/papers/v25/23-0984.html

#graphs #nodes #bipartite

I recently read a very interesting paper on Leakage-Abuse Attacks against Order-Preserving Encryption (OPE) schemes and Order-Revealing Encryption (ORE) Schemes.

In this paper, the researchers show how the widely used encryption schemes are inadequate. Here are some snippets from the paper.

Order-preserving encryption (#OPE) - ensures that Ek(m1)<Ek(m2) for m1<m2 and Ek the encryption algorithm. Most widely used scheme is #BCLO.

Order-revealing encryption (#ORE) - reveals ordering relations by way of a public comparison function that operates on pairs of plaintexts. Most widely used scheme is #CLWW.

Popular belief is that OPE and ORE schemes remain secure in practice for plaintext data drawn from larger domains, and practitioners could simply avoid using OPE for small-domain data.

The researchers used a non-crossing attack (min-weight non-crossing #bipartite matching) which runs in only a few hours, even for the largest target dataset, against real-world datasets using the BCLO scheme to encrypt a set of first names.

Using this attack they were able to recover almost half the data set. The leakage was even worse for last names, with almost 97% of last names trivially recoverable.

#Composition of the two (BCLO & CLWW) schemes does #decrease attack accuracy but is still far from providing acceptable security.

Exploiting known plaintexts is even easier.

Attacking frequency-hiding schemes - #Kerschbaum recently introduced a scheme that hides frequency information. However, a “#binomial” attack performs reasonably well, recovering on average 30% of first names and 7% of last names. Notably, it recovers majority of high-frequency plaintexts (despite not having frequency information leaked), suggesting these plaintexts are particularly poorly protected by any order-revealing scheme.

In terms of countermeasures, an obvious suggestion is to move towards less leaky schemes, such as those that only reveal order, including Kerschbaum's scheme and the more recent #Boneh et al. scheme based on #multilinear maps. Unfortunately in most settings there exists inherent #challenges to deployment of these schemes. Kerschbaum's scheme is relatively efficient, but requires client-side state which impedes scaling. The Boneh et al. scheme has ciphertexts larger by 10 orders of magnitude than BCLO ciphertexts and requires tens of minutes to compute encryptions.

#encryption #quantumcomputing #quantumcryptography