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.

0
votes
1answer
36 views

Are there any classical proven secure cryptographic algorithms other than OTP? [duplicate]

Boiled down to the core as I understand it: A cryptographic algorithm has provable security if it's unbreakable, even if an adversary has unlimited computational power / time. If my understanding ...
10
votes
2answers
90 views

Are interactive proofs more secure their non-interactive counterpart?

Given an interactive zk proof, if we use fiat-shamir to make it nizk proof, does the proof become less secure? Are there any new attack vectors that get introduced? Is there any reason to use the ...
1
vote
1answer
56 views

Are oracles needed in security proofs to prove that one problem is equivalent to the other?

I have seen a few security proofs where they show that solving one problem is equivalent to solving the other, via use of an oracle. For example, when proving that problem A is equivalent to problem ...
1
vote
1answer
38 views

Why ``adversary'' and ``challenger'' and what are typical roles of those?

I'm confused with words adversary and challenger, that are used in proof of security of some cryptosystems. For example, adversary and challenger appear in the formal definitions of IND-CPA, IND-CCA, ...
2
votes
1answer
45 views

What does “simulatable” mean in security proofs?

I am reading a security proof in a paper as follows. Regarding the data confidentiality of users, all related public transcripts are simply the ciphertexts $\mathcal{C}_1,\ldots,\mathcal{C}_n$. The ...
2
votes
2answers
103 views

What is the difference between the adversary and the algorithm?

I recently saw a sketch relating to provable security in a book, regarding the amount of time it takes to factor N where N = pq and p,q are primes. It says that "There is a trivial algorithm which ...
0
votes
0answers
44 views

Reduction to security of proof system for proving knowledge

I want to prove security of my system by reduction to the security of an underlying non-interactive proof system for proving knowledge. I know a game that captures the desired security property of my ...
0
votes
1answer
74 views

Can machine learning/AI lower the security existing cryptographic protocols similar to quantum computers? [duplicate]

Initial thinking would be not unless the protocol revealed sensitive local information that could then be analysed by an ML algorithm and applied globally. local meaning I see messages from Alice and ...
0
votes
1answer
42 views

Is the following non-interactive zero-knowledge set membership protocol provable secure?

Given the following Zero-knowledge set-membership protocol https://infoscience.epfl.ch/record/128718/files/CCS08.pdf]. That is given in the following steps (Please refer to page 9). The Verifier -...
6
votes
1answer
147 views

Are DSA and ECDSA provably secure assuming DL security?

Is there proof that the DSA construction, also used by ECDSA, is secure assuming that discrete logarithms in the relevant group representation are difficult?
57
votes
6answers
8k views

Soft question: Examples where lack of mathematical rigour cause security breaches?

Cryptographic tools can often become adopted even when their security proofs lack mathematical rigour - or altogether missing. Are there famous cases of security breaches in the industry, where the ...
1
vote
2answers
43 views

What is the Knowledge Of Secret Key Assumption (KOSK)

From what I've read it seems to be where an entity must prove that they own the secret key. Which is done by signing a message M using said secret key. Is this ...
2
votes
1answer
48 views

How does the random oracle model simplify proofs versus using the standard model?

If I use the standard model, then the proof must rely on mathematical assumptions. Will this security proof, generally be longer/more complex? Is there an example where the random oracle has been ...
8
votes
4answers
198 views

Signature security proof in the Random Oracle model

As a study case, I consider the BLS signature scheme, but the following question is relevant in the general context of security proofs in the Random Oracle model. Let us briefly recall BLS signature ...
2
votes
1answer
30 views

Variants of universal composability in security proofs

Universal composability (UC) framework seems to be a powerful framework for proving security of protocols, which guarantees security even in the presence of concurrent composition. Though, I see there ...
8
votes
3answers
611 views

Are there any symmetric cryptosystems based on computational complexity assumptions?

Are there any symmetric cryptosystems which are provably secure in the sense that there exists a reduction from their security to the hardness of some underlying hard problem such as integer ...
2
votes
2answers
195 views

What is the relation between computational security and provable security?

I read the book "Introduction modern cryptography". It gives the notion of computational security of private-key encryption at first which comes from perfect security and statistical security. Let $...
1
vote
2answers
80 views

modified substitution permutation networks

I have a model of substitution permutation networks, modified as follows: instead of iterating $n$ times a round(each of which is composed of the key mixing phase, substitution S-BOX) and ...
1
vote
0answers
26 views

What's the main difference between the non-uniform probabilistic polynomial-time adversary and the probabilistic polynomial-time adversary? [duplicate]

When I am reading some secure computing papers, the authors always assumed that there exist some adversaries, such as non-uniform adversary and the probabilistic polynomial-time adversary. So my ...
1
vote
0answers
41 views

Maximum security strength in bits of ISAAC cipher?

Wikipedia claims key length can be very big in this cipher, so I assume it can offer a million bits of security provided entropy of key is the same? Of course I can SHA-256 hash the key to allow any ...
1
vote
1answer
159 views

Simulation based proofs, what am I missing?

In the example given by in the top answer of Simulation based proofs: Simple examples claims that this is insecure the semi-honest, and I need assistance in where I am failing to reason why that this ...
1
vote
0answers
29 views

Malicious OT from 'Efficient Secure Two Party Protocols' — defining the simulators

I am looking at Protocol 7.5.1 in Hazay and Lindell's Efficient Secure Two Party Protocols, it can found here (p 201). A similar protocol is proven secure in Section 7.4 (p190) and the proof is ...
2
votes
0answers
28 views

Leftover hash lemma-like without lossy functions

In short: Are lossy function the only way to prove security using leftover hash lemma for computationally secure protocols? Longer: I recently discovered/understood the leftover hash lemma, that ...
6
votes
2answers
180 views

Understanding forking lemma and oracle replay attack

Many signature schemes use forking lemma to prove security, like scheme in here.In short, that goes through a reduction technique which called oracle-replay attack to solve the difficult algorithmic ...
4
votes
0answers
76 views

About Cocks IBE

Why doesn't Cocks IBE use the hash function H from ID space to quadratic residue set $\mathbb{QR}_N$ in $\mathbb{Z}/N\mathbb{Z}$ to reduce the ciphertext expansion by half? I think it is also IND-ID-...
1
vote
0answers
36 views

Prove that Alice’s solution x is equal to Bob’s plaintext m

The answer to the second part of this question exists already. However, I need help understanding how the first part of the question is solved. I have a feeling that it must have something to do with ...
0
votes
1answer
39 views

LWE: does using only a small subspace of the plaintext space influence the security of the encryption scheme?

Regarding LWE schemes where the encryption is performed this way: for $m \in \mathbb{Z}_t$, compute $c = LWE_{\mathbf{s}}^{t/q}(m) = \{ \mathbf{a}, \mathbf{a \cdot s} + m\cdot q/t + e\} \in \mathbb{Z}...
2
votes
2answers
96 views

Is OTP with homomorphic encryption trivial?

If my key size is as large as the data I'm encoding, is it trivial to devise a theoretically secure homomorphic encryption scheme for integers (or else any finite/infinite group with order) that ...
1
vote
0answers
29 views

Proof that secret sharing based scheme is CPA secure as long as one of the scheme is CPA secure

I want to construct a CPA-secure schemes using two given schemes $\prod_1$ and $\prod_2$ if only one of them is CPA secure. Taking suggestions from this answer, I am able construct a scheme as ...
1
vote
1answer
64 views

Why is the security level defined by $\log _{2} \inf \{ t_{i}/\varepsilon_{i} \mid i \in I \}$

In public-key cryptography, the security level indicates the strength of an adversary in breaking a scheme or solving a problem, which can be seen as the time cost of breaking a scheme or solving a ...
1
vote
1answer
186 views

What is purpose of a simulator and extractor in zero knowledge proof protocols?

I am new to zero knowledge proofs. I read the paper Efficient Protocols for Set Membership and Range Proofs by Jan Camenisch, Rafik Chaabouni and Abhi Shelat. The author proposed a zero knowledge ...
5
votes
0answers
51 views

Is there a standard definition of non-malleability for the encryption schemes?

I find some different definitions of non-malleability for the encryption schemes. They may be equivalent, but I am not sure which one is better or if there is a standard definition. I give two ...
16
votes
4answers
3k views

Are encryption algorithms with fixed-point free permutations inherently flawed?

Flaw in Enigma One of the Enigma machine's flaw was the derangement (fixed-point free permutation) of the produced ciphertext, or simply put: No plaintext-letter can be enciphered to itself. See this ...
1
vote
1answer
83 views

Show that CPA-security implies security against plaintext recovery

Consider the following experiment: $k = Gen(1^n)$ $m \stackrel{u}{\in} \{0,1\}^{l(n)}$ $c = Enc_k(m)$ $m' = B(1^n,c)$ Define the winning event as $m' = m$. I would like to show that if the ...
1
vote
1answer
65 views

Proof of ignorance to prevent “double-spend”?

Suppose I have some knowledge that I want to transfer securely from Alice's computer to Bob's computer, and prove that future breaches to Alice's computer will not reveal that information to someone ...
0
votes
1answer
76 views

The meaning of formal and semi-formal in cryptography

The question is about "formal" analysis, proofs, etc... What is a correct definition of a formal proof, or a formal analysis? Is there a good way and a bad way to formally prove something. What is the ...
3
votes
0answers
42 views

Equivalents of Yao's Xor lemma to rounds, or other hardness amplification methods?

Simple question: I just learn the existence of the great Yao's Xor lemma (see a quick sum-up at the end of this post). I'd like to use a similar argument, but instead of a simple function, I've a two ...
1
vote
1answer
43 views

Fairness in Multi party computation

Why for achieving the fairness, 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 number of the involved parties). How ...
0
votes
0answers
22 views

Is my reasoning sound in the included scenario?

There is a package that contains a device, the device is activated/deactivated over a short range radio signal - it's function is to detect any unauthorised tampering of the package during the time it ...
3
votes
1answer
132 views

Security of Fast Two-Party ECDSA Signing

The paper "Fast Secure Two-Party ECDSA Signing" by Yehuda Lindell describes a system in which two parties, $P_1$ (with 1/2 of a share of a long-term ECDSA signing key $x_1$) and $P_2$ (with the other ...
2
votes
1answer
73 views

For two LUKS volumes made with the same password, can stealing the encryption key from one volume allow access to the other?

A running computer has two LUKS volumes that were made with the same password. One volume is open (key is in RAM), the other is closed. If the running computer is stolen, is the closed volume safe? ...
0
votes
1answer
101 views

Is there distinguisher?

Are these distributions computationally indistinguishable ? $f:\{0,1\}^n \to \{0,1\}^n $ $\{X_n\}_{n\in N}$ : uniform distribution for function which $f(0^n)=0^n$ and for other function probability ...
3
votes
1answer
77 views

Relationship between the (provable) security and the size of the plaintext space

Motivation: An encryption scheme is used to encrypt the message which belongs to the plaintext space. The scheme designer does not know what kinds of message is valid (i.e. what the plaintext space is)...
2
votes
2answers
50 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 ...
4
votes
1answer
784 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
58 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
2answers
126 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
69 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[\...
6
votes
1answer
459 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
87 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 ...