All Questions
4,704
questions with no upvoted or accepted answers
19
votes
0
answers
465
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 ...
- 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 ...
- 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 ...
- 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, \...
- 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 ...
- 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, ...
- 161
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 ...
- 4,636
14
votes
0
answers
894
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 ...
- 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 ...
user991
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 ...
- 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.
...
- 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 ...
- 131
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 ...
- 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 ...
- 131
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 ...
- 341
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 ...
- 344
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 ...
- 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 ...
- 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 (...
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 ...
- 477
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 ...
user17887
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,...
- 10.4k
10
votes
0
answers
630
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 ...
- 797
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,...
- 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$, ...
- 141k
10
votes
0
answers
303
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 ...
- 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 ...
- 399
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, $...
- 5,188
10
votes
0
answers
666
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 ...
- 353
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.
...
- 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 ...
- 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 ...
- 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 ...
- 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:...
- 951
9
votes
0
answers
738
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}...
- 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 ...
- 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" - ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 141k
9
votes
0
answers
679
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/...
- 91
8
votes
0
answers
280
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 ...
- 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 ...
- 15.3k
8
votes
0
answers
438
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 ...
user4936
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)$
...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 3,890