Paper 2026/2734
Finite-Batch q-ary OT Extension for High-Arity Private Lookup: Certified Radix--Code Co-Design
Abstract
High-arity oblivious transfer is a natural abstraction for private lookup: a $\delta$-bit table address selects one entry out of $2^\delta$ candidates. This paper characterizes the finite-batch design space of the CCG q-ary OT-extension family and derives certified radix-selection rules. For $q=2^r$, we formulate radix-code selection as a security-constrained discrete optimization problem that accounts for subfield-check padding, code dimension, required distance, base-OT count, and q-ary symbol width. We derive exact communication thresholds showing when reduced base OTs can compensate for larger q-ary encoding cost. Then we convert the Griesmer bound into communication lower bounds, yielding certificates for regions where non-binary radices cannot improve communication, are provably beneficial, or remain dependent on better code constructions. Finally, we instantiate the framework with simplex and BCH constructions and CodeTables entries, and verify the selected $\delta=12$ codes with Magma.
Metadata
- Available format(s)
-
PDF
- Category
- Implementation
- Publication info
- Preprint.
- Keywords
- Oblivious transfer extensionq-ary codesprivate lookupfinite-batch analysissecure computation
- Contact author(s)
- zhangzhr @ zhejianglab org
- History
- 2026-11-05: approved
- 2026-11-03: received
- See all versions
- Short URL
- https://ia.cr/2026/2734
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2734,
author = {Zhuoran Zhang},
title = {Finite-Batch q-ary {OT} Extension for High-Arity Private Lookup: Certified Radix--Code Co-Design},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2734},
year = {2026},
url = {https://eprint.iacr.org/2026/2734}
}
