Questions tagged [reduction]
Reduction is a technique for proving the security of a cryptosystem.
46 questions
1
vote
0
answers
89
views
Reduction from approximate $SVP$ to approximate $GCD$
$SVP(n^a,p)$ be the problem of approximating $SVP$ in $p$-norm to $n^a$ approximation factor.
At $a<1$ there are complexity theoretic hardness results. $a\in[1,2]$ finds cryptographic applications.
...
- 1,215
2
votes
2
answers
132
views
The word "inefficient" means different in different context?
I'm reading a paper about reduction. There are some statements like
Reductions usually run the original adversary as a subroutine... most reductions even work for inefficient adversaries.
���...
- 318
2
votes
1
answer
103
views
Upper bound of ``subadversary'' in a reduction
Suppose there is a PPT adversary $\mathcal{A}$ against some scheme in game $G_1$ with non-negligible winning probability. My goal is to construct a $G_2$ adversary $\mathcal{B}$ using $\mathcal{A}$ as ...
- 318
3
votes
1
answer
227
views
Is LWE even an NP language?
I can define LWE with $m$ samples, $n$ dimensions of secret, modulus $q$, secret distribution $\chi_s$ and error distribution $\chi_e$. The LWE problem asks: given a uniformly random matrix $A$ and $b=...
- 1,920
1
vote
1
answer
128
views
Security reduction advantage bounds
Suppose we have a hard problem, and a signature scheme based on that hard problem. Why do we try and bound the advantage of forger for the signature scheme above by the advantage of an adversary ...
3
votes
1
answer
81
views
SelfTargetMSIS from PlainSelfTargetMSIS reduction
When analyzing Dilithium's security, JMW24 claims there is a reduction from $\mathsf{PlainSelfTargetMSIS}$ to $\mathsf{SelfTargetMSIS}$ (p. 9):
Proof. The probability that a uniformly random $B \gets ...
- 83
5
votes
1
answer
138
views
Security Reductions With Statistical Distance
Suppose I have a cryptographic problem $X$ (e.g.: LWE with a specific noise distribution), and an adversary $A$ against $X$ with non-negligible success probability. Then suppose I have another problem ...
- 1,920
4
votes
2
answers
179
views
Confusion in proof details of General Forking Lemma in paper [BN06]
In ACM CCS 2006, Mihir Bellare and Gregory Neven gave an elegant proof of General Forking Lemma [https://doi.org/10.1145/1180405.1180453]. However, it makes me really confused about steps to prove $\...
- 71
2
votes
0
answers
42
views
Can a reduction sample from conditional discrete gaussian in polynomial time without the help of a trapdoor?
For a matrix $\mathbf{A} \in \mathbb{Z}_q^{n\times m}$ I will use $\mathbf{A}^{-1}_\sigma (\mathbf{v})$ to denote a vector $\mathbf{u}$ sampled from a discrete gaussian over $\mathbb{Z}^m$ with ...
- 551
3
votes
1
answer
488
views
What's wrong with the obvious reduction of factoring to DLOG?
Suppose you can solve DLOG in arbitrary groups. Then I give you the challenge of solving DLOG$(a,1)$ over the group $\mathbb{Z}_n^*$, where $a$ is some arbitrary integer and $n$ is some integer to be ...
- 1,920
1
vote
1
answer
71
views
Has the Regev PKE pseudorandom ciphertexts?
I was wondering if the following claim is true.
Claim. Under decisional ${\sf LWE}_{q,m,n,\chi}$, the Regev PKE scheme $\Pi=(\sf KG,Enc,Dec)$ has pseudorandom ciphertexts.
Suppose for contradiction ...
- 266
3
votes
2
answers
210
views
Reduction to the DDH problem
I am struggling with a specific reduction as a part of a question I am solving and I was wondering if I can get some advice.
Assume we have Adversary A that can distinguish with high probability ...
- 111
1
vote
2
answers
170
views
Prove that this Modified CBC-MAC is not secure
In the following problem:
Prove that the following modifications of basic CBC-MAC do not yield a secure
MAC (even for fixed-length messages):
(b) A random initial block is used each time a message ...
1
vote
0
answers
41
views
On the proof of building an SKE from a PRF
I am reading the construction that we make a SKE scheme $\sf \Pi=(Gen,Enc,Dec)$ from a PRF $F$. In particular, work on the proof there we assume that given a secure PRF, we can construct a CPA-secure ...
- 266
1
vote
0
answers
164
views
'Tightness loss' in security reductions
This is probably similar to "What does 'a reduction is tight' mean rigorously?".
I am getting into security proofs, and started reading about reduction tightness. If problem P1 reduces to ...
- 11