All Questions

2,268 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
30
votes
2answers
1k 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 ...
28
votes
0answers
1k 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 ...
18
votes
0answers
566 views

Memory-hard password hash in practice?

Dan Boneh, Henry Corrigan-Gibbs, and Stuart Schechter have proposed Balloon Hashing: A Memory-Hard Function Providing Provable Protection Against Sequential Attacks (in proceedings of AsiaCrypt 2016). ...
14
votes
0answers
202 views

Fewest qubits required for the discrete logarithm problem and integer factorization

According to a paper from 2002, the most efficient circuit to factor an $n$-bit integer requires $2n+3$ qubits and $O(n^{3}\lg(n))$ elementary quantum gates, assuming ideal qubits. Later on, according ...
13
votes
1answer
356 views

Is Pohlig-Hellman Cipher the only option?

I am looking for a cipher which would allow something like this: E(E(M, a), b) = E(M, ab), where a and b are encryption keys, and ab is a combination of the keys that is impractical to separate into a ...
13
votes
0answers
271 views

Finding $x$ such that $g^x\bmod p<p/k$?

In a Schnorr group as used for DSA, of prime modulus $p$, prime order $q$, generator $g$ (with $p/g$ small), how can we efficiently exhibit an $x$ with $0<x<q$ such that $g^x\bmod p<p/k$, for ...
13
votes
0answers
226 views

Name of an archaic type of RSA padding (0BBBBBBB…)

In some legacy code, I encountered RSA signature padding in the following format (hexadecimal): 0B BB BB BB BB BB BB ... BB BB <hash> Is there a name for ...
12
votes
0answers
582 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 ...
12
votes
0answers
149 views

Space complexity of quantum collision search?

Is there a known way to reduce the space complexity of quantum collision search (PDF) beyond what is offered by the built-in time-space tradeoff, while keeping the time complexity significantly below ...
11
votes
0answers
380 views

Potential Flaws With Lattice Based Cryptography?

From researching post-quantum cryptographic schemes it seems hash-based and lattice-based algorithms are the most promising (MQ-based seem to be covered by patents and have more potential unknowns ...
11
votes
0answers
2k views

Cracking a PRNG by observing ranks within groups of its output

Suppose that I am generating random numbers with Python's random module, so that there is a known random number generator (Mersenne Twister in this case). I've ...
11
votes
0answers
464 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 ...
10
votes
0answers
256 views

How Significant is the New Quasi-Polynomial-Time Attack on Fixed Characteristic Discrete Logarithms?

There is a new paper by Kleinjung and Wesolowski on eprint that claims and proves a new attack on the discrete logarithm problem in finite fixed characteristic fields in quasi-polynomial time. ...
10
votes
0answers
217 views

Do trinomials weaken the Alternating Step Generator?

The Alternating Step Generator was proposed by Christoph G. Günther: Alternating step generators controlled by de Bruijn sequences, in proceedings of Eurocrypt 1987. It's perhaps the conceptually ...
10
votes
0answers
248 views

What was the BassOmatic cipher, and what made it so weak?

According to Wikipedia, this homebrew cipher was originally used in PGP, before Phil Zimmermann replaced it with IDEA. Supposedly, insecurities in the algorithm were pointed out to him, leading to ...
10
votes
0answers
62 views

Decision R-LWE parameters for spherical error with worst-case hardness

In Peikert et al.'s most recent work (STOC 2017) a direct reduction of worst-case lattice problems to decision R-LWE is achieved for $\alpha q \ge 2 \cdot \omega(1)$ (Theorem 6.2), where $\alpha q$ is ...
10
votes
0answers
150 views

How exactly does ASKE (Alpha Secure Key Establishment) in Zigbee work?

I am working on Zigbee security. For key establishment, some approaches are given in Zigbee. Some of them are: ASKE (Alpha Secure Key Establishment), ASAC (Alpha Secure Access Control), and SKKE (...
10
votes
0answers
297 views

What might be assumed about a PRF if the key has been chosen?

The defining feature of a PRF $f:\{0,1\}^k\times\{0,1\}^s\mapsto\{0,1\}^*$ is that, if the first parameter is selected at random, it should be indistinguishable from a function $g:\{0,1\}^s\mapsto\{0,...
10
votes
1answer
2k views

What is the difference between OTR and Signal protocols?

The Signal Protocol is a relatively new secure messaging protocol that was recently implemented in Signal, WhatsApp, and several other messenging apps. According to Wikipedia, the Signal protocol is ...
9
votes
0answers
330 views

RSA factorization with special primes

Suppose that primes for RSA modulus are generated using formula: $P_i(x,y) = \operatorname{next\_prime}(x^{z_i}+y^{z_i}) = x^{z_i}+y^{z_i}+d_i$ where $x,y$ are unknown random numbers with size 128 ...
9
votes
0answers
608 views

Are there attacks against broken RSA signature pad checking with $e = 65537$?

Let's say that an RSA implementation of PKCS #1 signatures fails to validate that the 00 01 FF FF FF ... FF 00 portion of the decrypted signature is exactly as long ...
9
votes
0answers
669 views

Yaos Millionaire Problem: Why distance >= 2?

I'm currently reading about Yao' Millionaire Problem: http://research.cs.wisc.edu/areas/sec/yao1982-ocr.pdf Alice and Bob want to know which of them is richer. Let $j \in \{1, \cdots 10\}$ be Bobs ...
9
votes
0answers
458 views

Why SIVP Is Worst Case Problem?

I just started to study lattice Cryptography. I'm now studying worst-case to average-case reduction for SIS. In previous question, "worst means any and average means random". And I wonder why the ...
9
votes
0answers
997 views

CPA-security of a pseudorandom permutation encryption scheme

Let $F$ be a pseudorandom permutation, and define a fixed-length encryption scheme $(Gen, Enc, Dec)$ as follows: on input $m \in$ $\{0,1\}^{n/2}$ and key $k \in \{0,1\}^n$, algorithm $Enc$ chooses ...
9
votes
0answers
1k views

Rationale for use of right-shift (rather than rotate) in SHA-2?

The SHA-2 hashes in FIPS 180 define $\Sigma$ and $\sigma$ bijections of words, with $\Sigma$ used in the round function, and $\sigma$ used in preparing 48 words of message schedule from 16 words of a ...
9
votes
0answers
284 views

What are the current limitations (and capabilities) of Functional Encryption used for access control?

I'm trying to make my way in Functional Encryption used for access control. I read a lot of papers such as "How to Run Turing Machines on Encrypted Data", "Functional Encryption: New Perspectives and ...
8
votes
0answers
127 views

Time-memory tradeoffs in Shor's algorithm

Can a quantum computer with insufficient qubits to factor an integer of a given size make any progress in factoring it? For example, what if a quantum computer is only one qubit short of what is ...
8
votes
0answers
151 views

How to build a security model

What are the minimal components to build a security model proof for a protocol? This question might seem trivial, but having read many papers-- from the IEEE, ACM, etc., that talk about a KMP-- I ...
8
votes
0answers
223 views

Bleichenbacher RSA1024 signature forgery, closed-form solution

Hal Finney's writeup (Bleichenbacher's RSA signature forgery based on implementation error) shows a formula for RSA3072. I tried to replicate the attack for RSA1024 and failed, since the first term of ...
8
votes
0answers
1k views

Has Telegram security been significantly improved with MTProto 2.0?

Telegram messenger's original encryption scheme, MTProto 1.0, has been shunned by most cryptographers for a number of reasons, like being vulnerable to IND-CCA attack; being unorthodox in general, ...
8
votes
0answers
117 views

Software timing attack using Kocher method

What's the minimum number of random sample points needed in Kocher's timing attack, so that we can determine enough valid measurements of $A_{i,r}$ and $D_{i,r}$? I'm working from this paper: Volker ...
8
votes
0answers
375 views

What level of security is provided when a Feistel Cipher is used as a round function of another Feistel Cipher?

Recently, I was reading: Are there any specific requirements for the function F in a Feistel cipher?, and the answer posted mentions a Feistel Cipher named Turtle, which uses a four-round Feistel ...
8
votes
0answers
338 views

Is the key schedule of Serpent a circle?

The creation of the prekeys for Serpent works by XORing some previous values with a counter and a fixed value. Every word is 32 bits big and 4 words form a round key (after applying a S-Box, but this ...
8
votes
0answers
500 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 http://blog.notdot.net/2012/...
8
votes
0answers
242 views

Unique GCM/CCM initial counters without recipient side message counters

I am implementing the encryption layer for a communication protocol. The bulk encryption method used is either AES-CCM or AES-GCM. Due to implementation details, encryption of packets is usually, but ...
7
votes
0answers
145 views

Why is BLAKE2 faster than chacha20?

Chacha20 is essentially a hash function that maps 512-bit strings to other 512-bit strings which are in turn xored with the plaintext to create the ciphertext. Of the 512-bit input 128-bit are used ...
7
votes
0answers
114 views

What is the origin of the phrase “Don't roll your own crypto”?

The phrase is well-known and widely used, it is often attributed to Bruce Schneier and is indeed relevant to his Schneier's Law. However, I wasn't able to find this specific wording among Schneier's ...
7
votes
0answers
103 views

Differences between “NewHope” and “NewHope-simple”

The well-known paper described a key exchange (KE) scheme named "NewHope" on USENIX 2016. The authors then proposed "NewHope-Simple" - a PKE/KEM scheme. They also submitted "NewHope for NIST" - ...
7
votes
0answers
136 views

GCM with reversed poly

These slides talk about how GCM can be sped up if one uses $x^{128}+x^{127}+x^{126}+x^{121}+1$ as the reduction polynomial instead of $x^{128}+x^7+x^2+x^1+1$. When one is doing that one needs to ...
7
votes
1answer
143 views

Two plaintexts map to the same ciphertext in fully homomorphic encryption?

In standard symmetric encryption, we can create an encryption scheme, in which two plaintexts $x_1, x_2$ map to the same ciphertext $y$, by choosing appropriate keys $k_1,k_2$ (!). The most simple ...
7
votes
0answers
175 views

Adding bit constants to the key schedule to reduce rounds?

Bit constants are often added to the key schedule to reduce slide attacks. I have reviewed David Wagner's work, where he showed that the increased rounds in a Feistel network do not help if you have ...
7
votes
0answers
140 views

Are there conventions for signing JSON as a tree, to allow proofs of signed subtrees?

Given some JSON with a chosen encoding, you can obviously cryptographically-sign the whole thing as a binary blob. However, it might be useful if the logical structure of the JSON-compatible object ...
7
votes
0answers
136 views

Replacing signer with simulator

Assume we can prove security of digital signature scheme against key-only (no message) attacks. Now we want to prove security against adaptive chosen message attack. We use random oracle model. The ...
7
votes
0answers
302 views

Security proof in (Ciphertext-Policy) Attribute-Based Encryption

I am having hard time understanding the security proof in Attribute-Based Encryption, especially in Ciphertext-Policy Attribute-Based Encryption. To do reduction in CP-ABE scheme, how do I check that ...
6
votes
0answers
75 views

Most influential/illuminating papers/books/courses on lattice based cryptography?

I'm interested in some sort of "compendium" on lattice based crypto. There are a bunch of maths behind FALCON and other stuff. A lot of articles are devoted to lattice crypto, but not of them are of ...
6
votes
0answers
95 views

Are there two known ASCII-only strings which have the same MD5 hash value?

Up to now, the pairs of strings that create an MD5 collision that have been discovered all contain non-ASCII (binary) characters. Are there two known ASCII-only strings which have the same MD5 hash ...
6
votes
0answers
135 views

What's the difference among Vector Commitment, Zero-knowledge Set, Zero-knowledge Accumulator, and Zero-knowledge Elementary Database?

Vector commitment allows to commit to an ordered sequence of $q$ value ($m_1,\cdots,m_q$) in such a way that one can later open the commitment at specific positions(e.g., prove that $m_i$ is the $i$-...
6
votes
0answers
315 views

Why does the Signal protocol use AES/CBC instead of AES/GCM?

AES/GCM has obviously proved itself to be better than AES/CBC. Unless the key is re-used with the same initialization vector (see disadvantages of GCM). More information of its advantages against CBC ...
6
votes
1answer
136 views

Key confirmation and other benefits of double ratchet

I'm trying to understand a comment from the Signal blog post Advanced cryptographic ratcheting. This article uses the term OTR ratchet to refer to a simple asymmetric DH ratchet, where Alice ...
6
votes
0answers
58 views

Is there a standard definition of non-malleability for the encryption schemes?

I find some different definitions of non-malleability for the encryption schemes. They may be equivalent, but I am not sure which one is better or if there is a standard definition. I give two ...

15 30 50 per page