Léo Colisson
  • Member for 3 years, 11 months
  • Last seen more than a month ago
comment

So $y$ is a classical cipher text, but it is determined using a superposition that is still useful after the end of the protocol.

comment

@Maeher It's because the goal of the protocol is to create a quantum state unknown to Bob. Basically to obtain the $y$, Bob is supposed to create a superposition $\sum_x | x \rangle | g(x) \rangle$. The function $g$ is 2-to-1: so after measuring the second register we get $| x \rangle+|x' \rangle$ on the first register for the 2 preimages of $g$. From this state we can obtain a new quantum state that will be used in other protocols (the adversary cannot fully describe this state since it can't invert $g$). If Bob wanted to learn one $x$ ,he could measure it... but it would destroy it.

comment

@Mikero also, if Bob echos back $y$, then it would basically set $x = 00$ (which is perfectly fine).

comment

@Mikero Thanks for your answer, but I'm not sure if it works (at least in my case). If the simulator picks the public key of Alice, we need an argument to say that the simulator can encrypt a random $d_0'$ in place of $d_0$ (because $d_0$ should not leak to the simulator) without being detected. However, I don't think this is directly implies by IND-CPA (see my edit). Am I missing something?

revised

added 847 characters in body

Loading…
comment

@Maeher Thanks for your answer. Unfortunately this cannot work in my case because I'm in a quantum setting: basically, for the adversary to learn $x$, it needs to destroy its state (and then, the protocol is not useful anymore). I could of course do a "cut and choose" approach by asking from time to time do destroy the state and from time to time to continue, but then I only get polynomial security :-( I also don't think that the approach proposed by Mikero works, I'll try to ellaborate in another message.

asked
Loading…
revised

deleted 467 characters in body

Loading…
answered
Loading…
revised

[Edit removed during grace period]; added 471 characters in body

Loading…
awarded
revised

added 176 characters in body

Loading…
revised

added 31 characters in body

Loading…
revised

edited body

Loading…
asked
Loading…
comment

Ok great, thanks a lot! It would be great to have a "LWE zoo" with all the know reductions, how tight they are, and which paper superseeds which one... Anyway, thanks a lot!

comment

Sorry to annoy you again, but I was having one more related question. I'd like to have a reduction GapSVP -> Decision Discrete LWE (modulo 2^k). Right now I'm doing GapSVP --[Reg05]--> Search Continous LWE --[MP12]--> Decision Continuous LWE --[Pei10]--> Decision Discrete LWE. But I found it is suboptimal, as [PRS20] provides directly GapSVP --[PRS20, Cor. 5.2]--> Decision Continuous LWE. Do I still need to use [Pei10] for the last reduction to Discrete LWE, or is there a more efficient solution to directly do GapSVP --> Decision Discrete LWE? [PRS20] eprint.iacr.org/2017/258.pdf

comment

Therefore, to obtain meaningful security results, one must only consider what I call "Information theoretically secure IF". Again, this is not defined formally directly in the CC framework, but I think that it is something important to understand when using the CC framework. I'm sorry if you got confused by my pedagogical choices, it was not intended, and I hope this clarify the confusion.

comment

Now, if Eve is unbounded, m is not hidden anymore in the case of IF2. I will say that IF2 is "computationnally secure", in the sense that an unbounded adversary can break the initial expectation I had on my IF. Finally, when interacting with IF3, even an unbounded Eve cannot obtain m: I will say that IF3 is "information theoretically secure". My claim is that proving that a protocol P realizes IF2 is not better than proving the game-based security of P (actually, you will have more guarantees if you consider game based security: at least you can quantify what an adversary can learn or not).

comment

For example, lets consider 3 IF for secure channel: IF1 will take message m from Alice as input, and outputs m to Eve. IF2 will take message m, and outputs the encryption of m. IF3 will take message m, and outputs nothing but the size of m. Informally, I don't consider IF1 as meaningful (in the context of secure channel) because an eavedropper can learn m, which is not what you expect from a secure channel: I will say that IF1 is not secure (if you prefer, you can replace "secure IF" with "meaningful IF"). IF2 and IF3 are "more meaningful/secure" because a bounded Eve cannot directly learn m.

1
2 3 4 5