Questions tagged as ['provable-security']

(I guess no but why is this the case? Any way to make it possible?)

Out of a given equilateral triangle T1 (with his 3 vertices A,B,C lying in a finite Field $\mathbb F_N^D $) another equilateral triangle T2 can get constructed by mirroring one of the 3 vertices at the edge in between the two other vertices. This will be repeated multiple times.

Given just two random triangle T1 and T2 (and $\mathbb F_N^ ...

I've a problem with a protocol for which I can prove the security if the messages sent by the adversary are sent in clear, but I can't prove the security anymore if the messages sent by the adversary are encrypted... and this is a bit strange since I expect the protocol to also be secure in that second case.

More precisely, I'm considering a protocol for which a server Bob receives a message $k$ from ...

I think I found a small error in the security proof Link end of page 37. It states that

$ \sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q +1)q/2+2}{p - (3q +2)^2 /4}$.

But shouldn't it be

$\sum_{i\leq q} \frac{3i+2}{p-(3q +2)^2/4} \leq \frac{3(q+1)q/2+2q}{p - (3q +2)^2 /4}$ ?

I think that the proof still works, since we want to show that you need $\mathcal{O}(\sqrt{q})$ queries to succe ...

I'm currently studying a paper (Sequences of Games: A Tool for Taming Complexity in Security Proofs) on proving semantic security using the Game Hopping technique by Victor Shoup.

On pages 9-11, he is using a sequence of three games, $Game 1$, $Game 2$, and $Game 3$ to deduct the semantic security of Hashed ElGamal to DDH and entropy smoothing assumptions. How does he combine the three probabilitie ...

In cryptography security proofs mainly use the reduction proof technique. I now have read a lot of reductions proofs and also did some on my own and I think I understand it pretty well. While reading those proofs I noticed two main styles of such a reduction.

Say we have scheme $B$ based on $A$. We know $A$ is secure. If one wants to proof the security of $B$ by reducing it to the security of $A$ ...

In Katz & Lindell's textbook (2nd edition)) is said, that only non deterministic encryption can lead to security for multiple encryptions. Now I looked at the experiment for multiple indistinguishable security and there is said, that the challenger gets two sets of messages from the adversary. Say we have the PRG cryptosystem, that XORs messages with the output of the PRG. Why couldn't the ch ...

Bernstein proofs in his paper that single-key security of the classic Schnorr signature system tightly implies the single-key security of the key-prefixed variant of the system. Can this statement be applied also for short schnorr signatures (halved hash output length)? In other words: Does single-key security of short schnorr signature system tightly implies the multi-key security of the key-prefixed va ...

I don't have a very specific question, but reductions have been a weaker suit of mine and I was wondering if there is a secure MAC scheme, and a derived MAC' that uses MAC but modifies it in some way, how could you prove that MAC' is secure via reduction? I know how to do reductions for PRGs and PRFs, but not sure how to use it for MACs. I don't have a concrete example, but a walkthrough of the general  ...

In cryptography there are 4 basic attack classifications:

• Ciphertext-Only Attack
• Known-Plaintext Attack
• Chosen-Plaintext Attack
• Chosen-Ciphertext Attack

In Katz & Lindell's textbook (2nd edition) one can find a security definition and experiment for those attacks. E.g. to define CPA-security. Those experiment are between a arbitrary adversary and a challenger. I was wondering, if there exists such  ...

Neven et al. stated in their paper Hash Function Requirements for Schnorr Signatures following theorem (using the forking lemma): $\mathbb{G}$ is the generic group (section 2), $s \approx \log_2q$, hash function $H: \lbrace 0,1 \rbrace^* \rightarrow \lbrace 0,1 \rbrace^n$.

Theorem 1 If the discrete logarithm problem in $\mathbb{G}$ is $(t_\text{dlog}, \epsilon_\text{dlog}$-hard, then the Schnorr Signatu ...

I read about the provable cryptography in Wikipedia. The article referred to tense controversies around 2007.

Do these controversies still exist?

What is the substitution for the provable-security? Is not it sufficient? I think AES does not follow provable cryptography style, am I right?

Which is the accepted/preferred view in the Cryptography community?

Why did it started in the first place, Is n ...

I'm currently reading this paper [PDF]. On page 4, I bumped into these notations :

\begin{equation} \text { Experiment } \operatorname{Exp}_{\mathcal{F} \mathcal{E}, A}^{\text {ind-mode }}(k) \text { : } \end{equation}

\begin{equation} A_{1}^{\mathrm{KDer}\left(s k_{i}\right)}(p k) \end{equation}

I tried searching online and resolved most of the other notations involved, like the $ \stackrel{\\\$}{ ...

I know that this is a very specific question, but I still hope that someone can help me. I'm trying to understand the security of the short schnorr signature a little bit better. The security parameter is $k$. The Schnorr Signature $\sigma = (s,e)$ with $s,e \in \mathbb{Z}_q$ has a signature length of $4k$ bits ($s$ and $e$ have $2k$ bits, $e$ is a hash output). The Short Schnorr Signature uses a shorter  ...

Given the popular Private Set Intersection (PSI) protocol first described in [1]:

• Alice choose a random $a$, and sends $\{H(x_i)^{a}\bmod p\}| (i=1,...m)$ to Bob.
• Bob choose a random $b$, and sends $\{H(y_i)^{b}\bmod p\}| (i=1,...n)$ to Alice.
• Alice computes and sends $\{H(y_i)^{ba}\bmod p\}| (i=1,...n)$ to Bob.
• Bob computes and sends $\{H(x_i)^{ab}\bmod p\}| (i=1,...m)$ to Alice.
• Each party locall ...

Let $n$ be the number parties in a distributed cryptographic protocol where an adversary can corrupt up to $n/3$ nodes in the network.

Static Adversary: The set of corrupt nodes is fixed a priori.
Adaptive Adversary: Adversary selects the set of corrupt nodes during execution of the protocol.

Let’s say we do not know how to prove a distributed cryptographic primitive X secure against an adaptive adver ...

I have just checked a few FPE schemes like "Swap-or-not", "Mix-and-cut" which are provably secure. What techniques do the provably secure FPE scheme provably secure?

The FPE schemes used in practice use Feistel Network like FF1 and FF3. What makes provable secure FPEs work slower so that they are not used in practice?

homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection.

Is there an simple way to calculate the security level?

I have so far seen the proof by reduction technique to prove the security guarantee of cryptosystem where we consider breaking the cryptosystem as hard as solving a difficult mathematical problem. What are the other proof techniques used to prove the security of the Cryptosystem? It would be beneficial if the technique is briefly stated.

There are 2 different definitions of special soundness in the literature:

(1) can be found in Damgard:

We say that a Sigma-protocol $\Pi$ satisfies special soundness, if there exists a PPT extractor $\mathcal{E}$, such that given any pair of accepting transcripts $(com,ch_1,resp_1),(com,ch_2,resp_2)$ with $ch_1\neq ch_2$, $\mathcal{E}$ can recover $sk$.

(2) can be found in Katz: Digital Signature ...

In speedrunning video games, one records a game being played and beaten in one continuous attempt. However, what can be done to cheat is to do multiple attempts, and splice together clips of the best segments to make one fast speedrun that wasn't done in a single continuous hop. This splicing isn't hard, as e.g. loading screens always look the same, so you can swap the video at those points witho ...

I am defining multi-party computation using the real-ideal paradigm (see A Pragmatic Introduction to Secure Multi-Party Computation). That is, for any successful attack on an MPC protocol in the real world, there exists a simulator that carries out this attack successfully in the ideal world. It follows that security in the real world must be equivalent to security in the ideal world.

I am defining inter ...

While reading tutorials on two-party computation I encountered two (at least formally) different definitions of security (with semi-honest adversaries). What I want to know is whether these definitions are actually different or can be shown to be equivalent. I suspect that they are different, but I might be missing something, considering that I have not read anywhere about different definitions.

 ...

In this paper ("Strong key insulated signature schemes" by by Dodis, Katz, Xu, Yung (2002)), I understand most of the proof for Lemma 1 (pg. 9); I struggle with how some of the probability is calculated though.

No need to read the paper, I think, all you need is the following:

Context

• Adversary $A$ breaks (the "new") scheme $\Pi$
• Challenger $A'$ wants to break the underlying scheme $\Theta$ usin ...

I've recently found some work on the use of Formal Verification Software, like ProVerif for enclaves. I wonder is if its feasible to have something similar for MPC and Homomorphic Encryption and their applications?

I always thought there were limitations adopting simulation based proofs and Universal Composability, in general, in Formal Verification, but as of late I'm thinking there must be mor ...

In "How To Simulate It" (page 45, line 10), Lindell noted that, in the $f_{\textsf{zk}}$-hybrid model (where $f_{\textsf{zk}}$ denotes the ideal zero-knowledge functionality) in the stand-alone model,

if the adversary controls the party running the prover, then it directly sends the input and witness pair $(x, w)$ to $f_{\textsf{zk}}$. This means that a simulator who internally runs the adversary wi ...

I've often read about the security of a signature scheme in the multi-user setting Link1 Link2, but I couldn't find a real definition. I would like to be sure that I understand it correctly. So my question is: If we consider Def 1, would Def 2 make sense for the multi-user setting?

Def 1: The signature scheme yields k-bits of security in the single-user setting if the probability that an attacker can  ...

I was doing the following exercise from the Introduction of Modern Cryptography from Katz and Lindell:

Let $F$ be a length preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0,1\}^n \times \{0,1\}^{n-1} \rightarrow \{0,1\}^{2n}$, state whether $F'$ is a pseudorandom function. If yes, prove it; if not, show an attack.

(d) $F'_k(x) \stackrel{def}{=} F_k(0||x) || ...

Background

The following zero-knowledge (ZK) counterexample is described in Canetti's work [Security and Composition of Cryptographic Protocols: A Tutorial, page 26] to show that there exists some protocol that is secure in the stand-alone model but insecure in the UC model:

Assume there is such a "puzzle system" that both the prover and the verifier can efficiently generate puzzles, and

• The prover c ...

In Shamir's secret sharing scheme, Dealer performs the following steps

1. Choose a prime number $q$ such that $q > n$

2. Choose a secret $s$ from finite field $\mathbb{Z}_q$

3. Choose $t-1$ degree polynomial

$$g(x)=s+c_1x+c_2x^2+\cdots +c_{t-1}x^{t-1}$$

4. Compute shares $s_i = g(id_i) \mod q \text{ for } i=1,2, \cdots,n$ and sends secretly to participants

5. At least threshold number of participants ca ...

I would like to know if there are some methods or techniques that can convert a public key encryption scheme from CPA secure to CCA secure?