Paper 2026/2928

Shifting Dark Matter: Two-Query Key Recovery on a Post-Quantum OPRF

Hanbeom Shin, Korea University
Insung Kim, Korea University
Seokhie Hong, SmartM2M
Dongjae Lee, Kangwon National University
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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.