Questions tagged [cr.crypto-security]

Theoretical aspects of cryptography and information security.

Filter by
Sorted by
Tagged with
1
vote
3answers
692 views

Simple question about pseudorandom generator

I am stuck on the following question related to pseudorandom generator and any help would be appreciated. Let $G:\{0,1\}^k \to \{0,1\}^{k+1}$ be a pseudorandom generator. Define $G':\{0,1\}^{2k}...
13
votes
1answer
543 views

What languages have been successfully cryptographically trapdoored?

An observation associated with asymmetric cryptography is that some functions are (believed to be) easy to perform in one direction but difficult to invert. Furthermore, if there exists some 'trapdoor'...
3
votes
1answer
530 views

Collision Attacks, Message Digests and a Possible solution

I've been doing some preliminary research in the area of message digests. Specifically collision attacks of cryptographic hash functions such as MD5 and SHA-1, such as the Postscript example and X.509 ...
0
votes
1answer
251 views

Help needed on method to use for anomaly detection [closed]

I think people here could guide me in solving a problem related to anomaly detection. The term anomaly here refers to some malware attack. I could get information about the malware infection from ...
3
votes
1answer
443 views

Comparison of Hashing and Modular Exponentiation

Suppose we want to compare two protocols on the computational costs. One of the protocols is designed using random oracle model (we call it the first protocol) and the other protocol uses is designed ...
6
votes
1answer
279 views

The Complexity of Advice in Computational Indistinguishability

One of the cornerstones of the modern cryptography is the definition of computational indistinguishability: It is used in definition of cryptosystems, pseudorandom generators, zero-knowledge, etc. ...
5
votes
3answers
590 views

Precise definition for cryptographic protocol?

Is there some precise definition of cryptographic protocol? I'm asking because I have tried a few good books and they don't seem to define it (Douglas Stinson, Wenbo Mao, Trappe/Washington). The ...
2
votes
1answer
189 views

Encrypting or obfuscating transport stream identifiers in SSL-like connections

First, a longish prologue. Assume typical SSL/IKE/SSH-like connections where a Diffie-Hellman exchange is done first to establish session encryption and decryption keys, where those keys are ...
10
votes
2answers
623 views

Motivating Talk on Foundations of Cryptography

This question is in the same vein as inspirational talk for final year high school pupils. My Ph.D. advisor asked me to give an inspirational talk for new M.Sc. students. The subject is foundations of ...
20
votes
4answers
647 views

Is there current research into the implemention of Randomness Extractors?

Has there been research into implementing randomness extractor constructions? It seems that extractor proofs make use of Big-Oh, leaving the possibility for large hidden constants, making ...
9
votes
2answers
695 views

One-Way Permutations without Trapdoor

In Short: Assuming one-way permutations exist, can we construct one that has no trapdoor? More info: A one-way permutation is a permutation $\pi$ which is easy to compute, but hard to invert (see the ...
4
votes
2answers
532 views

Resources on Cryptographic Applications of Expander Graphs

I want to read papers on cryptography like How to Recycle Random Bits or Security Preserving Amplification of Hardness. They use random walks on expander graphs. I need a short introduction to the ...
8
votes
0answers
629 views

A generalisation of one-wayness

$\mathbf{NP}$-complete problems are worst-case hard. Their average-case counterpart are one-way functions. Is there an analogous one-wayness notion for $\mathbf{coNP}$-complete problems? More ...
7
votes
0answers
199 views

Equivocal primitives in practice

To prove a protocol secure in the computational model, one can use game-based approach or the simulation approach (I just assume these two models for simplicity). In the game based approach, the ...
9
votes
2answers
479 views

Forcing an honest behavior

How can you force a party to be honest (obey protocol rules)? I have seen some mechanisms such as commitments, proofs and etc., but they simply do not seem to solve the whole problem. It seems to ...
4
votes
1answer
311 views

Extracting Independent Information About Sequences

Related to this question, but asked in a different way. For the purposes of a text-based implementation of a fuzzy vault, what metrics can we take on Sequences that are isolated such that the set of ...
6
votes
1answer
972 views

NP-Complete Hard-on-Average Problems

This question considers a special class of problems in (NP,P-samplable). The question is: Do there exists a problem $(L,\mu) \in \mbox{(NP,P-samplable)}$ such that: $L$ is $\rm{NP}$-complete, and $L$...
2
votes
1answer
716 views

Subexponential hardness assumption

Edited I want to read more about subexponential hardness assumption, but I didn't find any good survey on this. I just took a look at Heavy-tailed distribution and Some properties of subexponential ...
5
votes
1answer
415 views

Efficient Algorithm for bilinear pairing on ECC

Bilinear Pairing in the elliptic curves is a wonderful mathematical mapping which is usually defined by the map $e:G_{1} \times G_{1} \rightarrow G_2$ for some groups of $G_{1}$ and $G_{2}$. For ...
1
vote
1answer
275 views

Superpolynomial Simulator

One method for proving a protocol secure is through simulation-based models. This simulator uses ideal/real paradigm in which a protocol is secure in the real model if it is proven secure in an ideal ...
3
votes
3answers
1k views

What is mathematical difference between “random” and “unique”?

Once in a while when a question like "how I get good random numbers" is asked the suggested approach is to just generate an UUID. UUID looks like a random number and it is designed in such way that ...
1
vote
1answer
115 views

Is the model in which a protocol is proven secure more important than type of hardness from which the algorithm gains its strength

Question: If I prove a protocol secure in the plain model (i.e., without any prerequisites or setup before running the protocol, setups like a common reference string distributed among all parties) ...
20
votes
2answers
1k views

Why isn't Montgomery modular exponentiation considered for use in quantum factoring?

It is well known that modular exponentiation (the main part of an RSA operation) is computationally expensive, and as far as I understand things the technique of Montgomery modular exponentiation is ...
1
vote
2answers
494 views

When we are using Random Oracle Model

There are protocols which make use of invoking an oracle or submitting queries to an oracle and getting response from that. There are many examples in which oracles are used to define security, like ...
8
votes
1answer
452 views

Using game-based proofs in simulation-based proofs

Simulation-based security provides more natural and more powerful definition of security than game-based security. I have seen the simulation based approaches use the game-based proofs in-part to ...
3
votes
0answers
186 views

Simulator Efficiency versus Algorithm Efficiency

I have a question about the simulator efficiency. I am reading a group key exchange protocol which is UC-Secure (the security is proven on universal composability framework of Canetti). The proof uses ...
1
vote
2answers
731 views

Resources on Jablon's Protocol

Are there any good resources (descriptions, explanations, examples) regarding Jablon's protocol for password authentication using multiple servers, aside from this paper?
22
votes
6answers
769 views

Curriculum: Logical/Formal Methods in Security

At present I teach a small course (Four two hour lectures at the Masters level) on Logical Methods in Security, though the title Formal Methods in Security might be more apt. It covers briefly the ...
11
votes
2answers
449 views

straight-line simulatability

Does any body know any good reference for meaning of straight-line simulatability? I am currently deep into Universal Composability (UC) framework of Canetti but I can't find any good reference for ...
5
votes
2answers
244 views

Hardness of approximation assuming the existence of one-way functions

This question is inspired by a question posed by Shiva Kintali, Hardness of approximation assuming NP != coNP . Multiplication of two prime numbers of equal size is strong candidate for one-way ...
22
votes
2answers
2k views

Can a fully homomorphic encryption be used for oblivious code execution?

After reading this answer a while ago, I took an interest in fully homomorphic encryption. After reading the introduction of Gentry's thesis, I started wondering if his encryption scheme could be used ...
16
votes
5answers
923 views

Do “One Way Functions” have any applications outside crypto ?

A function $f \colon \{0, 1\}^* \to \{0, 1\}^*$ is one-way if $f$ can be computed by a polynomial time algorithm, but for every randomized polynomial time algorithm $A$, $\Pr[f(A(f(x))) = f(x)] < ...
10
votes
1answer
238 views

Dependent corrections in measurement-based Universal Blind Quantum Computation

In Universal Blind Quantum Computation the autors describe a measurement-based protocol which allows an almost classical user to perform arbitrary computations on a quantum server without revealing ...
16
votes
2answers
1k views

Does bit commitment yield oblivious transfer in the information-theoretic security model?

Suppose you have two arbitrarily powerful participants who don't trust each other. They have access to bit commitment (e.g., sealed envelopes containing data that one player can hand to the other but ...
10
votes
1answer
474 views

Finite One-Way Permutation with Infinite Domain

Let $\pi \colon \{0,1\}^* \to \{0,1\}^*$ be a permutation. Note that while $\pi$ acts on an infinite domain, its description might be finite. By description, I mean a program that describes $\pi$'s ...
3
votes
2answers
1k views

An explanation of Whirlpool C implementation - or the general algorithm

Note: Question originally asked on StackOverflow - was directed here Anyone got a tutorial on the designers concept implementation of Whirlpool in C, or the Whirlpool algorithm in general? I find the ...
12
votes
3answers
3k views

How can DES have 6x4 S-Boxes and still be reversible?

Wouldn't data be lost when mapping 6-bit values to 4-bit values in DES's S-Boxes? If so, how can we reverse it so the correct output appears?
7
votes
3answers
468 views

Creating HMAC keys using a fixed prefix and a random string

In a system that uses HMAC for a number of different applications, it is important to use different keys for different applications. Suppose: there is just a single random string available (50 bytes ...
16
votes
1answer
1k views

Where's the Flaw in Blum-Feldman-Micali's Method

Blum, Micali, and Feldman (BFM) put forward a new (cryptographic) model, in which all parties (honest or adversarial) have access to some string. The string is assumed to be selected according to some ...
14
votes
1answer
316 views

Generating Graphs with Trivial Automorphisms

I'm revising some cryptographic model. To show its inadequacy, I've devised a contrived protocol based on graph isomorphism. It is "commonplace" (yet controversial!) to assume the existence of BPP ...
14
votes
3answers
588 views

Associative hash mixing

Consider the lowly singly-linked list in a purely functional setting. Its praises have been sung from the mountain tops and will continue to be sung. Here I will address one among its many strengths ...
10
votes
1answer
254 views

Worlds Relative to Which “Invulnerable Generators” Do Not Exist

Invulnerable generators are defined as follows: Let $R$ be an NP relation, and $M$ be a machine which accepts $L(R)$. Informally, a program is an invulnerable generator if, on input $1^n$, it ...
6
votes
2answers
324 views

Confidentiality of “partial private keys” in certificateless public key crypto

I'm looking at alternatives to PKI and I'm having trouble understanding exactly how certificateless public key algorithms (e.g. Al-Riyami and Paterson, Liu et al) work in practice. It seems like the "...
13
votes
2answers
434 views

Exhausting Simulator of Zero-Knowledge Protocols in the Random Oracle Model

In a paper titled "On Deniability in the Common Reference String and Random Oracle Model," Rafael Pass writes: We note that when proving security according to the standard zero-knowledge definition ...
14
votes
3answers
618 views

Hardness Guarantees for AES

Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring. I wonder whether such kind of provable security exists for ...
12
votes
3answers
3k views

What are some examples of secret sharing schemes actually being used in real-world applications?

The concept of a secret sharing scheme is often attributed to Shamir (A. Shamir, How to share a secret, Comm. ACM, 22 (1979), pp. 612-613.) and Blakey (G. R. Blakey, Safeguarding cryptographic keys, ...
2
votes
0answers
267 views

Some problems involving polynomials of public and private variables over GF(2).

Suppose there are a set of low degree (less than some degree $z$) polynomials $P_0, P_1, ..., P_k$ each of which is defined over two types of variables, red variables ${v_r}_0, {v_r}_1, ..., {v_r}_n$ ...
27
votes
3answers
14k views

What is the difference between a second preimage attack and a collision attack?

Wikipedia defines a second preimage attack as: given a fixed message m1, find a different message m2 such that hash(m2) = hash(m1). Wikipedia defines a collision attack as: find two arbitrary ...
21
votes
6answers
3k views

Difference between theory and practice of security and cryptography?

What interesting differences are there between theory and practice of security and cryptography? Most interesting will of course be examples that suggest new avenues for theoretical research based on ...
11
votes
7answers
2k views

How does Theoretical Computer Science relate to security?

When I think of software that is insecure I think that it is "too useful" and can be abused by an attacker. So in a sense securing software is the process of making software less useful. In ...