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
38 views

dining metaphysicians problem

Here is a problem vaguely related to the dining philosophers problem. Three metaphysicians go to a restaurant for dinner. When it is time to pay the bill, they decide that they want one of them to pay ...
3
votes
2answers
1k views

Can a public key be used to decrypt a message encrypted by the corresponding private key?

From what I have seen about usage of a pair of public and private keys, the public key is used for encrypting a message, and the private key is used for decrypting the encrypted message. If a message ...
7
votes
2answers
81 views

Zero-knowledge proof: Abstract example

So I was reading about ZKP on wikipedia, the abstract example in summary goes like this: Peggy wants to prove to Victor that she knows the secret to a door inside a cave that connect A and B ...
4
votes
1answer
33 views

Is it possible to derive a deterministic CSPRNG given two functions, at least one of which is a CSPRNG?

Let f and g be two functions with integer range 0..m-1. They may keep state and interact ...
15
votes
2answers
2k views

If P=NP, are there cryptosystems that would require n^2 time to break?

If P does equal NP, will it still be possible do design a cryptosystem where the optimal cryptanalysis algorithm takes, say, the square of the time taken up by the legitimate encryption and decryption ...
2
votes
1answer
54 views

Hash function which is invariant under small changes

I am looking for a hash function which is invariant under small changes. E.g., if I have two strings MyString and MySttring ...
2
votes
2answers
29 views

Monoalphabetic Cipher Key

I am not sure how to get the key for the following Monoalphabetic Cipher question. This is a textbook question and I know the answer, but I juts dont know how they got the key. Question: ...
3
votes
1answer
69 views

Bijective algorithm(s) that can shuffle a range of numbers back and forth

I've spent the last hours trying to come up with an algorithm that shuffles an ordered set of numbers (i.e a simple range of numbers) in a way that I can retrieve from a shuffled value the original ...
14
votes
4answers
2k views

Why did RSA encryption become popular for key exchange?

This is a soft question. I don't know a lot about cryptography or its history, but it seems like a common use for RSA is to do key exchange by encrypting a symmetric key to send a longer message (e.g....
6
votes
1answer
84 views

How do you rank the strings represented by a regular expression?

This question is about the use of 'ranking' of regular languages in applications such as format preserving encryption. I understand format preserving encryption but I don't understand how regular ...
0
votes
0answers
27 views

What are some data mining algoritms used in finance?

I want to test the applicability of homomorphic encryption in the financial domain, as suggested in Can homomorphic encryption be practical ?. Now, I want to know what algorithms are used for ...
5
votes
2answers
67 views

Invertible function that randomizes order

I am looking for an invertible discrete function $f:\{0,1,2,\dots,n-1\} \to \{0,1,2,\dots,n-1\}$ for some given integer $n$. I want $f(0),f(1),\dots,f(n-1)$ to return all the integers in range $[0..n)...
1
vote
1answer
38 views

How broken is LCG in the case of partial output?

Suppose we have a linear congruential generator defined by $X_{n+1} = (a X_n + c) \mod 2^n$ where $a, c, n$ are all known and we would like to determine the initial value $X_0$. However, if we can ...
-1
votes
1answer
31 views

will breaking not used anymore RSA codes in the future affect privacy?

just read and watch some stuff on how RSA works. main idea seems to be if someone steals your communication he cannot decode it anyway. but let's say someone steals it and keeps it along with current ...
1
vote
2answers
85 views

XOR of one-way function

Considering the top answer to the question “If xor-ing a one way function with different input, is it still a one way function?”… The function is no longer one-way. we build a counter example ...
1
vote
1answer
42 views

Is there a zero-knowledge protocol for bit vector agreement?

Suppose Alice knows a secret vector of $N$ bits, say $A=\langle a_1, a_2, \ldots, a_N\rangle$ and Bob similarly knows $B=\langle b_1, b_2, \ldots, b_N\rangle$. Is there a protocol that allows them to ...
0
votes
0answers
25 views

Are there any classes of functions whose definitions can be easily procedurally generated and have implementations easily procedurally checked, but

Are there any classes of functions whose definitions can be easily procedurally generated and have implementations easily procedurally checked, but for which valid implementations are difficult or ...
7
votes
3answers
296 views

1-to-1 cryptographically secure bit shuffling

Given an input item (N bytes), I'm looking for a function that will map this to an output (still N bytes). The function should have the following qualities: It should be 1-to-1 so that all inputs ...
2
votes
2answers
509 views

What if p and q are not distinct in RSA Crypto System? What could go wrong?

In RSA Crypto System we choose p and q such that they are distinct primes. Calculate n=pq and phi=(p-1)(q-1). Then e is chosen for public key (n,e) s.t. gcd(e,phi)=1
24
votes
5answers
4k views

Meaning of: “If factoring large integers is hard, then breaking RSA is hard, is unproven”

I was reading CLRS and is said: If factoring large integers is easy, then breaking the RSA cryptosystem is easy. Which makes sense to me because with the knowledge of $p$ and $q$, it is easy ...
1
vote
1answer
31 views

Issues in RSA setup

Suppose we have public key: $$n= 1015, e= 3$$ and private key: $$d= 635, p= 35, q= 29, \phi(n)= 952$$ For $m = 100$, we have $$c = m^e ~mod~n = 100^3 mod~1015 = 225.$$ To decipher this, let us ...
4
votes
1answer
40 views

One-shot Private Randomness Extractor

Suppose a pair of random variables $(X,Y)\in\mathcal{X}\times \mathcal{Y}$ with joint distribution $P_{XY}$ is given. I am interested in a deterministic mapping $f:\mathcal{Y}\to \{0, 1\}^k,$ for ...
4
votes
1answer
93 views

Do one way function exist?

I was going through Wiki Page List of unsolved Problems in Computer Science There was a Problem which I do not understand Do one-way functions exist ? [Is public-key cryptography possible ?] A<...
5
votes
3answers
83 views

One way recurrence O(N)->O(1)

Imagine we have a random number generator where g(n+1) = f(g(n)), where f is some function (e.g linear recurrence). I'm trying to find a system where it's fast to find many steps in the future ...
7
votes
2answers
73 views

Running an algorithm on data remotely and ensuring answer has not been tampered with

I´ve been thinking about this particular computing/crypto/database problem for years and I just want to know if there are already solutions to it. To be honest I don´t even know what field this ...
4
votes
3answers
604 views

Encrypting a 180-bit plaintext into a 180 bit ciphertext with a 128-bit block cipher

I have a field in my data store which must take exactly 180 bits of information. Some users will choose to make this data encrypted, some won't, so some of those 180 bit fields will be ciphertext some ...
2
votes
1answer
32 views

If a Ptime function loses x bits of data at every call, is it a one way function?

If we have a computational function $f(x)=g(f(x-1)^2)$, where $g(y)$ is a floating point operation, mapped onto a given number of bits say 32 bits (thus leading to loss of a given number of precision ...
4
votes
1answer
81 views

Hardcore Bit proof for discrete log

I am studying Crypto and am trying to understand why discrete log creates is useful for creating a PRG. More specifically, I want to prove via reduction that $B(x)=(x<p/2)$ is a hardcore bit for ...
5
votes
0answers
32 views

Correctness of a zigzag algorithm to find the most similar vector in a bounded integer lattice

I am currently working on an integer lattice problem, called the "most similar vector problem," and wondering if can be solved correctly by a simple "zig-zagging" algorithm. Given a real vector $u \...
0
votes
2answers
27 views

Show that a function is not a PRFs

I am studying cryptography and having some trouble with the PRFs How do I show that $f_{k}(x) =x+k^2$ mod $2^n$ is not a Psuedo Random function? I know that I need to show that the distignuisher can ...
22
votes
3answers
1k views

Given RSA, why do we not know if public-key cryptography is possible?

I was on wikipedia on list of unsolved computer science problems and found this: Is public-key cryptography possible? I thought RSA encryption was a form of public-key cryptography? Why is this a ...
4
votes
2answers
304 views

Can systems that prevent double-spending (e.g. crypto-currencies) be used to attach other unique data?

The Bitcoin-solution can be described as "[...] a solution to the double-spending problem using a peer-to-peer network. (official Bitcoin paper, PDF, abstract, first page). Now I wonder if a similar ...
3
votes
1answer
37 views

“Most Similar Vector Problem” on an Integer Lattice

I am currently working on problem that I think could be expressed as an integer lattice problem, and hoping to find some guidance on this forum. Given $u \in \mathbb{R}^n$ and a bounded integer ...
2
votes
1answer
40 views

About the definition of “differential privacy” in communication complexity

In the context of communication complexity I see a definition of differential privacy which isn't totally clear to me as to why it makes sense. So the two parties $A$ and $B$ draw two strings $X$ ...
2
votes
3answers
283 views

Formula for sufficiently lengthy encryption key?

As you add length to an encryption key, at some point the message becomes impossible to brute-force decrypt. This is because at that point, if you go through all the possible keys, you'll get many ...
3
votes
1answer
281 views

If one-way functions exist are we definitely using them?

I know that if one-way functions exist then there are certain universal one-way functions that exist, but to my knowledge they are too impractical to implement (which is the main reason why they are ...
-1
votes
1answer
56 views

What is the relation between differential-privacy mechanism and entropy?

Why do differential-privacy people care whether or not the noise function saturates the lower bound of Shannon entropy? For example : Laplace distribution that is used to model the noise function ...
3
votes
0answers
54 views

How is Chinese Remainder Theorem used in the proof of correctness for RSA

Question At the very end of (most) proofs of RSA's correctness we have something like $$m^{ed}\equiv m\pmod p$$ $$m^{ed}\equiv m\pmod q$$ Therefore by the Chinese Remainder Theorem (CRT) $$m^{ed}\...
7
votes
1answer
182 views

Is there a continuous hash?

Questions: Can there be a (cryptographically secure) hash that preserves the information topology of $\{0,1\}^{*}$? Can we add an efficiently computable closeness predicate which given $h_k(x)$ and $...
4
votes
2answers
249 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
48 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 ...
-1
votes
1answer
71 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
85 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
68 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
46 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 ...
2
votes
1answer
77 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
143 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
90 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?
1
vote
1answer
583 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 ...
13
votes
2answers
661 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 ...