You are currently browsing the tag archive for the ‘quadratic residue’ tag.

Scribed by Anindya De

Summary

In this lecture, we show that the protocol for quadratic residuosity discussed last week is indeed zero-knowledge. Next we move on to the formal definition of proof of knowledge, and we show that the quadratic residuosity protocol is also a proof of knowledge. We also start discussing the primitives required to prove that any language in {NP} admits a zero-knowledge proof.

Read the rest of this entry »

Scribed by Alexandra Constantin

Summary

Today we show that the graph isomorphism protocol we defined last time is indeed a zero-knowledge protocol. Then we discuss the quadratic residuosity problem modulo a composite, and define a protocol for proving quadratic residuosity. (We shall prove that the protocol is zero knowledge next time.)

Read the rest of this entry »

Scribed by Cynthia Sturton

Summary

Today we continue to discuss number-theoretic constructions of CPA-secure encryption schemes.

First, we return to the Decision Diffie Hellman assumption (the one under which we proved the security of the El Gamal encryption scheme) and we show that it fails for {{\mathbb Z}^*_p}, although it is conjectured to hold in the subgroup of quadratic residues of {{\mathbb Z}^*_p}.

Then we introduce the notion of trapdoor permutation and show how to construct CPA-secure public-key encryption from any family of trapdoor permutations. Since RSA is conjectured to provide a family of trapdoor permutations, this gives a way to achieve CPA-secure encryption from RSA.

Read the rest of this entry »

Summary

After showing that last week’s protocol for quadratic residuosity is indeed zero-knowledge, we move on to the formal definition of proof of knowledge, and we show that the quadratic residuosity protocol is also a proof of knowledge.

Read the rest of this entry »

Summary

Today we show that the graph isomorphism protocol we defined last time is indeed a zero-knowledge protocol. Then we discuss the quadratic residuosity problem modulo a composite, and define a protocol for proving quadratic residuosity. (We shall prove that the protocol is zero knowledge next time.)

Read the rest of this entry »

Summary

Today we continue to discuss number-theoretic constructions of CPA-secure encryption schemes.

First, we return to the Decision Diffie Hellman assumption (the one under which we proved the security of the El Gamal encryption scheme) and we show that it fails for {{\mathbb Z}^*_p}, although it is conjectured to hold in the subgroup of quadratic residues of {{\mathbb Z}^*_p}.

Then we introduce the notion of trapdoor permutation and show how to construct CPA-secure public-key encryption from any family of trapdoor permutations. Since RSA is conjectured to provide a family of trapdoor permutations, this gives a way to achieve CPA-secure encryption from RSA.

Read the rest of this entry »

a

Follow

Get every new post delivered to your Inbox.

Join 270 other followers