All Questions

3,077 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
32
votes
0answers
2k 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 ...
31
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 ...
20
votes
0answers
710 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). ...
15
votes
0answers
288 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 ...
14
votes
0answers
644 views

Crypto AG (Switzerland) - Which algorithms were used and how did the backdoors work?

Backstory Crypto AG was a company located in Switzerland that specialized in communication security. They produced a number of encryption machines (some similar to the infamous Enigma) used for ...
14
votes
0answers
248 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 ...
14
votes
0answers
301 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 ...
14
votes
0answers
253 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 ...
13
votes
0answers
154 views

The aftermath and considerations of the new record of 30750-Bit Binary Field Discrete Logarithm - 2020

Granger et al. recently published a paper about breaking a record for discrete logarithm on the Binary field Computation of a 30 750-Bit Binary Field Discrete Logarithm, Robert Granger and Thorsten ...
12
votes
0answers
705 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
169 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
188 views

RSA key such that pi deciphers to your name per RSA-OAEP

Can you efficiently construct an RSA public/private key pair with $8k$-bit public modulus such that $C=\left\lfloor\pi\,2^{8k-2}\right\rfloor$ deciphers per RSA-OAEP to your name as a bytestring in ...
11
votes
0answers
392 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. ...
11
votes
0answers
456 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
900 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 ...
11
votes
0answers
488 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
233 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
297 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
74 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
169 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
323 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
591 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
175 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 ...
9
votes
0answers
2k 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, ...
9
votes
0answers
663 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
509 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
502 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 ...
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
297 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
1answer
145 views

Details about ROS attack on blind Schnorr signatures

My question concerns the recently uploaded paper On the (in)security of ROS that describes an expected polynomial-time attack on the unforgeability of Schnorr blind signatures. a) Does this mean that ...
8
votes
0answers
101 views

Are there any weak nonce-misuse resistant encryption scheme?

Nonce-misuse resistance seems to have two standard notions: The stronger notion: this reveals nothing unless the exact same nonce is used to encrypt the exact same message twice. In this case, the ...
8
votes
0answers
81 views

Is anyone using ORAM in practice?

Oblivious RAM has been around in theory for about 30 years at this point. Is anyone using it in practice? Has it made its way into industry? (Including any variants such as MPC ORAM or ORAM that uses ...
8
votes
0answers
131 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" - ...
8
votes
0answers
161 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
614 views

Key size, performance, and security tradeoffs for AES GCM / CCM

AES can be used with 128, 192 or 256 bit keys and each one appears to have a performance vs security trade-off (What is the effect of the different AES key lengths?, What are the practical differences ...
8
votes
0answers
104 views

Offline Group Key Agreement - Cross Device Syncing

I have a specific use case I am interested in. I have spent the better part of the night reading research papers. I am beginning to believe what I want is not possible so I wanted to confirm here. ...
8
votes
0answers
322 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
152 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 ...
8
votes
0answers
124 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
371 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
533 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/...
7
votes
0answers
119 views

About a SETUP mechanism on ECDH

I'm following these three articles: Kleptography: Using Cryptography Against Cryptography, Kleptographic Attack on Elliptic Curve Based Cryptographic Protocols and Elliptic Curve Kleptography . In ...
7
votes
0answers
184 views

In RSA, given public key $(n,e)$ and $d^e\bmod n$, can we factor $n$?

Given an RSA public key $(n,e)$ and the textbook-RSA encryption $c$ of a valid matching private exponent $d$, computed as $c\gets d^e\bmod n$:  can we factor $n$ ? Assume $n,e,d$ are per PKCS#1v2.2. ...
7
votes
0answers
152 views

How to implement arbitrary s-box in a side-channel-free way in C?

This could be a question for CodeReview.SE, but I thought it might require non-trivial cryptographic knowledge to merit it on-topic here. The C language is chosen as it's a common language for ...
7
votes
0answers
89 views

Hardness of iterated squaring in Pailler group

The (computational) problem of iterated squaring (IS) in the RSA group is defined as follows, where $\leftarrow$ denotes sampling uniformly at random: Input: $(N,x,T)$, where $N$ is the RSA modulus, $...
7
votes
0answers
162 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 ...
7
votes
0answers
227 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
178 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
790 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 ...

15 30 50 per page
1
2 3 4 5
62