86 results sorted by ID
Possible spell-corrected query: deterministic signature
Revisiting the Security of Fiat-Shamir Signature Schemes under Superposition Attacks
Quan Yuan, Chao Sun, Tsuyoshi Takagi
Public-key cryptography
The Fiat-Shamir transformation is a widely employed technique in constructing signature schemes, known as Fiat-Shamir signature schemes (FS-SIG), derived from secure identification (ID) schemes. However, the existing security proof only takes into account classical signing queries and does not consider superposition attacks, where the signing oracle is quantum-accessible to the adversaries. Alagic et al. proposed a security model called blind unforgeability (BUF, Eurocrypt'20), regarded as a...
Arctic: Lightweight and Stateless Threshold Schnorr Signatures
Chelsea Komlo, Ian Goldberg
Public-key cryptography
Threshold Schnorr signatures are seeing increased adoption in practice, and offer practical defenses against single points of failure. However, one challenge with existing randomized threshold Schnorr signature schemes is that signers must carefully maintain secret state across signing rounds, while also ensuring that state is deleted after a signing session is completed. Failure to do so will result in a fatal key-recovery attack by re-use of nonces.
While deterministic threshold...
A Cautionary Note: Side-Channel Leakage Implications of Deterministic Signature Schemes
Hermann Seuschek, Johann Heyszl, Fabrizio De Santis
Two recent proposals by Bernstein and Pornin emphasize the use of deterministic signatures in DSA and its elliptic curve-based variants. Deterministic signatures derive the required ephemeral key value in a deterministic manner from the message to be signed and the secret key instead of using random number generators. The goal is to prevent severe security issues, such as the straight-forward secret key recovery from low quality random numbers. Recent developments have raised skepticism...
Exponent-VRFs and Their Applications
Dan Boneh, Iftach Haitner, Yehuda Lindell
Public-key cryptography
Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF, which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the...
Stateless Deterministic Multi-Party EdDSA Signatures with Low Communication
Qi Feng, Kang Yang, Kaiyi Zhang, Xiao Wang, Yu Yu, Xiang Xie, Debiao He
Cryptographic protocols
EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature based on Edwards curves, and enjoys the benefit of statelessly and deterministically deriving nonces (i.e., it does not require reliable source of randomness or state continuity). Recently, NIST calls for multi-party threshold EdDSA signatures in one mode of deriving nonce statelessly and deterministically and verifying such derivation via zero-knowledge (ZK) proofs. Multi-party full-threshold EdDSA...
Correction Fault Attacks on Randomized CRYSTALS-Dilithium
Elisabeth Krahmer, Peter Pessl, Georg Land, Tim Güneysu
Attacks and cryptanalysis
After NIST’s selection of Dilithium as the primary future standard for quantum-secure digital signatures, increased efforts to understand its implementation security properties are required to enable widespread adoption on embedded devices. Concretely, there are still many open questions regarding the susceptibility of Dilithium to fault attacks. This is especially the case for Dilithium’s randomized (or hedged) signing mode, which, likely due to devastating implementation attacks on the...
Efficient Post-Quantum Secure Deterministic Threshold Wallets from Isogenies
Poulami Das, Andreas Erwig, Michael Meyer, Patrick Struck
Cryptographic protocols
Cryptocurrency networks crucially rely on digital signature schemes, which are used as an authentication mechanism for transactions. Unfortunately, most major cryptocurrencies today, including Bitcoin and Ethereum, employ signature schemes that are susceptible to quantum adversaries, i.e., an adversary with access to a quantum computer can forge signatures and thereby spend coins of honest users. In cryptocurrency networks, signature schemes are typically not executed in isolation, but...
Multi-Signatures for Ad-hoc and Privacy-Preserving Group Signing
Anja Lehmann, Cavit Özbay
Public-key cryptography
Multi-signatures allow to combine individual signatures from different signers on the same message into a short aggregated signature. Newer schemes further allow to aggregate the individual public keys, such that the combined signature gets verified against a short aggregated key. This makes them a versatile alternative to threshold or distributed signatures: the aggregated key can serve as group key, and signatures under that key can only be computed with the help of all signers. What makes...
LedgerLocks: A Security Framework for Blockchain Protocols Based on Adaptor Signatures
Erkan Tairi, Pedro Moreno-Sanchez, Clara Schneidewind
Cryptographic protocols
The scalability and interoperability challenges in current cryptocurrencies have motivated the design of cryptographic protocols that enable efficient applications on top and across widely used cryptocurrencies such as Bitcoin or Ethereum. Examples of such protocols include (virtual) payment channels, atomic swaps, oracle-based contracts, deterministic wallets, and coin mixing services. Many of these protocols are built upon minimal core functionalities supported by a wide range of...
Almost Tight Multi-User Security under Adaptive Corruptions from LWE in the Standard Model
Shuai Han, Shengli Liu, Zhedong Wang, Dawu Gu
Public-key cryptography
In this work, we construct the first digital signature (SIG) and public-key encryption (PKE) schemes with almost tight multi-user security under adaptive corruptions based on the learning-with-errors (LWE) assumption in the standard model. Our PKE scheme achieves almost tight IND-CCA security and our SIG scheme achieves almost tight strong EUF-CMA security, both in the multi-user setting with adaptive corruptions. The security loss is quadratic in the security parameter, and independent of...
From MLWE to RLWE: A Differential Fault Attack on Randomized & Deterministic Dilithium
Mohamed ElGhamrawy, Melissa Azouaoui, Olivier Bronchain, Joost Renes, Tobias Schneider, Markus Schönauer, Okan Seker, Christine van Vredendaal
Attacks and cryptanalysis
The post-quantum digital signature scheme CRYSTALS-Dilithium has been recently selected by the NIST for standardization. Implementing CRYSTALS-Dilithium, and other post-quantum cryptography schemes, on embedded devices raises a new set of challenges, including ones related to performance in terms of speed and memory requirements, but also related to side-channel and fault injection attacks security. In this work, we investigated the latter and describe a differential fault attack on the...
$\mathsf{Skye}$: An Expanding PRF based Fast KDF and its Applications
Amit Singh Bhati, Antonin Dufka, Elena Andreeva, Arnab Roy, Bart Preneel
Secret-key cryptography
A Key Derivation Function (KDF) generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF, the most deployed KDF in practice, is based on the extract-then-expand paradigm. It is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging.
HKDF is a generic KDF for general input sources and thus is not optimized for...
Compact Lattice Gadget and Its Applications to Hash-and-Sign Signatures
Yang Yu, Huiwen Jia, Xiaoyun Wang
Public-key cryptography
Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions.
For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based...
hinTS: Threshold Signatures with Silent Setup
Sanjam Garg, Abhishek Jain, Pratyay Mukherjee, Rohit Sinha, Mingyuan Wang, Yinuo Zhang
Public-key cryptography
We propose hinTS --- a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features:
\begin{itemize}
\item A {\em silent setup} process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys.
\item Support for {\em dynamic} choice of thresholds and signers, after the silent setup, without further interaction.
\item Support for {\em general}...
A Differential Fault Attack against Deterministic Falcon Signatures
Sven Bauer, Fabrizio De Santis
Attacks and cryptanalysis
We describe a fault attack against the deterministic variant of the Falcon signature scheme. It is the first fault attack that exploits specific properties of deterministic Falcon. The attack works under a very liberal and realistic single fault random model. The main idea is to inject a fault into the pseudo-random generator of the pre-image trapdoor sampler, generate different signatures for the same input, find reasonably short lattice vectors this way, and finally use lattice reduction...
A Map of Witness Maps: New Definitions and Connections
Suvradip Chakraborty, Manoj Prabhakaran, Daniel Wichs
Public-key cryptography
A \emph{witness map} deterministically maps a witness $w$ of some NP statement $x$ into computationally sound proof that $x$ is true, with respect to a public common reference string (CRS). In other words, it is a deterministic, non-interactive, computationally sound proof system in the CRS model. A \emph{unique witness map} (UWM) ensures that for any fixed statement $x$, the witness map should output the same \emph{unique} proof for $x$, no matter what witness $w$ it is applied to. More...
BIP32-Compatible Threshold Wallets
Poulami Das, Andreas Erwig, Sebastian Faust, Julian Loss, Siavash Riahi
Cryptographic protocols
Cryptographic wallets have become an essential tool to secure users' secret keys and consequently their funds in Blockchain networks. The most prominent wallet standard that is widely adopted in practice is the BIP32 specification. This standard specifies so-called hierarchical deterministic wallets, which are organized in a tree-like structure such that each node in the tree represents a wallet instance and such that a parent node can derive a new child node in a deterministic fashion....
Two-Round Stateless Deterministic Two-Party Schnorr Signatures From Pseudorandom Correlation Functions
Yashvanth Kondi, Claudio Orlandi, Lawrence Roy
Cryptographic protocols
Schnorr signatures are a popular choice due to their simplicity, provable security, and linear structure that enables relatively easy threshold signing protocols. The deterministic variant of Schnorr (where the nonce is derived in a stateless manner using a PRF from the message and a long term secret) is widely used in practice since it mitigates the threats of a faulty or poor randomness generator (which in Schnorr leads to catastrophic breaches of security). Unfortunately, threshold...
Post-Quantum Secure Deterministic Wallet: Stateless, Hot/Cold Setting, and More Secure
Mingxing Hu
Public-key cryptography
Since the invention of Bitcoin, cryptocurrencies have gained
huge popularity. Crypto wallet, as the tool to store and manage the
cryptographic keys, is the primary entrance for the public to access
cryptocurrency funds. Deterministic wallet is an advanced wallet mech-
anism that has been proposed to achieve some appealing virtues, such
as low-maintenance, easy backup and recovery, supporting functionali-
ties required by cryptocurrencies, and so on. But deterministic wallets
still...
DME: a full encryption, signature and KEM multivariate public key cryptosystem
Ignacio Luengo, Martín Avendaño
Public-key cryptography
DME is a multivariate public key cryptosystem based on the composition of linear and exponential maps that allow the polynomials of the public key to be of a very high degree. A previous version of DME was presented to the NIST call (in the KEM category). The new version of DME adds one or two extra rounds of exponentials to the original two rounds. With this setting the composition gives a deterministic trapdoor one way permutation, which can be combined with an OAEP padding scheme for KEM...
Deterministic Wallets for Adaptor Signatures
Andreas Erwig, Siavash Riahi
Cryptographic protocols
Adaptor signatures are a new cryptographic primitive that binds the authentication of a message to the revelation of a secret value. In recent years, this primitive has gained increasing popularity both in academia and practice due to its versatile use-cases in different Blockchain applications such as atomic swaps and payment channels. The security of these applications, however, crucially relies on users storing and maintaining the secret values used by adaptor signatures in a secure...
Protecting Dilithium against Leakage: Revisited Sensitivity Analysis and Improved Implementations
Melissa Azouaoui, Olivier Bronchain, Gaëtan Cassiers, Clément Hoffmann, Yulia Kuzovkova, Joost Renes, Markus Schönauer, Tobias Schneider, François-Xavier Standaert, Christine van Vredendaal
Implementation
CRYSTALS-Dilithium has been selected by the NIST as the new stan-
dard for post-quantum digital signatures. In this work, we revisit the side-channel
countermeasures of Dilithium in three directions. First, we improve its sensitivity
analysis by classifying intermediate computations according to their physical security
requirements. Second, we provide improved gadgets dedicated to Dilithium, taking
advantage of recent advances in masking conversion algorithms. Third, we combine
these...
Efficient Zero-Knowledge Proofs on Signed Data with Applications to Verifiable Computation on Data Streams
Dario Fiore, Ida Tucker
Cryptographic protocols
We study the problem of privacy-preserving proofs on streamed authenticated data. In this setting, a server receives a continuous stream of data from a trusted data provider, and is requested to prove computations over the data to third parties in a correct and private way. In particular, the third party learns no information on the data beyond the validity of claimed results. A challenging requirement here, is that the third party verifies the validity with respect to the specific data...
PLUME: An ECDSA Nullifier Scheme for Unique Pseudonymity within Zero Knowledge Proofs
Aayush Gupta, Kobi Gurkan
Cryptographic protocols
ZK-SNARKs (Zero Knowledge Succinct Noninteractive ARguments of Knowledge) are one of the most promising new applied cryptography tools: proofs allow anyone to prove a property about some data, without revealing that data. Largely spurred by the adoption of cryptographic primitives in blockchain systems, ZK-SNARKs are rapidly becoming computationally practical in real-world settings, shown by i.e. tornado.cash and rollups. These have enabled ideation for new identity applications based on...
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
Lalita Devadas, Rishab Goyal, Yael Kalai, Vinod Vaikuntanathan
Cryptographic protocols
We present a rate-$1$ construction of a publicly verifiable non-interactive argument system for batch-$\mathsf{NP}$ (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of $k$ NP statements each with an $m$-bit witness, has size $m + \mathsf{poly}(\lambda,\log k)$.
In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size $m \cdot \mathsf{poly}(\lambda,\log k)$ (Choudhuri, Jain, and Jin, STOC 2021,...
The inspection model for zero-knowledge proofs and efficient Zerocash with secp256k1 keys
Huachuang Sun, Haifeng Sun, Kevin Singh, Akhil Sai Peddireddy, Harshad Patil, Jianwei Liu, Weikeng Chen
Applications
Proving discrete log equality for groups of the same order is addressed by Chaum and Pedersen's seminal work. However, there has not been a lot of work in proving discrete log equality for groups of different orders.
This paper presents an efficient solution, which leverages a technique we call delegated Schnorr. The discovery of this technique is guided by a design methodology that we call the inspection model, and we find it useful for protocol designs.
We show two...
Fiddling the Twiddle Constants - Fault Injection Analysis of the Number Theoretic Transform
Prasanna Ravi, Bolin Yang, Shivam Bhasin, Fan Zhang, Anupam Chattopadhyay
Attacks and cryptanalysis
In this work, we present the first fault injection analysis of the Number Theoretic Transform (NTT). The NTT is an integral computation unit, widely used for polynomial multiplication in several structured lattice-based key encapsulation mechanisms (KEMs) and digital signature schemes. We identify a critical single fault vulnerability in the NTT, which severely reduces the entropy of its output. This in turn enables us to perform a wide-range of attacks applicable to lattice-based KEMs as...
Secure Hierarchical Deterministic Wallet Supporting Stealth Address
Xin Yin, Zhen Liu, Guomin Yang, Guoxing Chen, Haojin Zhu
Public-key cryptography
Over the past decade, cryptocurrency has been undergoing a rapid development. Digital wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency assets.
Hierarchical Deterministic Wallet (HDW), proposed in Bitcoin Improvement Proposal 32 (BIP32), has attracted much attention and been widely used in the community, due to its virtues such as easy backup/recovery, convenient cold-address management, and supporting trust-less...
Attacks Against White-Box ECDSA and Discussion of Countermeasures - A Report on the WhibOx Contest 2021
Sven Bauer, Hermann Drexler, Maximilian Gebhardt, Dominik Klein, Friederike Laus, Johannes Mittmann
Public-key cryptography
This paper deals with white-box implementations of the Elliptic Curve Digital Signature Algorithm (ECDSA): First, we consider attack paths to break such implementations. In particular, we provide a systematic overview of various fault attacks, to which ECDSA white-box implementations are especially susceptible. Then, we propose different mathematical countermeasures, mainly based on masking/blinding of sensitive variables, in order to prevent or at least make such attacks more difficult. We...
Improved Straight-Line Extraction in the Random Oracle Model With Applications to Signature Aggregation
Yashvanth Kondi, abhi shelat
Cryptographic protocols
The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover $P^*(x)$ on some theorem $x$, is able to produce a witness $w$ for $x$ with roughly the same probability that $P^*$ produces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable...
Blind accumulators for e-voting
Sergey Agievich
Public-key cryptography
We present a novel cryptographic primitive, blind accumulator, aimed at constructing e-voting systems. Blind accumulators collect private keys of eligible voters in a decentralized manner not getting information about the keys. Once the accumulation is complete, a voter processes the resulting accumulator deriving a public key that refers to the private key previously added by this voter. Public keys are derived deterministically and can therefore stand as fixed voter pseudonyms. The voter...
On the security of ECDSA with additive key derivation and presignatures
Jens Groth, Victor Shoup
Public-key cryptography
Two common variations of ECDSA signatures are additive key derivation and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With...
The Exact Security of BIP32 Wallets
Poulami Das, Andreas Erwig, Sebastian Faust, Julian Loss, Siavash Riahi
Cryptographic protocols
In many cryptocurrencies, the problem of key management has become one of the most fundamental security challenges. Typically, keys are kept in designated schemes called 'Wallets', whose main purpose is to store these keys securely. One such system is the BIP32 wallet (Bitcoin Improvement Proposal 32), which since its introduction in 2012 has been adopted by countless Bitcoin users and is one of the most frequently used wallet system today. Surprisingly, very little is known about the...
Primary Elements in Cyclotomic Fields with Applications to Power Residue Symbols, and More
Eric Brier, Rémi Géraud-Stewart, Marc Joye, David Naccache
Foundations
Higher-order power residues have enabled the construction of numerous public-key encryption schemes, authentication schemes, and digital signatures. Their explicit characterization is however challenging; an algorithm of Caranay and Scheidler computes $p$-th power residue symbols, with $p \le 13$ an odd prime, provided that primary elements in the corresponding cyclotomic field can be efficiently found.
In this paper, we describe a new, generic algorithm to compute primary elements in...
Threshold Schnorr with Stateless Deterministic Signing from Standard Assumptions
François Garillot, Yashvanth Kondi, Payman Mohassel, Valeria Nikolaenko
Cryptographic protocols
Schnorr's signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major attack vector in practice. Sources of randomness in deployments are frequently either unreliable, or require state continuity, i.e. reliable fresh state resilient to rollbacks. State continuity is a notoriously difficult guarantee to achieve in practice, due to system crashes caused by software errors,...
History Binding Signature
Shlomi Dolev, Matan Liber
Cryptographic protocols
Digital signatures are used to verify the authenticity of digital messages, that is, to know with a high level of certainty, that a digital message was created by a known sender and was not altered in any way.
This is usually achieved by using asymmetric cryptography, where a secret key is used by the signer, and the corresponding public key is used by those who wish to verify the signed data.
In many use-cases, such as blockchain, the history and order of the signed data, thus the...
Deterministic Wallets in a Quantum World
Nabil Alkeilani Alkadri, Poulami Das, Andreas Erwig, Sebastian Faust, Juliane Krämer, Siavash Riahi, Patrick Struck
Cryptographic protocols
Most blockchain solutions are susceptible to quantum attackers as they rely on cryptography that is known to be insecure in the presence of quantum adversaries. In this work we advance the study of quantum-resistant blockchain solutions by giving a quantum-resistant construction of a deterministic wallet scheme. Deterministic wallets are frequently used in practice in order to secure funds by storing the sensitive secret key on a so-called cold wallet that is not connected to the Internet....
MuSig-DN: Schnorr Multi-Signatures with Verifiably Deterministic Nonces
Jonas Nick, Tim Ruffing, Yannick Seurin, Pieter Wuille
Public-key cryptography
MuSig is a multi-signature scheme for Schnorr signatures, which supports key aggregation and is secure in the plain public key model. Standard derandomization techniques for discrete logarithm-based signatures such as RFC 6979, which make the signing procedure immune to catastrophic failures in the randomness generation, are not applicable to multi-signatures as an attacker could trick an honest user into producing two different partial signatures with the same randomness, which would reveal...
Does Fiat-Shamir Require a Cryptographic Hash Function?
Yilei Chen, Alex Lombardi, Fermi Ma, Willy Quach
Foundations
The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently...
Lattice-based Fault Attacks on Deterministic Signature Schemes of ECDSA and EdDSA
Weiqiong Cao, Hongsong Shi, Hua Chen, Jiazhe Chen, Limin Fan, Wenling Wu
Public-key cryptography
The deterministic ECDSA and EdDSA signature schemes have found plenty of applications since their publication and standardization. Their theoretical security can be guaranteed under certain well-designed models, while their practical risks from the flaw of random number generators can be mitigated since no randomness is required by the algorithms anymore. But the situation is not completely optimistic, since it has been gradually found that delicately designed fault attacks can threaten the...
Thresholdizing HashEdDSA: MPC to the Rescue
Charlotte Bonte, Nigel P. Smart, Titouan Tanguy
Public-key cryptography
Following recent comments in a NIST document related to threshold cryptographic standards, we examine the case of thresholdizing the HashEdDSA signature scheme. This is a deterministic signature scheme based on Edwards elliptic curves. Unlike DSA, it has a Schnorr like signature equation, which is an advantage for threshold implementations, but it has the disadvantage of having the ephemeral secret obtained by hashing the secret key and the message. We show that one can obtain relatively...
Witness Maps and Applications
Suvradip Chakraborty, Manoj Prabhakaran, Daniel Wichs
We introduce the notion of Witness Maps as a cryptographic notion of
a proof system. A Unique Witness Map (UWM) deterministically maps all
witnesses for an $\mathbf{NP}$ statement to a single representative witness, resulting
in a computationally sound, deterministic-prover, non-interactive witness
independent proof system. A relaxation of UWM, called Compact Witness Map
(CWM), maps all the witnesses to a small number of witnesses, resulting in a
``lossy'' deterministic-prover,...
Auditable Asymmetric Password Authenticated Public Key Establishment
Antonio Faonio, Maria Isabel Gonzalez Vasco, Claudio Soriente, Hien Thi Thu Truong
Public-key cryptography
Non-repudiation of messages generated by users is a desirable feature in a number of applications ranging from online banking to IoT scenarios. However, it requires certified public keys and usually results in poor usability as a user must carry around his certificate (e.g., in a smart-card) or must install it in all of his devices. A user-friendly alternative, adopted by several companies and national administrations, is to have a ``cloud-based'' PKI. In a nutshell, each user has a PKI...
Threshold Multi-Signature with an Offline Recovery Party
Riccardo Longo, Alessio Meneghetti, Massimiliano Sala
Cryptographic protocols
Key custody is a sensitive aspect of cryptocurrencies.
The employment of a custodian service together with threshold-multi-party signatures helps to manage secret keys more safely and effectively, e.g. allowing the recovery of crypto-assets when users lose their own keys.
Advancing from a protocol by Gennaro et al. we propose a protocol with two main properties.
First it allows the recovery party to remain offline during the enrollment of any user, solving a real-life problem of maintaining...
On the Security of RSA-PSS in the Wild
Saqib A. Kakvi
Cryptographic protocols
The RSA Probabilistic Signature Scheme (RSA-PSS) due to Bellare and Rogaway (EUROCRYPT 1996) is a widely deployed signature scheme. In particular it is a suggested replacement for the deterministic RSA Full Domain Hash (RSA-FDH) by Bellare and Rogaway (ACM CCS 1993) and PKCS#1 v1.5 (RFC 2313), as it can provide stronger security guarantees. It has since been shown by Kakvi and Kiltz (EUROCRYPT 2012, Journal of Cryptology 2018) that RSA-FDH provides similar security to that of RSA-PSS, also...
Modeling Memory Faults in Signature and Authenticated Encryption Schemes
Marc Fischlin, Felix Günther
Memory fault attacks, inducing errors in computations, have been an ever-evolving threat to cryptographic schemes since their discovery for cryptography by Boneh et al. (Eurocrypt 1997). Initially requiring physical tampering with hardware, the software-based rowhammer attack put forward by Kim et al. (ISCA 2014) enabled fault attacks also through malicious software running on the same host machine. This led to concerning novel attack vectors, for example on deterministic signature schemes,...
Security of Hedged Fiat-Shamir Signatures under Fault Attacks
Diego F. Aranha, Claudio Orlandi, Akira Takahashi, Greg Zaverucha
Public-key cryptography
Deterministic generation of per-signature randomness has been a widely accepted solution to mitigate the catastrophic risk of randomness failure in Fiat--Shamir type signature schemes. However, recent studies have practically demonstrated that such de-randomized schemes, including EdDSA, are vulnerable to differential fault attacks, which enable adversaries to recover the entire secret signing key, by artificially provoking randomness reuse or corrupting computation in other ways. In order...
Unique Rabin-Williams Signature Scheme Decryption
Lynn Margaret Batten, Hugh Cowie Williams
Public-key cryptography
Abstract. The extremely efficient Rabin-Williams signature scheme relies on decryption of a quadratic equation in order to retrieve the original message. Customarily, square roots are found using the Chinese Remainder Theorem. This can be done in polynomial time, but generally produces four options for the correct message which must be analyzed to determine the correct one. This paper resolves the problem of efficient deterministic decryption to the correct message modulo $p^2q$ by...
Exploiting Determinism in Lattice-based Signatures - Practical Fault Attacks on pqm4 Implementations of NIST candidates
Prasanna Ravi, Mahabir Prasad Jhanwar, James Howe, Anupam Chattopadhyay, Shivam Bhasin
Public-key cryptography
In this paper, we analyze the implementation level fault vulnerabilities of deterministic lattice-based
signature schemes. In particular, we extend the practicality of skip-addition fault
attacks through exploitation of determinism in certain variants of Dilithium (Deterministic variant) and qTESLA signature scheme (originally submitted deterministic version), which are two leading candidates for the NIST standardization of post-quantum cryptography. We show that single targeted faults...
On the Security of Lattice-based Fiat-Shamir Signatures in the Presence of Randomness Leakage
Yuejun Liu, Yongbin Zhou, Shuo Sun, Tianyu Wang, Rui Zhang, Jingdian Ming
Implementation
Leakages during the signing process, including partial key exposure and partial (or complete) randomness exposure, may be devastating for the security of digital signatures. In this work, we investigate the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage. To this end, we present a generic key recovery attack that relies on minimum leakage of randomness, and then theoretically connect it to a variant of Integer-LWE (ILWE) problem. The ILWE problem,...
Arcula: A Secure Hierarchical Deterministic Wallet for Multi-asset Blockchains
Adriano Di Luzio, Danilo Francati, Giuseppe Ateniese
Applications
This work presents Arcula, a new design for hierarchical deterministic wallets that brings identity-based addresses to the blockchain. Arcula is built on top of provably secure cryptographic primitives. It generates all its cryptographic secrets from a user-provided seed and enables the derivation of new public keys based on the identities of users, without requiring any secret information. Unlike other wallets, it achieves all these properties while being secure against privilege...
Robust and Scalable Consensus for Sharded Distributed Ledgers
Eleftherios Kokoris-Kogias
Applications
ByzCoin, a promising alternative of Bitcoin, is a scalable consensus protocol used as a building block of many research and enterprise-level decentralized systems. In this paper, we show that ByzCoin is unsuitable for deployment in an anopen, adversarial network and instead introduceMOTOR. MOTORis designed as a secure, robust, and scalable consensus suitable for permissionless sharded blockchains. MOTORachieves these properties by making four key design choices: (a) it prioritizes robustness...
Minicrypt Primitives with Algebraic Structure and Applications
Navid Alamati, Hart Montgomery, Sikhar Patranabis, Arnab Roy
Foundations
Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives:
• One-Way Function (OWF)
• Weak Unpredictable Function (wUF)
• Weak Pseudorandom...
Lattice-Based Signature from Key Consensus
Leixiao Cheng, Boru Gong, Yunlei Zhao
Public-key cryptography
Given the current research status in lattice-based cryptography, it is commonly suggested that lattice-based signature could be subtler and harder to achieve. Among them, Dilithium is one of the most promising signature candidates for the post-quantum era, for its simplicity, efficiency, small public key size, and resistance against side channel attacks. The design of Dilithium is based on a list of pioneering works (e.g.,[VL09,VL12,BG14]), and has very remarkable performance by very...
Key-Insulated and Privacy-Preserving Signature Scheme with Publicly Derived Public Key
Zhen Liu, Guomin Yang, Duncan S. Wong, Khoa Nguyen, Huaxiong Wang
Since the introduction of Bitcoin in 2008, cryptocurrency has been undergoing a quick and explosive development. At the same time, privacy protection, one of the key merits of cryptocurrency, has attracted much attention by the community.
A deterministic wallet algorithm and a stealth address algorithm have been widely adopted in the community, due to their virtues on functionality and privacy-protection, which come from a key derivation mechanism that an arbitrary number of derived keys can...
On the Security of the PKCS#1 v1.5 Signature Scheme
Tibor Jager, Saqib A. Kakvi, Alexander May
Foundations
The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the...
Attribute-Based Signatures for Unbounded Languages from Standard Assumptions
Yusuke Sakai, Shuichi Katsumata, Nuttapong Attrapadung, Goichiro Hanaoka
Attribute-based signature (ABS) schemes are advanced signature schemes
that simultaneously provide fine-grained authentication while protecting
privacy of the signer. Previously known expressive ABS schemes support
either the class of deterministic finite automata and circuits from
standard assumptions or Turing machines from the existence of
indistinguishability obfuscations.
In this paper, we propose the first ABS scheme for a very general policy
class, all deterministic Turin machines,...
Reducing Complexity of Pairing Comparisons using Polynomial Evaluation
Adam Bobowski, Marcin Słowik
Foundations
We propose a new method for reducing complexity of the pairing comparisons based on polynomials. Thought the construction introduces uncertainty into (usually deterministic) checks, it is easily quantifiable and in most cases extremely small. The application to CL-LRSW signature verification under n messages and group order q allows to reduce the number of computed pairings from 4n down to just 4, while the introduced uncertainty is just (2n-1)/q.
Differential Fault Attacks on Deterministic Lattice Signatures
Leon Groot Bruinderink, Peter Pessl
Implementation
In this paper, we extend the applicability of differential fault attacks to lattice-based cryptography. We show how two deterministic lattice-based signature schemes, Dilithium and qTESLA, are vulnerable to such attacks. In particular, we demonstrate that single random faults can result in a nonce-reuse scenario which allows key recovery. We also expand this to fault-induced partial nonce-reuse attacks, which do not corrupt the validity of the computed signatures and thus are harder to...
Attacking Deterministic Signature Schemes using Fault Attacks
Damian Poddebniak, Juraj Somorovsky, Sebastian Schinzel, Manfred Lochter, Paul Rösler
Public-key cryptography
Many digital signature schemes rely on random numbers that are unique and non-predictable per signature. Failures of random number generators may have catastrophic effects such as compromising private signature keys. In recent years, many widely-used cryptographic technologies adopted deterministic signature schemes because they are presumed to be safer to implement.
In this paper, we analyze the security of deterministic ECDSA and EdDSA signature schemes and show that the elimination of...
Breaking Ed25519 in WolfSSL
Niels Samwel, Lejla Batina, Guido Bertoni, Joan Daemen, Ruggero Susella
Public-key cryptography
Ed25519 is an instance of the Elliptic Curve based signature scheme EdDSA that was recently introduced to solve an inconvenience of the more established ECDSA. Namely, both schemes require the generation of a random value (scalar of the ephemeral key pair) during the signature generation process and the secrecy of this random value is critical for security: knowledge of one such a random value, or partial knowledge of a series of them, allows reconstructing the signer's private key. In ECDSA...
Differential Attacks on Deterministic Signatures
Christopher Ambrose, Joppe W. Bos, Björn Fay, Marc Joye, Manfred Lochter, Bruce Murray
Public-key cryptography
Deterministic signature schemes are becoming more popular, as illustrated by the deterministic variant of ECDSA and the popular EdDSA scheme, since eliminating the need for high-quality randomness might have some advantages in certain use-cases. In this paper we outline a range of differential fault attacks and a differential power analysis attack against such deterministic schemes. This shows, contrary to some earlier works, that such signature schemes are not naturally protected against...
A Concrete Treatment of Fiat-Shamir Signatures in the Quantum Random-Oracle Model
Eike Kiltz, Vadim Lyubashevsky, Christian Schaffner
Public-key cryptography
The Fiat-Shamir transform is a technique for combining a hash function and an identification scheme to produce a digital signature scheme. The resulting scheme is known to be secure in the random oracle model (ROM), which does not, however, imply security in the scenario where the adversary also has quantum access to the oracle. The goal of this current paper is to create a generic framework for constructing tight reductions in the QROM from underlying hard problems to Fiat-Shamir...
Clarifying the subset-resilience problem
Jean-Philippe Aumasson, Guillaume Endignoux
Public-key cryptography
We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity...
Non-Malleable Functions and Their Applications
Yu Chen, Baodong Qin, Jiang Zhang, Yi Deng, Sherman S. M. Chow
Foundations
We formally study ``non-malleable functions'' (NMFs), a general cryptographic primitive which simplifies and relaxes ``non-malleable one-way/hash functions'' (NMOWHFs) introduced by Boldyreva et al. (Asiacrypt 2009) and refined by Baecher et al. (CT-RSA 2010). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs.
We mainly follow Baecher et al. to formalize a game-based definition for NMFs. Roughly, a function $f$ is non-malleable if...
Accelerating Bliss: the geometry of ternary polynomials
Léo Ducas
Public-key cryptography
The signature scheme Bliss proposed by Ducas, Durmus, Lepoint and Lyubashevsky at Crypto’13, is currently the most compact and efficient lattice-based signature scheme that is provably secure under lattice assumptions. It does compare favourably with the standardized schemes RSA and ECDSA on both Software and Hardware.
In this work, we introduce a new technique that improves the above scheme, offering an acceleration factor up to 2.8, depending on the set of parameters.
Namely, we improve...
Making RSA-PSS Provably Secure Against Non-Random Faults
Gilles Barthe, François Dupressoir, Pierre-Alain Fouque, Benjamin Grégoire, Mehdi Tibouchi, Jean-Christophe Zapalowicz
Public-key cryptography
RSA–CRT is the most widely used implementation for RSA signatures. However, deterministic and many probabilistic RSA signatures based on CRT are vulnerable to fault attacks. Nevertheless, Coron and Mandal (Asiacrypt 2009) show that the randomized PSS padding protects RSA signatures against random faults. In contrast, Fouque et al. (CHES 2012) show that PSS padding does not protect against certain non-random faults that can be injected in widely used implementations based on the Montgomery...
On the Lossiness of the Rabin Trapdoor Function
Yannick Seurin
Public-key cryptography
Lossy trapdoor functions, introduced by Peikert and Waters (STOC~'08), are functions that can be generated in two indistinguishable ways: either the function is injective, and there is a trapdoor to invert it, or the function is lossy, meaning that the size of its range is strictly smaller than the size of its domain. Kakvi and Kiltz (EUROCRYPT 2012) proved that the Full Domain Hash signature scheme based on a lossy trapdoor function has a \emph{tight} security reduction from the lossiness...
Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Verification
Aviad Kipnis, Eliphaz Hibshoosh
Secret-key cryptography
We present high performance non-deterministic fully-homomorphic methods for practical randomization of data (over commutative ring), and symmetric-key encryption of random mod-N data (over ring of reidues mod-N) well suited for crypto applications. These methods secure, for example, the multivariate input or the coefficients of a polynomial function running in an open untrusted environment. We show that random plaintext is the sufficient condition for proof of security for the homomorphic...
Relation between Verifiable Random Functions and Convertible Undeniable Signatures, and New Constructions
Kaoru Kurosawa, Ryo Nojima, Le Trieu Phong
Public-key cryptography
Verifiable random functions (VRF) and selectively-convertible undeniable signature (SCUS) schemes were proposed independently in the literature. In this paper, we observe that they are tightly related. This directly yields several deterministic SCUS schemes based on existing VRF constructions. In addition, we create a new probabilistic SCUS scheme, which is very compact. The confirmation and disavowal protocols of these SCUS are efficient, and can be run either sequentially, concurrently, or...
2012/109
Last updated: 2012-03-20
Chosen-Ciphertext Secure Efficiently Searchable Encryption in the Standard Model
Yang Cui, Kirill Morozov
Public-key cryptography
In the standard model, deterministic public-key encryption (PKE) secure against chosen-ciphertext attacks by privacy adversary (PRIV-CCA) is known to be built only from lossy trapdoor functions as demonstrated by Boldyreva et al at Crypto 2008. We show that the method of achieving IND-CCA security via correlated products, recently introduced by Rosen and Segev at TCC 2009, can be used to achieve PRIV-CCA secure PKE of uniform messages from any trapdoor permutation (TDP) in the standard...
Message Authentication, Revisited
Yevgeniy Dodis, Eike Kiltz, Krzysztof Pietrzak, Daniel Wichs
Secret-key cryptography
Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows:
* We show several...
Deterministic Identity Based Signature Scheme and its Application for Aggregate Signatures
S. Sharmila Deva Selvi, S. Sree Vivek, C. Pandu Rangan
Public-key cryptography
The revolutionary impact offered by identity based cryptography is phenomenal. This novel mechanism was first coined by Adi Shamir in 1984. Since then, several identity based signature schemes were reported. But surprisingly, none of the identity based signature scheme is having the property of determinism and does rely on bilinear pairing. We think positively in answering this long standing question of realizing deterministic identity based signature in composite order groups and we succeed...
Pseudorandom Signatures
Nils Fleischhacker, Felix Günther, Franziskus Kiefer, Mark Manulis, Bertram Poettering
Public-key cryptography
We develop a three-level hierarchy of privacy notions for (unforgeable) digital signature schemes. We first prove mutual independence of existing notions of anonymity and confidentiality, and then show that these are implied by higher privacy goals. The top notion in our hierarchy is \emph{pseudorandomness}: signatures with this property hide the entire information about the signing process and cannot be recognized as signatures when transmitted over a public network. This implies very...
Security of Blind Signatures Revisited
Dominique Schröder, Dominique Unruh
Public-key cryptography
We revisit the definition of unforgeability of blind signatures as proposed by Pointcheval and Stern (Journal of Cryptology 2000). Surprisingly, we show that this established definition falls short in two ways of what one would intuitively expect from a secure blind signature scheme: It is not excluded that an adversary submits the same message $m$ twice for signing, and then produces a signature for $m'\neq m$. The reason is that the forger only succeeds if \emph{all} messages are...
Identity Based Deterministic Signature Scheme Without Forking-Lemma
S. Sharmila Deva Selvi, S. Sree Vivek, C. Pandu Rangan
Public-key cryptography
Since the discovery of identity based cryptography, a number of identity based signature schemes were reported in the literature. Although, a lot of identity based signature schemes were proposed, the only identity based deterministic signature scheme was given by Javier Herranz. This signature scheme uses Schnorr signature scheme for generating the private key of the users and uses BLS short signature scheme for generating users signature. The security of this scheme was proved in the...
BiTR: Built-in Tamper Resilience
Seung Geol Choi, Aggelos Kiayias, Tal Malkin
Cryptographic protocols
The assumption of the availability of tamper-proof hardware tokens has been
used extensively in the design of cryptographic primitives. For example,
Katz (Eurocrypt 2007) suggests them as an alternative to other setup
assumptions, towards achieving general UC-secure multi-party computation.
On the other hand, a lot of recent research has focused on protecting
security of various cryptographic primitives against physical attacks such
as leakage and tampering.
In this paper we put forward...
2010/493
Last updated: 2010-11-12
A Suite of Identity Based Aggregate Signatures and a Multi-Signature Scheme from RSA
S. Sharmila Deva Selvi, S. Sree Vivek, C. Pandu Rangan
Public-key cryptography
Fully aggregateable identity based signature schemes without prior communication between the signing parties is an interesting issue in identity based cryptography. On this front, we identify that deterministic identity based signature schemes lead to full aggregation of signatures without the aforementioned overhead. Inspired by Shamir's identity based signature scheme, we propose a deterministic identity based signature scheme which is also based on RSA. Based on this newly proposed...
Confidential Signatures and Deterministic Signcryption
Alexander W. Dent, Marc Fischlin, Mark Manulis, Martijn Stam, Dominique Schroder
Public-key cryptography
Encrypt-and-sign, where one encrypts and signs a message in
parallel, is usually not recommended for confidential message
transmission. The reason is that the signature typically leaks
information about the message. This motivates our investigation of
confidential signature schemes, which hide all information about
(high-entropy) input messages. In this work we provide a formal
treatment of confidentiality for such schemes and a comprehensive
discussion of the relationship of different...
Fault Attacks on RSA Signatures with Partially Unknown Messages
Jean-Sebastien Coron, Antoine Joux, Ilya Kizhvatov, David Naccache, Pascal Paillier
Implementation
Fault attacks exploit hardware malfunctions to recover secrets from embedded electronic devices.
In the late 90's, Boneh, DeMillo and Lipton introduced fault-based attacks on {\sc crt-rsa}.
These attacks factor the signer's modulus when the message padding
function is deterministic. However, the attack does not apply when the
message is partially unknown, for example when messages contain some
randomness which is recovered only when
verifying a {\sl correct} signature.
In this paper we...
Comparing With RSA
Julien Cathalo, David Naccache, Jean-Jacques Quisquater
Public-key cryptography
A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings.
This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures.
In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution...
On the Number of Synchronous Rounds Required for Byzantine Agreement
Matthias Fitzi, Jesper Buus Nielsen
Cryptographic protocols
Byzantine agreement is typically considered with respect to either a
fully synchronous network or a fully asynchronous one. In the
synchronous case, either $t+1$ deterministic rounds are necessary in
order to achieve Byzantine agreement or at least some expected large
constant number of rounds.
In this paper we examine the question of how many initial synchronous
rounds are required for Byzantine agreement if we allow to switch to
asynchronous operation afterwards.
Let $n=h+t$ be the...
Deterministic Identity-Based Signatures for Partial Aggregation
Javier Herranz
Public-key cryptography
Aggregate signatures are a useful primitive which allows to aggregate into a single and constant-length signature many signatures on different messages computed by different users. Specific proposals of aggregate signature schemes exist only for PKI-based scenarios. For identity-based scenarios, where public keys of the users are directly derived from their identities, the signature schemes proposed up to now do not seem to allow constant-length aggregation.
We provide an intermediate...
On the Composition of Authenticated Byzantine Agreement
Yehuda Lindell, Anna Lysyanskaya, Tal Rabin
Cryptographic protocols
A fundamental problem of distributed computing is that of
simulating a secure broadcast channel, within the setting of a
point-to-point network. This problem is known as Byzantine
Agreement (or Generals) and has been the focus of much research.
Lamport et al. showed that in order to achieve Byzantine Agreement
in the standard model, more than 2/3 of the participating
parties must be honest. They further showed that by augmenting the
network with a public-key infrastructure for digital...
Universal Designated-Verifier Signatures
Ron Steinfeld, Laurence Bull, Huaxiong Wang, Josef Pieprzyk
Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ‘Universal Designated-Verifier Signature’ (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier’s public key). Given the...
Some Applications of Threshold Signature Schemes to Distributed Protocols
Vanesa Daza, Javier Herranz, Germán Sáez
Cryptographic protocols
In a threshold signature scheme, a group of players share a secret information in such a way that only those subsets with a minimum number of players can compute a valid signature. We propose methods to construct some useful and computationally secure distributed protocols from threshold signature schemes satisfying some suitable properties.
Namely, we prove that any threshold signature scheme which is non-interactive can be used to construct a metering scheme. We also design a distributed...
The Fiat-Shamir transformation is a widely employed technique in constructing signature schemes, known as Fiat-Shamir signature schemes (FS-SIG), derived from secure identification (ID) schemes. However, the existing security proof only takes into account classical signing queries and does not consider superposition attacks, where the signing oracle is quantum-accessible to the adversaries. Alagic et al. proposed a security model called blind unforgeability (BUF, Eurocrypt'20), regarded as a...
Threshold Schnorr signatures are seeing increased adoption in practice, and offer practical defenses against single points of failure. However, one challenge with existing randomized threshold Schnorr signature schemes is that signers must carefully maintain secret state across signing rounds, while also ensuring that state is deleted after a signing session is completed. Failure to do so will result in a fatal key-recovery attack by re-use of nonces. While deterministic threshold...
Two recent proposals by Bernstein and Pornin emphasize the use of deterministic signatures in DSA and its elliptic curve-based variants. Deterministic signatures derive the required ephemeral key value in a deterministic manner from the message to be signed and the secret key instead of using random number generators. The goal is to prevent severe security issues, such as the straight-forward secret key recovery from low quality random numbers. Recent developments have raised skepticism...
Verifiable random functions (VRFs) are pseudorandom functions with the addition that the function owner can prove that a generated output is correct, with respect to a committed key. In this paper we introduce the notion of an exponent-VRF, or eVRF, which is a VRF that does not provide its output $y$ explicitly, but instead provides $Y = y \cdot G$, where $G$ is a generator of some finite cyclic group (or $Y = g^y$ in multiplicative notation). We construct eVRFs from DDH and from the...
EdDSA, standardized by both IRTF and NIST, is a variant of the well-known Schnorr signature based on Edwards curves, and enjoys the benefit of statelessly and deterministically deriving nonces (i.e., it does not require reliable source of randomness or state continuity). Recently, NIST calls for multi-party threshold EdDSA signatures in one mode of deriving nonce statelessly and deterministically and verifying such derivation via zero-knowledge (ZK) proofs. Multi-party full-threshold EdDSA...
After NIST’s selection of Dilithium as the primary future standard for quantum-secure digital signatures, increased efforts to understand its implementation security properties are required to enable widespread adoption on embedded devices. Concretely, there are still many open questions regarding the susceptibility of Dilithium to fault attacks. This is especially the case for Dilithium’s randomized (or hedged) signing mode, which, likely due to devastating implementation attacks on the...
Cryptocurrency networks crucially rely on digital signature schemes, which are used as an authentication mechanism for transactions. Unfortunately, most major cryptocurrencies today, including Bitcoin and Ethereum, employ signature schemes that are susceptible to quantum adversaries, i.e., an adversary with access to a quantum computer can forge signatures and thereby spend coins of honest users. In cryptocurrency networks, signature schemes are typically not executed in isolation, but...
Multi-signatures allow to combine individual signatures from different signers on the same message into a short aggregated signature. Newer schemes further allow to aggregate the individual public keys, such that the combined signature gets verified against a short aggregated key. This makes them a versatile alternative to threshold or distributed signatures: the aggregated key can serve as group key, and signatures under that key can only be computed with the help of all signers. What makes...
The scalability and interoperability challenges in current cryptocurrencies have motivated the design of cryptographic protocols that enable efficient applications on top and across widely used cryptocurrencies such as Bitcoin or Ethereum. Examples of such protocols include (virtual) payment channels, atomic swaps, oracle-based contracts, deterministic wallets, and coin mixing services. Many of these protocols are built upon minimal core functionalities supported by a wide range of...
In this work, we construct the first digital signature (SIG) and public-key encryption (PKE) schemes with almost tight multi-user security under adaptive corruptions based on the learning-with-errors (LWE) assumption in the standard model. Our PKE scheme achieves almost tight IND-CCA security and our SIG scheme achieves almost tight strong EUF-CMA security, both in the multi-user setting with adaptive corruptions. The security loss is quadratic in the security parameter, and independent of...
The post-quantum digital signature scheme CRYSTALS-Dilithium has been recently selected by the NIST for standardization. Implementing CRYSTALS-Dilithium, and other post-quantum cryptography schemes, on embedded devices raises a new set of challenges, including ones related to performance in terms of speed and memory requirements, but also related to side-channel and fault injection attacks security. In this work, we investigated the latter and describe a differential fault attack on the...
A Key Derivation Function (KDF) generates a uniform and highly random key-stream from weakly random key material. KDFs are broadly used in various security protocols such as digital signatures and key exchange protocols. HKDF, the most deployed KDF in practice, is based on the extract-then-expand paradigm. It is presently used, among others, in the Signal Protocol for end-to-end encrypted messaging. HKDF is a generic KDF for general input sources and thus is not optimized for...
Lattice gadgets and the associated algorithms are the essential building blocks of lattice-based cryptography. In the past decade, they have been applied to build versatile and powerful cryptosystems. However, the practical optimizations and designs of gadget-based schemes generally lag their theoretical constructions. For example, the gadget-based signatures have elegant design and capability of extending to more advanced primitives, but they are far less efficient than other lattice-based...
We propose hinTS --- a new threshold signature scheme built on top of the widely used BLS signatures. Our scheme enjoys the following attractive features: \begin{itemize} \item A {\em silent setup} process where the joint public key of the parties is computed as a deterministic function of their locally computed public keys. \item Support for {\em dynamic} choice of thresholds and signers, after the silent setup, without further interaction. \item Support for {\em general}...
We describe a fault attack against the deterministic variant of the Falcon signature scheme. It is the first fault attack that exploits specific properties of deterministic Falcon. The attack works under a very liberal and realistic single fault random model. The main idea is to inject a fault into the pseudo-random generator of the pre-image trapdoor sampler, generate different signatures for the same input, find reasonably short lattice vectors this way, and finally use lattice reduction...
A \emph{witness map} deterministically maps a witness $w$ of some NP statement $x$ into computationally sound proof that $x$ is true, with respect to a public common reference string (CRS). In other words, it is a deterministic, non-interactive, computationally sound proof system in the CRS model. A \emph{unique witness map} (UWM) ensures that for any fixed statement $x$, the witness map should output the same \emph{unique} proof for $x$, no matter what witness $w$ it is applied to. More...
Cryptographic wallets have become an essential tool to secure users' secret keys and consequently their funds in Blockchain networks. The most prominent wallet standard that is widely adopted in practice is the BIP32 specification. This standard specifies so-called hierarchical deterministic wallets, which are organized in a tree-like structure such that each node in the tree represents a wallet instance and such that a parent node can derive a new child node in a deterministic fashion....
Schnorr signatures are a popular choice due to their simplicity, provable security, and linear structure that enables relatively easy threshold signing protocols. The deterministic variant of Schnorr (where the nonce is derived in a stateless manner using a PRF from the message and a long term secret) is widely used in practice since it mitigates the threats of a faulty or poor randomness generator (which in Schnorr leads to catastrophic breaches of security). Unfortunately, threshold...
Since the invention of Bitcoin, cryptocurrencies have gained huge popularity. Crypto wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency funds. Deterministic wallet is an advanced wallet mech- anism that has been proposed to achieve some appealing virtues, such as low-maintenance, easy backup and recovery, supporting functionali- ties required by cryptocurrencies, and so on. But deterministic wallets still...
DME is a multivariate public key cryptosystem based on the composition of linear and exponential maps that allow the polynomials of the public key to be of a very high degree. A previous version of DME was presented to the NIST call (in the KEM category). The new version of DME adds one or two extra rounds of exponentials to the original two rounds. With this setting the composition gives a deterministic trapdoor one way permutation, which can be combined with an OAEP padding scheme for KEM...
Adaptor signatures are a new cryptographic primitive that binds the authentication of a message to the revelation of a secret value. In recent years, this primitive has gained increasing popularity both in academia and practice due to its versatile use-cases in different Blockchain applications such as atomic swaps and payment channels. The security of these applications, however, crucially relies on users storing and maintaining the secret values used by adaptor signatures in a secure...
CRYSTALS-Dilithium has been selected by the NIST as the new stan- dard for post-quantum digital signatures. In this work, we revisit the side-channel countermeasures of Dilithium in three directions. First, we improve its sensitivity analysis by classifying intermediate computations according to their physical security requirements. Second, we provide improved gadgets dedicated to Dilithium, taking advantage of recent advances in masking conversion algorithms. Third, we combine these...
We study the problem of privacy-preserving proofs on streamed authenticated data. In this setting, a server receives a continuous stream of data from a trusted data provider, and is requested to prove computations over the data to third parties in a correct and private way. In particular, the third party learns no information on the data beyond the validity of claimed results. A challenging requirement here, is that the third party verifies the validity with respect to the specific data...
ZK-SNARKs (Zero Knowledge Succinct Noninteractive ARguments of Knowledge) are one of the most promising new applied cryptography tools: proofs allow anyone to prove a property about some data, without revealing that data. Largely spurred by the adoption of cryptographic primitives in blockchain systems, ZK-SNARKs are rapidly becoming computationally practical in real-world settings, shown by i.e. tornado.cash and rollups. These have enabled ideation for new identity applications based on...
We present a rate-$1$ construction of a publicly verifiable non-interactive argument system for batch-$\mathsf{NP}$ (also called a BARG), under the LWE assumption. Namely, a proof corresponding to a batch of $k$ NP statements each with an $m$-bit witness, has size $m + \mathsf{poly}(\lambda,\log k)$. In contrast, prior work either relied on non-standard knowledge assumptions, or produced proofs of size $m \cdot \mathsf{poly}(\lambda,\log k)$ (Choudhuri, Jain, and Jin, STOC 2021,...
Proving discrete log equality for groups of the same order is addressed by Chaum and Pedersen's seminal work. However, there has not been a lot of work in proving discrete log equality for groups of different orders. This paper presents an efficient solution, which leverages a technique we call delegated Schnorr. The discovery of this technique is guided by a design methodology that we call the inspection model, and we find it useful for protocol designs. We show two...
In this work, we present the first fault injection analysis of the Number Theoretic Transform (NTT). The NTT is an integral computation unit, widely used for polynomial multiplication in several structured lattice-based key encapsulation mechanisms (KEMs) and digital signature schemes. We identify a critical single fault vulnerability in the NTT, which severely reduces the entropy of its output. This in turn enables us to perform a wide-range of attacks applicable to lattice-based KEMs as...
Over the past decade, cryptocurrency has been undergoing a rapid development. Digital wallet, as the tool to store and manage the cryptographic keys, is the primary entrance for the public to access cryptocurrency assets. Hierarchical Deterministic Wallet (HDW), proposed in Bitcoin Improvement Proposal 32 (BIP32), has attracted much attention and been widely used in the community, due to its virtues such as easy backup/recovery, convenient cold-address management, and supporting trust-less...
This paper deals with white-box implementations of the Elliptic Curve Digital Signature Algorithm (ECDSA): First, we consider attack paths to break such implementations. In particular, we provide a systematic overview of various fault attacks, to which ECDSA white-box implementations are especially susceptible. Then, we propose different mathematical countermeasures, mainly based on masking/blinding of sensitive variables, in order to prevent or at least make such attacks more difficult. We...
The goal of this paper is to improve the efficiency and applicability of straightline extraction techniques in the random oracle model. Straightline extraction in the random oracle model refers to the existence of an extractor, which given the random oracle queries made by a prover $P^*(x)$ on some theorem $x$, is able to produce a witness $w$ for $x$ with roughly the same probability that $P^*$ produces a verifying proof. This notion applies to both zero-knowledge protocols and verifiable...
We present a novel cryptographic primitive, blind accumulator, aimed at constructing e-voting systems. Blind accumulators collect private keys of eligible voters in a decentralized manner not getting information about the keys. Once the accumulation is complete, a voter processes the resulting accumulator deriving a public key that refers to the private key previously added by this voter. Public keys are derived deterministically and can therefore stand as fixed voter pseudonyms. The voter...
Two common variations of ECDSA signatures are additive key derivation and presignatures. Additive key derivation is a simple mechanism for deriving many subkeys from a single master key, and is already widely used in cryptocurrency applications with the Hierarchical Deterministic Wallet mechanism standardized in Bitcoin Improvement Proposal 32 (BIP32). Because of its linear nature, additive key derivation is also amenable to efficient implementation in the threshold setting. With...
In many cryptocurrencies, the problem of key management has become one of the most fundamental security challenges. Typically, keys are kept in designated schemes called 'Wallets', whose main purpose is to store these keys securely. One such system is the BIP32 wallet (Bitcoin Improvement Proposal 32), which since its introduction in 2012 has been adopted by countless Bitcoin users and is one of the most frequently used wallet system today. Surprisingly, very little is known about the...
Higher-order power residues have enabled the construction of numerous public-key encryption schemes, authentication schemes, and digital signatures. Their explicit characterization is however challenging; an algorithm of Caranay and Scheidler computes $p$-th power residue symbols, with $p \le 13$ an odd prime, provided that primary elements in the corresponding cyclotomic field can be efficiently found. In this paper, we describe a new, generic algorithm to compute primary elements in...
Schnorr's signature scheme permits an elegant threshold signing protocol due to its linear signing equation. However each new signature consumes fresh randomness, which can be a major attack vector in practice. Sources of randomness in deployments are frequently either unreliable, or require state continuity, i.e. reliable fresh state resilient to rollbacks. State continuity is a notoriously difficult guarantee to achieve in practice, due to system crashes caused by software errors,...
Digital signatures are used to verify the authenticity of digital messages, that is, to know with a high level of certainty, that a digital message was created by a known sender and was not altered in any way. This is usually achieved by using asymmetric cryptography, where a secret key is used by the signer, and the corresponding public key is used by those who wish to verify the signed data. In many use-cases, such as blockchain, the history and order of the signed data, thus the...
Most blockchain solutions are susceptible to quantum attackers as they rely on cryptography that is known to be insecure in the presence of quantum adversaries. In this work we advance the study of quantum-resistant blockchain solutions by giving a quantum-resistant construction of a deterministic wallet scheme. Deterministic wallets are frequently used in practice in order to secure funds by storing the sensitive secret key on a so-called cold wallet that is not connected to the Internet....
MuSig is a multi-signature scheme for Schnorr signatures, which supports key aggregation and is secure in the plain public key model. Standard derandomization techniques for discrete logarithm-based signatures such as RFC 6979, which make the signing procedure immune to catastrophic failures in the randomness generation, are not applicable to multi-signatures as an attacker could trick an honest user into producing two different partial signatures with the same randomness, which would reveal...
The Fiat-Shamir transform is a general method for reducing interaction in public-coin protocols by replacing the random verifier messages with deterministic hashes of the protocol transcript. The soundness of this transformation is usually heuristic and lacks a formal security proof. Instead, to argue security, one can rely on the random oracle methodology, which informally states that whenever a random oracle soundly instantiates Fiat-Shamir, a hash function that is ``sufficiently...
The deterministic ECDSA and EdDSA signature schemes have found plenty of applications since their publication and standardization. Their theoretical security can be guaranteed under certain well-designed models, while their practical risks from the flaw of random number generators can be mitigated since no randomness is required by the algorithms anymore. But the situation is not completely optimistic, since it has been gradually found that delicately designed fault attacks can threaten the...
Following recent comments in a NIST document related to threshold cryptographic standards, we examine the case of thresholdizing the HashEdDSA signature scheme. This is a deterministic signature scheme based on Edwards elliptic curves. Unlike DSA, it has a Schnorr like signature equation, which is an advantage for threshold implementations, but it has the disadvantage of having the ephemeral secret obtained by hashing the secret key and the message. We show that one can obtain relatively...
We introduce the notion of Witness Maps as a cryptographic notion of a proof system. A Unique Witness Map (UWM) deterministically maps all witnesses for an $\mathbf{NP}$ statement to a single representative witness, resulting in a computationally sound, deterministic-prover, non-interactive witness independent proof system. A relaxation of UWM, called Compact Witness Map (CWM), maps all the witnesses to a small number of witnesses, resulting in a ``lossy'' deterministic-prover,...
Non-repudiation of messages generated by users is a desirable feature in a number of applications ranging from online banking to IoT scenarios. However, it requires certified public keys and usually results in poor usability as a user must carry around his certificate (e.g., in a smart-card) or must install it in all of his devices. A user-friendly alternative, adopted by several companies and national administrations, is to have a ``cloud-based'' PKI. In a nutshell, each user has a PKI...
Key custody is a sensitive aspect of cryptocurrencies. The employment of a custodian service together with threshold-multi-party signatures helps to manage secret keys more safely and effectively, e.g. allowing the recovery of crypto-assets when users lose their own keys. Advancing from a protocol by Gennaro et al. we propose a protocol with two main properties. First it allows the recovery party to remain offline during the enrollment of any user, solving a real-life problem of maintaining...
The RSA Probabilistic Signature Scheme (RSA-PSS) due to Bellare and Rogaway (EUROCRYPT 1996) is a widely deployed signature scheme. In particular it is a suggested replacement for the deterministic RSA Full Domain Hash (RSA-FDH) by Bellare and Rogaway (ACM CCS 1993) and PKCS#1 v1.5 (RFC 2313), as it can provide stronger security guarantees. It has since been shown by Kakvi and Kiltz (EUROCRYPT 2012, Journal of Cryptology 2018) that RSA-FDH provides similar security to that of RSA-PSS, also...
Memory fault attacks, inducing errors in computations, have been an ever-evolving threat to cryptographic schemes since their discovery for cryptography by Boneh et al. (Eurocrypt 1997). Initially requiring physical tampering with hardware, the software-based rowhammer attack put forward by Kim et al. (ISCA 2014) enabled fault attacks also through malicious software running on the same host machine. This led to concerning novel attack vectors, for example on deterministic signature schemes,...
Deterministic generation of per-signature randomness has been a widely accepted solution to mitigate the catastrophic risk of randomness failure in Fiat--Shamir type signature schemes. However, recent studies have practically demonstrated that such de-randomized schemes, including EdDSA, are vulnerable to differential fault attacks, which enable adversaries to recover the entire secret signing key, by artificially provoking randomness reuse or corrupting computation in other ways. In order...
Abstract. The extremely efficient Rabin-Williams signature scheme relies on decryption of a quadratic equation in order to retrieve the original message. Customarily, square roots are found using the Chinese Remainder Theorem. This can be done in polynomial time, but generally produces four options for the correct message which must be analyzed to determine the correct one. This paper resolves the problem of efficient deterministic decryption to the correct message modulo $p^2q$ by...
In this paper, we analyze the implementation level fault vulnerabilities of deterministic lattice-based signature schemes. In particular, we extend the practicality of skip-addition fault attacks through exploitation of determinism in certain variants of Dilithium (Deterministic variant) and qTESLA signature scheme (originally submitted deterministic version), which are two leading candidates for the NIST standardization of post-quantum cryptography. We show that single targeted faults...
Leakages during the signing process, including partial key exposure and partial (or complete) randomness exposure, may be devastating for the security of digital signatures. In this work, we investigate the security of lattice-based Fiat-Shamir signatures in the presence of randomness leakage. To this end, we present a generic key recovery attack that relies on minimum leakage of randomness, and then theoretically connect it to a variant of Integer-LWE (ILWE) problem. The ILWE problem,...
This work presents Arcula, a new design for hierarchical deterministic wallets that brings identity-based addresses to the blockchain. Arcula is built on top of provably secure cryptographic primitives. It generates all its cryptographic secrets from a user-provided seed and enables the derivation of new public keys based on the identities of users, without requiring any secret information. Unlike other wallets, it achieves all these properties while being secure against privilege...
ByzCoin, a promising alternative of Bitcoin, is a scalable consensus protocol used as a building block of many research and enterprise-level decentralized systems. In this paper, we show that ByzCoin is unsuitable for deployment in an anopen, adversarial network and instead introduceMOTOR. MOTORis designed as a secure, robust, and scalable consensus suitable for permissionless sharded blockchains. MOTORachieves these properties by making four key design choices: (a) it prioritizes robustness...
Algebraic structure lies at the heart of much of Cryptomania as we know it. An interesting question is the following: instead of building (Cryptomania) primitives from concrete assumptions, can we build them from simple Minicrypt primitives endowed with additional algebraic structure? In this work, we affirmatively answer this question by adding algebraic structure to the following Minicrypt primitives: • One-Way Function (OWF) • Weak Unpredictable Function (wUF) • Weak Pseudorandom...
Given the current research status in lattice-based cryptography, it is commonly suggested that lattice-based signature could be subtler and harder to achieve. Among them, Dilithium is one of the most promising signature candidates for the post-quantum era, for its simplicity, efficiency, small public key size, and resistance against side channel attacks. The design of Dilithium is based on a list of pioneering works (e.g.,[VL09,VL12,BG14]), and has very remarkable performance by very...
Since the introduction of Bitcoin in 2008, cryptocurrency has been undergoing a quick and explosive development. At the same time, privacy protection, one of the key merits of cryptocurrency, has attracted much attention by the community. A deterministic wallet algorithm and a stealth address algorithm have been widely adopted in the community, due to their virtues on functionality and privacy-protection, which come from a key derivation mechanism that an arbitrary number of derived keys can...
The RSA PKCS#1 v1.5 signature algorithm is the most widely used digital signature scheme in practice. Its two main strengths are its extreme simplicity, which makes it very easy to implement, and that verification of signatures is significantly faster than for DSA or ECDSA. Despite the huge practical importance of RSA PKCS#1 v1.5 signatures, providing formal evidence for their security based on plausible cryptographic hardness assumptions has turned out to be very difficult. Therefore the...
Attribute-based signature (ABS) schemes are advanced signature schemes that simultaneously provide fine-grained authentication while protecting privacy of the signer. Previously known expressive ABS schemes support either the class of deterministic finite automata and circuits from standard assumptions or Turing machines from the existence of indistinguishability obfuscations. In this paper, we propose the first ABS scheme for a very general policy class, all deterministic Turin machines,...
We propose a new method for reducing complexity of the pairing comparisons based on polynomials. Thought the construction introduces uncertainty into (usually deterministic) checks, it is easily quantifiable and in most cases extremely small. The application to CL-LRSW signature verification under n messages and group order q allows to reduce the number of computed pairings from 4n down to just 4, while the introduced uncertainty is just (2n-1)/q.
In this paper, we extend the applicability of differential fault attacks to lattice-based cryptography. We show how two deterministic lattice-based signature schemes, Dilithium and qTESLA, are vulnerable to such attacks. In particular, we demonstrate that single random faults can result in a nonce-reuse scenario which allows key recovery. We also expand this to fault-induced partial nonce-reuse attacks, which do not corrupt the validity of the computed signatures and thus are harder to...
Many digital signature schemes rely on random numbers that are unique and non-predictable per signature. Failures of random number generators may have catastrophic effects such as compromising private signature keys. In recent years, many widely-used cryptographic technologies adopted deterministic signature schemes because they are presumed to be safer to implement. In this paper, we analyze the security of deterministic ECDSA and EdDSA signature schemes and show that the elimination of...
Ed25519 is an instance of the Elliptic Curve based signature scheme EdDSA that was recently introduced to solve an inconvenience of the more established ECDSA. Namely, both schemes require the generation of a random value (scalar of the ephemeral key pair) during the signature generation process and the secrecy of this random value is critical for security: knowledge of one such a random value, or partial knowledge of a series of them, allows reconstructing the signer's private key. In ECDSA...
Deterministic signature schemes are becoming more popular, as illustrated by the deterministic variant of ECDSA and the popular EdDSA scheme, since eliminating the need for high-quality randomness might have some advantages in certain use-cases. In this paper we outline a range of differential fault attacks and a differential power analysis attack against such deterministic schemes. This shows, contrary to some earlier works, that such signature schemes are not naturally protected against...
The Fiat-Shamir transform is a technique for combining a hash function and an identification scheme to produce a digital signature scheme. The resulting scheme is known to be secure in the random oracle model (ROM), which does not, however, imply security in the scenario where the adversary also has quantum access to the oracle. The goal of this current paper is to create a generic framework for constructing tight reductions in the QROM from underlying hard problems to Fiat-Shamir...
We investigate the subset-resilience problem, defined in 2002 by Reyzin and Reyzin to analyze their HORS signature scheme. We show that textbook HORS is insecure against adaptive attacks, and present a practical attack based on a greedy algorithm. We also describe weak messages for HORS, that map to smaller subsets than expected, and are thus easier to cover. This leads to an improved attack against HORS and to an improved classical attack against the signature scheme SPHINCS, of complexity...
We formally study ``non-malleable functions'' (NMFs), a general cryptographic primitive which simplifies and relaxes ``non-malleable one-way/hash functions'' (NMOWHFs) introduced by Boldyreva et al. (Asiacrypt 2009) and refined by Baecher et al. (CT-RSA 2010). NMFs focus on basic functions, rather than one-way/hash functions considered in the literature of NMOWHFs. We mainly follow Baecher et al. to formalize a game-based definition for NMFs. Roughly, a function $f$ is non-malleable if...
The signature scheme Bliss proposed by Ducas, Durmus, Lepoint and Lyubashevsky at Crypto’13, is currently the most compact and efficient lattice-based signature scheme that is provably secure under lattice assumptions. It does compare favourably with the standardized schemes RSA and ECDSA on both Software and Hardware. In this work, we introduce a new technique that improves the above scheme, offering an acceleration factor up to 2.8, depending on the set of parameters. Namely, we improve...
RSA–CRT is the most widely used implementation for RSA signatures. However, deterministic and many probabilistic RSA signatures based on CRT are vulnerable to fault attacks. Nevertheless, Coron and Mandal (Asiacrypt 2009) show that the randomized PSS padding protects RSA signatures against random faults. In contrast, Fouque et al. (CHES 2012) show that PSS padding does not protect against certain non-random faults that can be injected in widely used implementations based on the Montgomery...
Lossy trapdoor functions, introduced by Peikert and Waters (STOC~'08), are functions that can be generated in two indistinguishable ways: either the function is injective, and there is a trapdoor to invert it, or the function is lossy, meaning that the size of its range is strictly smaller than the size of its domain. Kakvi and Kiltz (EUROCRYPT 2012) proved that the Full Domain Hash signature scheme based on a lossy trapdoor function has a \emph{tight} security reduction from the lossiness...
We present high performance non-deterministic fully-homomorphic methods for practical randomization of data (over commutative ring), and symmetric-key encryption of random mod-N data (over ring of reidues mod-N) well suited for crypto applications. These methods secure, for example, the multivariate input or the coefficients of a polynomial function running in an open untrusted environment. We show that random plaintext is the sufficient condition for proof of security for the homomorphic...
Verifiable random functions (VRF) and selectively-convertible undeniable signature (SCUS) schemes were proposed independently in the literature. In this paper, we observe that they are tightly related. This directly yields several deterministic SCUS schemes based on existing VRF constructions. In addition, we create a new probabilistic SCUS scheme, which is very compact. The confirmation and disavowal protocols of these SCUS are efficient, and can be run either sequentially, concurrently, or...
In the standard model, deterministic public-key encryption (PKE) secure against chosen-ciphertext attacks by privacy adversary (PRIV-CCA) is known to be built only from lossy trapdoor functions as demonstrated by Boldyreva et al at Crypto 2008. We show that the method of achieving IND-CCA security via correlated products, recently introduced by Rosen and Segev at TCC 2009, can be used to achieve PRIV-CCA secure PKE of uniform messages from any trapdoor permutation (TDP) in the standard...
Traditionally, symmetric-key message authentication codes (MACs) are easily built from pseudorandom functions (PRFs). In this work we propose a wide variety of other approaches to building efficient MACs, without going through a PRF first. In particular, unlike deterministic PRF-based MACs, where each message has a unique valid tag, we give a number of probabilistic MAC constructions from various other primitives/assumptions. Our main results are summarized as follows: * We show several...
The revolutionary impact offered by identity based cryptography is phenomenal. This novel mechanism was first coined by Adi Shamir in 1984. Since then, several identity based signature schemes were reported. But surprisingly, none of the identity based signature scheme is having the property of determinism and does rely on bilinear pairing. We think positively in answering this long standing question of realizing deterministic identity based signature in composite order groups and we succeed...
We develop a three-level hierarchy of privacy notions for (unforgeable) digital signature schemes. We first prove mutual independence of existing notions of anonymity and confidentiality, and then show that these are implied by higher privacy goals. The top notion in our hierarchy is \emph{pseudorandomness}: signatures with this property hide the entire information about the signing process and cannot be recognized as signatures when transmitted over a public network. This implies very...
We revisit the definition of unforgeability of blind signatures as proposed by Pointcheval and Stern (Journal of Cryptology 2000). Surprisingly, we show that this established definition falls short in two ways of what one would intuitively expect from a secure blind signature scheme: It is not excluded that an adversary submits the same message $m$ twice for signing, and then produces a signature for $m'\neq m$. The reason is that the forger only succeeds if \emph{all} messages are...
Since the discovery of identity based cryptography, a number of identity based signature schemes were reported in the literature. Although, a lot of identity based signature schemes were proposed, the only identity based deterministic signature scheme was given by Javier Herranz. This signature scheme uses Schnorr signature scheme for generating the private key of the users and uses BLS short signature scheme for generating users signature. The security of this scheme was proved in the...
The assumption of the availability of tamper-proof hardware tokens has been used extensively in the design of cryptographic primitives. For example, Katz (Eurocrypt 2007) suggests them as an alternative to other setup assumptions, towards achieving general UC-secure multi-party computation. On the other hand, a lot of recent research has focused on protecting security of various cryptographic primitives against physical attacks such as leakage and tampering. In this paper we put forward...
Fully aggregateable identity based signature schemes without prior communication between the signing parties is an interesting issue in identity based cryptography. On this front, we identify that deterministic identity based signature schemes lead to full aggregation of signatures without the aforementioned overhead. Inspired by Shamir's identity based signature scheme, we propose a deterministic identity based signature scheme which is also based on RSA. Based on this newly proposed...
Encrypt-and-sign, where one encrypts and signs a message in parallel, is usually not recommended for confidential message transmission. The reason is that the signature typically leaks information about the message. This motivates our investigation of confidential signature schemes, which hide all information about (high-entropy) input messages. In this work we provide a formal treatment of confidentiality for such schemes and a comprehensive discussion of the relationship of different...
Fault attacks exploit hardware malfunctions to recover secrets from embedded electronic devices. In the late 90's, Boneh, DeMillo and Lipton introduced fault-based attacks on {\sc crt-rsa}. These attacks factor the signer's modulus when the message padding function is deterministic. However, the attack does not apply when the message is partially unknown, for example when messages contain some randomness which is recovered only when verifying a {\sl correct} signature. In this paper we...
A multi-set (MS) is a set where an element can occur more than once. MS hash functions (MSHFs) map MSs of arbitrary cardinality to fixed-length strings. This paper introduces a new RSA-based MSHF. The new function is efficient and produces small hashes. We prove that the proposed MSHF is collision-resistant under the assumption of unforgeability of deterministic RSA signatures. In many practical applications, programmers need to compare two (unordered) sets of integers. A trivial solution...
Byzantine agreement is typically considered with respect to either a fully synchronous network or a fully asynchronous one. In the synchronous case, either $t+1$ deterministic rounds are necessary in order to achieve Byzantine agreement or at least some expected large constant number of rounds. In this paper we examine the question of how many initial synchronous rounds are required for Byzantine agreement if we allow to switch to asynchronous operation afterwards. Let $n=h+t$ be the...
Aggregate signatures are a useful primitive which allows to aggregate into a single and constant-length signature many signatures on different messages computed by different users. Specific proposals of aggregate signature schemes exist only for PKI-based scenarios. For identity-based scenarios, where public keys of the users are directly derived from their identities, the signature schemes proposed up to now do not seem to allow constant-length aggregation. We provide an intermediate...
A fundamental problem of distributed computing is that of simulating a secure broadcast channel, within the setting of a point-to-point network. This problem is known as Byzantine Agreement (or Generals) and has been the focus of much research. Lamport et al. showed that in order to achieve Byzantine Agreement in the standard model, more than 2/3 of the participating parties must be honest. They further showed that by augmenting the network with a public-key infrastructure for digital...
Motivated by privacy issues associated with dissemination of signed digital certificates, we define a new type of signature scheme called a ‘Universal Designated-Verifier Signature’ (UDVS). A UDVS scheme can function as a standard publicly-verifiable digital signature but has additional functionality which allows any holder of a signature (not necessarily the signer) to designate the signature to any desired designated-verifier (using the verifier’s public key). Given the...
In a threshold signature scheme, a group of players share a secret information in such a way that only those subsets with a minimum number of players can compute a valid signature. We propose methods to construct some useful and computationally secure distributed protocols from threshold signature schemes satisfying some suitable properties. Namely, we prove that any threshold signature scheme which is non-interactive can be used to construct a metering scheme. We also design a distributed...
