# Questions tagged [provable-security]

A primitive or protocol with provable security is accompanied by a mathematical proof that shows how to reduce the security claims about the protocol to a set of assumptions.

628 questions
Filter by
Sorted by
Tagged with
46 views

### How Cut-and-Choose can leak information?

I'm currently reading the book "A Pragmatic Introduction to Secure Multi-Party Computation". On pages 103-104 I came across the following related to the Cut-and-Choose technique: If $P_2$ ...
• 502
27 views

### Noise flooding with Renyi divergence

According to this question, I found papers that deal with noise flooding with Renyi divergence. However, the answer is still unclear to me on how to use Renyi divergence on the noise flooding ...
• 21
21 views

### Is Regev’s public-key encryption with $sk$ chosen from $\{0, 1\}^n$ circular secure under CPA security?

I thought maybe this is true with something like the following reduction (if we assume for contradiction that it is not circular secure): For $A$ to 'break' CPA security, let $C$ be the 'collaborator' ...
• 189
57 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, "...
• 189
1 vote
49 views

• 97
1 vote
63 views

### Asymmetric key Cryptography

In asymmetric key cryptography, public key is available to everyone. If an attacker encrypts the message sent by another user then the receiver might receive that message. Then how the security is ...
74 views

### Is it necessary for a round function $F$ in a Feistel cipher to be pseudorandom?

I stumbled across this question where the questioner asked for specific requirements for the round function $F$ in a Feistel network so that the construction is secure. The answer explained that a ...
1 vote
56 views

### Is it possible to verify that the output of an executable came from its unaltered control flow?

I suppose an executable could contain a key which signs its output, but that key could be extracted and used to sign other data. Is it possible to verify that the output of an executable is the direct ...
96 views

### Katz/Lindell 2.4 - Generalizing from 2 messages to any message space?

I'm trying to solve problem 2.4 in "Introduction to Modern Cryptography" (2nd edition) for self-study. The problem asks to prove that perfect secrecy $$Pr[M = m | C = c] = Pr[M = m]$$ ...
• 247
52 views

### Security in a pipeline

I am new to cryptography, I am trying to design a secure pipeline environment for the fast transfer of messages. To reduce the Key size I am planning to encrypt the messages with AES session keys (for ...
28 views

### Methods of security proofs used in bibliography, apart from games and simulations?

The question in mainly stated on the title. I am currently studying various cryptographic schemes and most of them use either game based or simulation based methodologies for their proof. I was ...
• 502
54 views

### Some misunderstanding on the Security Proof with Oracle

I have a question about the security proof. Suppose that I proved the following relations. That is, I proved that $Adv_A \le Adv_A^{O} \le Adv_B$, where A,B are some cryptographic schemes and O is an ...
• 129
1 vote
46 views

### Showing that $F'(k, x) := F(F(k, 0^{n}), x)$ is a PRF [duplicate]

I wanted to do some practice on security reduction proofs, and I am stumped on this one from the Boneh-Shoup book. If $F(k, x)$ is a secure PRF, then show that $F'(k, x) := F(F(k, 0^{n}), x)$ is a ...
• 43
59 views

### Where can I find good practice questions for proofs by reduction?

I already have the Katz-Lindell textbook, but I also want some additional practice problems for security reductions for stuff like PRFs, MACs, digital signatures, private and public key schemes, and ...
• 43
1 vote