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.

learn more… | top users | synonyms

0
votes
1answer
126 views
+50

Proof for composed signatures

Assumes that we have 3 signature algorithms, $S^A$ with key pair $(sk^A,pk^A)$, $S^B$ with key pair $(sk^B,pk^B)$,$S^C$ with key pair $(sk^C,pk^C)$. We denote by $\epsilon$, $\epsilon'$ and ...
3
votes
1answer
57 views

OCB and GCM security

Is OCB as secure as GCM or CCM ? Since OCB design is quite different from GCM and CCM, I was wondering if the security properties of these latters are satisfied by OCB, as well. Thank you.
3
votes
1answer
201 views

Security equivalent to Diffie–Hellman problem?

I've been doing the security proof for one of my Theorem. Basically, given $g^a$, $g^b$, $g^{cb}$, $g$ and $c$ as known values. Is the problem of computing $g^{acb^{-1}}$ equivalent to the Diffie ...
4
votes
1answer
58 views

Are HMACs based on hashes with larger bit-lengths also more secure?

When doing encrypt-then-mac, I can choose to use a hmac as the MAC. For example, I could use a hash like SHA-256 or SHA-512 (by using it as a keyed hash) to create that HMAC. Does it increase ...
1
vote
1answer
86 views

Use ElGamal to solve Diffie-Hellman problem

Say we are able to decrypt a Elgamal ciphertext $c$ using only the public key. Apparantly it is now possible to solve the Diffie-Hellman problem (given $g^a, g^b$ calculate $g^{ab}$). How? I know how ...
4
votes
2answers
273 views

Is SipHash cryptographically secure?

I'm evaluating different hash algorithms for use in my application. One of the kind of algorithms I am looking at are cryptographically secure ones to protect against DOS attacks. SipHash seems ...
1
vote
1answer
65 views

Protocol composition [closed]

I have been trying to wrap my head around different definitions of protocol security (stand alone, sequential composition, parallel composition, universal composition) and how the proofs of any of ...
2
votes
1answer
100 views

Hamiltonicity proof of knowledge

I'm learning the POK notion and definitions and as a self exercise I wante to prove the statement that the Hamiltonicity protocol is a POK system with knowledge error $1/2$. So the question will be ...
2
votes
2answers
102 views

Reductionist proofs of decisional problems to computational

Are they any reductionist proofs where an attacker $\mathcal{I}$ for a well established computationally "hard" problem $\mathsf{Π}$ is employing an attacker $\mathcal{A}$ who we assume is able to ...
5
votes
1answer
137 views

What is the “artificial abort” technique?

In the security proof of Brent Waters's paper Efficient Identity-Based Encryption Without Random Oracles, he uses a novel “artificial abort” step on page 6. At this point the simulator is still ...
4
votes
2answers
99 views

Is it possible to construct a secure block cipher of size $2n$ given a secure block cipher of size $n$?

Given, say, the Blowfish block cipher, which is considered secure but only has a 64-bit block size, can we construct a secure block cipher of 128-bit block size? Say we run the key through two KDFs, ...
2
votes
1answer
25 views

Is the CONF key sharing Problem equivalent to discrete log problem?

If there a proof in the literature which says the CONF Problem is equivalent to solving the discrete log ? Let $g$ be a generator of a cyclic group $\mathbb{G}$ of prime order $q$ CONF problem: ...
-1
votes
1answer
82 views

Is less security required for a short stream cipher than for the AES enciphering of very long messages? [closed]

Criticisms of a cipher system such as 'the ciphertext from one message must be indistinguishable from the ciphertext of a second message" surely only apply when there are very large amounts of ...
1
vote
1answer
72 views

Exchanging Keyspace and Message space in PRF

Suppose there is a secure PRF $F: K \times X \to Y$. Then is $F': X \times K \to Y$, defined by $F'(x,k):=F(k,x)$, a secure PRF? In my opinion it should be because exchanging the keyspace with ...
1
vote
1answer
50 views

Showing that security of a elgamal invariant is insecure

Original Elgamal signature is defined $S(m, \alpha) = (r, s)$, where $$r = g^k \bmod p$$ $$s = (m – r*α)k^{-1} \bmod (p – 1)$$ more information on Elgamal signature can be found here. Variant ...
3
votes
2answers
168 views

security in the standard model → random oracle model?

Can a protocol proved secure in the standard model be considered secure in the random oracle model?
0
votes
2answers
82 views

Times of nested algorithms in proofs of security

Proofs of security may be constructed such that an adversary $A$ is used to construct an adversary $A'$. The reduction/algorithm which uses $A$ has to perform a number of computations in order to ...
2
votes
1answer
101 views

Security proof of FO(Fujisaki-Okamoto) hybrid encryption

The proof of FO hybrid encryption is hard to understand. $\:$ Especially, how does the challenger respond to the decryption queries when the challenger can only have some encryption queries? Can ...
2
votes
0answers
80 views

Looking for a detailed example of proof by reduction

I'm looking for a very detailed example of proof by reduction. Say we have two or three protocols (that have been proven secure) and we construct a new protocol. We want to provide a proof of security ...
3
votes
2answers
184 views

Is a random oracle controled by the challenger?

When proving a Crypto scheme security under random oracle model, is the random oracle always controlled by the challenger? What if the Hash is only used by the adversary?
1
vote
1answer
100 views

Rock-paper-scissors over network, how to protect from cheating server?

I'm trying to design cryptographic protocol to play Rock-Paper-Scissors with two parties, neither trusting each other, nor trusting server they use for communication, so game is 'provably fair'. So ...
4
votes
1answer
139 views

Would a symmetric cipher with a keylength a big as the data length be information theoretically secure?

One-Time-Pad is information theoretically secure as long as the random number stream is evenly long or longer than the data stream it encrypts, for a "decyphered" message could have been any message ...
5
votes
4answers
561 views

Is this a pseudo random function (PRF)? F(k,x) = f(k,x) - f(k,x-1)

I have a question about Pseudo Random Functions. Let $f:\{0,1\}^m \times \{0,1\}^n → \{0,1\}^n$ be a secure PRF. Define $F(k,x) = f(k,x) - f(k, x-1 \bmod 2^{n}) \bmod 2^{n}$. Is $F$ is a secure ...
1
vote
1answer
80 views

Modular protocol design

What does modular protocol design mean? Why does TLS not have modular protocol design? What protocols have modular design? (IPSec, SSH)
3
votes
1answer
120 views

Proofs by reduction and times of adversaries

I have some difficulties to understand, when we construct a reduction, how we determine the time for the constructed adversary to break a target security property. In general these details are not ...
3
votes
2answers
320 views

Signature based on public key cryptography and forgery

In the definition of existential unforgeability, there is no detail about the following questions. In general, can we suppose that a signer is also a possible adversary ? When generating a signature, ...
3
votes
1answer
337 views

Perfect Secrecy -> One Time Semantic Security -> Secure PRG

I think I have some sense of what Perfect Security means, and even Semantic Security, but I am struggling with randomness, so I'm going to ask a question about CSPRG's (Cryptographically Secure PRG's) ...
2
votes
2answers
163 views

What does “Worst-case hardness” mean in lattice-based cryptography?

In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below: Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with ...
4
votes
1answer
134 views

Reason for difference in assumptions for practical private-key and public-key crypto

Theoretical cryptography tells us that everything in the world of private-key cryptography (CCA-secure symmetric encryption, message authentication codes, etc.) can be built from one-way functions and ...
0
votes
2answers
120 views

Can you prove the existance of a PRG $G$ s.t. for each even $k$: $G(k)=G(k+1)$?

In one of the exercises in [KL] Book I need to tell whether an encryption scheme is secure under an eavesdropper of only one message. Given a PRG $G: \{0,1\}^n \rightarrow \{0,1\}^{n+1}$. The ...
1
vote
0answers
56 views

Is it feasible to break an encrypted and later encoded message?

A message is sent from a person to another. The plain message is first encrypted, even with a weak algorithm - say, DES. Then, the encrypted message is encoded with a simple substitution, which is ...
3
votes
3answers
215 views

Chance in cryptography

I was just thinking about my own chance and the way chance can defeat even the most advanced algorithm. My thought was : you can make a strong session id, but what if by chance, a hacker set this ...
2
votes
1answer
88 views

A confusion about HMQV?

As the full version of HMQV is very long, I will give a graph of it below \begin{array}{@{}l@{}c@{}l@{}} \hat{A} && \hat{B} \\ (a,A=g^a)&&(b,B=g^b) \\ x\in_R[1,q-1],\quad X=g^x ...
3
votes
1answer
123 views

CDH problem and Square-DH problem

CDH problem roughly says that choose $U=g^u, V=g^v$ uniformly at random from cyclic group $G$, it's hard to compute $CDH(U,V)=g^{uv}$. Square-DH problem roughly says choose $U=g^u$ uniformly at ...
4
votes
2answers
165 views

Can we say that if $P=NP$ there is no CPA secure public key encryption?

I've learned that public key encryption is based on the problem of Discrete Log (as regard to group theory) which believed to be hard. But, can we say that it doesn't matter on which problem our ...
1
vote
1answer
56 views

Are those two distributions indistinguishable?

The Decision composite residuosity problem problem states that is impossible two distinguish between those two ensembles: $\{x^N \mod {N^2} | x \in \mathbb{Z^*_{N{^2}}}\}$ and $\{r \in ...
4
votes
1answer
159 views

Unforgeability and type of adversary

When trying to prove security of asymmetric signature, for instance for existential (or strong) unforgeability against chosen messages attack, do we need to consider the signer as a possible ...
4
votes
1answer
134 views

How can I tell how many bits of security a secure hash function has?

How can I tell how many bits of security a secure hash function has? For example, how would I calculate or tell how many bits of security a secure hash function with 160 bits output would have? ...
0
votes
1answer
58 views

The real-life meaning of proving over a group that doesn't support the oracle?

If I proved a scheme's security under GDH assumption, in real-life, if this DDH oracle does exist, then it's good, but what about other side ? In real-life, if this DDH oracle doesn't exist, then ...
3
votes
1answer
131 views

Flaw in the security definition of *Stateful* Authenticated Encryption?

I'm in search of the correct definition of a stateful authenticated encryption scheme (sAE), and its related security notion. This has been treated several times in the academic literature, however, ...
3
votes
1answer
170 views

Is $q(n)=1/n$ a negligible function?

By definition - $q(n)$ is a negligible function if for every positive integer $c>0$ there exist an integer $N_c$ such that for all $x>N_c$ : $q(n)<1/x^c$ So for the function $1/x$, if we ...
3
votes
1answer
93 views

Difference between computational and statistical indistinguishabilities

What is the difference between the two notions of computational and statistical indistinguishability?
1
vote
1answer
53 views

order between adversaries and type of resources given

We have a game $G0$ for which an adversary $A$ has access to a certain amount of ressources. Let us suppose that the maximum advantage for the adversary to win this game is $Adv_{G0}$. If we modify ...
5
votes
4answers
252 views

Is there a proof for showing any cryptogram is crackable?

I commonly hear statements along the lines of "all cryptograms are crackable - it's only a matter of time". Is there a proof to show that any cryptogram is "crackable"? The proof may be of a more ...
1
vote
1answer
90 views

SHA-1 Keyed Hash Function

I know that SHA-1 is an unkeyed cryptographic hash function when used in practice. But, in the theory, all hash function are defined with keys. My question is: How I will be able to formalize the ...
4
votes
2answers
215 views

Can anyone give an example where (asymmetric) crypto can go wrong due to selection of wrong groups?

Basically the title says it all. It would be great if someone could tell give an example using provable security. More information about groups can be found at: ...
1
vote
2answers
116 views

PPT eavesdroper able to output $m_{0}$ and $m_{1}$ of different lengths

I've read the following two questions and their answers: Messages of different lengths and one-time computationally-secret Why is a non fixed-length encryption scheme worse than a fixed-length one? ...
1
vote
1answer
94 views

Security based on PRF

I've seen that there is several kinds of PRF, and sometimes people speak about strong PRFs. When proofs of a protocol or algorithm are given based on the assumption of the use of a PRF, are they ...
4
votes
2answers
179 views

Security proofs for CBC mode

I'm looking for different approaches to proofs for the security of CBC mode encryption. What are the best sources of information about this subject?
0
votes
1answer
63 views

Hash of multiset of values, which lets me compute the hash of the union

Cryptographic hash functions normally take as input a bitstring. I am looking for a hash function that takes as input a finite multiset of values. In other words, given $S \subset \{0,1\}^*$, I want ...