New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

# 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)$.

19 questions
Filter by
Sorted by
Tagged with
43 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 ...
• 370
44 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 ...
• 370
100 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 ...
• 113
1 vote
110 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 ...
• 962
495 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.
• 11
48 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$ ...
165 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?
• 261
169 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
248 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
310 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
146 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 ...
1 vote
232 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 ...
• 1,243
488 views

### Why can't we construct a PRG from a one-way function and hc, but only one-way permutation

From Katz & Lindell's book, theorem 7.19: Let f be a one way permutation with hard-core predicate hc. Then the algorithm $G(s)=f(s)||hc(s)$ is a PRG with expansion factor $\ell(n)=n+1$. But what ...
• 21
1k views

### Katz/Lindell Problem 7.6

Let $f$ be a length-preserving one-way function, and let $\text{hc}$ be a hard-core predicate of $f$. Define $G$ as $G(x)=f(x)\|\text{hc}(x)$. Is $G$ necessarily a pseudorandom generator? The answer ...
• 468
1 vote
82 views

### Lsb as hard core predicate in a sign-hash scheme

Given a random oracle and a deterministic signature scheme. Is the following $hc(x)$ an hardcore predicate of $H(SIG_k(x))$ ? $$hc(x)=lsb(H(SIG_k(x)))$$ How would I get to think about this? I saw a ...
1 vote
409 views

### Generic hardcore predicate for one way functions

I'm going over hardcore predicates now and trying to understand the concept. Some lecture slides I've seen online imply that there cannot be a generic hardcore predicate for all one way functions ...
• 225
251 views

### What Does This Symbol Mean? (Hardcore Predicates for One-Way Functions)

I am studying Pseudorandom Number Generators and when reading the discussion on One-Way Functions and Hardcore Predicates, I came upon this equation. $$b(x,r)=\displaystyle \bigoplus_jx_jr_j$$ I ...
445 views

### what is the difference between one way function and hard core predicate?

Does anyone know what the difference between a one way function is and a hard core predicate? Are they related to each other or different?
• 1
### Hard-core predicates: should the adversary be given $1^n$?
In most (all?) classical sources such as the book of Goldreich (2001), hard-core predicated are defined thus: A polynomial-time computable predicate $b : \{0,1\}^* \to \{0,1\}$ is a hard-core of a ...