什么是核心谓词？

#1 楼

在Goldwasser和Bellare的密码学讲义中，可以找到（第35页）以下文字：方式功能。例如。如果f是RSA函数，则将保留x的Jacobi符号，如果f是离散对数函数EXP，则可以通过简单的Legendre符号计算从f（x）计算x的最低有效位。但是，似乎x至少有一点很难从f（x）中“猜出”，因为x的整体很难计算。问题是：我们能否指出x的特定位，这些位很难计算，以及它们有多难计算。答案令人鼓舞。已知许多结果会给出x的特定位，对于某些特定f（例如RSA）和离散对数函数，给定f（x）很难猜测。我们将在随后的部分中对这些结果进行调查。
更笼统地说，我们将无法从f（x）计算出的关于x的谓词比随机猜测它作为f的核心谓词要好。

因此，超过$ x $的谓词是“一点$ x $”。在“ $ x $可以表示为比特序列”的意义上，不一定是一点；而是从$ x $返回0或1的函数。谓词因此是一个对$ x $进行“说些什么”的函数，其中某些是二进制选择。
例如，对于普通整数， “是7的倍数”是一个谓词（任何整数是否是7的倍数）。
函数$ f $的核心谓词是$ x $的谓词（$ f $的输入），可以很容易地从$ x $计算得出，但不能从$ f（x）$计算得出。当信息完全丢失时，会有非常琐碎的核心谓词（例如，如果$ f（x）$被定义为$ y $的SHA-256，其中$ y $是$ x $的位序列的第一位）谓词“ $ x $的第一位”，根据定义，无法从$ f（x）$）重新计算；这些对于密码学来说并不有趣。更有趣的是谓词，对于给定的$ f（x）$确实具有明确定义的值（即对于给定的值$ z $，谓词$ b（x）$对于所有$ x $始终具有相同的值） $ f（x）= z $）。
硬性谓词的一个示例是BBS伪随机数生成器。令$ n = pq $一个大整数（如RSA模数），其中$ p $和$ q $等于$ 3 $，取模$ 4 $。考虑以模$ n $为模的整数子集，它们是$ n $的互质数，并且是二次残差（二次残差是一个值$ x $，因此存在一个整数$ y $，使得$ y ^ 2 \ equiv x \ mod n $；简而言之，它是“一个至少具有一个平方根的值”）。可以证明一个二次残基（共质数为$ n $）有4个不同的平方根，而其中一个正好是本身是二次残基。
因此，我们可以定义函数$ f（x）= x ^ 2 \ mod n $。它是对模元nn $求模的二次残差的置换。对于给定的二次残基$ y $，存在单个二次残基$ x $，因此$ f（x）= y $。
现在，谓词：我将$ b（x）$定义为$ x $二进制表示形式的所有位的XOR。它返回0或1（它是一个谓词）。给定$ x $，计算起来并不重要。但是，给定$ f（x）$（即$ x ^ 2 \ mod n $），计算$ b（x）$似乎和分解$ n $一样困难。如果可以分解$ n $，则可以从$ x ^ 2 $计算$ x $，因此计算$ b（x）$变得容易；奇怪的是，在给定$ x ^ 2 $的情况下，没有已知更好的方法来计算$ b（x）$。然后说谓词$ b $捕获了$ f $的单向性的本质：给定$ f $的输出，不仅很难找到匹配的输入，而且“仅”找到了xf的异或。输入的内容已经足够困难了。
因此，我们将谓词称为“核心”。美国公民，其中之一是查克·诺里斯（Chuck Norris）。可以合理地假设，如果您可以击败Chuck Norris，那么其余的人都是小菜一碟。查克·诺里斯（Chuck Norris）是美军至高无上的坚决主张。

#2 楼

我不确定比Wikipedia解释的简单多少。 x）$。例如，考虑函数$ f（x）= x·x $。



假定$ x $是非零实数（或有理数，或整数）。那么$ y = f（x）= x·x $仍然是一个非零数字，在这种情况下，始终为正数。即

谓词通常是仅输出一位的函数，即两个可能的值。 （通常我们看一下值为$ 0 $和$ 1 $或false和true的函数。）对于我们的示例，我们采用谓词$ b（x）：=（x \ geq 0）$ ，或作为完整公式：

$$ b（x）= \ begin {cases} 1 \ quad和\ text {if} x \ geq 0 \\ 0＆\ text {if} x <0 \ end {cases} $$



现在，从$ x $计算$ b（x）$很容易。但是，如果我只给你$ f（x）$（一个秘密数字$ x $），那么与随机猜测相比，您没有机会从此信息中猜测$ b（x）$（即，甚至不知道$ f（ x）$）。

这意味着，$ b $是$ f $的核心谓词。

在密码学中，我们将使用此简单的二次函数来代替加密散列函数或加密函数（攻击者不知道密钥），并且我们不需要“不可能猜测”（这些函数/谓词没那么有趣），只需“

然后将这个“太多”正式定义为“在某些安全参数中大于多项式”（如输出大小），即，我们谈论一种功能。

（来自Wikimedia Commons的公共领域图像：Parabola，Heaviside。）