Questions tagged [cryptography]
The cryptography tag has no usage guidance.
16
questions
4
votes
0
answers
48
views
Complexity of solving random underdetermined polynomial equations over finite fields
Consider a random system of degree-$d$ polynomials, with $n$ variables and $m$ equations, over some finite field $\mathbb{F}_q:$
$$\begin{align}\sum_{\substack{(\alpha_1,\dots,\alpha_n) \in \mathbb{Z}...
- 41
3
votes
0
answers
84
views
Is universal hashing fully black-box reducible to error correcting code?
Fully black-box reduction is defined as in Notions of reducibility between crytpographic primitives, O. Reingold et al.
Error-correcting code is used in the black-box abstract way in the sense that ...
- 161
3
votes
0
answers
76
views
On the multiplicative overhead 2 in the construction of pairwise independent hashing from ERCs
A standard method of constructing pairwise independent hash function from error-correcting code is as follows:
Given a generator matrix $G$ of a distance-$d$ linear error-correcting code mapping $m$ ...
- 161
5
votes
1
answer
73
views
Does there exist constant overhead reduction between common cryptographic primitives?
I have proved that there exist such reduction between error-correcting codes and exposure resilient functions, which is because that the transpose of a generator matrix for a ERC mapping $\mathbb{F}_2^...
- 161
1
vote
0
answers
67
views
Circuit depth of linear algebra operations
I was checking the following paper [1] about low-depth PRFs from lattices. In table 1 on page 4, there is comparison with other constructions, and it shows evaluation depths of certain PRFs. I'm not ...
- 151
3
votes
0
answers
131
views
Inverse of leftover hash lemma
Leftover hash lemma:
Let $X$ be a random variable over $X \in {\mathcal {X}}$ and let $m>0$. Let $h: {\mathcal S} \times {\mathcal X} \rightarrow \{0,1\}^m$ be a 2-universal hash function. If $m \...
- 818
3
votes
0
answers
28
views
(Classical) Zero Knowledge protocol with quantum poly time simulator
We have lower bounds for classical zero-knowledge protocols (eg we cannot have 3-round zero-knowledge protocols for NP, with negligible soundness and black-box simulation). However, some of these ...
- 31
2
votes
0
answers
69
views
Open Quantum Analogs to Classical Problems
I am looking for interesting examples of complexity-theoretic and cryptographic problems where we have a significant amount of knowledge about the classical version of the problem, but we have no ...
- 121
2
votes
1
answer
64
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 ...
- 149
1
vote
1
answer
99
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 ...
- 387
0
votes
1
answer
86
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 ...
- 101
1
vote
1
answer
175
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
173
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
56
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 ...
- 217
5
votes
0
answers
84
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 ...
- 1,439
3
votes
1
answer
160
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 ...
- 554