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
1
vote
1answer
30 views

How does the security parameter within a digital locker help prove that it unlocked correctly?

I refer to Canetti et all, "Reusable Fuzzy Extractors for Low-Entropy Distributions", available here. Paraphrasing the relevant part from §3:- The locking algorithm $lock(key,val)$ outputs ...
-1
votes
1answer
83 views

On the security definitions

What are the differences between: perfect security information-theoretic security semantic security indistinguishability Are there any other definitions which are closely related? Do these security ...
3
votes
0answers
37 views

Are there any more ways to validate a security proof except peer review?

Are there any ways better than peer review to validate a security proof? Are there any ways to make your security proof easier to validate; using a simulator based proof instead of a game based proof? ...
0
votes
0answers
29 views

Do simulator based proofs still rely on the ROM?

I have seen many game based proofs using the ROM, do simulator based proofs require it? Is it possible to do a simulator based proof for every game based proof? For context: What are the differences ...
1
vote
0answers
19 views

Shamir Secret Sharing: Using $a_0 \ldots a_k$ to store secret? [duplicate]

Let's assume I have a truly random secret $s$ that is 256 bits long, and I want to use SSS with e.g. $(k=4,n=8)$. The normal approach is to set $a_0=s$ and choose $a_1 \ldots a_{k-1}$ randomly, ...
0
votes
0answers
42 views

Security analysis using Statistics

I have a security protocol, there are total z number of nodes in the protocol and a group of n random nodes is made each time, the attacker nodes can break the protocol if the for a particular group ...
1
vote
1answer
17 views

In an encryption scheme, why can we say that the Encryption and Decryption are PPAs?

In cryptography, a reasonable computational complexity definition for an encryption scheme, is 3 algorithms, (Generate, Encrypt, Decrypt) where encrypt and decrypt can be probabilistic polynomial ...
1
vote
1answer
71 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
119 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
67 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 ...
2
votes
1answer
64 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
61 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
113 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 ...
1
vote
0answers
121 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
76 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
52 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
160 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?
59
votes
6answers
9k 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
55 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
64 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 ...
9
votes
4answers
217 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
40 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
614 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 ...
4
votes
2answers
225 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
83 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
50 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
249 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
30 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
29 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
187 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
78 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
37 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
42 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
101 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
31 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
65 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
237 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
54 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
84 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
70 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
77 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
44 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
45 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
24 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
154 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
77 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
102 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
78 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)...