  Random access coding is an information task that has been extensively studied
and found many applications in quantum information. In this scenario, Alice
receives an $n$-bit string $x$, and wishes to encode $x$ into a quantum state
$\rho_x$, such that Bob, when receiving the state $\rho_x$, can choose any bit
$i \in [n]$ and recover the input bit $x_i$ with high probability. Here we
study two variants: parity-oblivious random access codes, where we impose the
cryptographic property that Bob cannot infer any information about the parity
of any subset of bits of the input apart from the single bits $x_i$; and
even-parity-oblivious random access codes, where Bob cannot infer any
information about the parity of any even-size subset of bits of the input.
  In this paper, we provide the optimal bounds for parity-oblivious quantum
random access codes and show that they are asymptotically better than the
optimal classical ones. Our results provide a large non-contextuality
inequality violation and resolve the main open problem in a work of Spekkens,
Buzacott, Keehn, Toner, and Pryde (2009). Second, we provide the optimal bounds
for even-parity-oblivious random access codes by proving their equivalence to a
non-local game and by providing tight bounds for the success probability of the
non-local game via semidefinite programming. In the case of
even-parity-oblivious random access codes, the cryptographic property holds
also in the device-independent model.
