All Questions

4,703 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
19 votes
0 answers
464 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 ...
b degnan's user avatar
  • 4,820
18 votes
0 answers
509 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 ...
kelalaka's user avatar
  • 48.5k
18 votes
0 answers
480 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 ...
fgrieu's user avatar
  • 141k
18 votes
3 answers
2k views

RSA factorization for special primes $p$ and $q$

I want to factorize the modulus $n = pq$ knowing that $p$ and $q$ are not random, but constructed based on integer numbers $a$ and $b$ as following ($a$ and $b$ are not given): $$p = a^2 + b^2, \...
Lisbeth's user avatar
  • 497
16 votes
0 answers
421 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 ...
forest's user avatar
  • 15.3k
16 votes
0 answers
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, ...
Dark Lotus's user avatar
15 votes
0 answers
1k 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 ...
pg1989's user avatar
  • 4,636
14 votes
0 answers
891 views

The backdoor of Telegram on Diffie-Hellman Key Exchange and possibly other examples?

Diffie-Hellman Key-Exchange (DHKE) should be used carefully during the end-to-end encryption. A man-in-the-middle (MITM) attack is possible. Standard DHKE The simple protocol on the multiplicative ...
kelalaka's user avatar
  • 48.5k
14 votes
0 answers
223 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 ...
user avatar
13 votes
0 answers
299 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 ...
fgrieu's user avatar
  • 141k
13 votes
0 answers
496 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. ...
SEJPM's user avatar
  • 46k
13 votes
0 answers
844 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 ...
Kamil Pliszka's user avatar
13 votes
0 answers
690 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 ...
CoryG's user avatar
  • 559
13 votes
0 answers
1k 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 ...
Calculatrix's user avatar
12 votes
0 answers
534 views

Requirements for security against multi-target attacks, for McEliece and other code-based cryptosystems?

This question is potentially relevant to NIST post-quantum cryptography standards, involving code-based cryptosystems such as McEliece, BIKE and HQC. For these cryptosystems, it seems that an attacker ...
Ray Perlner's user avatar
12 votes
0 answers
2k 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 on its advantages against CBC ...
OughtToPrevail's user avatar
11 votes
0 answers
241 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 ...
CipherX's user avatar
  • 381
11 votes
0 answers
98 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 ...
Daniela's user avatar
  • 111
11 votes
0 answers
211 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 (...
Prasanth Kumar Arisetti's user avatar
11 votes
0 answers
665 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 ...
Jonghyun Kim's user avatar
11 votes
0 answers
687 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 ...
user avatar
11 votes
0 answers
505 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,...
Henrick Hellström's user avatar
10 votes
0 answers
627 views

How to write proofs for universal composable security?

Recently, I learn Ran Canetti's famous paper, "Universally Composable Security: A New Paradigm for Cryptographic Protocols". But I find it very difficult to grasp. When I read the paper that ...
user77340's user avatar
  • 787
10 votes
0 answers
209 views

Do CCM and EAX provide key commitment?

In an interesting paper called "Partitioning Oracle Attacks" by Julia Len, Paul Grubbs & Thomas Ristenpart an attack is presented on 1.5 pass AEAD schemes that utilize GMAC (GCM, AES-GCM,...
Maarten Bodewes's user avatar
  • 92.6k
10 votes
0 answers
232 views

How many additions modulo $2^k$ and multiplications in $\mathbb F_{2^k}$ are needed to resist cryptanalysis?

Consider a $k$-bit block cipher with $r$ rounds, and key composed of $r$ subkeys $K_i\in\{0,1\}^k-\{0^k\}$ (that is, non-zero $k$-bit bitstrings), for $i\in[0,r)$. Plaintext is $P=S_0\in\{0,1\}^k$, ...
fgrieu's user avatar
  • 141k
10 votes
0 answers
302 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 ...
kelalaka's user avatar
  • 48.5k
10 votes
0 answers
210 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 ...
Daniel-耶稣活着's user avatar
10 votes
0 answers
151 views

Hardness of iterated squaring in Paillier 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, $...
ckamath's user avatar
  • 5,188
10 votes
0 answers
665 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 ...
rkiyanchuk's user avatar
10 votes
0 answers
137 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. ...
Mark's user avatar
  • 201
10 votes
0 answers
314 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 ...
fgrieu's user avatar
  • 141k
10 votes
0 answers
478 views

Share Conversion between Different Finite Fields

Let us have any linear secret sharing scheme (LSSS) that works on some field $Z_{p}$, where p is some prime or a power of a prime e.g., Shamir Secret Sharing, Additive secret Sharing. The problem at ...
DaWNFoRCe's user avatar
  • 872
10 votes
0 answers
813 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 ...
Myria's user avatar
  • 2,575
9 votes
0 answers
2k views

Comparison of SNARK-friendly hash algorithms MiMC7, Poseidon, Pederson?

There are some cryptographically secure hash algorithms designed to be efficient for SNARKs, STARKs and FHE. Some of them already implemented in Zcash, Zokrates and circom. The ones that I know of are:...
Habib's user avatar
  • 951
9 votes
0 answers
726 views

Can LWE be NP-hard?

Regev's reduction shows that LWE is quantumly at least as hard as CVP with an approximation factor of $n/\alpha$ for $0<\alpha<1$. But I just watched this talk which said that if $\sqrt{n/\log n}...
Sam Jaques's user avatar
  • 1,137
9 votes
0 answers
570 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 ...
Astolfo's user avatar
  • 149
9 votes
0 answers
176 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" - ...
Zachary's user avatar
  • 177
9 votes
0 answers
1k 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 ...
Raghu's user avatar
  • 255
9 votes
0 answers
249 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 ...
neubert's user avatar
  • 2,927
9 votes
0 answers
196 views

Parity of the order of a element

Given an element $g$ in a cyclic group $G$ of known order $m$ its easy to test if $g$ has even or odd order. In other words $\textrm{ord}(g) \bmod 2$ can be computed easily. In some cases where the ...
duckstar's user avatar
  • 269
9 votes
0 answers
2k 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 ...
fgrieu's user avatar
  • 141k
9 votes
0 answers
677 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/...
user794034's user avatar
8 votes
0 answers
279 views

How are the constants found in the AVX2 implementation of CRYSTALS-KYBER round 2 generated?

The post-quantum lattice-based cryptosystem CRYSTALS-KYBER which has made it to the second round of NIST PQC includes two implementations: 1) a baseline reference implementation in C and 2) an ...
caesar's user avatar
  • 315
8 votes
0 answers
225 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 ...
forest's user avatar
  • 15.3k
8 votes
0 answers
437 views

Does there exist trapdoor permutation from lattices?

It seems that the lattice functions are either surjective (SIS) or injective (LWE), due to the error that is basically intended to destroy the structure and provide security. I was wondering whether ...
user avatar
8 votes
1 answer
735 views

Zero knowledge proof for Paillier addition under multiple keys

Suppose $m_0, m_1, m_2 \in \mathbb{N}$ such that $m_0 = m_1 + m_2$, $m_i > 0$ (none of them can be 0 or lower) Under a Paillier cryptosystem, set $e_0 = E(m_0, r_0)$ for a public key $(g_0, n_0)$ ...
Guillem's user avatar
  • 81
8 votes
0 answers
190 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 ...
gojomo's user avatar
  • 221
8 votes
0 answers
200 views

Replacing signer with simulator

Assume we can prove the security of the digital signature scheme against key-only (no message) attacks. Now we want to prove security against adaptive chosen message attack. We use the random oracle ...
Student20's user avatar
  • 431
8 votes
0 answers
156 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 ...
alfred's user avatar
  • 83
8 votes
0 answers
426 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 ...
Nova's user avatar
  • 3,890

15 30 50 per page
1
2 3 4 5
95