Questions about the construction and analysis of protocols and algorithms for secure computation and communication (including authentication, integrity, and privacy aspects).

learn more… | top users | synonyms

3
votes
1answer
57 views

What happens to quantum algorithms such as BB84 if P=NP

Under the hypothesis that P=NP, many cryptographic protocols are no longer secure (i.e. attacks are feasible). The BB84 algorithm (http://en.wikipedia.org/wiki/BB84) is based on the idea that by ...
3
votes
1answer
24 views

Iterative Byzantine consensus in directed graphs with unbounded malicious nodes

I've found many articles describing iterative procedures to reach Byzantine agreement on a graph (for instance http://www.crhc.illinois.edu/wireless/papers/icdcn14-vaidya.pdf or ...
5
votes
1answer
74 views

What is the complete version of the paper: “How to Generate and Exchange Secrets (extended abstract)” by Andrew Yao?

I've found numerous places that claim that the paper "How to Generate and Exchange Secrets" by Andrew Yao introduces garbled circuits as a solution to the secure multiparty computation problem. ...
0
votes
1answer
20 views

Finding the private key in BB84 quantum cryptography

I'm trying to teach myself Quantum Cryptography for an exam I have soon, and I came across the following question: To establish a common key, Alice and Bob analyse a sequence of 20 photon pairs. ...
2
votes
0answers
9 views

Proof of correctness of the XL-algorithm for polynomial systems

Section 12.4 of G.V. Bard's Algebraic Cryptanalysis discusses the XL-algorithm (first reported by N.T. Courtois and A. Shamir in Efficient algorithms for solving overdefined systems of multivariate ...
1
vote
1answer
88 views

RSA encryption why does ed=1?

So I fully understand the how the RSA algorithm works, but now I am trying to reason with the formula. I want to know: why the public key e and the private key d in the RSA encryption have to ...
7
votes
1answer
124 views

NP Problems with unique solution

Is there any class of NP problems that have one unique solution? I'm asking that, because when I was studying cryptography I read about the knapsack and I found very interesting the idea.
1
vote
2answers
46 views

In RSA, must $p$ and $q$ have the same number of bits?

Is it necessary to take the same bit size of "p" and "q" in case of RSA algorithm? i had read that bitsize of p and q must be same. BUT after calculating, i found that bit size could be different ...
8
votes
6answers
194 views

Could program verification techniques prevent bugs of the genre of Heartbleed from occurring?

On the matter of the Heartbleed bug, Bruce Schneier wrote in his Crypto-Gram of 15th April: '"Catastrophic" is the right word. On the scale of 1 to 10, this is an 11.' I read several years ago that a ...
5
votes
4answers
136 views

Can all NP-complete cryptosystems be broken if one is broken?

I was just reading something about NP-hard problems and cryptosystems. I was thinking: Every NP-complete problem can be reduced to another and every NP-complete problem has an equivalent (NP-hard) ...
0
votes
1answer
41 views

Finding prime factors of non-random key generator

I have been working on a challenge i found on the internet. It is as follows: You've stumbled onto a significant vulnerability in a commonly used cryptographic library. It turns out that the ...
1
vote
1answer
53 views

Help in understanding exactly how lattices used as one way functions for hashing

(This question is related to homework) I am doing a cryptography course via long distance and we have been given an assignment which is based on lattice-based cryptography. I have spent the majority ...
4
votes
1answer
48 views

If a one-way functions (OWF) exist, then there exits a OWF that is computable in quadratic running time by a padding argument

I believe this question should be extremely easy but I am having a (embarrassing) hard time figuring out why its true if there exist OWF (computable in polynomial time) then there exits a OWF that is ...
0
votes
2answers
76 views

Decrypting transposition ciphers

How do I see if the following ciphertext eaeairtntrnaeemtve is a transposition cipher, using letter frequency? This article suggest how to detect by using letter ...
0
votes
1answer
51 views

Cryptography substitution frequency analysis

I am trying to find the plain text for the following cipher text using a frequency analysis vr pvst yqlp mq nvf But for the letters above this is really ...
3
votes
1answer
60 views

What is a protocol for determining which of two numbers is larger, without sharing those numbers?

Situation: Alice has selected a positive integer $a$, and Bob has selected a positive integer $b$. Alice and Bob want to know whether $a > b$, $a = b$, or $a < b$, but neither wishes to reveal ...
3
votes
2answers
89 views

Perfectly Secure Ciphers known other than the OTP

By Information-Theoretic definitions, the One Time Pad (OTP) is called/was proved to be a Perfectly Secure Cipher. For the sake of completeness, we define OTP: An enc/dec function, $f:\mathcal{P} ...
2
votes
1answer
75 views

Mealy machines to model ciphers [closed]

Similar questions have occurred quite a number of times (1) (2) (3), but I have, say, a specific instance of one. I'm aware of a bunch of applications of finite automata, but would you provide an ...
5
votes
1answer
65 views

Completeness of formal definition of 'hardness on the average'

While reading a cryptography textbook, i find the definition of a function that is hard on the average.(More precisely, it is 'hard on the average but easy with auxiliary input', but i omit latter for ...
5
votes
2answers
197 views

What mathematics can be interesting for these CS areas?

For my CS degree I have had most of the "standard" mathematical background: Calculus: differential, integral, complex numbers Algebra: pretty much the concepts up until fields. Number Theory: XGCD ...
2
votes
1answer
39 views

Which areas in CS will be (or have been) most affected by fully homomorphic cryptography?

I'm in the middle of planning a 5000ish word essay on fully homomorphic cryptography, the current practical implementations and their limitations. Which areas of CS as a subject have been (or will ...
1
vote
1answer
74 views

Doubts on Definition of Indistinguishable Encryption in the Textbook

In the classic crypto textbook "Introduction to Modern Cryptography" by Jonathan Katz and Yehuda Lindell, there is a definition for indistinguishable encryption in the presence of an eavesdropper as ...
11
votes
2answers
234 views

How to practically construct regular expander graphs?

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices. What is the easiest method to do this in practice? Constructing a random d-regular graph, which is ...
3
votes
2answers
95 views

Assumptions of One Way Functions

I try to get the intuition behind the notion of strong one way function and weak one way function by reading the scribe One-Way Functions. Particularly, I am interested in examples and definitions of ...
7
votes
2answers
119 views

How hard is it to solve for $P$ in $A = PBP^{-1}$?

From graph isomorphism, we know that two graphs A and B are isomorphic if there is a permutation matrix P such that $A = P \times B \times P^{-1}$ So, to solve the problem, if two graphs are ...
4
votes
1answer
551 views

Negligible Function in Cryptography

In the field of Cryptography and Computation Complexity there is a notion of negligible function. I have some difficulties in understanding intuition behind this notion. The following are some ...
2
votes
4answers
1k views

A good introductory book on cryptography

Can anyone suggest me some good books on cryptography? I have just starting studying cryptography but I know elementary number theory, abstract algebra and algorithms. Also please mention the ...
5
votes
1answer
204 views

Length-preserving one-way functions

Unfortunately my background in computational complexity is still weak, but I am working on it. As I understand, the question of existence of one-way functions is very important in the field. Assume ...
4
votes
2answers
277 views

If xor-ing a one way function with different input, is it still a one way function?

Suppose $f(x)$ is a one way function. What about $h(x)=f(x_1) \, \oplus \,f(x_2)$, where $x=x_1 || x_2$ and $\lvert x_1 \rvert = \lvert x_2\rvert$? $\oplus$ is exclusive disjunction (xor) $||$ is ...
6
votes
2answers
121 views

Complexity of GF(2) and applications to cryptography

If I have a system of N polynomial equations with N unknowns in GF(2): What are some good methods to solve them? What are some software packages or libraries that implement this? What's the highest ...
6
votes
1answer
173 views

Quadratic residue and integer factoring

I often read that deciding whether or not a number $r$ is a quadratic residue modulo $n$ is an interesting (and hard) problem from number theory (especially if $n$ is not prime). I am looking at the ...
2
votes
2answers
415 views

Collision resistant hash function

A function is $(\varepsilon, t)$-collision resistant if there is no boolean circuit (using "not", "and", "or") of size at most $t$ which outputs a collision with probability at least $\varepsilon$. ...
6
votes
1answer
129 views

Mental poker: proving dealt hand is fair

I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman. Assuming I have a website, (TTP) how can I prove to the ...
3
votes
1answer
211 views

What will i obtain if i apply a xor-ing a one way function and it's input?

I know that a one-way function is informally a function that it's easy to compute but hard to invert. If f(x) is a one way function the function $g(x) = x\oplus f(x)$ is a one-way function? My ...
4
votes
1answer
431 views

How to show composition of one way function is not such?

I was wondering how should I proceed in order to show that the composition of (say) two one-way functions (either weak or strong or both together) is not a one-way function? Specifically: Say $f$ and ...
2
votes
2answers
78 views

Condition in Shamir Secret Sharing Scheme

For Shamir's secret sharing scheme (doi 10.1145/359168.359176), one obtains a random polynomial $q$ of degree at most $n-1$ (over $\mathbb{Z}_p[x]$). The constant coefficient of this polynomial is ...
2
votes
1answer
635 views

One time pad, get plaintext using ciphers encoded with the same key

I'm trying to solve a problem: I have 11 ciphers encoded with the same key. My aim is to decode target cipher. If I do xor C1, C2 (ciphers encoded with the same key) I do get M1 xor M2 (where M1, M2 ...
5
votes
1answer
367 views

In the Miller-Rabin primality test, for a composite number, why are at least $\frac{3}{4}$ of the bases witnesses of compositeness?

The following is an excerpt from the Wikipedia article on the Miller-Rabin primality test: It can be shown that for any odd composite $n$, at least $\frac{3}{4}$ of the bases $a$ are witnesses for ...
2
votes
0answers
33 views

Mersenne twister middle word

In some literature, as well as in Wikipedia, the middle term parameter m of Mersenne twister is called "number of parallel sequences". Why? What is meant here by "parallel sequences"?
3
votes
1answer
416 views

Rigorous proof against pseudo random function

I have the following problem: Define the keyed function F as follows: On input k ∈ {0, 1}$^n$ and x ∈ {0, 1}$^n$ , Fk(x) = k ⊕ x.Rigorously prove that F is not a pseudorandom function. How do I ...
1
vote
2answers
176 views

Collisions of prefixes of MD5 hashes in some fixed interval

I was wondering, if there is an MD5 hash collision in the UNSIGNED MEDIUMINT Range (0 - 16777215). Sadly, I'm unable to run a script to check this myself, due to Memory (RAM) limitations. The answer ...
4
votes
1answer
89 views

LFSR sequence computation

I need to calculate the output of the sequence generated by this shift register but I cannot find anywhere how to do it. Everywhere the results are just given but there is no explanation how to do ...
5
votes
1answer
183 views

A hash function with predicted collisions

As far as I know, the more collision-resistant a hash function is, the better. But is there any way to define a hash function with predicted collisions? In other words, a hash function that collides ...
9
votes
1answer
327 views

Weak hashing function for memorable IPv6 addresses

IPv6 addresses in the form of 862A:7373:3386:BF1F:8D77:D3D2:220F:D7E0 are much harder to memorize or even transcribe than the 4 octets of IPv4. There have been ...
1
vote
1answer
64 views

Are tamper attacks considered side-channel?

Wikipedia defines side-channel attacks as: any attack based on information gained from the physical implementation of a cryptosystem Usually in side channel attacks the implementations leak ...
6
votes
4answers
300 views

After implementing a novel encryption algorithm, how would one go about analyzing its security or get help from others in doing so?

Preface: This question was originally asked on Theoretical Computer Science, and the kind people there referred me to this web site. It is being repeated here in an attempt to find a satisfying ...
8
votes
5answers
212 views

How can encryption involve randomness?

If an encryption algorithm is meant to convert a string to another string which can then be decrypted back to the original, how could this process involve any randomness? Surely it has to be ...
8
votes
3answers
287 views

Key secrecy vs Algorithm secrecy

it's a well known statement that "Cryptographic security must rely on a secret key instead of a secret algorithm." I would like to ask about some details about it. And which are their differences? ...
8
votes
1answer
404 views

Is WPA2 with pre-shared key an example of a zero-knowledge proof?

When setting up an access point and selecting WPA2, one must manually enter a pre-shared key (a password), PSK, into both the AP and the STA. Both parties, AP and STA, must authenticate each other. ...
7
votes
2answers
340 views

What is the difference between classical crypto and post-quantum crypto?

Will there be a need to change the definitions of security if we have quantum computers? What cryptographic constructions will break? Do you know a survey or an article that explains what will be ...