Paper 2023/1392

Robust Publicly Verifiable Covert Security: Limited Information Leakage and Guaranteed Correctness with Low Overhead

Yi Liu, Jinan University
Junzuo Lai, Jinan University
Qi Wang, Southern University of Science and Technology
Xianrui Qin, The University of Hong Kong
Anjia Yang, Jinan University
Jian Weng, Jinan University

Protocols with \emph{publicly verifiable covert (PVC) security} offer high efficiency and an appealing feature: a covert party may deviate from the protocol, but with a probability (\eg $90\%$, referred to as the \emph{deterrence factor}), the honest party can identify this deviation and expose it using a publicly verifiable certificate. These protocols are particularly suitable for practical applications involving reputation-conscious parties. However, in the cases where misbehavior goes undetected (\eg with a probability of $10\%$), \emph{no security guarantee is provided for the honest party}, potentially resulting in a complete loss of input privacy and output correctness. In this paper, we tackle this critical problem by presenting a highly effective solution. We introduce and formally define an enhanced notion called \emph{robust PVC security}, such that even if the misbehavior remains undetected, the malicious party can only gain an additional $1$-bit of information about the honest party's input while maintaining the correctness of the output. We propose a novel approach leveraging \emph{dual execution} and \emph{time-lock puzzles} to design a robust PVC-secure two-party protocol with \emph{low overhead} (depending on the deterrence factor). For instance, with a deterrence factor of $90\%$, our robust PVC-secure protocol incurs \emph{only additional ${\sim}10\%$ overhead} compared to the state-of-the-art PVC-secure protocol. Given the stronger security guarantees with low overhead, our protocol is highly suitable for practical applications of secure two-party computation.

Available format(s)
Cryptographic protocols
Publication info
A minor revision of an IACR publication in ASIACRYPT 2023
Secure two-party computationPublicly verifiable covert security1-bit leakageDual execution
Contact author(s)
liuyi @ jnu edu cn
laijunzuo @ gmail com
wangqi @ sustech edu cn
xrqin @ cs hku hk
anjiayang @ gmail com
cryptjweng @ gmail com
2023-09-18: approved
2023-09-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yi Liu and Junzuo Lai and Qi Wang and Xianrui Qin and Anjia Yang and Jian Weng},
      title = {Robust Publicly Verifiable Covert Security: Limited Information Leakage and Guaranteed Correctness with Low Overhead},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1392},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.