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

0
votes
0answers
19 views

Is perfect zero knowledge sequentially composable without auxiliary input? [on hold]

It is known that plain and computational zero knowledge proof systems are not sequentially composable without auxiliary input (see for example ...
4
votes
2answers
89 views

Why is it important to solve a problem in Polynomial time, In cryptography?

I have just started to learn Cryptography. I am trying to learn "Merkle-Hellman Knapsack Cryptosystem". So, right at the beginning of the discussion, a question came in my mind: Why is it important ...
3
votes
1answer
27 views

What are the examples of the easily computable “wild” permutations?

I am looking for the function $y=f(x)$ that would map the integer interval $[0,n)$ into itself $[0,n)$. The function must be bijective, so it is a permutation of n elements. It should "randomize" the ...
-3
votes
1answer
49 views

A question on RSA

Why were primes which are $1$ modulo $4$ considered to be weak for use in RSA cryptography (http://en.wikipedia.org/wiki/Blum_integer)? Was there a time it was considered there could be an efficient ...
0
votes
1answer
24 views

RSA Decryption from Simple Public Key Values

I'm a little stuck trying to figure out how to decrypt some messages and could use some hints as to what I may be doing wrong. I was given a series of integer values that make up my cipher text. Here ...
0
votes
1answer
59 views

What's the complexity of the Bombe?

Now my knowledge of this comes through watching The Imitation Game, a glance of a wiki article, and a couple of computerphile videos, so forgive me if it's obvious. While watching the Imitation Game, ...
4
votes
1answer
32 views

Computing modular exponent given order

I want to compute $g^{mn}$ mod $n^2$ where $n=pq$ and I know that $g$ has order $kn$ mod $n^2$ where $m<k$. Is there any clever way of doing it utilizing the order? I have tried other methods of ...
1
vote
1answer
33 views

Hash values that are impossible to reach

I was just curious as to if there are (or could by) any hash values that are impossible to compute due to the implementation of the algorithm. For example, SHA-256 produces a value that is 256-bits ...
1
vote
2answers
66 views

What is the complexity of finding the two prime numbers a composite number (used in RSA Protocol) is made of?

I am aware that as the number increases in Digits the process of locating the two prime numbers that when multiplied produce the given number is increased as well. I also know that is it somewhat ...
2
votes
1answer
70 views

Is a very long plain text password harder to crack than a short complicated password? [closed]

Is it true that a password consisting of the alphabet, even of common known names is much harder to find for a computer program than a short password, even though it uses numbers and other characters? ...
0
votes
1answer
114 views

How to explain the steps in the implementation of hashing functions like SHA1

I was reading the article about the SHA1 hashing function (I know it is not secure anymore) and I've found a pseudocode implementation on Wikipedia. I can see that there are a lot of mathematical ...
10
votes
2answers
91 views

How does an operating system create entropy for random seeds?

On Linux, the files /dev/random and /dev/urandom files are the blocking and non-blocking (respectively) sources of pseudo-random ...
4
votes
1answer
53 views

Partially homomorphic encryption (on addition modulo N) not based on prime factorization

A cryptographic function is homomorphic on some operation if that operation is preserved in the encrypted data. Such a function is homomorphic on addition modulo if the following holds for some ...
3
votes
1answer
82 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
42 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
118 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
35 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
19 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
110 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
143 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
59 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
233 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
169 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
64 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
56 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
58 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
90 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
54 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
66 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
141 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
87 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 ...
6
votes
1answer
71 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 ...
6
votes
2answers
266 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
43 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
81 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
418 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
115 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
158 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
1k 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
3k 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 ...
6
votes
1answer
308 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
367 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
150 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
251 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
504 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
137 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
281 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
604 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
87 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
805 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 ...