给出了一个函数$H(x)$。如果有一个算法$B(H(x))$获得了$x$的一部分，那么$H(x)$是单向函数吗？

Question

我在阅读这篇论文时提出了这个问题: Pilaram、Hossein和Taraneh Eghlidos。一种高效的基于格的多级秘密共享方案。IEEE关于可靠和安全计算的事务14.1 (2015)：2-8。

在第4节的定理1中，作者指出:因此，在输入Ex上，算法\mathcal{B}输出x的第一部分，即x_1，这与Ajtai函数的单程性相矛盾。

我想知道这是否是证明函数满足单向性的一种正确方法。我是密码学的新手，英语不是我的第一语言。为你的麻烦深感抱歉。谢谢你抽出时间:P

Answer 1

如果有一个算法B(H(x))获得了x的一部分，那么H(x)是一个单向函数吗？

这仍然是可能的。

简化了Katz和Lindel's 现代密码学概论中单向函数的定义，它是一个有效的可计算函数f，使得不存在算法\mathcal A，作为随机x的输入y=f(x)，以非消失概率输出f(x')=y的x'。

该定义与算法\mathcal B的存在相兼容，该算法作为随机x的输入y=f(x)，总是输出x的某些段(例如，它的第一位)。

说明:假设函数h与随机甲骨文无法区分(SHA-3希望如此)。很明显这是个OWF。用f构造一个函数f(x) -- x的第一个位，后面是h(x)。一个算法\mathcal B总是从f(x)产生第一个x比特，但是破坏f单程性的算法\mathcal A可以转化为破坏h单程性的算法\mathcal A'，其成功率至少是\mathcal A的一半。

问题的引语在这个在线文件中。我准备遵循这样的观点，即所做的证明是局部错误的，但我不排除这一点可以通过一些简单的参数来修复，即:如果我们能够找到一个组件x_1，通过对称性，我们可以找到任何x_i。格型密码离我的舒适区太远了，而且我花在纸上的时间太低，所以我可以有一个有用的意见。

注:问题中提到"14.1 (2015)：2-8"，但这与这和这的说法不一致，“第14卷，第1期:2017年1月至2月1日”。上述在线文件的日期是2015年5月20日，以及另一个在线版本，上面写着“内容可能会在最终发布前发生变化”，因此我不能排除该文件后来被修改。