Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [cryptography]

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

0
votes
0answers
11 views

How could the Cuckoo Search be implemented into Python? (Presumably a solver) [closed]

I was looking to do this for just a fun project, and maybe mine some GRIN coin.The proof-of-work for GRIN is the cuck(ar)oo29 algorithm, with 29 nodes in each graph. There is also an ASIC chain, for ...
-1
votes
2answers
43 views

Finding small-length RSA private key

I was wondering if there is an algorithm to derive $p$ and $q$ or is it simply trial and error? Consider the following RSA crypto-system with public key $(437,13)$. Since the numbers are so small, ...
1
vote
0answers
27 views

Is it possible to build a secure PRG from two functions one of them being a PRG?

Having two deterministic functions $G_1, G_2 : \left\{0,1\right\}^\lambda \rightarrow \left\{0,1\right\}^{\lambda+l}$, at least one of which is a secure PRG. Being $\alpha$ a constant, is it possible ...
1
vote
1answer
44 views

Is the bitwise-xor of a Uniform bit string and a non_uniform bit string Uniform?

Having two bit strings $x,y \in \left\{0,1\right\}^n$, where $x$ is selected following a uniform distribution but $y$ is not. Is $z = x \oplus y$ uniform?
1
vote
1answer
24 views

DES encryption - what happens if all sub-keys are the same?

What will happen if we change the DES encryrption algorithm to use the same key in each round ? How will it affect the encryption - will it only make the encryption same as decryption or are the more ...
1
vote
1answer
30 views

Prove hash family is 3-wise independent

Let $q$ be a prime number and let $\mathbb{Z}_q = \left\{1,\dots,q-1\right\}$; I need to prove that the family $\mathcal{H} = \left\{h_s \colon \mathbb{Z}_q \rightarrow \mathbb{Z}_q\right\}_{s \in \...
1
vote
1answer
57 views

fully homomorphic encryption with information-theoretic security?

An encryption algorithm with information-theoretic security is one which even with infinite amount of computation cannot be broken. That is, given only the ciphertext, no amount of computation can ...
1
vote
0answers
22 views

Anonymous Visibility Check in P2P networks

I'm working on a problem for a P2P network for games. The problem is the following: Consider two opponents on a grid, each stores it's own position. Player 1 wants to know if it sees player 2. In ...
1
vote
1answer
41 views

Can I decrypt an RSA algorithm using only the message I am wanting to decrypt, an “e” value and a “n” value?

I have a ciphertext $c$ encrypted with RSA algorithm that needs to decrypt. I have the public key $(n,e)$. Is it possible to decrypt with this amount of information?
4
votes
1answer
118 views

Any evidence that one way functions exist?

There is no known proof that one way functions exist. But what is the heuristic evidence that they exist? I sometimes read that the existence of cryptography is heuristic evidence that they exist. E....
0
votes
1answer
15 views

Is it possible to give a guarantee about the accuracy of the local time?

Assuming there is no attack/bug and I use NTP: Are there any formal guarantees about the accuracy of the local time? Can there be any over the network? Even if the communication is going directly ...
0
votes
1answer
38 views

Interchangeable role of public/private key pair and encoding/decoding algorithms

In designing a public-key cryptosystem, there are often two desirable properties: Public/private key pair of each participant can be exchanged. Meaning that whenever a participant has generated a key ...
4
votes
0answers
69 views

Optimal parallel-time repeated modular squaring circuit

Given a 4096-bit integer $x$ and a 4096-bit RSA modulus $N$ (of unknown factorisation) what is the fastest circuit to compute $x^{2^T} \mod N$ where $T=2^{40}$. That is, what is the fastest parallel-...
4
votes
1answer
81 views

Why is fully homomorphic encryption so slow?

What are the reasons that FHE is so slow? Is it possible to make the FHE algorithm so fast that it can be used in practice (say, the practical FHE algorithm should be slower no more than 10 times ...
1
vote
2answers
40 views

Can the program determine the frequency of the CPU or is it impossible?

In order to understand the question, imagine a simple situation. Alice tells Bob that her CPU's frequency is X Hz. Bob does not take her word for it. Bob can not meet with Alice and check what ...
0
votes
2answers
19 views

How does storing encrypted password provide secure authentication?

It's universally accepted that storing an unencrypted password for automated authentication is a very bad idea, for the saved password can be used by malware, etc. There is a number of systems that ...
4
votes
1answer
40 views

How to make smart contracts work in a small network?

Suppose we have a small computer network, there are 30 random people who have provided their computers to perform any computational tasks on them. Let's call these 30 computers nodes. We can access ...
2
votes
2answers
27 views

Proof of non-receipt of the file

The condition of the problem and the statement of the problem: Alice pays Bob for the fact that he, at the request of users, gives out files of interest to users. For example, the user is interested ...
0
votes
1answer
48 views

Can anyone find a mapping from the set of all possible string to the natural numbers?

Can anyone find a map(injection) $h$ from the set of all possible strings $S^*$ to the natural numbers $\mathbb{N}$? $$h : S^* \rightarrow \mathbb{N} $$ Assume $S$ is finite. I would prefer an ...
0
votes
1answer
57 views

Finding the Entropy of a random experiment with probability of $\frac{1}{3}$

Entropy is the randomness collected by an operating system or application for use in Cryptography or other uses that require random data. The formula for Entropy is $$H(p_1, ..., p_k)=-\sum_{i=1}^{k} ...
2
votes
1answer
57 views

Finding $d$ in RSA Encryption mathematically and by hand

I'm working on this RSA encryption problem and the catch is that it must be done by hand and mathematically. Let's say $p=11$, $q=13$ $$N=p \cdot q=11 \cdot 13=143$$ I chose $e$ to be relatively ...
7
votes
3answers
2k views

Problem with the pseudo random number generator One-Time-Pad

I've started learning cryptography in class and we've come across One-Time-Pads, in which the key (uniformally agreed upon) is as long as the message itself. Then you turn the message into bits, do $...
3
votes
1answer
80 views

Trustless exchange without a third party

Is there a cryptographic (or even not entirely cryptographic) way of exchanging objects between Alice and Bob that would not require a third party, and Alice and Bob would not need to trust each other?...
0
votes
2answers
52 views

What's the correct term for this analog of cryptography?

Suppose there is a communications channel between two parties. Suppose I want to send information through this channel, but I want to make it look like noise. Ie, I don't necessarily want to encrypt ...
4
votes
2answers
76 views

Blockchain cipher suitable for preschoolers

Is there a cipher that well suited for preschool-aged children to work out on pencil and paper, to learn concepts of block chains? It must have the following requirements: Able to be easily verified ...
3
votes
1answer
358 views

Computation of discrete logarithm

I know that an equation $$a^x \equiv b \pmod{p}$$ can be solved for $x$ in $O(\sqrt{p} \ log(p) )$ time using meet-in-the-middle technique, which relies on fact that we can rewrite the equation as ...
1
vote
1answer
45 views

Why do Alice and Bob get the same key even after modular reduction in Diffie-Hellman Cryptography?

In this cryptography scheme, we take $g$ and $p$ (a large prime number). and taking the customary clients Alice and Bob who chose $a$ and $b$ secretly whereas $p$ and $g$ are known in public. I haven'...
4
votes
1answer
86 views

Prove complexity bound without reduction?

The most common method of proving that some problem, P, is at least as difficult as some other problem, Q, is to demonstrate that Q can be solved in terms of P (with the usual caveats for the ...
0
votes
1answer
33 views

Can SSL be hacked if we know some of plain data?

As I know, SSL/HTTPS is two stage, first stage is public key encryption/decryption which transfers key of the second stage which is symmetric. It is true we don't have key, but we can have some of ...
1
vote
0answers
34 views

eVoting with Damgard-Jurik-Cryptosystem

I am trying to implement a secure elecetronic voting system. Therefore I found the Damgard and Jurik Cryptosystem. In their paper the authors describe a secure protocol for "A Length-Flexible ...
1
vote
1answer
114 views

Understanding the Bitcoin White Paper's Notion of “Signing” and “Verifying”

Consider from the Bitcoin white paper a graphic that includes dotted arrows, labeled "sign" and "verify": What does it mean to "sign" and "verify", as outlined in this paper? Are the terms "...
29
votes
4answers
3k views

What is an extremely basic asymmetric cipher that I can present at the pub?

I'm trying to explain the basics of Bitcoin to my parents. One of the core components of bitcoin, is signing transactions to make sure your identity can't be impersonated, and thus the need to ...
0
votes
1answer
35 views

3 blocks CBC-MAC

Let $M=(m_1, m_2)$, $M'= (m_0', m_1')$ be two two-block messages. In other words, $|m_1|=|m_2|=|m_1'|=|m_2'|=n$. We say that $M, M'$ collide for key $k$ if $$E_k(E_k(m_1)⊕m_2) = E_k(E_k(m_1')⊕m_2')...
0
votes
0answers
23 views

Secrecy rate of eavesdropper channel?

I want to find secrecy rate of a main channel in case of Gaussian broadcast channel. e.g. I have a single transmitter and a receiver where eavesdropper wants to eavesdrop the communication over ...
3
votes
2answers
47 views

Indexing a random permutation

I am curious if there exists a method for specifying a permutation $F_k: X \to X$ with a small(ish) $k$. Something that comes very close to my goal is a block cipher, say AES. But block ciphers have ...
1
vote
1answer
51 views

Problem about getting a value of the hashed password [closed]

Given a database with usernames and the first six bytes of their hashed passwords. A standard hashing function has been used for hashing. admin 827ccb0eea8a user c3981fa8d26e operator 5f4dcc3b5aa7 ...
1
vote
0answers
26 views

Prove you computed hash^r(input) for some cryptographic hash function [closed]

What is the most efficient way to prove that a person computed r rounds of some cryptographic hash function (ex. sha256) on an input?. The trivial solution seems to be to show all r hashes, where <...
3
votes
1answer
112 views

Understanding Incentive Compatibility of pooled Bitcoin Mining paper

I'm trying to understand the paper Incentive Compatibility of Bitcoin Mining Pool Reward Functions (Schrijvers, Bonneau, Doneh and Roughgarden, in Financial Cryptography and Data Security – ...
2
votes
0answers
40 views

AKS primality test- Lemma 4.3, not following

I'm reading the AKS primality test paper as it is found here. I'm confused about a statement in Lemma 4.3: "Note that $(r, n)$ cannot be divisible by all the prime divisors of $r$ since otherwise $r$...
0
votes
1answer
52 views

Finding a trapdoor function for the 3-partition problem

I am working on a cryptography project. Let's say I want to build a public key cryptosystem using the 3-partition problem, which is NP-Complete, as a basis (just like RSA uses integer factorization). ...
1
vote
0answers
51 views

On “practical” polynomial coefficients if P = NP

I got riddled by the following problem: Wikipedia states (without citation) Cryptography, for example, relies on certain problems being difficult. A constructive and efficient solution[Note 1] to ...
1
vote
1answer
35 views

Complex property of sparse horner polynomials by induction

I'm following this article to do a formal proof on elliptic curve cryptography. My question here addresses only a property "easily proved by induction". Definitions (the important part is the ...
1
vote
0answers
29 views

Generation of 11 bit random number

I need camera to sign one random line(there are something like 2000 lines) from the frame each second. At the beginning I have some 64 bits seed with high entropy from physical RNG and a secure ...
0
votes
1answer
38 views

On $1$-way functions and formalizing my intuitions about them

Let $a: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way function and $b: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way permutation. Now, it makes intuitive sense to me that $a \circ b$ should be a $1$-way function,...
7
votes
2answers
1k views

Does there exist an equivalent arithmetic circuit for each computable function?

Does there exist an equivalent arithmetic circuit for each computable function? I've been trying to wrap my head around the statement above, but haven't found a counter example although I believe ...
1
vote
1answer
83 views

An encoding algorithm with an expensive encoder and a cheap decoder

I am looking for an encoding algorithm that would have an encoding function with highly expensive computational costs (ideally like scrypt). At the same time its decoding function must be a lot easier ...
2
votes
1answer
36 views

Counter Mode Encryption Vulnerabilities

Hi All, I am solving a question about counter mode encryption in symmetric crypto. I am new to the topic and don't really understand the matter, could you help me a little how to solve the following ...
1
vote
1answer
111 views

Collision resistant Hash function in chaos cryptography

In my earlier Question asked here Help in understanding how to apply nonlinear function in hashing about chaos cryptography, since then I have come across several research papers that apply atleat ...
4
votes
0answers
55 views

creating new PRF from existing one

I have encountered a problem in class, tried solving it and faced a problem, I will include my ideas, and the problems i faced. Assume F is a PRF, 1.denote $P_k(x) = F_k(x) ⊕ F_k(1^n)$ for any $n ∈ ...
3
votes
1answer
60 views

Prove count without revealing data

Suppose I maintain a proprietary database and claim that it has N records. Before subscribing to my database a client wants a proof that the database is indeed this large. What theoretical protocol ...