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
1answer
507 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
63 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
92 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
104 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 ...
1
vote
0answers
71 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
108 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
79 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
102 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
45 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
78 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
90 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
190 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
57 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
55 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
49 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
300 views

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

Would this encryption and signing scenario be considered tamper-proof? ...
0
votes
1answer
185 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
47 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
468 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
59 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
5k 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
61 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
73 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
87 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$ ...
0
votes
1answer
51 views

How to formally prove that random guess is the best attack

How to formally argue that there exists no efficient $A$ who can come up with a $e$ such that $$\begin{align}x&=PRF(e,0) \land \\ y &= PRF(e,1) \land \\ x &= H(y)\end{align}$$ where $H$ is ...
1
vote
0answers
70 views

Solving RLWE modulo a prime ideal

Suppose you have the following set up for RLWE: $K$ is a cyclotomic field of degree $n$ over $\mathbb{Q}$, and $p\in\mathbb{Z}$ is a prime integer that splits as follows in $R = \mathcal{O}_K$: $p\...
1
vote
1answer
58 views

Is it meaningful to allow parties to use a non-uniform random tape in 2-party computation?

Consider a trivial example where two semi-honest parties want to flip a biased coin. Since the sender is semi-honest, the sender can locally flip a biased coin and send it to the receiver. A natural ...
-2
votes
2answers
214 views

Is this a provably secure scheme to encrypt a private key?

I got this idea to use the features of the one-time pad, an encryption technique that provably cannot be cracked, but this time applied to encrypt a private key. A possible application could be to ...
1
vote
0answers
20 views

Technological based solution needed for a real world problem of transferring a physical object between two untrusted parties [closed]

Suppose I have a physical object A. Another person also has some rights over the object A. After some litigations, a schedule has been made under which object A will be passed for some time to the ...
5
votes
2answers
276 views

Can a PRF distiguisher invoke the function's algorithm?

The definition of a function $F:\ \{0,1\}^n\times\{0,1\}^n\to\{0,1\}^n$ being a Pseudo Random Function Family (PRF) is that it's implementable by a P.P.T. algorithm $\mathcal F$, and there is no P.P.T....
0
votes
0answers
34 views

Is ORAM security definition adaptive?

Based on the "obliviousness" definition of the access pattern of the ORAM: Given the RAM, after a sequence of read/write operations, the physical addresses accessed will be computationally ...
2
votes
2answers
413 views

Which of those functions are PRFs?

Assume that $F: \{0,1 \}^n \rightarrow \{0,1 \}^n$ is PRF. Examine if the following functions are PRFs: $$ \begin{align} 1. \, F_1(k,x) &= F(k,x) \oplus x \\ 2. \, F_2(k,x) &= F\left(F(k,0^n), ...
2
votes
1answer
88 views

Using Optimal Prime Field in ECC

"Optimal Prime Field is a family of 'low-weight' prime fields that allow for efficient software implementation of all operations requiring a modular reduction, in particular the field-...
1
vote
1answer
190 views

Security proof, Sequence of games

I hope someone can help me with the sequence of games security proof for protocols. Here are my questions: What is the aim of each individual game? i.e. why can't we do this in one indistinguishable ...
0
votes
0answers
36 views

Extractability of random oracle in simulation-based proof

I am working on the simulation-based proof, where Random Oracle (RO) is used to extract malicious parties' input. In particular, the RO considered in the proof has a small range (whose size is ...
0
votes
0answers
48 views

Security Proof, Sequence of games and birthday paradox

The sequence of games security proof approach is very confusing. For example, I am trying to understand it in the following paper https://www.dropbox.com/s/dhsgsognxviwacv/Provably%20Secure%...
3
votes
1answer
77 views

Boneh DDH Paper - Sampling Integers in Random Reduction

I've been reading Dan Boneh's DDH paper, in particular section 3.1 which covers DDH randomized reduction. The first two sentences of theorem 3.1 state: Let $\Bbb G = \{G_p\}$ be a family of finite ...
0
votes
0answers
37 views

What is a quantifier in game-based definitions?

I'd like to know what are quantifiers in game-based security definitions (in cryptography) Some relevant examples and sources are also much appreciated. Edit: for example, in a formal definition, we ...
1
vote
1answer
52 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 ...
1
vote
1answer
97 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. ...
1
vote
2answers
142 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 ...
3
votes
0answers
54 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 ...
1
vote
1answer
41 views

Guessing the Secret in RLWE Search-to-Decision

In On Ideal Lattices and Learning with Errors over Rings, the authors prove a search-to-decision reduction by guessing the RLWE secret $s$, and using the guess to transform a sample from $\mathfrak{q}...
-2
votes
1answer
151 views

Does the following protocol of secure a matrix satisfy one-time-pad?

Problem Definition: Alice wants to send a matrix $MR_A$ which encrypts its original private matrix $M_A$ ($M\times N$ size, all elements in $M_A$ is in {0,1,2,3,4,5}) to Bob without letting Bob knows ...
0
votes
1answer
80 views

On the Acceptability of a Naive Pseudo Random Number Generator

My question is probably both philosophical and technical. Background I was developing a CSPRNG, and I needed to shuffle the bits in one step in the middle of the algorithm - any naive shuffle would ...
0
votes
1answer
74 views

May an adversary be fooled by a random-looking input that in reality is fixed?

I want to prove the EUF-CMA-security of a signature scheme. It is a variation on an established scheme, therefore I would ideally like to reduce the new-scheme-security to the old-scheme-security. the ...
2
votes
0answers
58 views

Secure Protocol

How to show there is no secure protocol to compute OR? I need to know the mathematical proof of this statement. I am understanding this statement using the matrix representation of $f(x,y)$ but unable ...
2
votes
0answers
40 views

How are security proofs performed for Certificateless PEKS schemes?

I have been studying several CLPEKS (CertificateLess Public-key Encryption scheme with Keyword Search) schemes and I understand the security assumptions and the several types of security models used ...

1
2
3 4 5
12