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
0
votes
0answers
43 views

How much information of the length of a plaintext can an adversary get from its ciphertext?

Let $\Pi$ be a public-key encryption scheme. For every palintext $x \in \{0,1\}^{*}$, is there a PPT adversary $A$ such that $$\Pr \left[ 1^{|x|} \leftarrow A\left( pk, \mathrm{Enc}_{pk} (x) \right) \...
4
votes
1answer
106 views

For a random permutation $P$, what's the probability of the following event?

For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\...
0
votes
3answers
555 views

Information-theoretic security [closed]

From Wikipedia: Information-theoretic security is a cryptosystem whose security derives purely from information theory. In other words, it cannot be broken even if the adversary had unlimited ...
1
vote
1answer
84 views

Does semi-honest adversary eavesdrop honest parties communication?

Assume we have a multi-party computation protocol and the protocol definition, where both of them consider a semi-honest adversary, without explicitly assuming the type of channel the parties want to ...
3
votes
1answer
264 views

Why is the lite version of Cramer-Shoup not IND-CCA2 secure?

In the lite version of Cramer-Shoup we have a group $G$ with generators $g_1$ and $g_2$, private key $a_1, a_2, b_1, b_2$, and public key $A = g_1^{a_1} g_2^{a_2}$, $B = g_1^{b_1} g_2^{b_2}$. ...
1
vote
0answers
76 views

Can RSA be used as a one-time pad for authentication?

In the case of Smart Contracts, there are self-destruct functions for the contract which can only be run by the contract owner. In many cases attackers have found a way to take over the contract ...
4
votes
1answer
146 views

A problem in secret sharing and mixed operators over $\mathbb{Z}$

Recently, I studied an article in which it was written that having $(A-B)\oplus C$ and $B\oplus C$, we cannot find $A$. The authors used this result to build a secret sharing scheme, but they did not ...
3
votes
1answer
218 views

How hard is the following q-Strong Diffie-Hellman problem?

From On the $q$-Strong Diffie-Hellman Problem, the following problem is well-known to be hard. For an randomly chosen element $x \in \mathbb{Z}_p$ and a random generator $g \in \mathbb{G}$, the ...
0
votes
1answer
141 views

Commit and prove as a general trick for malicious security

After reading through Lindell's excellent tutorial (https://eprint.iacr.org/2016/046.pdf), I wonder about the following. To make a protocol secure against fully-malicious security, it seems that ...
2
votes
1answer
69 views

Is there a way to double the size of ciphertexts of a public-key scheme which is IND-CCA2

Let $\Pi = \left( \mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec} \right)$ a public-key scheme which is secure in the sense of IND-CCA2. Assume the ciphertexts space is $\mathcal{C} \subset \{0,1\}^{n}$. Can ...
2
votes
1answer
55 views

Why do the game-hops in Kyber and related papers contain 2 steps at a time?

In the Kyber paper in section 3 about the Kyber IND-CPA Encryption there is a proof by sequence of games containing three games. I understand that in the first game hop the M-LWE advantage is used to ...
-3
votes
1answer
428 views

Could you list all of the security models in cryptography?

I only know some of security models: rom->crs->std How about others? Or may it be different in several fileds? Thanks.
3
votes
0answers
74 views

Assuming the difference between success probabilities to be positive

Context: I am currently studying Theorem 3.1 in the paper Number-Theoretic Constructions of Efficient Pseudo-Random Functions by Naor and Reingold. The theorem basically states the randomized self-...
4
votes
2answers
301 views

Role of session identifier in Otway-Rees protocol

According to Wikipedia, Otway-Ress protocol is as follow: The protocol can be specified as follows in security protocol notation, where Alice is authenticating herself to Bob using a server $S$ ($M$...
4
votes
1answer
261 views

Formal Verification of DHKE protocol using ProVerif

I am new to ProVerif and trying to verify a simple DHKE protocol. The attacker is assumed as passive. The specifications are: The attacker cannot obtains the mutual key. Both participants obtain the ...
2
votes
1answer
115 views

Practical implications of the switching lemma and the counter mode security bound

I have some trouble with determining how many times a key can be safely used when using counter mode encryption. For example: We split the IV into two parts, a message counter (nonce) and a block ...
3
votes
1answer
109 views

Complexity leveraging in case of exponentially many hybrids

Complexity leveraging is a proof technique in cryptography where the reduction algorithm runs in super-poly time. (see this). Many papers use complexity leveraging when there are exponentially many ...
2
votes
2answers
255 views

Is Discrete Logarithmic assumption enough to design a secure searchable encryption scheme?

I have a basic question in my mind which is "Can we develop a scheme based on Discrete Logarithmic (DL) assumption only? " Most of the "Searchable Encryption" schemes use assumptions like Decisional ...
2
votes
2answers
65 views

Sensitivity of probability measure in differential privacy

I know that we need some sort of sensitivity(global, local) to calculate noise that needs to be added for differential privacy. The noise is the maximum difference between two neighboring datasets. ...
3
votes
1answer
121 views

Notion of Security in case of Covert Adversaries

On the page 31 of the Book "Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay", while defining the notion of security in case of covert adversaries, it is mentioned: Define an ...
0
votes
1answer
94 views

Simple designs for provable security in cryptographic primitives

We can say that a cryptographic primitive has $n$ bits security against a type of attack if it cannot break it in less than $2^n$ time (time-area product in some cases). The cryptographic primitive ...
1
vote
1answer
277 views

Security proof of mix net

I am writing an exercise in cryptography about anonymous communication. One of the systems I have looked into is the mix net protocol. I want to prove that this is secure. I have seen many different ...
1
vote
3answers
619 views

Is there a cryptography algorithm that will remain safe if P=NP?

From what I heard, many encryption algorithms are based on the assumption that some problems are computationally hard, i.e, NP-complete. In the unlikely event that someone proves that P=NP, these ...
2
votes
1answer
274 views

Security of a given hash function

We have a message denoted $M$. Let us suppose that we have a collision-resistant hash function $h_0$ with output length $n$. We then consider two other independent (different) hash functions $h_1$ and ...
3
votes
0answers
229 views

ring-LWE: Minkowski Embedding , the Co-Different Ideal, etc

While (trying) to go over the reductions from approx. SVP on ideal lattices to search ring-LWE, [1] and [2], for $K = \mathbb{Q}(\zeta)$ where $\zeta$ is an abstract root of a cyclotomic polynomial, ...
3
votes
1answer
255 views

Security in case of Malicious and Augmented Semi-Honest Adversaries

On page 29 of Book Efficient Secure Two-Party Protocols by Y. Lindell and C. Hazay, there's this proposition: Let π be a protocol that securely computes a functionality f in the presence of ...
5
votes
1answer
626 views

Merkle trees instead of the Sponge or the Merkle-Damgård constructions for the design of cryptorgraphic hash functions

Most modern cryptographic hash functions use some form of compression function combined with a construction such as the Merkle-Damgård (MD5, SHA1, SHA2, etc), the Sponge construction (with Keccak as a ...
3
votes
1answer
167 views

Security proof for CBC as a prefix-free PRF

I am currently trying to fully understand Dan Boneh's/ Victor Shoup's proof in their excellent crypto book draft, that the raw CBC construction is a secure pseudo random function family for prefix-...
-1
votes
1answer
96 views

Does hashing a weak hash with a stronger hash make it secure?

If you made a hash function that worked like this: SHA(std::hash(T input) Would it be a secure hash? The reason I am asking is that std::hash provides a template input, which is much more convenient ...
8
votes
1answer
694 views

Lattice Crypto worst case to average case

I am currently reading the ETSI white paper Quantum Safe Cryptography and Security On page 24 one finds the following statement: Lattice problems also benefit from something called worst-case to ...
1
vote
1answer
50 views

What does the “Type 1 query” model on Miles, Sahai, and Zhandry's paper?

On the paper Annihilation Attacks for Multilinear Maps: Cryptanalysis of Indistinguishability Obfuscation over GGH13, authors present, in section 2, an abstract model to analyze security of $i\mathcal{...
5
votes
1answer
1k views

Prove the Security of Schnorr's Signature Scheme

I know that Schnorr's signature is important since it is one of the most compact signature schemes whose security has been proved in the random oracle model. Now, I want to know if such proof is ...
1
vote
0answers
49 views

Cryptographic Tagging of Information over an Insecure Channel

Is there an efficient algorithm for the tagging and location of information over an insecure channel, where two parties (the tagger and the intended recipient for the tag) can recognize a piece of ...
1
vote
1answer
300 views

PPT vs NP problems

The common definition of security (for some cryptographic primitive) is to be secure against any PPT adversary (any probabilistic algorithm which runs in polynomial time). At the same time, we assume ...
5
votes
5answers
273 views

How to rigorously prove that $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$ is CPA secure assuming $\Pi$ is?

Assume $\Pi$ is a CPA secure scheme. Let $\Pi'$ be a derived scheme, such that the encryption of a message $M$ is as follows: $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$, where $LSB(k)$ is the ...
2
votes
0answers
111 views

Why does the DBDH simulator have half the advantage of an adversary?

Literature that includes the DBDH assumption such as this paper or this paper has a formal security proof that states: Suppose an adversary with non-negligible advantage $\varepsilon = Adv$. A ...
4
votes
0answers
293 views

Provable Security: concrete approach vs asymptotic approach [closed]

I was reading Professor Lindell and Katz's book. Their book takes the asymptotic approach to the security proof, while lots of papers on crypto seems to use the concrete approach when it comes to ...
1
vote
3answers
501 views

How to explain just how secure AES is in layman terms?

I have a rather particular classmate who wholeheartedly believes that there isn't such a thing as reasonably secure cryptography and that most people can steal encrypted data. I have attempted to ...
1
vote
1answer
292 views

Security of SWIFFT Hash Function

Is the SWIFFT hash function described in: https://en.wikipedia.org/wiki/SWIFFT still considered a provably secure one way function? Is it also considered secure against attacks by a quantum ...
3
votes
0answers
260 views

Is a PRG that reveals the first bit of the input secure

Let $G:(0,1)^n \rightarrow (0,1)^{n+1}$ be a secure PRG. Define $G'(s):=s_1 ||G(s)_{2,...,n+1} $. ($||$ is concatenation, and the subscript $ _{2,...,n+1}$ means the last $n$ bits of $G$) I claim ...
3
votes
1answer
334 views

Is it insecure using addition instead of multiplication in Elgamal encryption?

I am wondering why most textbook only explain Elgamal encryption using multiplication operation, i.e. $c = m\cdot g^{ab} \pmod p$ instead of addition modulo $p$, i.e. $c = m + g^{ab} \pmod p$? Is ...
7
votes
1answer
345 views

Relation between decisional SIS and leftover hash lemma in lattices

The semantic security of Regev's cryptosystem [Reg05] is based on the LWE assumption and leftover hash lemma. This lemma implies that because $m \approx (n+1)\log q$ is large enough, so for uniform $A\...
2
votes
1answer
104 views

Is it possible to prove the time a message was produced?

Say Bob wants to tell Alice a secret message, then they start some message exchanges protocol. At the end, Alice will receive the secret message and can be convinced that the message was not produced ...
4
votes
0answers
188 views

Complexity: Taylor series and security proofs [closed]

Taylor Series For some functions entered into Wolfram, a Taylor series expansion is represented in Big-O notation. E.g. $\sin x, x = \frac \pi4$ produces: $\frac {1} {\sqrt[]{2}} +\frac{x-\frac{\pi}...
3
votes
2answers
473 views

Is the following construction of a secure PRG is also a secure PRG?

Given a secure PRG $G :\text{{0,1}}^n \rightarrow \text{{0,1}}^{2n}$, I've constructed the following PRG: $$ G'(x) = \begin{cases} 0^{2n} & \text{if x is palindrome;}\\ G(x) & \text{...
4
votes
0answers
121 views

What's the difference between game-based and simulation-based security? [duplicate]

What's the difference between game-based and simulation-based security? When we use the simulation-based, how to construct the simulator based on the adversary?
6
votes
1answer
466 views

The notion of sub-exponential security

I have been reading a paper where they construct probabilistic IO (indistinguishability obfuscation) from sub exponential IO. I want to know if the following two notions of sub-exponential security ...
3
votes
1answer
502 views

Is this a secure PRG?

Suppose that we have a secure PRG $$G:\{0,1\}^{n} \rightarrow \{0,1\}^{l(n)}$$ I want to construct a secure PRG $G'$ that when we select its seed $s \in \lbrace 0,1 \rbrace^n$ that $parity(s)=0$, it ...
5
votes
1answer
194 views

Is it possible to determine if data was encrypted by a specific public key?

If the prover provides a block of data and a public key. The provided data is supposedly ciphertext that was encrypted using the provided public key. Is there a way to prove that the provided data has ...
8
votes
1answer
516 views

Proof that $g(x) = f(x) || f(f(x))$ is a OWF when $f$ is a OWF

Assume that $f$ is a one-way function (OWF), and let $\mathbin\|$ denote string concatenation. Consider the function $g$ defined by $g(x) = f(x) \mathbin\| f(f(x))$. It is easy to prove that $g$ is a ...