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.

Filter by
Sorted by
Tagged with
1
vote
0answers
112 views
+200

Quantitative reduction of Schnorr's identification scheme to DLP

Question I seek a quantitative proof of theorem 13.11 in Katz and Lindell's Introduction to Modern Cryptography (3rd edition). The proof is about the Schnorr identification scheme for a generic group $...
0
votes
0answers
59 views

Proof of theoritical security of Shamir's secret sharing

community ! I'm looking for the proof of theoritical security of Shamir's secret sharing. I found some articles saying that it's assimilable to the halting problem, which implies that there is no ...
4
votes
2answers
645 views

What does existential unforgeability mean in a digital signature scheme?

In a digital signature scheme (Gen, Sign, Verfiy) that satisfies correctness and existential unforgeability, can you assume that the outputs of Sign() are computationally indistinguishable from random?...
3
votes
1answer
163 views

How to build a periodic PRF from a PRF?

This question may be related to this one, though the construction differs. Let us consider a PRF $f$. We define $g_k$ as $g_k(x)=f(x)\oplus f(x\oplus k)$. Is $g_k$ a PRF, assuming $k$ is chosen at ...
2
votes
1answer
60 views

Difference between Generic Group Models

I'm trying to understand the difference between the (classical) Generic Group Model as it is described by Shoup [Shoup] and the somewhat restricted Generic Group Model as it is described by Schnorr ...
2
votes
1answer
60 views

Names and games for security properties preventing substitution of signed message by the signer

Some signature schemes, notably ECDSA, unwillingly allow users to prepare their public/private key pair as a function of two arbitrary messages of their choice, and compute a signature that checks for ...
1
vote
0answers
36 views

Security game for factoring

this is probably a fairly simple request, but I have'nt been able to find it anywhere. A lot of cryptography schemes have security games associated with them. In the Book by Katz, a bunch of schemes ...
2
votes
1answer
54 views

Why require that public and private key each have length at least the security parameter?

In Jonathan Katz and Yehuda Lindell's Introduction to Modern Cryptography (3rd edition), the key generator of e.g. signature has The key-generation algorithm $\mathsf{Gen}$ takes as input a security ...
4
votes
1answer
92 views

Relation between short and «regular» Schnorr signature

I'm failing to fully understand the reasoning in 19.2.3 of Boneh and Shoup's A Graduate Course in Applied Cryptography. That constructs short («optimized»/original) Schnorr signature from «regular» (...
2
votes
0answers
65 views

Security of Full Domain Hash (or not quite full)

Full Domain Hash is the simplest signature scheme based on a trapdoor permutation (such as textbook RSA) that enjoys a strict security reduction. It was introduced by Mihir Bellare and Phillip Rogaway:...
0
votes
0answers
37 views

Random Oracle Model for an ideal block cipher vs Ideal Cipher Model

Some security proof involving an ideal function use the Random Oracle Model (ROM). They posit a thing that given integer $b$ and bistring $M$, returns what it previously returned for that input $(b,M)$...
2
votes
0answers
27 views

Is it secure to use the same master secret key in two independent IBE schemes?

Given two IBE schemes: Boneh-Franklin IBE scheme (https://doi.org/10.1007/3-540-44647-8_13) Secure under the CBDH problem (in the ROM) The master secret key is a random element in $\mathbb{Z}_p$ ...
1
vote
1answer
94 views

RSA public key identification

Consider a multi party system where public keys of all receivers are known. Server wants to send message to one of them using (textbook?) RSA. Adversary is given ciphertext and even Message to be send,...
7
votes
2answers
225 views

Rabin-Williams signature and it's reduction to factorization

Rabin signature is rightly celebrated as a signature scheme with provable reduction to factorization. How do we show that for Rabin-Williams signature as standardized, under the common and realistic ...
1
vote
0answers
49 views

Cardinality of a set of successful hash values

Im trying to comprehend a proof from the paper "Efficient Identity Based Signature Schemes Based on Pairings"(2002) by Florian Hess. At one point of the proof for Theorem 2 I don't ...
0
votes
1answer
49 views

Reduction to the discrete log problem

Let $G$ be a group of prime order $p$ and generator $g$. Let $msk_i = (x_i, y_i) \in Z_p^2$ be two master secret keys and $mpk_i = (g^{x_i}, g^{y_i})$ the corresponding master public keys, $i \in [0, ...
0
votes
0answers
47 views

Question about game based security

When a game between an adversary $A$ and a challenger $CH$ is used in the security model of a scheme, and oracles are defined, does the adversary only have access to those oracles in the attack or ...
1
vote
0answers
47 views

How to compare two post quantum digital signature schemes in terms of latency?

I want to compare two digital signature schemes of different nature. One is Hash-based (Winternitz one time signature scheme) and the other is lattice-based (Dilithium Crystals). What about be an ...
1
vote
0answers
36 views

How to evaluate number of security bits of a signature scheme?

I am trying to evaluate the effective security levels that a digital signature scheme (namely post-quantum digital schemes like WOT-S (Winternitz one time signature scheme) and Dilithium Crystals). ...
1
vote
0answers
61 views

What's the difference between H(m) $\oplus$ H(key) and H(m || key) in MAC construction?

We all know that HMAC has the form of $H(ikey || H(okey || M))$. I'm wondering what if we replace the H(okey || M) into H(okey) $\oplus$ H(M)? In other words, is $$H\Big( ikey \mathbin\| \big( H(okey) ...
4
votes
1answer
62 views

What is meant by the probability distribution of a verifier?

I'm having trouble understanding the role of probability distributions in the definitions of computational/statistical indistinguishability, especially in the definition of zero-knowledge. From A ...
0
votes
0answers
64 views

About CPA or CCA security proof

Recently reading about CPA, CCA safety security proof. After reading a few papers, the author is in the process of proof. The challenger maintains some lists. I really don’t understand why the ...
0
votes
0answers
27 views

Does IND-CPA to INC-CCA effects on the error probability?

If we have a key encapsulation mechanism (KEM) that is IND-CPA secure, with some error probability $P_e$ (probability that the shared keys are not equal). The goal is to use the Fujisaki-Okamoto ...
2
votes
1answer
82 views

Data Security and Encryption

I have a research paper on data security using proxy re-encryption, and I need to provide an answer to a reviewer's comment. However, I have no idea on what to do or how to answer it. The security ...
1
vote
1answer
457 views

Is it safe to use many nonces for XChaCha20?

I have a very simple question. Since XChaCha20 nonces are 192-bit, there's technically no limitation to the max number of message encrypted, since the chances of two random nonces being the same are ...
1
vote
1answer
60 views

How do we know a single differential/linear trail dominates the others?

I have read the proof of AES's resistance against differential cryptanalysis. In the proof the authors show that there is no single differential trail with prop ratio higher than $2^{-300}$ over 8 ...
1
vote
1answer
78 views

Constructing a mac scheme secure to regular definition but insecure to special case

The mac-forge security game for mac schemes looks like this: $k \leftarrow \operatorname{Gen}(1^n)$; $(m,t) \leftarrow A^{\operatorname{MAC}_k(⋅)}(1^n)$; Let $Q$ denote the set of all queries that $A$...
2
votes
2answers
83 views

Question on the CPA-security proof of the CTR-Mode

While reading Katz & Lindell's textbook (2nd edition) I found a proof for the CPA-Security of CTR-Mode. It can be found at the end of chapter 3.6.2 (page 93 and 94). I don't quite understand, why ...
0
votes
0answers
60 views

IND-CCA game proof of Encrypt-then-Mac

In [BN07, Subsection 4.3], the authors show that if a symmetric scheme $\mathcal{SE}$ is IND-CPA and a MAC $\mathcal{MA}$ is EUF-CMA (though they use the SUF-CMA notation, but I think it refers to the ...
1
vote
2answers
104 views

Hashes as mutually independent keys

For cascading encryption (ie. AES-Twofish-Serpent), the most secure implementation is with mutually independent keys. My question is if it is secure to hash the previous key for each layer of ...
2
votes
0answers
76 views

Authenticated sharing in MASCOT protocol

I am studying MASCOT protocol for multiparty computation and I am stuck in the comprehension of the authentication protocol $\Pi_{[[ \cdot ]]}$ and its security proof. Supposing the initialize phase ...
1
vote
1answer
94 views

Combined scheme security proof

Let CS be a combined scheme of $n$ public key subschemes. CS is composed of two algorithms Setup and KeyGen, that all the subschemes share, plus all the other algorithms of each subscheme. Suppose ...
0
votes
1answer
43 views

Can a broken cipher reveal the key?

Suppose I cascade cipher A and cipher B to encrypt a message. Both ciphers use the same key. I know that theoretically, the security of the setup when used correctly is at least as secure as the most ...
1
vote
1answer
46 views

Clarification of Advantage vs Probability/Success of an Adversary

In cryptography, for a polynomial time-bounded adversary $\mathcal{A}$, given a scheme $\Pi$, the success or probability of succeeding $\mathcal{A}$ is the likelihood for $\mathcal{A}$ to break $\Pi$, ...
1
vote
2answers
75 views

How to generate a random point on an elliptic curve without knowing it's corresponding scalar private key

Given an elliptic curve with generator $G$, is it possible to generate a random point on the curve $Q = a \cdot G$ without knowing the secret value $a$ that generated it? Note that just using an $a$ ...
2
votes
0answers
93 views

An exercise to show that CBC Chain is insecure

The CBC-Chain mode of operation is a CBC variant in which the IV that is used for the very first message to be encrypted is randomly selected, whereas the IV used for each subsequent encrypted message ...
0
votes
0answers
43 views

Question about IND-CCA security

We are given the following securitygame $G^{\text{LOSTNAME}}$: Generate $k \leftarrow \{0,1\}^{\kappa}$ uniformly at random Choose $h \leftarrow \{0,1\}$ uniformly random Create decryption oracle $\...
1
vote
1answer
61 views

Where to find a comprehensive content on security proof systems in cryptography

Proof systems (provable security) are seen in many research papers related to cryptography and security. Where would I be able to find a comprehensive resource covering the purpose and the ...
32
votes
8answers
10k views

Why do some people believe that humans are “bad at” generating random numbers/characters like this?

I'm not even sure if they are serious, but I've heard many times that some people refuse to not only trust their computer to generate a random string (which is understandable) but also don't trust ...
0
votes
0answers
50 views

How secure is Encrypt-And-MAC?

From this popular Crypto.SE thread, the general feeling is that Encrypt-Then-MAC is the most secure. From the first answer, the poster says that Encrypt-And-MAC provides integrity of the plaintext. If ...
0
votes
0answers
47 views

SHA3_512 as dynamic SBOX generator

I'm creating a substitution-permutation cipher (for learning purposes only of course) and I'd like to implement dynamic SBOXs. The cipher will have a block size of 128, and 32 rounds. These SBOXs will ...
2
votes
2answers
296 views

Is E_k(M)||H(m) form of MAC secure?

Would this encryption and signing scenario be considered tamper-proof? ...
0
votes
1answer
124 views

Security of ChaCha compared to AES and Serpent

I'm trying to understand how secure XChaCha20 is in comparison with other ciphers. From what I know, ChaCha is more secure than AES, but less secure than Serpent. My question is how much more "...
2
votes
1answer
34 views

Is it possible to convert a selective secure broadcast encryption scheme to an adaptive secure broadcast encryption scheme?

I was reading the paper, entitled "Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation", by Boneh et al. On page 23, the authors have claimed ...
1
vote
5answers
388 views

Is it theoretically possible to create an unbreakable cipher?

I know this question might sound strange, but is it theoretically possible to create an unbreakable cipher if we don't consider bruteforce? Some of us believe that it is possible to create ciphers and ...
0
votes
1answer
53 views

May it be possible that the trusted third party knows the parties' private keys in an “ideal model” of a Secure multiparty computation protocol?

May it be possible that the trusted third party knows the parties' private keys in an “ideal model” of a Secure multiparty computation protocol? I wonder if it may be possible that a trusted third ...
12
votes
2answers
4k views

Why don't we use Blowfish if it hasn't been cracked?

Since Blowfish is old, well-audited, and has no published attacks, why are we using AES instead? I know that Bruce Schneier said that Blowfish is insecure and told people to transition to Twofish, but ...
0
votes
0answers
59 views

Cascading encryption with blocks or output

For educational purposes, I'm trying to build a cascading encryption implementation with AES, Twofish, Blowfish, Salsa20, and ChaCha20. First of all, please don't judge my paranoia or choices, this is ...
1
vote
1answer
64 views

Not understanding deterministic authenticated encryption (DAE) security definition

I have a question regarding the security definition of deterministic authenticated encryption (DAE) as defined by Bellare and Shrimpton. Their definition is reproduced below, and my question pertains ...
0
votes
1answer
83 views

Unconditionally secure block cipher for a finite number of blocks

I am wondering if someone can point me toward a block cipher that provides unconditional security for only a bounded number of encryptions. For example, you can encrypt $h > 1$ length $n>1$ ...

1
2 3 4 5
12