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

684 questions
Filter by
Sorted by
Tagged with
1 vote
86 views

### Can we determine a security parameter in the hybrid argument where the number of hybrids is polynomially bounded but not known?

Let $\lambda$ be a statistical security parameter. Consider a security proof that is based on hybrid argument, where there are polynomially many (say, $n = p(\lambda)$) hybrids, $H_1, ..., H_n$. Any ...
• 424
1 vote
298 views

### Security of block cipher PRP(k⊕m)⊕k

Let $\mathcal S=\{0,1\}^n$ be the set of bitstrinsg of $n$ bits (for security parameter $n$). Let $P$ be a public Pseudo-Random Permutation of $\mathcal S$, efficiently computable in both directions. ...
• 142k
1 vote
224 views

### Proving security of $\Pi' = E_k(E_k(m))$ knowing $\Pi = E_k(m)$ is secure

I recently started studying cryptography but I am not sure I quite understand the concept of proof by reduction. Question I am trying to solve is as follow: Suppose $\Pi$ is a symmetric encryption ...
• 35
60 views

### trust-less blind execution environment (thought experiment)

I apologize for the theoretical nature of this question, but It has cost me a lot of sleep over the past months. Querying my immediate peers has so far failed to produce results. I assume this ...
• 131
1 vote
74 views

190 views

### Multi-users RSA problem

Rivest and Kalisky's RSA problem considers various notions on security of the RSA One-Way Trapdoor Permutation. They do it only from the perspective of a single user. What's the state of the art in ...
• 142k
225 views

### "Reduced to" vs "deduced from"

Assume it's proven: "Security of protocol $\Pi$ can be deduced from hardness of problem $P$". Is it correct to state: "Security of protocol $\Pi$ can be reduced to (hardness of) problem $P$" ? My ...
• 142k
1 vote
45 views

### Assumption of difficulty of attack in restricted short time

As well known, different assumptions of difficulty of some problems are used in provable security. E.g., if some crypto-scheme is breakable only in case the attacker finds preimages for hash function, ...
86 views

### Are there only two ways to prove a cryptographic protocol is secure?

If I want to prove my protocol is secure, can I just use a game based approach and/or a simulator approach? Or are there other common approaches?
• 1,343
1 vote
66 views

### What is the underlying hard problem in the reduction of game-based proofs?

I am confused by how game-based proofs fit in the provable security paradigm. I understand reductions in the style of proving secrecy of RSA reducing it to integer factorization. However, when proving ...
• 123
72 views

### Balanced Feistel networks: Are there any lower bounds on the computational complexity of breaking a $k$-round Feistel cipher?

This paper by Patarin presents an attack (section 9) on balanced Feistel networks with $k$ rounds, where the input is a bit-string is of length $2n$. (Since it is balanced, this means each PRF takes ...
• 399
444 views

### MAC security game

In the applied cryptography book by Boneh and Shoup, Chapter 6 on MACs, it is stated that one can modify SUF-CMA game by removing verify oracle access to the adversary. Therefore, the two versions are ...
• 3,338
149 views

### The security of blind RSA signatures with modular exponentiation as padding

It is known that (blind) RSA signature implementations should apply some sort of padding to messages before signing or blinding them. Does blind RSA signature with modular exponentiation as a padding ...
• 1,184
1 vote
5k views

### Using RSA encryption to encrypt large files

The following post discusses the use of RSA for file encryption: https://medium.com/@ismailakkila/black-hat-python-encrypt-and-decrypt-with-rsa-cryptography-bd6df84d65bc The file encrypted is a JPEG ...
• 687
82 views

76 views

### Why does the random oracle receive much more criticism than the ideal cipher?

The random oracle model seems to be criticized a lot as lacking practical relevance, making wrong predictions, being programmable, etc. However, I have never heard such criticism about the ideal ...
• 264
317 views

### Is the EdDSA signature scheme provable security?

The EdDSA signature scheme is a deterministic scheme. So could it be proven provable security in Random oracle model?
1 vote
595 views

### Game-based proofs and semantic security

After reading this question, I understood that "game-based" and "simulation-based" have to do with the way that security properties are postulated. In particular, IND-CPA is a canonical example of ...
• 11
1k views

### Are there any hash functions that are commutative yet secure for ordered lists?

I'm looking for a hashing function that can combine random numbers together in any order yet still find the same value. But it needs to be secure against hackers. The idea is if I'm hashing together: ...
• 203
49 views

### Simulation-based proof in a particular scenario

Suppose we have a two-party protocol in the semi-honest model, which is based on an additive homomorphic cryptosystem like Paillier.(P2 will generate the public and private key and publish the public ...
1 vote
84 views

### Simulation-based proof in the semi-honest model when a party is corrupted

Full paper Would you mind telling me based on the attached file, why in case 3(corrupted client B), the authors did not use the real input which is $S_B$ and instead they have generated $S'_B$? In ...
33k views

### Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers

Given that much of our ECC crypto primitives provide “only” 128-bit security when defined over a 256-bit curve due to pollard-rho, is it then still safe in 2020 to consider 128-bit security safe for ...
• 1,424
65 views

### Need help in proving of disproving security of generic partially-blind-signature construction

I have a project where I need to use a linear partially blind signature scheme. I looked at Abe-Okamoto, but I can't easily make it linear. So I looked at Okamoto-Schnorr blind signatures (here and ...
• 226
88 views

### Help understanding syntax used in security proof

I am looking through this paper and am trying to understand the proofs better. One of the theorems the authors are proving (Theorem 5.1) contains syntax of Adv followed by "cdh" in the superscript and ...
525 views

### Security properties of ElGamal encryption variants

I'll use Taher ElGamal's A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms (July 1985 in IEEE Transactions on Information Theory, formerly in proceedings of Crypto 1984) as ...
• 142k
738 views

### Is non-adaptive CPA strictly weaker than standard CPA security?

Today during a cryptography lecture an interesting question came up: Whether non-adaptive CPA security is equivalent to adaptive (FtG / LOR) CPA security. Now for a short description of what this ...
• 46.1k
49 views

### decrypting a one-time-pad that outputs 0,1 in preknown probabilities

assuming a two users want to use a one time pad ciphersystem, and they are using a program that was developed by a third party that was supposed to create random undependable bits, but for some reason ...
5k views

### What are standard cryptographic assumptions?

I am struggling to understand what is meant by "standard cryptographic assumption". The Wikipedia artice on the Goldwasser–Micali system (GM) reads "GM has the distinction of being the first ...
• 617
394 views

### Does an information-theoretically secure hash function exist?

Does an information theoretically secure hash function exist? (By exist I mean is discovered/invented and implemented, not whether it could exist.)
1 vote
51 views

### Computationally indistinguishably vs Perfect Indistinguishably [duplicate]

I know that perfect security means absolutely no information about the plaintext is leaked to the adversary while computational secrecy is okay with a tiny amount of leak. But, what is the difference ...
1 vote
52 views

### Again on discrete gaussians over lattices [duplicate]

Define $$\rho_{s,c}(x) = exp(-\pi \cdot \frac{\|x - c\|^2}{s^2})$$ and $$\rho_{s,c}(L) = \sum_{x \in L} \rho_{s,c}(x)$$ Then Discrete Gaussian over $L$ with center $c$ and standard deviation $s$ is ...
• 599
329 views

### The security level of double encryption

Let PKE $\Pi' = (Gen', Enc', Dec')$ and it is secure in the sense of $S'$. Let PKE $\Pi'' = (Gen'', Enc'', Dec'')$ and it is secure in the sense of $S''$. $S'$ and $S''$ may be separation which means ...
• 1,622
2k views

This is so trivial that authors usually don't bother to give an explicit proof. But for me there is some vagueness. We say that two ensembles $X_n$ and $Y_n$ are statistically close, if $$\Delta(n) ... • 599 2 votes 0 answers 145 views ### Security of MAC-Then-Encrypt without MAC key authentication We have the following settings in our system: TLS 1.2 using legacy cipher suite - OFB mode (using 64 bit block cipher) and trunkated CBC-MAC (32 bit). The goal is to achieve authenticated encryption ... • 43 -1 votes 1 answer 1k views ### 1/(2^n)! is negligible function? By definition \frac {1} {n}, \frac{1}{2^n} and \frac{1}{n!} are negligible functions. I have got the function$$f(n) = \frac{1}{(2^n)!}$$where n is security parameter. I don't understand, ... 0 votes 1 answer 889 views ### How does the challenger choose the message randomly in the one-wayness security game of PKE? I have read some papers that give the definition of one-wayness of PKE schemes. Let \Pi = (G,E,D) be a PKE scheme, and the security game of OW-CPA is defined as follow:$$\mathrm{Adv}_{\Pi,\...
• 1,622
1 vote
I refer to Canetti et all, "Reusable Fuzzy Extractors for Low-Entropy Distributions", available here. Paraphrasing the relevant part from §3:- The locking algorithm $lock(key,val)$ outputs ...