International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Knowledge Encryption and Its Applications to Simulatable Protocols With Low Round-Complexity

Authors:
Yi Deng , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chinese Academy of Sciences
Xinxuan Zhang , State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences; School of Cyber Security, University of Chinese Academy of Sciences
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: ASIACRYPT 2022
Abstract: We introduce a new notion of public key encryption, knowledge encryption, for which its ciphertexts can be reduced to the public-key, i.e., any algorithm that can break the ciphertext indistinguishability can be used to extract the (partial) secret key. We show that knowledge encryption can be built solely on any two-round oblivious transfer with game-based security, which are known based on various standard (polynomial-hardness) assumptions, such as the DDH, the Quadratic($N^{th}$) Residuosity or the LWE assumption. We use knowledge encryption to construct the first three-round (weakly) simulatable oblivious transfer. This protocol satisfies (fully) simulatable security for the receiver, and weakly simulatable security ($(T,\epsilon)$-simulatability) for the sender in the following sense: for any polynomial $T$ and any inverse polynomial $\epsilon$, there exists an efficient simulator such that the distinguishing gap of any distinguisher of size less than $T$ is at most $\epsilon$. Equipped with these tools, we construct a variety of fundamental cryptographic protocols with low round-complexity, assuming only the existence of two-round oblivious transfer with game-based security. These protocols include three-round delayed-input weak zero knowledge argument, three-round weakly secure two-party computation, three-round concurrent weak zero knowledge in the BPK model, and a two-round commitment with weak security under selective opening attack. These results improve upon the assumptions required by the previous constructions. Furthermore, all our protocols enjoy the above $(T,\epsilon)$-simulatability (stronger than the distinguisher-dependent simulatability), and are quasi-polynomial time simulatable under the same (polynomial hardness) assumption.
Video from ASIACRYPT 2022
BibTeX
@inproceedings{asiacrypt-2022-32503,
  title={Knowledge Encryption and Its Applications to Simulatable Protocols With Low Round-Complexity},
  publisher={Springer-Verlag},
  author={Yi Deng and Xinxuan Zhang},
  year=2022
}