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
2 votes
0 answers
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$ ...
user avatar
  • 502
2 votes
0 answers
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 ...
user avatar
  • 21
0 votes
0 answers
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' ...
user avatar
  • 189
3 votes
1 answer
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, "...
user avatar
  • 189
1 vote
1 answer
49 views

Why do we need the leftover hash lemma for this hybrid proof (Learning with Errors)?

I've been reading about Learning with Errors here. On p. 7 there's a proof for the security of the PKE scheme, that goes through the leftover hash lemma, in order to prove that: $$ (pk, Enc(0))\equiv (...
user avatar
  • 189
0 votes
3 answers
192 views

Do we want to allow/Have we allowed parallelization (e.g GPU programming) to enter the cryptographic field? What are the consequences?

With the term GPU programming, I'm referring to highly parallelizable computing in general. Lastly, I have built a bit of a background in cryptography. So I have started to wonder if/where GPU ...
user avatar
  • 502
1 vote
0 answers
43 views

Is the following statistically close to uniform? (and how does one prove such claims in general)

For every $a \in \{0,1\}^n$ define: $$h_a : \{0,1\}^n\to \{0,1\}$$ $$ h_a(b)=\langle a,b \rangle$$ So $\{h_a\}_{a \in \{0,1\}^n}$ is known to be a universal hash function family. This means that if we ...
user avatar
  • 189
1 vote
1 answer
72 views

When does the need of random data become an assumption?

Suppose an encrypion scheme uses a random string to encrypt and decrypt, which is publicly available, such as an IV or nonce. In all the cases I am aware of, the existence of say an IV is not "...
user avatar
  • 480
1 vote
1 answer
40 views

Question on Simulation based security proof for Oblivious Transfer (OT) against semi-honest adversaries

I'm currently reading this How To Simulate It – A Tutorial on the Simulation Proof Technique. On p. 10, there is a proof using simulation for 1/2-OT, against semi-honest adversaries. Briefly, the ...
user avatar
  • 502
0 votes
1 answer
70 views

Question on notation of random variables in probability ensembles

Let's consider this definition of computational indistinguishability. Computational indistinguishability. A probability ensemble $X=\{X(a, n)\}_{a \in\{0,1\}^{*} ; n \in \mathbb{N}}$ is an infinite ...
user avatar
  • 502
1 vote
2 answers
88 views

Relative bits of security of slower functions

Leaving memory-hardness assumptions aside, some slow hash functions are iterated salted hash-chain versions of regular cryptographic hashes. This is usually defined by a ...
user avatar
0 votes
0 answers
26 views

Difference of unconditional and perfect security in terms of IND-Game

Both unconditional and perfect security were very clear to me, until I bumped upon different sources that confused me. For example : 1 2 3. Also in 3 the DH76 paper is referenced and it doesn't ...
user avatar
  • 502
1 vote
1 answer
54 views

A security issue of a Bit commitment scheme constructed by Naor in 1990

In the Section 3.12 of book writen by Boneh and Shoup, a Bit commitment from secure PRGs is presented as follow: Bob commits to bit $b_0\in_R\{0,1\}$: Step 1: Alice chooses a random $r\in R$ and sends ...
user avatar
  • 186
0 votes
0 answers
36 views

How to securely implement a deadpool in a PoW blockchain?

Imagine you have a blockchain where the Proof of Work scheme is integer factorization. There is an opcode that takes two integers $N,M$ where it returns true if $M\not\in \{0,1,N\}$ and $N \mod M \...
user avatar
  • 21
2 votes
0 answers
74 views

Quantitative security of signature scheme obtained by Fiat-Shamir tranform

I'm looking for a quantitative yet simple proof of the EUF-CMA security of a signature scheme obtained by Fiat-Shamir transform. Recall the Fiat-Shamir transform starts from a 3-pass identification ...
user avatar
  • 124k
0 votes
0 answers
17 views

BB - IBE and the BDDH assumption

Given the BB-IBE scheme how can changing the hash fnc. result in the scheme no longer being IND-SID-CPA secure?
user avatar
  • 35
0 votes
1 answer
85 views

Proving you're from the year 2069

Just a question I thought of while playing an amazing game about time travel (13 sentinals aegis rim). What are the most bullet-proof cryptographic methods for proving you've come from beyond a ...
user avatar
  • 335
1 vote
1 answer
96 views

What kind of assumptions usually go into the design of block ciphers?

What are some standard assumptions made in showing the security of a block cipher? For example, is it commonly assumed that $P\not=NP$? To this end, are there any block ciphers whose security does ...
user avatar
  • 480
1 vote
1 answer
51 views

Simulation based proof for Beaver's multiplication protocol

Setup Recently, I became interested in simulation based proofs in the context of secure two party computation. I read some book chapters (from Secure MPC and Secret Sharing and Foundations on ...
user avatar
  • 13
1 vote
1 answer
50 views

What's the probability of cracking this cipher using partial information about the private key obtained from $k$ public keys?

For the following cipher, what is the probability of someone without the private key generating a valid public key, using only information from a list of $k$ public keys previously generated with the ...
user avatar
1 vote
1 answer
58 views

Create an or-proof for a given list of elements with public input

Let $g\in G$ and $h\in H$ be two group generators. Given a list L of m group elements, where $L=(L_1,...,L_m)$, a prover wants to convince a public verifier (namely, a verifier who only has public ...
user avatar
  • 21
4 votes
1 answer
156 views

Can a digital signature be used to generate a key for AES encryption?

I am looking to see if using a digital signature is a secure and reasonable way to generate a key for AES encryption. To flow would be as follows: A user signs a message ...
user avatar
  • 55
0 votes
0 answers
50 views

Indistinguishability proof of an encryption scheme

Is there any indistinguishability proof (e.g., IND-CPA, IND-CCA, IND-CCA1, IND-CCA2, IND-CKA) based on games that involve breaking the AES security? Usually the proof involve breaking hard problems ...
user avatar
2 votes
1 answer
154 views

The essential differences between IND-CCA1 and IND-CCA2?

For some encryption scheme $(\mathcal{E}, \mathcal{D})$: In the definition of IND-CCA, the adversary $\mathcal{A}$ can access the decryption oracle $\mathcal{D}$. The deep reason of this setting is to ...
user avatar
  • 115
0 votes
1 answer
55 views

Does the searchable encryption scheme satisfy trapdoor indistinguishability?

In a searchable encryption scheme based on the certificateless cryptosystem, the trapdoor generation algorithm only has a hash function that outputs an integer value. Does the scheme satisfy trapdoor ...
user avatar
2 votes
1 answer
107 views

Does shared randomness between two cryptographic primitives complicate the hybrid argument for computational indistinguishability?

Let $(Enc, Dec)$ be an IND-CPA secure encryption scheme, where $Enc: \mathcal{K} \times \mathcal{M}_1 \rightarrow \mathcal{C}_1$, and $F: \mathcal{K} \times \mathcal{M}_2 \rightarrow \mathcal{C}_2$ be ...
user avatar
  • 359
1 vote
2 answers
62 views

Is there a standardized way to evaluate the security of a key exchange algorithm?

I'm now trying to design a more secure key-change algorithm to replace widely used DH. However, I am only able to prove that my algorithm is more secure logically, which means I can only prove it from ...
user avatar
  • 31
1 vote
0 answers
62 views

Security of anonymous group credential issued over multiple user secret keys plus a common/public system message

In a group signature scheme based on Pointcheval-Sanders (PS) single-message signature, the anonymous credential $(\sigma_1,\sigma_2)$ issued by the group manager (GM) with secret key $sk = (x,y) \in \...
user avatar
0 votes
0 answers
27 views

Why is a protocol that is secure in the presence of a malicious adversary also secure in the presence of an augmented semi-honest adversary?

Proposition Let π be a protocol that securely computes a functionality f in the presence of malicious adversaries. Then π securely computes f in the presence of augmented semi-honest adversaries. ...
user avatar
3 votes
1 answer
115 views

Can a collision resistant hash return zero?

Recently, I have been reading the original proof of GCM. It mentioned the properties of "almost universal" and "return zero" for hash function. I wonder if there is a connection ...
user avatar
  • 115
0 votes
0 answers
46 views

Collision resistance analysis

I am learning about collision resistance security notion of hash functions. However, I got confused when collision resistance experiment started using "keyed" hash functions in the ...
user avatar
0 votes
1 answer
41 views

How to understand the "Authenticity" and "Privacy" of CCM-mode encryption scheme?

CCM mode refers to CTR+ CBC-MAC encryption mode. Based on this paper, the adversary's advantages against the authenticity of CCM is: Eq(1) Authenticity: it should be infeasible for an adversary to ...
user avatar
0 votes
0 answers
45 views

The simulation sound extractable NIZK

I was recently reading the paper Hawk: The Blockchain Model of Cryptography and Privacy-Preserving Smart Contracts. To prove the security, the authors assume that the NIZK used in the protocol is ...
user avatar
1 vote
2 answers
87 views

What is the relationship between "Challenger" and "Oracle" in a security proof?

In game-based security proof, I found that games are defiend to be played between a PPT adversary and a challenger. The adversary is able to issue queries to different oracles and receives ...
user avatar
26 votes
7 answers
5k views

Is there any famous protocol that were proven secure but whose proof was wrong and lead to real world attacks?

Are there moderns (post World War II) and famous protocols that were proven secure (in any model: game-based, UC...) but whose proof was wrong and could have led to real-world attacks? Note that: I'm ...
user avatar
1 vote
0 answers
68 views

The Responsibility of Key Exchange

I've been implementing an asymmetric key exchange for creating a symmetric key. My question is more of a philosophical/legal one in terms of key-exchange responsibility, and what happens when let's ...
user avatar
0 votes
0 answers
52 views

Security of a variant of DDH

The standard DDH assumption states that given $(g,g^a,g^b,g^c)$, it is hard to determine whether $c$ is $ab$ or not. A variant of DDH assumption is: given $(g,g^a,g^b,g^c, g^{ab} ,g^{bc},g^{ac})$, it ...
user avatar
2 votes
1 answer
78 views

Question about malicious security in protocol using OT

I was studying a protocol that used an OT and suddenly and suddenly I realize that I fail to imagine how a protocol using an OT could be malicious secure. Suppose we have a protocol P that use an OT ...
user avatar
  • 21
0 votes
1 answer
78 views

XChaCha20 With a Zeroed Nonce?

We know that for ChaCha20 and XChaCha20, the same key can never be used with the same nonce. But let's say I use a random 256-bit key every time... Then the nonce can be whatever because the key is ...
user avatar
  • 421
6 votes
1 answer
326 views

Is it secure to do Shamir key split on a key in blocks and recombine?

Yesterday I made a PR to a python crypto library to support key sizes larger than 16 bytes for Shamir secret sharing scheme. Currently it supports 16 bytes, as follows: $$ K = \{ 0, 1 \}^{128} $$ $$ ...
user avatar
  • 97
1 vote
1 answer
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 ...
user avatar
3 votes
0 answers
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 ...
user avatar
1 vote
2 answers
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 ...
user avatar
2 votes
1 answer
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] $$ ...
user avatar
  • 247
0 votes
1 answer
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 ...
user avatar
0 votes
0 answers
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 ...
user avatar
  • 502
0 votes
1 answer
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 43
0 votes
1 answer
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 ...
user avatar
  • 43
1 vote
2 answers
109 views

What are security reductions of symmetric-key algorithms?

I was reading Wikipedia page of post-quantum cryptography. It says that it is desirable for cryptographic algorithms to be reducible to some particular mathematical problem, that is intractability of ...
user avatar

1
2 3 4 5
13