# 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.

670 questions
Filter by
Sorted by
Tagged with
63 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 ...
70 views

1 vote
59 views

### Unbounded distinguishers and statistical indistinguishability

In constructing a SHVZK simulator for a sigma protocol I am working on I have encountered some fairly basic questions, but ones which are not often discussed in textbooks and papers - consider the two ...
283 views

### How big of a threat are *diffusion model* based AIs to cryptographic systems?

The diffusion model, which is used by products like Midjourney and Dall-E, trains AI systems to de-noise (remove added randomness) from data to infer what the original de-noised data is. That would ...
1 vote
54 views

### Existence of PRGs satisfying the following weaker definition

Consider the following definition. Let $p(n) > n$ be a polynomial, and $G_n: \{0, 1\}^n \rightarrow \{0, 1\}^{p(n)}$ a PRG. Moreover, given $x \leftarrow \{0, 1\}^n$, we say $S$ is a length $n-1$ ...
1 vote
86 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 ...
47 views

### self-decryption paradox in identity based encryption

In the paper Dual system encryption: realizing fully secure IBE and HIBE under simple assumption (free PDF), the authors said "there is an apparent paradox in this strategy since it seems that ...
1 vote
34 views

### Does blockcipher decryption always offer equivalent security as blockcipher encryption? [duplicate]

I'm not sure if anyone explored this area before. Blockcipher encryption definitely fullfills IND-CCA, but what about its inverse? Is there a proof that shows blockcipher decryption is as secure as ...
95 views

### confusion about the meaning of reduction

I'm learning provable security, and I'm a bit confused with the concept of reduction. So, here's my understanding: to prove a protocol/scheme/generic construction is at some level of security, there ...
1 vote
69 views

### Does game-theoretical fairness work in when the goal of one party is randomness

When we take the coin flip in Blum's algorithm in "Coin flipping by telephone a protocol for solving impossible problems", where Alice and Bob both want ownership over the same car, then one ...
149 views

### Provably secure cryptography in blockchains

Do you know a blockchain that does not use at all cryptographic primitives standardized by USA or other countries? It is strange to me that the security of many cryptocurrencies is based on ciphers, ...
64 views

### Is a Pedersen commitment still secure when r is either 0 or 1?

Specifically if we know the $r$ takes values from the set $\{0,1\}$and $c=g^r*h^m$ does the hiding property still hold? I think I already managed to prove that the binding property holds due to the ...
81 views

### Security of RLWE encryptions of secret keys

Under which conditions is it secure to publish an encryption of the secret key $s$ under itself in terms of an $RLWE_s(s)$ ciphertext? Because for some schemes this is (repeatedly) used in ...
56 views

### Replacing the Hash function with messages in the BLS signature scheme, the security degenerates from EUF to SUF?

​I have been thinking about this question: if I directly replace the hash function with the message in the BLS signature, does the security of the BLS degenerate from existential unforgeability(EUF) ...
1 vote
88 views

### Is it appropriate to prohibit an adversary from querying a specific input in an algorithm in some situation?

There are two algorithms in my framework, $E_1(\cdot)$ and $E_2(\cdot)$. In particular, executing $E_1(\cdot)$ on a specific input $x$ (i.e., $E_1(x)$) is equivalent to executing $E_2(y)$ for some ...
54 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, ...
47 views

### Security assumption: Where is an assumption from (who provides and formalizes it)?

Is there a list of all the (most) assumptions (such as RSA and DDH assumptions) used in cryptography and the corresponding properties?
190 views

### Are rejected Dilithium commitments secret?

On 6 March, Yi Lee sent over the NIST mailing list an announcement of their submitted paper that found a flaw in the original security proof for Dilithium. In their manuscript, they fix the proof on ...
30 views

### Stand-alone simulation proof: Ideal functions and leakage collection

Are ideal functions and leakage collections the terms of UC security? Why I often see them in a simulation-based proof under stand-alone model? Some papers use the definition in Lindell's How to ...
1 vote
43 views

### Simulation based proofs: how many simulators should be constructed?

In simulation based proof of cryptographic scheme, if k parties are invovled in the scheme, then k simulators should be ...
143 views

### Expanding stand-alone simulation-based proofs to UC proofs

This is a follow-up question to Mikero’s answer to Simulation-based proofs and universal composability proofs. Let there be some protocol $\pi$ running between two parties $A$ and $B$. Furthermore, ...
1 vote
156 views

### Showing that CPA encryption schemes cannot preserve the length of a message

I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am stuck on the following problem. Let $\mathcal{E}$ be be an encryption scheme where messages and ...
158 views

### How many bits of encryption are enforced in WEP (wired equivalent protocol)

I'm currently taking a computer security module in University and as part of a problem have been asked: My thought for the question is that no it does not provide 64 bits of security strength. This ...
135 views

### Proof for secure stream cipher implies secure PRG

I am self studying "A Graduate Course in Applied Cryptography" by Boneh-Shoup. I am not sure if my proof for the following problem in the book is correct. The problem asks to prove that if a ...
99 views

### Semantic Security equivalent to Real/Random Semantic Security

I'm reading Boneh and Shoup's book "A Graduate Course in Applied Cryptography." Im doing one of the questions at the end of the stream ciphers chapter. I'm not sure how to do this problem: ...
267 views

### Is exposing hash of private key provably secure?

Let's say we have an IND-CPA secure public key encryption scheme $\Pi = (\text{Gen}, \text{Enc}, \text{Dec})$. Construct a new PKE $\Pi' = (\text{Gen}', \text{Enc}', \text{Dec}')$ that behaves exactly ...
2k views

### Is 7-Zip Encryption really secure? [duplicate]

Is 7-Zip really a good encryption tool? I wonder what kind of encryption is used in 7-zip. I see most people using 7-Zip. Just curious about what extent it is safe.
101 views

### Automated Security Protocol tool that models algebraic operations

Are there any automated security protocol verification tools that model algebraic operations; specifically addition. I am familiar with AVISPA and Verifpal, and they are both great and user-friendly ...
35 views

### Game-based security notion and hybrid proofs - adversarial randomness

Say we have a game-based definition of security and wish to prove the security of our construction using a series of hybrids. Can we somehow "fix" an adversary that we interact with in one ...
150 views

### Random oracles and the Borel-Cantelli Lemma

I am trying to understand the implication of the Borel-Cantelli Lemma to the random oracle model. I think understanding a special case, say, a random oracle is one-way with probability 1, would be ...
93 views

### Composability of state-separable proofs

Brzusk et al. introduced the state-separation proof technique to tame complexity in game-based security proofs. The framework allows for modular, easy to understand, and reusable proofs. It has been ...
100 views

### Alternative definition of security for MAC

In the usual definition of security for message authentication codes, we let an adversary $A$ have access to an oracle for $Mac_k(.)$. However, if we consider that there exists a more powerful type of ...
1 vote
71 views

110 views

1 vote
37 views

### Can the proof only be the stateful?

Let SE be stateful encryption. Then, it is well known that the oracle for the security proof becomes stateful too. (We only consider the IND-CPA security game.) On the other hand, assume that E is ...