Theory of cryptography | Pseudorandomness

Hard-core predicate

In cryptography, 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). In formal terms, there is no probabilistic polynomial-time (PPT) algorithm that computes b(x) from f(x) with probability significantly greater than one half over random choice of x. In other words, if x is drawn uniformly at random, then given f(x), any PPT adversary can only distinguish the hard-core bit b(x) and a uniformly random bit with negligible advantage over the length of x. A hard-core function can be defined similarly. That is, if x is chosen uniformly at random, then given f(x), any PPT algorithm can only distinguish the hard-core function value h(x) and uniformly random bits of length |h(x)| with negligible advantage over the length of x. A hard-core predicate captures "in a concentrated sense" the hardness of inverting f. While a one-way function is hard to invert, there are no guarantees about the feasibility of computing partial information about the preimage c from the image f(x). For instance, while RSA is conjectured to be a one-way function, the Jacobi symbol of the preimage can be easily computed from that of the image. It is clear that if a one-to-one function has a hard-core predicate, then it must be one way. Oded Goldreich and Leonid Levin (1989) showed how every one-way function can be trivially modified to obtain a one-way function that has a specific hard-core predicate. Let f be a one-way function. Define g(x,r) = (f(x), r) where the length of r is the same as that of x. Let xj denote the jth bit of x and rj the jth bit of r. Then is a hard core predicate of g. Note that b(x, r) = where <·, ·> denotes the standard inner product on the vector space (Z2)n. This predicate is hard-core due to computational issues; that is, it is not hard to compute because g(x, r) is information theoretically lossy. Rather, if there exists an algorithm that computes this predicate efficiently, then there is another algorithm that can invert f efficiently. A similar construction yields a hard-core function with O(log |x|) output bits. Suppose f is a strong one-way function. Define g(x, r) = (f(x), r) where |r| = 2|x|. Choose a length function l(n) = O(log n) s.t. l(n) ≤ n. Let Then h(x, r) := b1(x, r) b2(x, r) ... bl(|x|)(x, r) is a hard-core function with output length l(|x|). It is sometimes the case that an actual bit of the input x is hard-core. For example, every single bit of inputs to the RSA function is a hard-core predicate of RSA and blocks of O(log |x|) bits of x are indistinguishable from random bit strings in polynomial time (under the assumption that the RSA function is hard to invert). Hard-core predicates give a way to construct a pseudorandom generator from any one-way permutation. If b is a hard-core predicate of a one-way permutation f, and s is a random seed, then is a pseudorandom bit sequence, where fn means the n-th iteration of applying f on s, and b is the generated hard-core bit by each round n. Hard-core predicates of trapdoor one-way permutations (known as trapdoor predicates) can be used to construct semantically secure public-key encryption schemes. (Wikipedia).

Video thumbnail

Predicates: Sample Problems

This video contains solutions to sample problems involving predicates. This includes: * Finding which elements of a domain make a predicate true * Determining whether a quantified statement is true or false

From playlist Discrete Mathematics

Video thumbnail

Predicates and their Truth Sets

A predicate is a sentence that depends on the value of a variable. For instance, "x is greater than 3". If you tell me a specific value of x, like 7 or 2, then the predicate becomes a logical statement which is either true or false. The Truth Set of a predicate is all of the values of the

From playlist Discrete Math (Full Course: Sets, Logic, Proofs, Probability, Graph Theory, etc)

Video thumbnail

1.5.1 Predicate Logic 1: Video

MIT 6.042J Mathematics for Computer Science, Spring 2015 View the complete course: http://ocw.mit.edu/6-042JS15 Instructor: Albert R. Meyer License: Creative Commons BY-NC-SA More information at http://ocw.mit.edu/terms More courses at http://ocw.mit.edu

From playlist MIT 6.042J Mathematics for Computer Science, Spring 2015

Video thumbnail

SEM_019 - Linguistic Micro-Lectures: Predications and Predicates

What are predicates and in what way are they related to predications? Within less than two minutes Prof. Handke explains the central machinery of predicate logic. (Optional Spanish subtitles by Andrea Yaques, Lima, Peru)

From playlist Micro-Lectures - Semantics

Video thumbnail

Introduction to Predicate Logic

This video introduces predicate logic. mathispower4u.com

From playlist Symbolic Logic and Proofs (Discrete Math)

Video thumbnail

SEM122 - Predicate Logic I

This first E-Lecture on Predicate Logic is meant as a gentle introduction. It first points out why propositional logic alone is not sufficient for the formalization of sentence meaning and then introduces the central machinery of predicate logic using several examples with which the studen

From playlist VLC103 - The Nature of Meaning

Video thumbnail

What is a Predicate? English Grammar for Beginners | Basic English | ESL

Do you know how to find the predicate of a sentence? The predicate contains the verb! You may also like What is a Subject http://bit.ly/2nUnVFp What is a Noun http://bit.ly/2o46sqS What is a Verb http://bit.ly/2nA16Gi You have great ideas. But no one will know about them if you can

From playlist It Starts With Literacy

Video thumbnail

Introduction to Predicates and Quantifiers

This lesson is an introduction to predicates and quantifiers.

From playlist Mathematical Statements (Discrete Math)

Video thumbnail

Discrete Math - 1.4.1 Predicate Logic

Introduction to predicates and propositional functions. Textbook: Rosen, Discrete Mathematics and Its Applications, 7e Playlist: https://www.youtube.com/playlist?list=PLl-gb0E4MII28GykmtuBXNUNoej-vY5Rz

From playlist Discrete Math I (Entire Course)

Video thumbnail

On the Approximation Resistance of Balanced Linear Threshold Functions - Aaron Potechin

Computer Science/Discrete Mathematics Seminar I Topic: On the Approximation Resistance of Balanced Linear Threshold Functions Speaker: Aaron Potechin Affiliation: University of Chicago Date: March 25, 2019 For more video please visit http://video.ias.edu

From playlist Mathematics

Video thumbnail

SYN106 - The Sentence I

It is usually assumed that the sentence is the highest-ranking unit of syntax. However, not all sentences are structurally complete. For this reason, a distinction is drawn between two sentence types: minor and major sentences. This clip discusses the central properties of these two senten

From playlist VLC201 - The Structure of English

Video thumbnail

Small-set expansion in Grassman graph and the 2-to-2 Games Theorem (Lecture 1) by Prahladh Harsha

Discussion Meeting Workshop on Algebraic Complexity Theory  ORGANIZERS Prahladh Harsha, Ramprasad Saptharishi and Srikanth Srinivasan DATE & TIME 25 March 2019 to 29 March 2019 VENUE Madhava Lecture Hall, ICTS Bangalore Algebraic complexity aims at understanding the computationa

From playlist Workshop on Algebraic Complexity Theory 2019

Video thumbnail

[LISA] Linguistically-Informed Self-Attention for Semantic Role Labeling | AISC

For more details including paper and slides, visit https://aisc.a-i.science/events/2019-04-25/

From playlist Natural Language Processing

Video thumbnail

Lecture 12: Core Data

In the second of the final series of four lectures targeted at helping students in Stanford’s iOS development course from Spring 2020 with their final projects, a powerful object-oriented database, Core Data, is used to enhance the previously-introduced Enroute application. To date in the

From playlist CS193p iPhone Application Development Spring 2020

Video thumbnail

RailsConf 2015 - RSpec: It's Not Actually Magic

By, Noel Rappin RSpec is often described with the word “magic” by both its users and its detractors. Understanding how RSpec matchers, doubles, and specifications work will help you as an RSpec user. You will be able to take advantage of RSpec’s flexibility to make your tests clearer and

From playlist RailsConf 2015

Video thumbnail

Garden City Ruby Conference - ActiveRecord can't do it? Arel can!

By, Vipul A Prathamesh S ActiveRecord can't do it? Arel can! Active Record is awesome. But how does ActiveRecord handle generating complex SQL queries? Under the hood it's handled by Arel. Most of the time, Rails developers don't have to know about how Arel works. But sometimes Active Rec

From playlist Garden City Ruby 2015

Video thumbnail

[Syntax] Adjectives, Adverbs, and Prepositions

We introduce Attributive Adjectives, Predicative Adjectives, Intensifiers, Adverbs, Prepositions, and Postpositions. LIKE AND SHARE THE VIDEO IF IT HELPED! Visit our website: http://bit.ly/1zBPlvm Subscribe on YouTube: http://bit.ly/1vWiRxW Like us on Facebook: http://on.fb.me/1vWwDRc Su

From playlist Syntax

Video thumbnail

SYN_028 - The Predicate (in Syntax)

In this short micro-lecture, Antonia Eisermann, one of Prof. Handke's students, discusses the significance and the role of the predicate in PDE grammar.

From playlist Micro-Lectures - Syntax

Related pages

Jacobi symbol | One-way function | Advantage (cryptography) | Semantic security | Vector space | Injective function | Inner product space | Information theory | Cryptography | Hadamard code