19
votes
0answers
628 views

Hardness of finding mutual discrete logarithms of small generators in $\mathbb{Z}_p$

Suppose you want to select a prime $p$ such that finding e.g. $log_2(3)$ in $\mathbb{Z}_p$ is expected to be either at least as hard as the general Discrete Logarithm Problem in $\mathbb{Z}_p$, or at ...
16
votes
0answers
928 views

Signal vs Telegram in terms of protocols?

Some time ago, the question was asked in chat, why MTProto (Telegram's protocol) is supposedly worse than Axolotl (Signal's protocol) as both protocols have been the inventions of their respective ...
10
votes
0answers
153 views

AMD and RDRAND instruction

The latest AMD programmer manuals, dated June 2015, include the RDRAND instruction in the instruction set. For completeness, it lacks ...
10
votes
0answers
621 views

Who first published the interest of more than two prime factors in RSA?

Multi-prime RSA is now a well known technique (described here): it uses $k>2$ distinct secret prime factors in the public RSA modulus, with the advantage that, using the CRT, we can gain a speed ...
9
votes
0answers
246 views

How were shift amount constants in MD5 found?

The md5 specification gives a series of 4 rounds to execute over a 16-word block. Each round has a repeating sequence of 4 shift amounts (s in ...
8
votes
0answers
929 views

Elliptic curve cryptography related key attacks

This question is an extension of Families of public/private keys in elliptic curve cryptography As described above, bitcoin "type 2" deterministic wallets use a root private/public key pair, where ...
7
votes
0answers
52 views

K friedman - two texts explanation

I have a question, I read the k friedman test to determine the period of a vigenere cipher text, and I understand something like this: Friedman's K test tries to find out what period of the cipher by ...
7
votes
0answers
67 views

Default algorithm for scalar multiplication of elliptic curve points by the MIRACL Library

What is the default algorithm used by the MIRACL-Library [1] for elliptic curve cryptography systems to perform scalar-point multiplication with curves of Weierstrass form satisfying the equation : ...
7
votes
0answers
131 views

Santa Claus' secret permutation

This December, $N$ friends play secret santa: they select a random permutation $\sigma$ of $N$ (without fixed point). For Santa Claus, everyone has to bring a gift to the next person in the ...
7
votes
0answers
115 views

Attacks on elliptic-curve based cryptosystems through solving the Decisional Diffie-Hellman Problem with the Weil Pairing

Are there any examples of practical attacks on cryptosystems set over elliptic curves which utilize the easiness of DDH for certain choices of curves $E(\textbf{F}_q)$, and as such their lack of ...
7
votes
0answers
177 views

Verbatim of early work on public-key cryptography?

In late 1997, the history of public-key cryptography was turned around with the announcement by the CESG (April 2000 archive) that public-key cryptography was theorized in a 1970 note [1] by James ...
7
votes
0answers
423 views

Security of RSA for paranoids with padding?

RSA for Paranoids (RSAP) (in cryptobytes v3n1), also known as Unbalanced RSA, is a variant of RSA proposed in 1995 by Adi Shamir, as a mean to increase the RSA public modulus size while keeping ...
7
votes
0answers
237 views

Efficient decoding of irreducible binary Goppa codes and the role of matrix P in McEliece cryptosystem

If we assume that the support for an irreducible binary Goppa code $\gamma_1, ..., \gamma_n$ is publicly known, when is it possible to efficiently decode the code? I know it's possible if one knows ...
6
votes
0answers
182 views

Is there any practical attack to create a printable chosen prefix MD5 collision?

I would like to create two ASCII text messages with the same MD5. Is this possible? If not, is there a similar but less strict attack that could work? Or to rephrase my last question: what are the ...
6
votes
0answers
175 views

Parallel Pollard's Rho: Number of distinguished points

When using the parallel version of Pollard's Rho algorithm for discrete logs, each processor performs its own random walk to find distinguished points, and reports the starting point and the ...
6
votes
0answers
172 views

Can a commutative block cipher be indistinguishable from a random one, assuming a random permutation of keyspace?

Define a commutative block cipher with keyspace the finite set $K$, and message space the finite set $S$, to be an application $$\begin{align} E:K\times S&\mapsto S\\ (k,x)&\mapsto ...
6
votes
0answers
164 views

Has the distributed project “Number Fields @ Home” project benefited cryptography in any meaningful way?

Is there any new understanding, property, or knowledge that has come from the Number Fields @Home distributed computing project? Has any outcome advanced the study of cryptography, or altered ...
5
votes
0answers
24 views

OTR AKE protocol implementations security

While looking at the different versions of OTR protocol I discovered a strange thing: there is no trace of the patch for the weaknesses that were noted in “Finite-State Security Analysis of OTR ...
5
votes
0answers
53 views

Performance of ECDSA, ECKCDSA and ECGDSA

It is proven that ECDSA algorithms are faster in key and signature generation compared to RSA. In addition, the signatures are much shorter. However, I would like to know the performance difference ...
5
votes
0answers
59 views

Rule 30 Cellular Automaton for Cryptography

Steven Wolfram of Mathematica uses a pseudorandom number generator based on Rule 30 for applications in Mathematica software but I would like to know if a pseudorandom generator based on Rule 30 is ...
5
votes
0answers
49 views

Proof that perfect privacy implies that the number of keys is at least the number of messages

I was reading a proof to the statement: Perfect privacy implies that $|K| = |M|$ where I am pretty sure that $K$ is the set of keys and $M$ is the set of messages. The proof is the following, ...
5
votes
0answers
112 views

Efficient way to confirm identity

I am working on a multiplayer game. I have a central server which handles all data transmission and coordinates all games. Clients which involved in a single session send requests to do actions to ...
5
votes
0answers
90 views

Big block cipher as memory-hard function

I'm wondering, if something like block cipher with big block size is a good memory-hard function? All memory-hard key derivation functions I've seen look more complex than that, which made me ...
5
votes
0answers
71 views

Is there a standardized tree hash?

SHA-1, SHA-2, and the standardized version of SHA-3 are all sequential. This is impractical for hashing very large files distributed across machines. Any sequential hash can be straightforwardly ...
5
votes
0answers
38 views

Is it possible and safe to use SAKKE for signing/verification, rather than for encryption?

Is it safe to use the Sakai–Kasahara key encryption algorithm (SAKKE) for signing/verification, rather than for encryption? (Example at bitbucket.org) In particular, I want many Bobs to be able to ...
5
votes
0answers
46 views

Can a one-way accumulator be used in place of a digital signature?

Could a one-way accumulator be used in a manner to replace a digital signature? Can it provide a way to: verify that the data has not been tampered with, and verify that the message is in fact ...
5
votes
0answers
141 views

How to break a columnar transposition cipher?

I'm currently studying for a cryptography exam. I've been given ciphertext that has been encrypted by a columnar transposition cipher. I've been given no shift key length or key word, the only thing I ...
5
votes
0answers
61 views

Elliptic curve point addition with $Z_1 = Z_2 = 1$

Elliptic curve point addition and point doubling operations using Projective and Jacobian coordinates require fewer field multiplication operations when considering $Z$ coordinates of input points ...
5
votes
0answers
30 views

Safe generation of $k$ points on a curve such that the mutual discrete logs are hard?

I have a multiplicative group $G$ of prime order $p$ implemented using a twisted Edwards curve (similar to Ed25519). I want to compute a set of $k$ distinct points $P_1,...,P_k$ that generate $G$, ...
5
votes
0answers
209 views

What is the original SKID3 protocol?

While searching for a mutual authentication protocol I often stumbled upon SKID3. However I encountered different variations of it. The basic structure is the following: (1) A --> B: rA (2) B --> ...
5
votes
0answers
107 views

Homogenous and heterogeneous Unbalanced Feistel Networks

Unbalanced Feistel networks can be homogenous (F-function identical in each round), or they can be heterogeneous (F-function not always identical in each round). The advantage of heterogeneous UFNs ...
5
votes
0answers
203 views

Given a 'good' basis for a lattice, how can we solve the CVP?

I'm doing a little bit of reading about lattices. I read that if we can find a 'short' basis for our given lattice, we can solve CVP and SVP very efficiently. However, the paper didn't describe an ...
5
votes
0answers
194 views

How can I create an RSA modulus for which no one knows the factors?

It's easy to create an RSA modulus where almost no one knows the factors: for example, I can generate two 1024-bit primes $p$ and $q$ and set $n=pq$. If I publish $n$, I will be the only person in ...
5
votes
0answers
295 views

LT codes with Homomorphic hashing

I have been working on a project implementing LT codes with Homomorphic hashing (inspired from http://blog.notdot.net/2012/08/Damn-Cool-Algorithms-Homomorphic-Hashing and ...
5
votes
0answers
310 views

Odds of false error detection in a randomness test using the chi-squared test?

Common Criteria classifies the requirements for true Random Number Generators, and specifies how these should be tested against failures (these can occur accidentally, or following deliberate attack, ...
4
votes
0answers
83 views

How to prove that a function F isn't a pseudo random function

Let $F$ be a length-preserving pseudorandom function. For the following constructions of a keyed function $F' : \{0, 1\}^n \times \{0, 1\}^{n−1} \to \{0, 1\}^{2n}$, state whether $F'$ is a ...
4
votes
0answers
114 views

Finding the subgroup in isogeny-based cryptography

Isogeny-based cryptography is one of the newest post-quantum cryptography. Hardness of this system is based on finding isogeny between two elliptic curves. Also this is theorem: Elliptic curves ...
4
votes
0answers
30 views

An MPC protocol from Elgamal is a good solution a homomorphic multiplication?

I want to compute a multiplication between many secret values and then distribute the result to everyone involved. For this, I thought about an MPC protocol built from Threshold Homomorphic Elgamal. ...
4
votes
0answers
62 views

Zero-knowledge proof for the product of additive Paillier ciphers

Suppose that Alice received the cipher values: $E(x_1), E(x_2), ..., E(x_n)$ that are encrypted using Paillier cryptosystem by $n$ entities with Bob's public key. Alice computes $E(\sum x_i)$ from ...
4
votes
0answers
61 views

How can I implement decryption for NTRU homomorphic encryption scheme?

I have come across this paper On-the-fly multiparty computation via on-the-cloud Multikey from Fully Homomorphic Encryption by Lopez-Alt et al., where authors describe a NTRU-based homomorphic ...
4
votes
0answers
23 views

Understanding the definition of HGD

On the section 4.2, page 10, of the paper Order-Preserving Symmetric Encryption, the authors define two subroutines: the first one is called $HGD$ and the second one is $GetCoins$. I have doubts ...
4
votes
0answers
38 views

Security parameter p =O(n)

In many homomorphic encryption scheme, a security parameter is calculated as p =O(n). How to use the complexity order as values? Is there any specific method with an appropriate example?
4
votes
0answers
55 views

Why is AES-SIV not used, but AESKW, AKW1?

I'm trying to investigate different key wrapping algorithms for my implementation. I've noticed that AES-SIV is very rarely implemented by most of open source libraries. Most of them implements key ...
4
votes
0answers
41 views

What is the correct definition of the blowfish F-function?

The Blowfish cipher uses a so called F-function which uses S-Boxes (S[i], i=0,1,2,3) to ...
4
votes
0answers
54 views

Additively homomorphic cryptosystem with non-interactive zero-knowledge proof of non-negativity

I need a cryptosystem that is additively homomorphic. Paillier preferably, but not neccessarily. Also, for every ciphertext the private key holder must be able to prove non-interactively that the ...
4
votes
0answers
62 views

Comparison Vigènere vs. Monoalphabetic cipher

I have a question for a class of secure communication, but I have no idea about how to proceed in order to answer it. I'll be very grateful to whom replies to me. Assuming that brute force attack ...
4
votes
0answers
81 views

Adding parameters to sponge's capacity

Is it safe to XOR parameters like domain, length of the message or block counter into sponge's capacity or that gives attacker control over capacity? For example NORX XORs domain into capacity. Does ...
4
votes
0answers
47 views

Reusing same source for single-source randomness extractor

Let $ext$ be a single-source randomness extractor which takes a $d$-bit seed and a $n$-bit source as input and produces a $m$-bit output. Suppose we have a source $X$ with min-entropy $k$. Is it ...
4
votes
0answers
54 views

How to use a stream cipher to sign a message?

Are there known constructions which allow to sign a message M (let's say it will be sent as clear text) using a stream cipher C and a symmetric secret key K? So, we have M, C, K and we want to send ...
4
votes
0answers
57 views

Salary Negotiation Problem

Imagine Alice is applying for a new job. Alice has an idea of the minimum salary that she is willing to accept—let's call this value A. Bob, the hiring manager for ...

15 30 50 per page