Skip to main content
New
Stack Overflow Jobs powered by Indeed: A job site that puts thousands of tech jobs at your fingertips (U.S. only). Search jobs

Questions tagged [reduction]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
95 views

Direct quantum reduction from GapSVP to SIS

Looking through Chen's recent paper, if we forget about complex Gaussians and just build uniform superpositions over hypercubes, we could create the state $$\sum_{v\in L}\vert v\rangle \sum_{y\in\...
Sam Jaques's user avatar
  • 1,192
0 votes
0 answers
20 views

Reduction For MAC systems

I am not too knowledgeable regarding reductions for message authentication code encryption. Here is an example I found: There is a MAC' based on a preliminary existing MAC as such: MAC'(k, m) = MAC(k,...
sangaCat's user avatar
1 vote
2 answers
93 views

MAC question i got in a test, would like your opinion on my answer

Given a MAC secure scheme $(\text{Gen}, \text{Mac}, \text{Vrfy})$, a new scheme is suggested: $\text{Gen}' \rightarrow \text{Gen} = (pk_1, sk_1), \text{Gen} = (pk_2,sk_2)$ $\text{Mac}'(m) = (\text{...
binyamin alony's user avatar
1 vote
1 answer
42 views

Proof that semantic security implies key-recovery security

I'm trying to prove that semantic security implies key-recovery security. There is already a question that addresses this, but it doesn't explain the setup of the security reduction, which is what I'm ...
cmplx96's user avatar
  • 113
0 votes
1 answer
35 views

Can the runtime of a reduction help an adversary distinguish the reduction from the adversary's challenger?

Generally, in cryptography, the security of a scheme/protocol $\Pi$ relying on a hard problem $P$ is demonstrated by constructing a reduction $\mathcal{B}$ that takes as input an instance of the ...
vxek's user avatar
  • 467
5 votes
1 answer
229 views

Is F(k,k) $\oplus$ F(k,x) a pseudorandom permutation?

Suppose that $F: \{0,1\}^n\times \{0,1\}^n\rightarrow \{0,1\}^n$ is a strongly pseudorandom permutation. Let $\hat{F}(k,x):=F(k,k)\oplus F(k,x)$. I know that $\hat{F}$ can't be a strongly ...
YirongHu's user avatar
1 vote
1 answer
113 views

Decision LWE vs Search LWE: Which one is harder?

Sometimes if we have an attacker who's able to solve decision-LWE problem then we can use them (as a sub-routine) to solve (search) LWE problem, i.e., $\mathsf{sLWE} \leq \mathsf{dLWE}$. Conversely, ...
user1035648's user avatar
1 vote
2 answers
258 views

The security of using a digital signature scheme twice with randomness

Suppose $\Pi=(Gen,Sign,Vrfy)$ is a secure signature scheme, is the following signature scheme $\Pi'$ secure? $Gen'$: The same as $Gen$, output public-private key pair $pk,sk$ on input $1^n$ $Sign'$: ...
Kagura Hitoha's user avatar
0 votes
0 answers
76 views

Distinguishing between two DDH-like tuples

Given a group generator $g$ (in a group where DDH is hard). Let $X_1=g^{x_1}$ and $X_2=g^{x_2}$ be two public elements, where $x_1$ and $x_2$ are selected randomly and kept secret. Consider a game ...
Doron's user avatar
  • 99
3 votes
1 answer
211 views

Resources for simple MPC proofs

Could anyone direct me to literature regarding privacy proofs in the MPC setting. For example, how can one prove the following simple problem: Suppose a setting with $n$ parties $S_1, \ldots, S_n$ ...
Kolja's user avatar
  • 143
1 vote
1 answer
141 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 ...
puppet puppet's user avatar
2 votes
0 answers
47 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 ...
GH HONG's user avatar
  • 33
5 votes
1 answer
140 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 ...
constantine's user avatar
2 votes
1 answer
73 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, ...
gamarcad's user avatar
4 votes
1 answer
316 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 ...
user108492's user avatar
3 votes
1 answer
184 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 ...
kangli's user avatar
  • 75
2 votes
2 answers
214 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 ...
constantine's user avatar
11 votes
1 answer
541 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$ ...
Lee Seungwoo's user avatar
3 votes
0 answers
202 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 ...
Kirill Tsar.'s user avatar
1 vote
0 answers
33 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 ...
Orla Mccoy's user avatar
2 votes
1 answer
291 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 ...
Tom Finet's user avatar
  • 125
5 votes
2 answers
729 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 ...
Marcellus's user avatar
  • 264
4 votes
1 answer
123 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, "...
Anon's user avatar
  • 403
1 vote
1 answer
127 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 ...
user918212's user avatar
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 :)
Facundo Fleitas's user avatar
2 votes
1 answer
90 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?
Novice_researcher's user avatar
3 votes
0 answers
147 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 ...
DP2040's user avatar
  • 73
1 vote
0 answers
59 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 ...
Léo Colisson's user avatar