# Tag Info

### Reducing exact SVP to exact SIVP

It is non-trivial, You need to see the Corollary 7 in Mic07, Micciancio proved that a series of problems (including CVP and SIVP) in the Euclidean norm are equivalent in their exact version under ...
• 179
Accepted

Edited in response to clarification You are assuming that you have A basis of your lattice (equivalently, for $\mathbf{V} = [\vec v_1,\dots, \vec v_n]$, and $\mathbf{U}\in\mathsf{SL}_n(\mathbb{R})$, ...
• 12.5k
Accepted

### What does 'a reduction is tight' mean rigorously?

The usual way to measure the tightness of a reduction (e.g., see [CMS]) is via the tightness gap, defined as $$\frac{t'}{\epsilon'}\big/\frac{t}{\epsilon}=\frac{t'\epsilon}{t\epsilon'}.$$ A reduction ...
• 5,178
Accepted

### Security reduction seems to wrongly show that a non-PRF is a PRF

The advantages of $D$ and $D’$ are not the same. Recall that a distinguisher’s advantage is the difference between the probabilities that it accepts in the “real” and “ideal” experiments, where its ...
• 5,793
Accepted

### How does the lengths of the Gram-Schmidt orthogonal basis of a lattice basis change after lll reduction?

Although there is not a formal result with respect to this question, there is a widely accepted empirical observation for "typical" lattices known as the Geometric Series Assumption (see the ...
• 22.8k
Accepted

• 22.8k
Accepted

### Private key encryption based on NP-complete problem

We do not have such an encryption. One of the challenges is the gap between worst case and average case. When we build an encryption based on a well known problem it is not sufficient to reduce the ...
• 11.8k
Accepted

### The rigorous proof in the commitment based on CRHF

I believe this is the commitment scheme from Halevi and Micali in Practical and Provably-Secure Commitment Schemes from Collision-Free Hashing. The security analysis is given in section 3.1. At a high ...
• 3,163

### Security reduction seems to wrongly show that a non-PRF is a PRF

The problem is, that you are using a high level description of the reduction proof technique. I mean, that you just describe the idea, the steps of the reduction, but you are missing the deeper look ...
• 2,214

### In reduction from search LWE to decsion LWE why sampling needs to repeat a polynomial number of times?

The assumptions on the decider are weak - it has advantage at least $\epsilon$ (which you can imagine to be some small, but non-trivial quantity, say .01). This is enough to break LWE. But the decider ...
• 12.5k

### Resources for simple MPC proofs

This won't be a full-fledged answer, since I don't have good pointers in mind (I read very few MPC textbooks). Still, a few comments on your proposal: the construction can be simplified a lot. First, ...
• 19.9k
Accepted

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

I think you're missing the main point of reductions, which I would describe as the following Any adversary $A$ that breaks the cryptographic algorithm can also be used to break the hardness ...
• 12.5k
1 vote

### Decision LWE vs Search LWE: Which one is harder?

The standard answer to this is Micciancio Mol. In general, we normally assume that search LWE is hard (algorithms breaking LWE typically break search LWE), and then connect the hardness of decision ...
• 12.5k
1 vote

### The security of using a digital signature scheme twice with randomness

This is a partial answer. The desired security goal (existential vs strong unforgeability or others?) hasn't been explicitly stated. Without restrictions, we can assume that (any) unforgeability is ...
• 3,163
1 vote

### Proving an identification-scheme based on a digital signature is secure

Let event $A$ denote $VERIFY(pk,r,\sigma)$ and event $B$ denote $(r,\sigma) \notin \{r_i, \sigma_i\}$. Then, \begin{align}Adv(\mathcal{A})=\Pr[A]&=\Pr[A\wedge B] + \Pr[A\wedge \bar B] \\&\leq\...
• 774
1 vote
Accepted

### Proving semantic security implies security from key-recovery attack

I belive that there isn't a way to know how much $\hat{k}$. And even if we did it isn't correct to assume that $Pr[\hat{b}=1|b=0]=\frac{x}{|K|}$. To handle the analysis when $b=0$ try fixing $c$ and ...
• 66

Only top scored, non community-wiki answers of a minimum length are eligible