Questions tagged [security-definition]
Questions about formal definitions of "security" for various cryptographic schemes (e.g. perfect secrecy, semantic security, ciphertext indistinguishability, etc.)
288
questions
1
vote
0
answers
214
views
Privacy-Preserving Protocols and Proofs of Security
While dabbling in privacy-preserving protocols (mainly using Semi-Homomorphic Encryption) and coming up with miscellaneous ideas for comparison tests or other similar primitives, based on obfuscation ...
- 375
5
votes
5
answers
2k
views
Effective security of block cipher – equal the key size, or half the key size?
The Wikipedia “Key Size” article states:
The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force), but it can be smaller. … … … Most symmetric-...
- 17.8k
8
votes
1
answer
3k
views
An unpredictable PRG is secure (Theorem Yao'82)
in the Mr Boneh's online course is stated the following theorem:
Let $G:K \to \{0,1\}^n$ be a PRG.
“Thm”: if $\forall i \in \{0, … ,n-1\}$ the PRG $G$ is unpredictable at pos. $i$,
then $G$ ...
- 3,922
4
votes
1
answer
950
views
Indistinguishable encryptions in the presence of an eavesdropper equivalence
I'm trying to prove that definition 5 and definition 6 in this document are equivalent. This is what I've done at the moment: Asume that the scheme has Indistinguishable encryptions in the presence of ...
- 3,922
9
votes
1
answer
7k
views
What does it mean for an adversary to run in PPT?
I've been reading this question where a detailed description of mine is given, I've understood that a polynomial-time adversary is an adversary for which the only feasible strategy are those that take ...
- 3,922
1
vote
1
answer
308
views
What does it mean that a protocol realizes "strong mutual authentication"?
What does it mean that a protocol realizes "strong mutual authentication"? And what does it mean that a protocol realizes "weak mutual authentication"? Can you define them formally ...
- 183
2
votes
1
answer
1k
views
Security of permutation cipher
I would like to understand how secure the permutation cipher is.
I would specifically like to understand the following concrete setup: If the alphabet is $L = \{0,1,\dots , 255\}$ and $\sigma_1, \...
- 1,154
5
votes
2
answers
3k
views
Block Ciphers and (Non-)Generic Attacks
I am currently reading through Cryptography Engineering and came across this definition of block cipher security:
Definition 2 An attack on a block cipher is a non-generic method of
...
- 193
4
votes
1
answer
6k
views
Hash functions with or without secret key
The classical definition of hash functions (found in books) are OK, but when studying a little more there is a lot of notions that seem ambiguous (contradictory) to me :
Sometimes we have hash ...
- 2,837
13
votes
1
answer
5k
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 ...
- 2,837
3
votes
2
answers
2k
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, ...
- 2,837
1
vote
2
answers
587
views
How can I simulate and measure brute force hacking using RSA?
I want to implement brute force hacking using RSA. How can I simulate and measure time duration? What software (or software-based simulator) would be needed?
- 11
3
votes
0
answers
392
views
On the Definition of a PRG and a CSPRG
I've been looking at the definition of a PRG, here. This is a broader notion than a cryptographically secure PRG ("CSPRG"), which is described here. I am realizing that I am very confused by this ...
- 193
6
votes
1
answer
2k
views
Public-Key Deterministic Encryption : Why does not provide perfect security?
I've got a question about an assignment . The question is "Why a Public-Key Deterministic Encryption Algorithm does not provide perfect security ?" . I suppose it means according to Shannon .
Any ...
- 163
2
votes
1
answer
18k
views
How can i predict the next number of a long sequence of seemingly random numbers? [closed]
How can I accurately predict the next random number between 1 and 999, given past results. I have no knowledge of the PRNG or algorithm used.
How can I predict the next number of a long sequence of ...
- 21
-1
votes
3
answers
273
views
How to judge if my work is meaningful in cryptography? [closed]
Suppose I have generated a new cryptographical result - for example a new cryptographical primitive, or a cryptanalytic attack. How can I find out whether this result is meaningful (significant)?
If ...
- 1,282
1
vote
2
answers
376
views
What is the difference between PPE and SPPE?
Can somebody explain, in simple terms, the difference between Pseudo Random Permutation Ensemble and Super Pseudo Random Permutation Ensemble?
- 6,134
3
votes
1
answer
442
views
The exact definition of a symmetric encryption
I have doubts for the definition of the decryption algorithm $D(.)$. I think I've already seen that the decryption returns a plaintext $M$ on input the key $K$ and $C=E_K(M)$.
I have also seen that ...
- 2,837
3
votes
1
answer
743
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, ...
- 2,695
11
votes
2
answers
1k
views
Definition of a CSPRNG
I am interested in what conditions are necessary and sufficient to define a cryptographically secure pseudo-random number generator (CSPRNG).
Wikipedia lists two defining characteristics:
It ...
- 213
2
votes
1
answer
1k
views
Definition of cryptographic advantage vs. probability of success
In game-based security definitions, like for example the one defining IND-CPA security, a given cryptosystem is said to be secure if any probabilistic polynomial time adversary has only a negligible ...
- 1,346
16
votes
6
answers
3k
views
How exactly is "true randomness" defined in the realms of cryptography?
Especially in relation to stream ciphers, I frequently read about (sometimes theoretical, sometimes practical) attacks that are able to "distinguish a ciphertext from a truly random stream".
What's ...
- 17.8k
3
votes
1
answer
7k
views
When NIST disallows the use of 1024-bit keys, what effect will that have on SHA-3 (with max. 512 bits)?
Quoting the article Gone in 60 Months or Less:
The National Institute of Standards and Technology (NIST) has disallowed the use of 1024-bit keys after 31 December 2013 because they are insecure. ...
- 17.8k
10
votes
1
answer
6k
views
Proof that IND$-CPA implies IND-CPA?
I've read a few papers recently that used a notion of security called "indistinguishability from random bits/strings" under chosen plaintext attack, also called IND\$-CPA. See e.g. http://pdf.aminer....
- 4,405
21
votes
2
answers
6k
views
Why is AES considered to be secure?
The security of RSA is based on the integer factorization problem, which is a very well defined and understood mathematical problem. This problem must be solved in order to fundamentally break RSA.
...
- 313
20
votes
2
answers
6k
views
What stops the Multiply-With-Carry RNG from being a Cryptographically Secure PRNG?
Despite the fact that Marsaglia's MWC PRNG (multiply-with-carry random number generator) is considered to be "the mother of all RNGs", it does not seem to be considered to be a CSPRNG (...
- 17.8k
2
votes
1
answer
272
views
a possibly stronger type of attack on identity-based encryption
What is known about the security of identity-based encryption schemes against attacks that involve seeing multiple ciphertexts and then receiving the private keys corresponding to some of those ...
user991
2
votes
0
answers
697
views
Ideal system for an encryption scheme
What is the ideal system for an encryption scheme? For a pseudorandom permutation the ideal one is a random permutation, for a pseudorandom function the ideal one is a random function. For an ...
- 2,837
4
votes
1
answer
1k
views
Formal definition of (perfect) forward security/secrecy
In recent weeks the concept of (perfect) forward security/secrecy has
been mentioned a lot, primarily in the context of the shocking
revelations about NSA eavesdropping. As far as I'm aware, this ...
- 215
5
votes
1
answer
2k
views
Signature with appendix
I see sometimes signatures schemes with appendix. This is about signatures schemes in which the message is needed in the verification algorithm, that is, the ouput of the signature algorithm is of the ...
- 2,837
3
votes
2
answers
605
views
Differential privacy definition
Differential privacy defines "privacy" of a mechanism $A$ as the "closeness" of the two distribution $Pr[A(D) \in S]$ and $Pr[A(D') \in S]$ where $D,D'$ differ in one element. And the distance between ...
- 371
7
votes
1
answer
2k
views
Proofs of security methodologies
I'm looking for course material on the subject of proofs, reductions, and games, as used to prove cryptographic schemes secure. What are the methodologies? What are the preferred ones? In what cases ...
- 2,837
5
votes
1
answer
632
views
What does "adaptively secure" mean?
In a paper it says "In the generic group model, the PRF is adaptively secure for inputs of $\mathbb{Z}_q^n$". Maybe a stupid question, but what does "adaptively secure" mean exactly?
- 579
3
votes
2
answers
800
views
Why is a non fixed-length encryption scheme worse than a fixed-length one?
I have the following definition (highlights by me):
An (efficient secret-key) encryption scheme $(Gen,Enc,Dec)$, where $Gen$ and $Enc$ are PPT algorithms and $Dec$ is a Deterministic Polytime ...
4
votes
2
answers
4k
views
Perfect security definitions
In my notes, there are 2 definitions of perfect security:
"For $M \in \{0,1\}^m$, define the distribution $D_M$ on strings as follows: to choose a random member of $D_M$, choose a random $K \in \...
- 141
6
votes
1
answer
868
views
Exact mathematical definition of simulation based security?
I've been trying to understand cryptographic protocols and how to define their security. The problem is that while I can understand what the intuitive definition says, I have trouble understanding how ...
- 61
39
votes
8
answers
54k
views
Simply put, what does “perfect secrecy” mean?
I would like to ask for a clear (but maybe not so deep) explanation of what the term "perfect secrecy" means.
As far as I have researched and understood, it has to do with probabilities of assuming ...
- 541
41
votes
3
answers
49k
views
What are preimage resistance and collision resistance, and how can the lack thereof be exploited?
What is "preimage resistance", and how can the lack thereof be exploited?
How is this different from collision resistance, and are there any known preimage attacks that would be considered feasible?
- 1,505