More Like this

1. Traceable PRFs: Full Collusion Resistance and Active Security

   https://doi.org/10.1007/978-3-030-97121-2_16  

   Maitra, Sarasij; Wu, David J. (March 2022, International Conference on Practice and Theory of Public-Key Cryptography (PKC))

   The main goal of traceable cryptography is to protect against unauthorized redistribution of cryptographic functionalities. Such schemes provide a way to embed identities (i.e., a “mark”) within cryptographic objects (e.g., decryption keys in an encryption scheme, signing keys in a signature scheme). In turn, the tracing guarantee ensures that any “pirate device” that successfully replicates the underlying functionality can be successfully traced to the set of identities used to build the device. In this work, we study traceable pseudorandom functions (PRFs). As PRFs are the workhorses of symmetric cryptography, traceable PRFs are useful for augmenting symmetric cryptographic primitives with strong traceable security guarantees. However, existing constructions of traceable PRFs either rely on strong notions like indistinguishability obfuscation or satisfy weak security guarantees like single-key security (i.e., tracing only works against adversaries that possess a single marked key). In this work, we show how to use fingerprinting codes to upgrade a single-key traceable PRF into a fully collusion resistant traceable PRF, where security holds regardless of how many keys the adversary possesses. We additionally introduce a stronger notion of security where tracing security holds even against active adversaries that have oracle access to the tracing algorithm. In conjunction with known constructions of single-key traceable PRFs, we obtain the first fully collusion resistant traceable PRF from standard lattice assumptions. Our traceable PRFs directly imply new lattice-based secret-key traitor tracing schemes that are CCA-secure and where tracing security holds against active adversaries that have access to the tracing oracle. 

   more » « less
2. Quantum-Access-Secure Message Authentication via Blind-Unforgeability

   https://doi.org/10.1007/978-3-030-45727-3_27  

   Alagic, G; Majenz, C; Russell, A; Song, F. (January 2020, Advances in Cryptology – EUROCRYPT 2020)

   Formulating and designing authentication of classical messages in the presence of adversaries with quantum query access has been a longstanding challenge, as the familiar classical notions of unforgeability do not directly translate into meaningful notions in the quantum setting. A particular difficulty is how to fairly capture the notion of “predicting an unqueried value” when the adversary can query in quantum superposition. We propose a natural definition of unforgeability against quantum adversaries called blind unforgeability. This notion defines a function to be predictable if there exists an adversary who can use “partially blinded” oracle access to predict values in the blinded region. We support the proposal with a number of technical results. We begin by establishing that the notion coincides with EUF-CMA in the classical setting and go on to demonstrate that the notion is satisfied by a number of simple guiding examples, such as random functions and quantum-query-secure pseudorandom functions. We then show the suitability of blind unforgeability for supporting canonical constructions and reductions. We prove that the “hash-and-MAC” paradigm and the Lamport one-time digital signature scheme are indeed unforgeable according to the definition. To support our analysis, we additionally define and study a new variety of quantum-secure hash functions called Bernoulli-preserving. Finally, we demonstrate that blind unforgeability is strictly stronger than a previous definition of Boneh and Zhandry [EUROCRYPT ’13, CRYPTO ’13] and resolve an open problem concerning this previous definition by constructing an explicit function family which is forgeable yet satisfies the definition. 

   more » « less
3. Pseudorandom Isometries

   Ananth, Prabhanjan; Gulati, Aditya; Kaleoglu, Fatih; Lin, Yao-Ting (April 2024, Springer Nature)

   We introduce a new notion called Q-secure pseudorandom isometries (PRI). A pseudorandom isometry is an efficient quantum circuit that maps an n-qubit state to an (n+m)-qubit state in an isometric manner. In terms of security, we require that the output of a q-fold PRI on \rho, for \rho \in Q, for any polynomial q, should be computationally indistinguishable from the output of a q-fold Haar isometry on \rho. By fine-tuning Q, we recover many existing notions of pseudorandomness. We present a construction of PRIs and assuming post-quantum one-way functions, we prove the security of Q-secure pseudorandom isometries (PRI) for different interesting settings of Q. We also demonstrate many cryptographic applications of PRIs, including, length extension theorems for quantum pseudorandomness notions, message authentication schemes for quantum states, multi-copy secure public and private encryption schemes, and succinct quantum commitments. 

   more » « less
4. On the Multi-User Security of Short Schnorr Signatures with Preprocessing

   Blocki, Jeremiah; Lee, Seunghoon. (January 2022, Advances in Cryptology - EUROCRYPT)

   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 multi-user security in the (Shoup's) generic group model and the programmable random oracle model. We further analyze the multi-user security of key-prefixed 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 Fiat-Shamir-based signature schemes, allowing us to establish analogous results for Chaum-Pedersen signatures and Katz-Wang signatures. As a building block, we also analyze the $$1$$-out-of-$$N$$ discrete-log problem in the generic group model, with and without preprocessing. 

   more » « less
5. Minimizing Trust in Hardware Wallets with Two Factor Signatures

   Marcedone, Antonio; Pass, Rafael; shelat, abhi (January 2019, Financial Crypto)

   We introduce the notion of two-factor signatures (2FS), a generalization of a two-out-of-two threshold signature scheme in which one of the parties is a hardware token which can store a high-entropy secret, and the other party is a human who knows a low-entropy 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 two-factor 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 provably-secure 2FS schemes which produce either Schnorr signature (assuming the DLOG assumption), or EC-DSA signatures (assuming security of EC-DSA and the CDH assumption) in the Random Oracle Model, and evaluate the performance of implementations of them. Our EC-DSA based 2FS scheme can directly replace currently used hardware wallets for Bitcoin and other major cryptocurrencies to enable security against malicious hardware vendors. 

   more » « less