# Questions tagged [cryptography]

The tag has no usage guidance.

8 questions
Filter by
Sorted by
Tagged with
2 votes
1 answer
43 views

### 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 ...
1 vote
0 answers
56 views

### 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 ...
0 votes
0 answers
61 views

### Vidick's proof of parallel DI-QKD

This question is based on the paper- https://arxiv.org/abs/1703.08508. As far as I understand, for this proof Vidick uses a quantum parallel repetition for 3 player- Alice, Bob and Eve but the results ...
1 vote
0 answers
79 views

### 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
165 views

### 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
49 views

### 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
77 views

### 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 ...
3 votes
1 answer
147 views

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