Paper 2026/788
Secret-Carrying Puzzles and Garbled Circuits Optimized for Zero-knowledge Proofs
, Indian Institute of Technology BombayAbstract
In this work, we introduce the concept of Obliviously Checkable Secret-Carrying Puzzles (OxSP) and build proof-friendly Garbled Circuits (GCs) to enable their practical implementation. OxSPs allow one to publicly pose puzzles and verify purported solutions received in response, keeping the desired parts of the puzzles and the responses hidden. We show how OxSPs can be based on Garbled Circuits (GCs). However, this requires ZK-SNARK proofs of correctness of garbling. We note that combining existing GC and ZK-SNARK constructions results in very large computational costs for the OxSP solvers. Our main technical contribution is to design a new proof-friendly GC construction which cuts down the cost of generating a proof of correct garbling to almost a third, without resorting to non-standard cryptographic assumptions. Beyond its use in OxSP, we expect our proof-friendly GCs to be of significant independent interest, as a tool for auditable secure 2-party computation.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Garbled CircuitZero-knowledge Proof2-PC
- Contact author(s)
-
draychawdhuri @ cse iitb ac in
mp @ cse iitb ac in - History
- 2026-04-23: approved
- 2026-04-21: received
- See all versions
- Short URL
- https://ia.cr/2026/788
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/788,
author = {Debasish Ray Chawdhuri and Manoj Prabhakaran},
title = {Secret-Carrying Puzzles and Garbled Circuits Optimized for Zero-knowledge Proofs},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/788},
year = {2026},
url = {https://eprint.iacr.org/2026/788}
}
