Skip to main content
The 2024 Developer Survey results are live! See the results

# Questions tagged [reduction]

Reduction is a technique for proving the security of a cryptosystem.

30 questions
Filter by
Sorted by
Tagged with
1 vote
0 answers
51 views

### Proof that Inverse CDH and Square CDH are equivalent

I am trying to prove said equivalence, but when proving SCDH -> ICDH using a reduction, I get stuck since I don't know how to compute $g^{x^2}$ starting from $g^{x^{-1}}$. Suppose exists $A_{ICDH}$ ...
2 votes
1 answer
83 views

### Reduction from factoring to RSA and the Oracle RSA problem

Recently I read some papers related to RSA Brown16,AM09,BNPS01 and I learned that there is a variant problem of RSA is The oracle RSA problem (or one more RSA Problem) is $m+1$ copies of the classic ...
• 311
2 votes
0 answers
103 views

2 votes
1 answer
305 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 ...
• 125
5 votes
2 answers
738 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
4 votes
1 answer
127 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, "...
• 403
1 vote
1 answer
137 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 ...
• 556
0 votes
0 answers
122 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
1 answer
110 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?
3 votes
0 answers
151 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 ...
• 73
1 vote
0 answers
61 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,501