Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

2
votes
2answers
37 views

Does side-channel attacks offer any difficulty to Stinson's concept of `provable security'?

Here's a quote from Douglas Stinson: “[i]f a cryptosystem can be ‘broken’ in some specific way, then it would be possible to efficiently solve some well-studied problem that is thought to be ...
3
votes
1answer
724 views

Is RSA provably secure in the sense of Douglas Stinson's ``provable security''?

Here's a quote from Douglas Stinson: “[i]f a cryptosystem can be ‘broken’ in some specific way, then it would be possible to efficiently solve some well-studied problem that is thought to be ...
2
votes
1answer
24 views

Estimate Security level of the Rabin Signature

I'm trying to figure out how long the modulus $n$ has to be in the Rabin Signature scheme, to provide 128 bit security. We assume that the used hash function is "secure enough". Then the naive ...
1
vote
0answers
43 views

Fiat-Shamir paradigm and the forking lemma

I am reading the proof by Pointcheval and Stern and by Bellare and Neven about the forking lemma. The papers discuss the security proof of digital signatures by applying the lemma. It seems also ...
2
votes
1answer
64 views

What is the meaning of $1$ in provable security?

Sometimes, we use $1$ to represent "succeed". In CPA, if the adversary guesses $b'=b$ outputs $1$. But I am confusing about the meanings of the following $1$. Take the DDH for example, $$|\Pr[\...
4
votes
1answer
437 views

Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?

Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks? I have been reading about homomorphic encryption and ...
1
vote
2answers
47 views

Why does WOTS+ need a checksum during signing operation?

I was reviewing WOTS+ scheme for consideration in our private blockchain, and noticed that it had a small overhead of calculating a checksum as seen in the following pseudocode excerpt from the ...
4
votes
0answers
57 views

Use of randomness in an Elgamal like encryption

Suppose I have the following encryption scheme: for a message $m\in\mathbb{F}_p^*$, I generate the ciphertext = $(g^r,f^mh^r)$ where $g$ is the generator of a cyclic group $G$ of unknown order $n$ and ...
1
vote
2answers
67 views

What conditions does a provable secure cryptosystem satisfy?

A cryptosystem can be entirely dependent on its underlying problem or it can have a reduction to other known problems. Solvability can be affordable if there exists a reduction of the base problem to ...
4
votes
1answer
78 views

Is this Sigma Protocol zero knowledge or is it just a proof of knowledge?

Suppose I have the witness $x$ and need to prove that I correctly computed $(g^x)^x$ to a verifier. $g$ and $g^x$ are public. The verifier asks me for $(g^x)^x$, but wants proof that I've given them ...
1
vote
0answers
34 views

Extractability property in Zero Knowledge Discrete Log problems

I am trying to construct a simulator and an extractor for a zero knowledge protocol. I just encountered this text that explains the construction of the simulator. Does someone know of a similar text ...
2
votes
2answers
247 views

What is the name of an attack where the compromise of one key compromises the whole system?

Consider the following: A whole system depends on the security of one private key and if this key is, for any reason, compromised, the whole system will be compromised. What's a suitable name for ...
1
vote
1answer
66 views

Is the simulation-based proof difficult and needed? [closed]

What is the role for simulation-based proof under the semi-honest model without considering malicious adversaries? I agree with that a view of a some party is important to prove that a protocol is ...
1
vote
1answer
43 views

Instead of sending a set of random values, send a key for a PRF

Some Protocols require one party to send $n$ random challenges (or random values) to another party. For communication efficiency purpose, one can pick a random key for a pseudorandom function, and ...
0
votes
2answers
108 views

How to compute secure sum using secure multparty computation?

Suppose there are three voters $P$, $Q$ and $R$, and each will vote only on one candidate out of $X$, $Y$ or $Z$, with a 6 bit vote vector corresponding to $X $, $Y$ and $Z$ respectively (with 2 bits ...
5
votes
2answers
113 views

Motivation of Adversarial Indistinguishability Experiment

I had a question about the motivation behind this definition provided in Katz and Lindell's cryptography book. I copied the paragraph in question along with the definition of the experiment. ...
2
votes
1answer
75 views

How well is it understood mathematically why encryption schemes are hard to crack?

I have read some intro material into cryptography. It mainly goes into the current encryption schemes like AES, but not very deeply into the mathematics of why they are secure. I know that encryption ...
2
votes
1answer
44 views

Does a key exchange protocol with mutual authentication which does not provide forward secrecy can be proven secure in Bellare-Rogway model?

Is forward secrecy a necessary security property for a AKE protocol to be proven secure in Bellare-Rogway model? Is freshness also a necessary security property for a AKE protocol to be proven secure ...
2
votes
0answers
116 views

How few cryptographic primitives can we use to derive all other constructions?

We have a lot of cryptographic primitives now, and many methods of deriving one type of scheme from another. There are even some like the Merkle signature scheme, which uses a hash function to derive ...
1
vote
0answers
32 views

Proofs of security for anonymity in a multi-party setting

I'm looking for material that proves the anonymity of parties in a non-interactive setting. I would like to know if there are simulation based proofs (UC) and property based proofs (game based) for ...
0
votes
1answer
39 views

Fairness and guaranteed output delivery

Why for achieving the fairness and guaranteed output delivery, less than a half of the parties should be corrupted? ($t < m/2$, where $t$ is the number of corrupted parties and $m$ is the total ...
1
vote
1answer
69 views

Any Arbitrary Function

According to the attached reference, does it mean that the adversary computes $PPT(initial~input)$, $PPT(z)$ and $PPT(f_i(x',y'))$? For example, suppose the corrupted party, in the malicious model, ...
1
vote
0answers
28 views

Non-uniform Deciders for computational indistinguishability

I don't quite understand the notion of a decider having a probability distribution function associated with it, and what it exactly says about the decider. From here on page 3-4 it says ...Now, in ...
14
votes
7answers
3k views

Possibility of Chosen Plaintext Attack (CPA) in real-world scenario?

In CPA, it is said that the adversaries get ciphertext for the choice of plaintext of adversaries through an encryption oracle. Is this a realistic assumption in real-world, in which the adversaries ...
1
vote
1answer
98 views

Why is this voting system not secure?

Why not have each person simply treated as a counterparty to an off-the-record chat? People show up in groups and show ID which is cross referenced against a central database to prevent sybil attacks ...
3
votes
0answers
92 views

Proving simulation-based security with unreliable real-world channels

An ideal functionality considers reliable communication channels, whereas a real functionality must consider unreliable communication channels (e.g., channels controlled by the adversary). Thus, it ...
0
votes
0answers
29 views

Can someone give an example of no-message attack>

I know that a no-message attack IS THAT if the adversary has access to a signing oracle and a public key, he can sign an arbitrary message. So can someone give an example of this kind of attack?
1
vote
0answers
33 views

A qusetion about the security game of Certificateless signatures

Recently I read Certificateless Public Auditing for Data Integrity in the Cloud , I have a question about the security of proposed HOMOMORPHIC AUTHENTICABLE CLS. (Sec. IV). For the Type-I Adversary, ...
1
vote
0answers
34 views

A modular approach to the design and analysis of authentication and key exchange protocols

I am studying modular approach to the design and analysis of authentication and of the key exchange protocols. One of them are proposed by bellare et al. On page number 11, I do not understand the ...
-1
votes
1answer
67 views

Is this construction a secure MAC?

Let $F:\{ 0,1 \}^n \times \{ 0,1 \}^ n \rightarrow Z^*_q $ is a PRF, and $H:\{ 0,1 \}^{2n} \rightarrow \{ 0,1\}^n$ is a secure hash function. Is the following construction $\Pi=(Gen,Mac,Vrfy)$ is a ...
4
votes
1answer
96 views

Secure Computation: Reactive Functionalities in the Hybrid Model for Standalone Security

A common approach to make (secure computation) protocol descriptions and proofs simpler is to describe them in a hybrid model, where the protocol in the real world has access to some auxiliary ideal ...
5
votes
4answers
191 views

Are deterministic adversaries as powerful as probabilistic adversaries?

SOURCE states the following in the proof of Theorem 2: Without loss of generality, I will assume that A is deterministic. If A is randomized, we can determinize it by fixing a sequence of coins ...
4
votes
1answer
102 views

Using a PRP $\pi: \{0,1\}^{16} \to \{0,1\}^{16}$ to construct an ideal cipher

Say we have an ideal 16-bit PRP. Since it appears that a permutation with a small domain can be used to turn it into a PRF, which can then be used in a Feistel network. On the surface, it makes it ...
0
votes
1answer
42 views

RSA-FDH and random oracle query count

I am now reading a paper 'The Exact Security of Digital Signatures - How to Sign with RSA and Rabin' and there is an equation e = (q_sig + q_hash) * e' on page 401. (e : success probability of RSA, e' ...
3
votes
0answers
48 views

Functional encryption for inner products from DDH

I have been reading this paper by Abdalla, et al. But there's something I don't get about the security proof (Theorem 3.2) for the basic IP scheme from DDH--how are they simulating the mpk's using $g^...
6
votes
1answer
341 views

Proof by reduction vs. hybrid argument

In many cases why going through the security proofs I have seen that some does it using a blackbox reduction to some known hardness assumption DDH and others do it using a hybrid argument by arguing ...
0
votes
1answer
67 views

Arguing security of an encryption scheme

I have an encryption scheme which masks the message m by multiplying it with a secret random group element i.e $g^r \cdot m$. I should allow decryption and get $g^r$ if I have a valid secret key; ...
0
votes
0answers
42 views

Funtional encryption to Attribute based encryption

I have been reading through the literature in Functional encryption and Attribute based encryption. Undoubtedly, FE is a stronger notion than ABE and FE implies ABE. But, to my knowledge till now I ...
4
votes
0answers
113 views

computational indistinguishable/distinguishable?

Let $a,b,c,d$ be selected at random from $Z_q$. Consider the following two distributions $X_1$ and $Y_1$: $X_1={(r_1\cdot a, r_2\cdot b, r_3\cdot c, (r_1+r_2-r_3)\cdot d)}$ where $r_1,r_2,r_3$ ...
1
vote
0answers
48 views

Security of certain homomorphic encryption scheme

Is the following homomorphic encryption scheme: Ahmed El-Yahyaoui and Mohamed Dafir Ech-Chrif El Kettani, A Verifiable Fully Homomorphic Encryption Scheme for Cloud Computing Security (April 2018, at ...
0
votes
0answers
36 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
86 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
221 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
38 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
113 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
65 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
141 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
139 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
78 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 ...
3
votes
1answer
62 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 ...