Questions tagged [cryptography]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer

Can polynomial sized DNF be used to construct weak PRF

Let $F_x : \{0;1\}^n \rightarrow \{0;1\}$ be a family of polyomially sized DNF (with respect to $n$). The key $x$ lives in $\{0;1\}^{\lambda(n)}$, $\lambda(n)$ is polynomially bounded in $n$. Can such ...
  • 109
1 vote
0 answers

Code indistinguishability assumption for Code based cryptography (in special cases)

Cryptosystems that are based on error correcting codes are often based with hardness of the two problem. Computational syndrome decoding is hard Indistinguishability Assumption (IA): Distinguishing ...
  • 387
0 votes
1 answer

Vidick's proof of parallel DI-QKD

This question is based on the paper- As far as I understand, for this proof Vidick uses a quantum parallel repetition for 3 player- Alice, Bob and Eve but the results ...
  • 101
1 vote
1 answer

Graph associated to a mathematical statement (for the purpose of zero-knowledge proofs)

I'll preface this question by saying I have very little (zero!) knowledge of theoretical computer science, and this post is a genuine attempt to understand something, even if at an intuitive level, ...
0 votes
0 answers

Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon

I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this ...
1 vote
0 answers

Living in Minicrypt, but sampling hard instances without the solution

In Impagliazzo's worlds, Minicrypt is the one, where one way functions exist. In other words, we can sample hard-on-average instances of NP complete problems. Question: Is living in Minicrypt, where ...
5 votes
0 answers

Chosen message attack on unhashed GGH signatures?

Background: I've been reading GGH's Public-Key Cryptosystems from Lattice Reduction Problems, and have a question about a remark the authors make: "It is important to remark at the outset, that ...
  • 1,429
3 votes
1 answer

Is there a notion of indistinguishability obfuscation for almost equivalent circuits?

In the definition of indistinguishability obfuscation (iO), we have a probabilistic algorithm Obs that receives as input a circuit C, such that $i)$ the output Obs(C) is a circuit with the same ...