Paper 2026/2928
Shifting Dark Matter: Two-Query Key Recovery on a Post-Quantum OPRF
Abstract
At the 2026 IEEE Symposium on Security and Privacy, Aranha et al. proposed a maliciously secure post-quantum oblivious pseudorandom function (OPRF) from Crypto Dark Matter. Its strong PRF is $F_k(x) = B \cdot \mathrm{vec}(k \cdot \mathrm{elt}(E(x))) \bmod 3$, where the key $k \in \mathbb{F}_{2^n}$ multiplies a systematic encoding $E(x)$. In this paper, we show that a client that follows the protocol recovers the key from two chosen queries. Multiplication by $\alpha^{-2}$ commutes with the key multiplication and acts on the polynomial basis as a shift, up to a correction from two bits. We prove that input pairs whose encodings differ by the factor $\alpha^2$ correspond to the binary solutions of six linear systems over $\mathbb{F}_3$. For the proposed parameters, we found such a pair in 146 seconds. After a guess of two bits, the outputs give a full-weight ternary syndrome decoding instance whose 164 equations almost always determine the other 254 bits of $k \cdot \mathrm{elt}(E(x))$. Counting memory in list elements, we estimate time and memory complexities of $2^{67.3}$ and $2^{51.8}$, or $2^{69.9}$ and $2^{33.3}$, both far below the claimed 128-bit security. For a 64-bit security target, the whole attack recovered the key with $2^{34.39}$ operations, matching our cost model. A dense field modulus does not prevent the attack. For 128-bit inputs, a non-systematic code of length at least 160 heuristically removes such pairs, and a public $\mathbb{F}_2$-linear mixing of the output removes the linear structure of the key recovery.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- oblivious pseudorandom functionCrypto Dark Matterkey recoveryternary syndrome decodingpost-quantum
- Contact author(s)
-
newonetiger @ korea ac kr
cmcom35 @ korea ac kr
shhong @ smartm2m co kr
dongjae lee @ kangwon ac kr - History
- 2026-11-22: approved
- 2026-11-18: received
- See all versions
- Short URL
- https://ia.cr/2026/2928
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2928,
author = {Hanbeom Shin and Insung Kim and Seokhie Hong and Dongjae Lee},
title = {Shifting Dark Matter: Two-Query Key Recovery on a Post-Quantum {OPRF}},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2928},
year = {2026},
url = {https://eprint.iacr.org/2026/2928}
}