Questions tagged [hard-core-predicate]
A hard-core predicate of a one-way function $f$ is a predicate b (i.e., a function whose output is a single bit) which is easy to compute (as a function of x) but is hard to compute given $f(x)$.
22 questions
4
votes
1
answer
113
views
Hardcore Predicate for ECDLP
The 1999 paper "The Security of all RSA and Discrete Log Bits" by Hastad and Naslund here states that any block of $O(\log \log N)$ bits where $N=pq,$ of the encrypted RSA output is known to ...
- 25.7k
0
votes
0
answers
66
views
Hard-Сore Functions and Hard-to-Approximate Functions
Definition of a hard-core:
Let $h: \{0, 1\}^* \rightarrow \{0, 1\}^*$ be a poly-time-computable function s.t. $|h(x)| = |h(y)| (\forall |x| = |y|)$ and let $l(n) := |h(1^n)|$
$h$ is a hard-core of a ...
user122572
1
vote
1
answer
202
views
Prove that there is no universal Hard-Core Predicates
A polynomial-time-computable predicate $b:\{0,1\}^* \to \{0,1\}$ is called a universal hard-core predicate if for every one-way function $f$, the predicate $b$ is a hard-core of $f$.
I need to prove ...
- 33
0
votes
0
answers
59
views
One way function bulit by singular matrices
Our one-way function $F:\mathbb{F}_q^{n\times n}\times \mathbb{F}_q^{n\times n}\to\mathbb{F}_q^{n\times n}$ differs from traditional OWFs, which focus on being hard to invert. Instead, ours aims to be ...
- 540
0
votes
0
answers
56
views
One-way function constructed by multivariable polynomials
Although the conjecture regarding the existence of one-way functions remained open, there are numerous NP-based methods for constructing diverse one-way functions, including DL, lattice, and subset ...
- 540
2
votes
1
answer
228
views
Goldreich Levin Theorem
I am running into the Goldreich Levin Theorem.
According to what I know a predicate $h: \{ 0,1 \}^* \to \{ 0,1 \} $ is a hardcore predicate for a function $f: \{ 0,1 \}^* \to \{ 0,1 \}^* $ if:
$h$ is ...
- 123
1
vote
1
answer
176
views
Question on Simulation based security proof for Oblivious Transfer (OT) against semi-honest adversaries
I'm currently reading this How To Simulate It – A Tutorial on the Simulation Proof Technique.
On p. 10, there is a proof using simulation for 1/2-OT, against semi-honest adversaries. Briefly, the ...
- 1,002
1
vote
1
answer
758
views
Suppose there exists a one-way function, show that there exists a one-way function with none of its input bit is a hardcore bit
I just learnt the definition of hardcore bit, and I have no intuition about this. I want to know what are the possible approaches to this problem.
- 31
0
votes
0
answers
56
views
PRGs from OW functions
Given a OW function $f:\{0,1\}^n\to\{0,1\}^n$ with hardcore predicate $h(x)$, you can build a PRG $G$ by setting $$G(s):=f(s)\Vert h(s), \quad s\leftarrow\{0,1\}^n.$$
The expansion condition for $G$ ...
0
votes
0
answers
217
views
XOR of all bits of $f(x)$ a hard-core bit
Why consider a random $r$ in building a hardcore predicate in Goldreich Levin theorem? Why not consider just the XOR of all bits of the input?
- 273
3
votes
1
answer
235
views
Understanding Lindell's proof of (semi-honest) oblivous transfer
In Lindell's tutorial "How to simulate it" [2016/046], section 4.3, he gives a semi-honest protocol for oblivious transfer, based on enhanced trapdoor permutations and a corresponding hard-...
- 461
3
votes
1
answer
315
views
Hard-core bits from RSA assumption
I am trying to understand better the hard-core bit property from the RSA assumption. The paper by Håstad and Nåslund shows that every single bit is hard-core. By the result itself, two or more bits ...
- 295
0
votes
0
answers
337
views
How to prove that a predicate is not hard-core?
How can I prove that given a predicate $hc$ and a one-way function $f$ that $hc$ is not hard-core?
I was thinking about something like that:
i define $f(x) = (g(x), hc(x))$ that is one-way but $hc$ ...
- 63
3
votes
0
answers
181
views
Does weak hardcore bit(s) implies strong hardcore bit(s)?
It is well known that weak OWF implies strong OWF
by concatenating several evaluations of weak OWF (see e.g. here),
where weak OWF is defined as
$ \exists $ poly $Q$, $\forall$ PPT $\mathcal A$ such ...
- 31
1
vote
1
answer
255
views
A modification of the Blum-Micali construction
Consider the following modification of the Blum-Micalli construction (denoted by BM):
$G_l(x) = f^l(x) || BM^l(x)$
I am asked the following questions about it:
Show it is a PRG of fixed stretch for ...
- 1,243