5 votes

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 ...
constantine's user avatar
4 votes
Accepted

A problem about matrix

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})$, ...
Mark's user avatar
  • 12.5k
4 votes
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 ...
ckamath's user avatar
  • 5,178
4 votes
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 ...
Chris Peikert's user avatar
4 votes
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 ...
Daniel S's user avatar
  • 22.8k
4 votes
Accepted

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

I found a counterexample to this problem. Suppose that $F':\{0,1\}^n\times\{0,1\}^n\rightarrow \{0,1\}^n$ is SPRP. Then define $F:\{0,1\}^n\times\{0,1\}^n\rightarrow \{0,1\}^n$ as follows: Let $F_{0^n}...
YirongHu's user avatar
3 votes

The security of using a digital signature scheme twice with randomness

The scheme is insecure; someone can, with two valid signatures, generate a valid signature to a different message. Suppose we have the signatures: $(r, \sigma_0, \sigma_1)$ a valid signature for the ...
poncho's user avatar
  • 146k
3 votes

A problem about matrix

I think that there will be (with high probability) enough information to solve the question, but I cannot yet think of a solution that takes less than exponential time in $n$. Given $\mathbf x_i$ and $...
Daniel S's user avatar
  • 22.8k
3 votes
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 ...
Meir Maor's user avatar
  • 11.8k
2 votes
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 ...
Marc Ilunga's user avatar
  • 3,163
2 votes

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 ...
Titanlord's user avatar
  • 2,214
2 votes

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 ...
Mark's user avatar
  • 12.5k
2 votes

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, ...
Geoffroy Couteau's user avatar
2 votes
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 ...
Mark's user avatar
  • 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 ...
Mark's user avatar
  • 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 ...
Marc Ilunga's user avatar
  • 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\...
lamontap's user avatar
  • 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 ...
seanL's user avatar
  • 66

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