On Basing Size-Verifiable One-Way Functions on NP-Hardness

被引：0

作者：

Bogdanov, Andrej ^{[1
]}

Brzuska, Christina ^{[2
,3
]}

机构：

[1] Chinese Univ Hong Kong, Dept Comp Sci & Engn, Hong Kong, Hong Kong, Peoples R China

[2] Microsoft Res, Cambridge, England

[3] Tel Aviv Univ, IL-69978 Tel Aviv, Israel

来源：

THEORY OF CRYPTOGRAPHY (TCC 2015), PT I | 2015年 / 9014卷

关键词：

D O I：

暂无

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We prove that if the hardness of inverting a size-verifiable one-way function can be based on NP-hardness via a general (adaptive) reduction, then NP subset of coAM. This claim was made by Akavia, Goldreich, Goldwasser, and Moshkovitz (STOC 2006), but was later retracted (STOC 2010).

引用

页码：1 / 6

页数：6