Questions tagged [reduction]
Reduction is a technique for proving the security of a cryptosystem.
18
questions
1
vote
1
answer
67
views
Proving an identification-scheme based on a digital signature is secure
I am trying to prove to myself that an identification scheme derived from a digital signature in a challenge/response manner is secure, based on the security of the digital signature scheme. I've ...
2
votes
0
answers
41
views
worst case to average case reduction in non-cyclotomic Ring LWE
I understand that we need 2-to-power cyclotomic ring to show that the solving decision RLWE is as hard as solving search RLWE.
Is there any chance to prove it without 'cyclotomic' property?
For ...
- 33
5
votes
1
answer
93
views
The rigorous proof in the commitment based on CRHF
I'm reading about the lecture of Yevgeniy Dodis. In his lecture 14, section 2.3.2, gives a commitment construction based on CRHF, but the proof of hiding is high-level. I want to know the rigorous ...
- 147
2
votes
1
answer
45
views
Reduction from Distinguisher to Indishtinguishability
Content and Informal Problem
Suppose a protocol $\pi$ doing an arbitrary task between two users A and B. I only know that $\pi$ relies on a IND-CPA symmetric encryption scheme $\mathcal{E} = $(KeyGen, ...
- 23
4
votes
1
answer
234
views
Reducing exact SVP to exact SIVP
In "Efficient reductions among lattice problems" by Micciancio (2007) it is said, that
SVP reduces to SIVP in their exact versions.
I did not found anything about this fact, is a reduction ...
- 41
3
votes
1
answer
171
views
How does the lengths of the Gram-Schmidt orthogonal basis of a lattice basis change after lll reduction?
Assuming there is a lattice basis $B=\{b_1,...,b_n\}$, we use $B^*=\{b_1^*,...,b_n^*\}$ to denote the Gram-Schmidt orthogonal basis, where $b_i^*=\pi_i(b_i)$ and $\pi_i(b_i)$ denotes the projection of ...
- 65
2
votes
2
answers
205
views
A problem about matrix
I have an idea but I don't know if it will work. For the appropriate $p$ it is easy to find $n$ linearly independent $x_i$. Then we compute the inner product between the $x_i$. I think the information ...
- 147
11
votes
1
answer
432
views
What does 'a reduction is tight' mean rigorously?
As far as I know, when someone says 'a reduction is tight', it means that given that there is an adversary $A$ with advantage $\epsilon$ and running time $t$ and another adversary $B$ utilizing $A$ ...
- 363
3
votes
0
answers
186
views
What does break with "usual" classical security reductions in quantum setting?
OK, so I know that this is somewhat really basic in "post-quantum discourse", but unfortunately I did not find any textbooks/entry level papers specific to the topic of reductions in the ...
- 589
1
vote
0
answers
29
views
Prove security against passive attacks by reduction
I have two private-key encryption ($Π$ and $Θ$) and their concatenation $Π\#Θ$. For example:
$$
Enc_{Π\#Θ}( \ ⟨k_Π, k_Θ⟩, \ ⟨m_Π, m_Θ⟩ \ ) = ⟨ \ Enc_Π(k_Π, m_Π),\ Enc_Θ(k_Θ, m_Θ) \ ⟩;
$$
(Same for ...
- 11
1
vote
1
answer
178
views
Proving semantic security implies security from key-recovery attack
I am working on problem 2.11 from the book: A Graduate Course in Applied Cryptography by Dan Boneh and Victor Shoup. The problem reads as follows:
Problem 2.11: Let $\mathcal{E} = (E, D)$ be a cipher ...
- 115
5
votes
2
answers
595
views
Security reduction seems to wrongly show that a non-PRF is a PRF
This is a well-known exercise that has already even been posted here.
I understand both arguments to prove and disprove that $F'$ and $\bar{F}$ are PRFs,
as I explain below,
however, it seems that the ...
- 264
3
votes
1
answer
98
views
In reduction from search LWE to decsion LWE why sampling needs to repeat a polynomial number of times?
I've been reading through MIT's lecture notes on learning with errors here, and I'm trying to understand the reduction from Search LWE to Decision LWE, as described there in Section 2.7, "...
- 383
1
vote
1
answer
94
views
Private key encryption based on NP-complete problem
Over a decade ago, a question was asked on Stack Overflow, which basically asked if there were any encryption schemes that are reducible to an NP-complete problem, in the sense that breaking the ...
- 526
0
votes
0
answers
100
views
How to reduce Diffie Hellman problem to ElGamal?
I'm trying to answer without success questions (ii - iv)
Any hint will be appreciated :)
2
votes
0
answers
61
views
Meta Reduction in Fiat Shamir Transformation
What is meant by meta reduction? What does it achieve and how is it different from the normal reduction technique?
2
votes
0
answers
110
views
polynomial time reduction from SIS to decisional-LWE?
Is the claim "If there is an efficient algorithm that solves SIS, then there is an efficient algorithm that solves decisional LWE" is sufficient?
or,
Is the claim above is equivalent to the ...
- 63
1
vote
0
answers
57
views
Provable security: impossible reduction when messages are encrypted/semantic security with function depending on the output of adversary
I've a problem with a protocol for which I can prove the security if the messages sent by the adversary are sent in clear, but I can't prove the security anymore if the messages sent by the adversary ...
- 1,126