We revisit the problem of finding Bblocklong collisions in MerkleDamg˚ard Hash Functions in the auxiliaryinput random oracle model, in which an attacker gets a piece of Sbit advice about the random oracle and makes T oracle queries. Akshima, Cash, Drucker and Wee (CRYPTO 2020), based on the work of Coretti, Dodis, Guo and Steinberger (EUROCRYPT 2018), showed a simple attack for 2 ≤ B ≤ T (with respect to a random salt). The attack achieves advantage Ω( e ST B/2 n + T 2/2 n) where n is the output length of the random oracle. They conjectured that this attack is optimal. However, this socalled STB conjecture was only proved for B ≈ T and B = 2. Very recently, Ghoshal and Komargodski (CRYPTO 22) confirmed STB conjecture for all constant values of B, and provided an Oe(S 4T B2/2 n + T 2/2 n) bound for all choices of B. In this work, we prove an Oe((ST B/2 n)· max{1, ST2/2 n}+T 2/2 n) bound for every 2 < B < T. Our bound confirms the STB conjecture for ST2 ≤ 2 n, and is optimal up to a factor of S for ST2 > 2 n (note asmore »
On the MultiUser Security of Short Schnorr Signatures with Preprocessing
The Schnorr signature scheme is an efficient digital signature scheme with short signature lengths, i.e., $4k$bit signatures for $k$ bits of security. A Schnorr signature $\sigma$ over a group of size $p\approx 2^{2k}$ consists of a tuple $(s,e)$, where $e \in \{0,1\}^{2k}$ is a hash output and $s\in \mathbb{Z}_p$ must be computed using the secret key. While the hash output $e$ requires $2k$ bits to encode, Schnorr proposed that it might be possible to truncate the hash value without adversely impacting security.
In this paper, we prove that \emph{short} Schnorr signatures of length $3k$ bits provide $k$ bits of multiuser security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multiuser security of keyprefixed short Schnorr signatures against preprocessing attacks, showing that it is possible to obtain secure signatures of length $3k + \log S + \log N$ bits. Here, $N$ denotes the number of users and $S$ denotes the size of the hint generated by our preprocessing attacker, e.g., if $S=2^{k/2}$, then we would obtain secure $3.75k$bit signatures for groups of up to $N \leq 2^{k/4}$ users.
Our techniques easily generalize to several other FiatShamirbased signature schemes, allowing us to establish analogous more »
 Publication Date:
 NSFPAR ID:
 10322481
 Journal Name:
 Advances in Cryptology  EUROCRYPT
 Sponsoring Org:
 National Science Foundation
More Like this


We introduce the notion of twofactor signatures (2FS), a generalization of a twooutoftwo threshold signature scheme in which one of the parties is a hardware token which can store a highentropy secret, and the other party is a human who knows a lowentropy password. The security (unforgeability) property of 2FS requires that an external adversary corrupting either party (the token or the computer the human is using) cannot forge a signature. This primitive is useful in contexts like hardware cryptocurrency wallets in which a signature conveys the authorization of a transaction. By the above security property, a hardware wallet implementing a twofactor signature scheme is secure against attacks mounted by a malicious hardware vendor; in contrast, all currently used wallet systems break under such an attack (and as such are not secure under our definition). We construct efficient provablysecure 2FS schemes which produce either Schnorr signature (assuming the DLOG assumption), or ECDSA signatures (assuming security of ECDSA and the CDH assumption) in the Random Oracle Model, and evaluate the performance of implementations of them. Our ECDSA based 2FS scheme can directly replace currently used hardware wallets for Bitcoin and other major cryptocurrencies to enable security against malicious hardware vendors.

One of the primary research challenges in AttributeBased Encryption (ABE) is constructing and proving cryptosystems that are adaptively secure. To date the main paradigm for achieving adaptive security in ABE is dual system encryption. However, almost all such solutions in bilinear groups rely on (variants of) either the subgroup decision problem over composite order groups or the decision linear assumption. Both of these assumptions are decisional rather than search assumptions and the target of the assumption is a source or bilinear group element. This is in contrast to earlier selectively secure ABE systems which can be proven secure from either the decisional or search Bilinear DiffieHellman assumption. In this work we make progress on closing this gap by giving a new ABE construction for the subset functionality and prove security under the Search Bilinear DiffieHellman assumption. We first provide a framework for proving adaptive security in AttributeBased Encryption systems. We introduce a concept of ABE with deletable attributes where any party can take a ciphertext encrypted under the attribute string and modify it into a ciphertext encrypted under any string where is derived by replacing any bits of with symbols (i.e. ``deleting" attributes of ). The semantics of the systemmore »

The epsilonapproximate degree, deg_epsilon(f), of a Boolean function f is the least degree of a realvalued polynomial that approximates f pointwise to within epsilon. A sound and complete certificate for approximate degree being at least k is a pair of probability distributions, also known as a dual polynomial, that are perfectly kwise indistinguishable, but are distinguishable by f with advantage 1  epsilon. Our contributions are:  We give a simple, explicit new construction of a dual polynomial for the AND function on n bits, certifying that its epsilonapproximate degree is Omega (sqrt{n log 1/epsilon}). This construction is the first to extend to the notion of weighted degree, and yields the first explicit certificate that the 1/3approximate degree of any (possibly unbalanced) readonce DNF is Omega(sqrt{n}). It draws a novel connection between the approximate degree of AND and anticoncentration of the Binomial distribution.  We show that any pair of symmetric distributions on nbit strings that are perfectly kwise indistinguishable are also statistically Kwise indistinguishable with at most K^{3/2} * exp (Omega (k^2/K)) error for all k < K <= n/64. This bound is essentially tight, and implies that any symmetric function f is a reconstruction function with constant advantagemore »

We investigate the security of the QUIC record layer, as standardized by the IETF in draft version 30. This version features major differences compared to Google's original protocol and prior IETF drafts. We model packet and header encryption, which uses a custom construction for privacy. To capture its goals, we propose a security definition for authenticated encryption with semiimplicit nonces. We show that QUIC uses an instance of a generic construction parameterized by a standard AEADsecure scheme and a PRFsecure cipher. We formalize and verify the security of this construction in F*. The proof uncovers interesting limitations of nonce confidentiality, due to the malleability of short headers and the ability to choose the number of least significant bits included in the packet counter. We propose improvements that simplify the proof and increase robustness against strong attacker models. In addition to the verified security model, we also give concrete functional specification for the record layer, and prove that it satisfies important functionality properties (such as successful decryption of encrypted packets) after fixing more errors in the draft. We then provide a highperformance implementation of the record layer that we prove to be memory safe, correct with respect to our concrete specificationmore »