(Page 62 of) 6168 results sorted by ID
Design and Analysis of Practical Public-Key Encryption Schemes Secure against Adaptive Chosen Ciphertext Attack
Ronald Cramer, Victor Shoup
Public-key cryptography
A new public key encryption scheme, along with several variants,
is proposed and analyzed.
The scheme and its variants are quite practical, and are proved
secure
against adaptive chosen ciphertext attack under standard
intractability assumptions.
These appear to be the first public-key encryption schemes
in the literature that are simultaneously practical and provably secure.
Secure Vickrey Auctions without Threshold Trust
Helger Lipmaa, N. Asokan, Valtteri Niemi
Cryptographic protocols
We argue that threshold trust is not an option in most of the real-life
electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller $S$, an auction authority $A$ so that unless $S$ and $A$ collude the outcome of auctions will be correct, and moreover, $S$ will not get any information about the bids, while $A$ will learn bid statistics. Further extensions make it possible to decrease damage that colluding $S$ and $A$...
Threshold Cryptosystems Based on Factoring
Jonathan Katz, Moti Yung
We consider threshold cryptosystems over a composite
modulus $N$ where the \emph{factors} of $N$ are shared among the
participants as the secret key.
This is a new paradigm for threshold cryptosystems based on a
composite modulus, differing from the
typical treatment of RSA-based systems where a ``decryption
exponent'' is shared among the participants. Our approach yields
solutions to some open problems in threshold cryptography; in particular, we obtain the following:
1. \emph{Threshold...
BDD-based Cryptanalysis of Keystream Generators
Matthias Krause
Secret-key cryptography
Many of the keystream generators which are used in practice are LFSR-based in the sense
that they produce the keystream according to a rule $y=C(L(x))$,
where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel
linear feedback shift registers (LFSRs),
and $C$ denotes some nonlinear compression function.
We present an $n^{O(1)} 2^{(1-\alpha)/(1+\alpha)n}$ time bounded attack, the FBDD-attack,
against LFSR-based generators, which computes the secret initial...
Perfect Hiding and Perfect Binding Universally Composable Commitment Schemes with Constant Expansion Factor
Ivan Damgård, Jesper B. Nielsen
Cryptographic protocols
Canetti and Fischlin have recently proposed the security notion {\em
universal composability} for commitment schemes and provided two
examples. This new notion is very strong. It guarantees that security
is maintained even when an unbounded number of copies of the scheme
are running concurrently, also it guarantees non-malleability,
resilience to selective decommitment, and security against adaptive
adversaries. Both of their schemes uses $\Theta(k)$ bits to commit to
one bit and can be...
Identity Based Encryption From the Weil Pairing
Dan Boneh, Matthew Franklin
Public-key cryptography
We propose a fully functional identity-based encryption scheme (IBE).
The scheme has chosen ciphertext security in the random oracle model
assuming an elliptic curve variant of the computational Diffie-Hellman
problem. Our system is based on bilinear maps between groups. The
Weil pairing on elliptic curves is an example of such a map. We give
precise definitions for secure identity based encryption schemes and
give several applications for such systems.
Linear broadcast encryption schemes
Carles Padró, Ignacio Gracia, Sebastià Martín, Paz Morillo
Cryptographic protocols
A new family of broadcast encryption schemes (BESs), which will be called linear broadcast encryption schemes (LBESs), is presented in this paper by using linear algebraic techniques. This family generalizes most previous proposals and provide a general framework to the study of broadcast encryption schemes. We present a method to construct LBESs for a general specification structure in order to find schemes that fit in situations that have not been considered before.
Improving the trade-off between storage and communication in broadcast encryption schemes
Ignacio Gracia, Sebastià Martín, Carles Padró
Cryptographic protocols
The most important point in the design of broadcast encryption schemes (BESs) is obtain a good trade-off between the amount of secret information that must be stored by every user and the length of the broadcast message, which are measured, respectively, by the information rate $\rho$ and the broadcast information rate $\rho_B$. In this paper we present a simple method to combine two given BESs in order to improve the trade-off between $\rho$ and $\rho_B$ by finding BESs with good...
Statistical Zero-Knowledge Proofs from Diophantine Equations
Helger Lipmaa
Foundations
A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a
representing $p$-bounded polynomial $R_{S,t}$, s.t. $x\in S_t \iff
(\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded
Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent
polynomial. We show that $p$-bounded (resp., unbounded) Diophantine
set has a polynomial-size (resp., constant-size) statistical
zero-knowledge proof system that a committed tuple $x$ belongs to
$S$. We describe efficient SZK proof...
Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption
Ronald Cramer, Victor Shoup
Public-key cryptography
We present several new and fairly practical public-key
encryption schemes and prove them secure against adaptive
chosen ciphertext attack. One scheme is based on
Paillier's Decision Composite Residuosity (DCR)
assumption, while another is based in the classical
Quadratic Residuosity (QR) assumption. The analysis is in
the standard cryptographic model, i.e., the security of
our schemes does not rely on the Random Oracle model.
We also introduce the notion of a universal hash
proof ...
COS Ciphers are not "extremely weak"! - The Design Rationale of COS Ciphers
Eric Filiol, Caroline Fontaine
Secret-key cryptography
This note summarizes the results of Babbage's cryptanalysis of COS ciphers and shows that in fact COS ciphers are not weak as claimed. These ciphers have been designed according a novel concept of encryption directly determined by the context of use. This concept is here more precisely defined.
Authenticated Encryption in the Public-Key Setting: Security Notions and Analyses
Jee Hea An
Public-key cryptography
This paper addresses the security of authenticated encryption schemes
in the public key setting. We present two new notions of
authenticity that are stronger than the integrity notions given in the
symmetric setting \cite{bn00}. We also show that
chosen-ciphertext attack security (IND-CCA) in the public key setting
is not obtained in general from the combination of chosen-plaintext
security (IND-CPA) and integrity of ciphertext (INT-CTXT), which is in
contrast to the results shown in the...
On the Security of Randomized CBC-MAC Beyond the Birthday Paradox Limit - A New Construction
Eliane Jaulmes, Antoine Joux, Frederic Valette
Cryptographic protocols
In this paper, we study the security of randomized CBC-MACs and propose a new construction that resists birthday paradox attacks and provably reaches full security. The size of the MAC tags in this construction is optimal, i.e., exactly twice the size of the block cipher. Up to a constant, the security of the proposed randomized CBC-MAC using an n-bit block cipher is the same as the security of the usual encrypted CBC-MAC using a 2n-bit block cipher. Moreover, this construction adds a...
Multi-Recipient Public-Key Encryption with Shortened Ciphertext
Kaoru Kurosawa
Public-key cryptography
In the trivial
$n$-recipient public-key encryption scheme,
a ciphertext is a concatenation
of independently encrypted messages for $n$ recipients.
In this paper,
we say that an $n$-recipient scheme
has a ``{\it shortened ciphertext}'' property
if
the length of the ciphertext is almost
a half (or less) of the trivial scheme
and the security is still almost the same
as the underlying single-recipient scheme.
We first present
(multi-plaintext, multi-recipient) schemes
with the ``{\it...
On the (Im)possibility of Obfuscating Programs
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, Ke Yang
Foundations
Informally, an {\em obfuscator} $O$ is an (efficient,
probabilistic) ``compiler'' that takes as input a program (or
circuit) $P$ and produces a new program $O(P)$ that has the
same functionality as $P$ yet is ``unintelligible'' in some sense.
Obfuscators, if they exist, would have a wide variety of
cryptographic and complexity-theoretic applications, ranging from
software protection to homomorphic encryption to
complexity-theoretic analogues of Rice's theorem. Most of these
applications are...
Analysis of chosen plaintext attacks on the WAKE Stream Cipher
Marina Pudovkina
Secret-key cryptography
Stream ciphers are an important class of encryption algorithms, which are widely used in practice. In this paper the security of the WAKE stream cipher is investigated. We present two chosen plaintext attacks on this cipher. The complexities of these attacks can be estimated as 10^^19.2 and 10^^14.4.
Revocation and Tracing Schemes for Stateless Receivers
Dalit Naor, Moni Naor, Jeff Lotspiech
Foundations
We deal with the problem of a center sending a message to a group
of users such that some subset of the users is considered revoked
and should not be able to obtain the content of the message. We
concentrate on the stateless receiver case, where the users
do not (necessarily) update their state from session to session.
We present a framework called the Subset-Cover framework,
which abstracts a variety of revocation schemes including some
previously known ones. We provide sufficient...
Elliptic curve Paillier schemes
Steven D Galbraith
Public-key cryptography
This paper is concerned with
generalisations of Paillier's
probabilistic encryption scheme
from the integers modulo a square
to elliptic curves over rings.
Paillier himself described
two public key encryption schemes
based on anomalous elliptic curves over rings.
It is argued that these schemes are not secure.
A more natural generalisation of Paillier's scheme to
elliptic curves is given.
A known plaintext attack on the ISAAC keystream generator
Marina Pudovkina
Secret-key cryptography
Stream ciphers are often used in applications where high speed and low delay are a requirement. The ISAAC keystream generator is a fast software-oriented encryption algorithm. In this papers the security of the ISAAC keystream generator is investigated. Cryptanalytic algorithm is developed for a known plaintext attack where only a small segment of plaintext is assumed to be known.
Keywords. ISAAC. Keystream generator. Cryptanalysis.
The simple ideal cipher system
Boris Ryabko
Secret-key cryptography
We address the problem of how to construct ideal cipher systems when the
length
of a key is much less than the length of an encrypted message. We suggest a
new
secret key cipher system in which firstly the message is transformed into two
parts in such a
way that
the biggest part consists of independent and equiprobable letters.
Secondly the relatively small second part is enciphered wholly by the Vernam
cipher
whereas only few bits from the biggest part are enciphered.
This transformation...
The order of encryption and authentication for protecting communications (Or: how secure is SSL?)
Hugo Krawczyk
We study the question of how to generically compose {\em symmetric}
encryption and authentication when building ``secure channels'' for
the protection of communications over insecure networks.
We show that any secure channels protocol designed to work with any combination
of secure encryption (against chosen plaintext attacks) and secure MAC
must use the encrypt-then-authenticate method.
We demonstrate this by showing that the other common methods
of composing encryption and authentication,...
Analysis of Key-Exchange Protocols and Their Use for Building Secure Channels
Ran Canetti, Hugo Krawczyk
We present a formalism for the analysis of key-exchange protocols
that combines previous definitional approaches and results in a definition
of security that enjoys some important analytical benefits:
(i) any key-exchange protocol that satisfies the security definition
can be composed with symmetric encryption and authentication functions
to provide provably secure communication channels;
and
(ii) the definition allows for simple modular proofs of security:
one can design and prove security...
Forward-Security in Private-Key Cryptography
Mihir Bellare, Bennet Yee
This paper provides a comprehensive treatment of
forward-security in the context of shared-key based cryptographic primitives,
as a practical means to mitigate the damage caused by key-exposure. We provide
definitions of security, practical proven-secure constructions, and
applications for the main primitives in this area. We identify forward-secure
pseudorandom bit generators as the central primitive, providing several
constructions and then showing how forward-secure message...
Dual of New Method for Upper Bounding the Maximum Average Linear Hull Probability for SPNs
Liam Keliher, Henk Meijer, Stafford Tavares
Secret-key cryptography
In [3], we present a new algorithm for computing an upper bound on
the maximum average linear hull probability (MALHP) for the SPN
symmetric cipher structure, a value required to make claims about
provable security against linear cryptanalysis. This algorithm
improves on existing work in that the resulting upper bound is a
function of the number of encryption rounds (other upper bounds
known to the authors are not), and moreover, it can be computed
for an SPN with any linear transformation...
On multivariate signature-only public key cryptosystems
Nicolas T. Courtois
Public-key cryptography
In a paper published at Asiacrypt 2000 a signature scheme that (apparently) cannot be abused for encryption is published.
The problem is highly non-trivial and every solution should be looked upon with caution.
What is especially hard to achieve is to avoid that the public key should leak some information, to be used as a possible "shadow" secondary public key.
In the present paper we argument that the problem has
many natural solutions within the framework of the multivariate...
Efficient Encryption for Rich Message Spaces Under General Assumptions
Alexander Russell, Hong Wang
Public-key cryptography
We present a new family of public-key encryption schemes which combine modest computational demands with provable security guarantees under only general assumptions. The schemes may be realized with any one-way trapdoor permutation, and provide a notion of security corresponding to semantic security under the condition that the message space has sufficient entropy. Furthermore, these schemes can be implemented with very few applications of the underlying one-way permutation: schemes which...
OCB Mode
Phillip Rogaway, Mihir Bellare, John Black, Ted Krovetz
Secret-key cryptography
This paper was prepared for NIST, which is considering new
block-cipher modes of operation. It describes a parallelizable
mode of operation that simultaneously provides both privacy
and authenticity. "OCB mode" encrypts-and-authenticates
an arbitrary message $M\in\bits^*$ using only $\lceil |M|/n\rceil + 2$
block-cipher invocations, where $n$ is the block length of the
underlying block cipher. Additional overhead is small.
OCB refines a scheme, IAPM, suggested by Jutla [IACR-2000/39],...
2001/025
Last updated: 2001-06-20
Cryptanalysis of some elliptic curve based cryptosystems of Paillier
Steven D. Galbraith
Public-key cryptography
Two public key encryption schemes
based on anomalous elliptic curves over rings
are studied.
It is argued that these schemes are not secure.
An Efficient System for Non-transferable Anonymous Credentials with Optional Anonymity Revocation
Jan Camenisch, Anna Lysyanskaya
Cryptographic protocols
A credential system is a system in which users can obtain
credentials from organizations and demonstrate possession of these
credentials. Such a system is anonymous when transactions carried out by the
same user cannot be linked. An anonymous credential system is of significant
practical relevance because it is the best means of providing privacy for
users. In this paper we propose a practical anonymous credential system that
is based on the strong RSA assumption and the decisional...
An observation regarding Jutla's modes of operation
Shai Halevi
Secret-key cryptography
Recently, Jutla suggested two new modes of operation for block ciphers. These modes build on traditional CBC and ECB
modes, respectively, but add to them masking of the outputs and inputs. Jutla proved that these masking operations considerably
strengthen CBC and ECB modes. In particular, together with a simple checksum, the modified modes ensure not only confidentiality, but
also authenticity. Similar modes were also suggested by Gligor and Donsecu and by Rogaway.
In Jutla's proposal (as...
Timed-Release Cryptography
Wenbo Mao
Public-key cryptography
Let $n$ be a large composite number. Without factoring $n$, the
validation of $a^{2^t} (\bmod \, n)$ given $a$, $t$ with $gcd(a, n) =
1$ and $t < n$ can be done in $t$ squarings modulo $n$. For $t \ll n$
(e.g., $n > 2^{1024}$ and $t < 2^{100}$), no lower complexity than $t$
squarings is known to fulfill this task (even considering massive
parallelisation). Rivest et al suggested to use such constructions as
good candidates for realising timed-release crypto problems.
We argue the necessity...
Ciphers with Arbitrary Finite Domains
John Black, Phillip Rogaway
We introduce the problem of enciphering members of a finite set $M$
where $k=|M|$ is arbitrary (in particular, it need not be a power
of two). We want to achieve this goal starting from a block cipher
(which requires a message space of size $N=2^n$, for some $n$).
We look at a few solutions to this problem, focusing on the case
when $M=[0, k-1]$.
Robust key-evolving public key encryption schemes
Wen-Guey Tzeng, Zhi-Jia Tzeng
Public-key cryptography
We propose a key-evolving paradigm to deal with the key
exposure problem of public key encryption schemes.
The key evolving paradigm is like the one used for
forward-secure digital signature schemes.
Let time be divided into time periods such that
at time period $j$, the decryptor holds the secret key
$SK_j$, while the public key PK is fixed during its
lifetime.
At time period $j$, a sender encrypts a message $m$ as
$\langle j, c\rangle$, which can be decrypted only
with the private key...
Are 'Strong' Primes Needed for RSA
Ron Rivest, Robert Silverman
Public-key cryptography
We review the arguments in favor of using so-called ``strong primes''
in the RSA public-key cryptosystem. There are two types of such
arguments: those that say that strong primes are needed to protect
against factoring attacks, and those that say that strong primes are
needed to protect against ``cycling'' attacks (based on repeated
encryption).
We argue that, contrary to common belief, it is unnecessary to use
strong primes in the RSA cryptosystem. That is, by using strong
primes one...
Secure and Efficient Asynchronous Broadcast Protocols
Christian Cachin, Klaus Kursawe, Frank Petzold, Victor Shoup
Cryptographic protocols
Reliable broadcast protocols are a fundamental building block for
implementing replication in fault-tolerant distributed systems. This paper
addresses secure service replication in an asynchronous environment with a
static set of servers, where a malicious adversary may corrupt up to a
threshold of servers and controls the network. We develop a formal model
using concepts from modern cryptography, present modular definitions for
several broadcast problems, including reliable, atomic, and...
A Model for Asynchronous Reactive Systems and its Application to Secure Message Transmission
Birgit Pfitzmann, Michael Waidner
Foundations
We present the first rigorous model for secure reactive systems in
asynchronous networks with a sound cryptographic semantics, supporting
abstract specifications and the composition of secure systems. This
enables modular proofs of security, which is essential in bridging
the gap between the rigorous proof techniques of cryptography and
tool-supported formal proof techniques.
The model follows the general simulatability approach of modern
cryptography. A variety of network structures and...
How to Encrypt Long Messages without Large Size Symmetric/Asymmetric Encryption Schemes
Masashi Mitomo, Kaoru Kurosawa
Public-key cryptography
Suppose that we wish to encrypt long messages
with small overhead by a public key encryption scheme
which is secure against adaptive chosen ciphertext attack (IND-CCA2).
Then the previous schemes require either
a large size one-way trapdoor permutation (OAEP)
or both a large size symmetric encryption scheme
and a small size asymmetric encryption scheme (hybrid encryption).
In this paper,
we show a scheme which requires only a small size
asymmetric encryption scheme satisfying IND-CCA2
for...
2000/062
Last updated: 2001-01-05
Non-Deforming Digital Watermarks
Gideon Samid
Applications
TaKE cryptography offers subliminal marking of a digital stream so that any tampering, induces an unacceptable distortion of the primary information. Encrypted audio and video streams are decrypted by one key to the original content (e.g. music), and through another key to the digital watermark (e.g. name of legitimate user). Unlike the prevailing methods which are based on distorting the protected contents, or locking it through a digital signature, TaKE -- Tailored Key Encryption --...
OAEP Reconsidered
Victor Shoup
Public-key cryptography
The OAEP encryption scheme was introduced by Bellare and Rogaway
at Eurocrypt '94.
It converts any trapdoor permutation scheme into a public-key
encryption scheme.
OAEP is widely believed to provide
resistance against adaptive chosen ciphertext attack.
The main justification for this belief is a supposed proof of security
in the random oracle model, assuming the underlying
trapdoor permutation scheme is one way.
This paper shows conclusively that this justification is invalid.
First, it...
Essential Shannon Security with Keys Smaller Than the Encrypted Message
Gideon Samid
Foundations
To a cryptographer the claim that “Shannon Security was achieved with keys smaller than the encrypted message" appears unworthy of attention, much as the claim of “perpetuum mobile” is to a physicist. Albeit, from an engineering point of view solar cells which power satellites exhibit an “essential perpetuum mobile” and are of great interest. Similarly for Shannon Security, as it is explored in this article. We discuss encryption schemes designed to confound a diligent cryptanalyst...
Multiparty Computation from Threshold Homomorphic Encryption
Ronald Cramer, Ivan Damgård, Jesper Buus Nielsen
Cryptographic protocols
We introduce a new approach to multiparty computation (MPC)
basing it on homomorphic
threshold crypto-systems. We show that given keys for any
sufficiently efficient
system of this type, general MPC protocols for $n$ players can be
devised which are
secure against an active adversary that corrupts any minority of the
players.
The total number of bits sent is $O(nk|C|)$, where $k$ is the
security parameter and $|C|$ is
the size of a (Boolean) circuit computing the function to be
securely...
On Symmetrically Private Information Retrieval
Sanjeev Kumar Mishra
Cryptographic protocols
In this paper we give single-round single-server symmetrically private information retrieval (SPIR) scheme, in which privacy of user follows from intractability of quadratic residuosity problem and and privacy of database follows from the number theoretic XOR assumption introduced in this paper. Proposed scheme achieves the communication complexity $O(n^{\e})$, for any $\e > 0$, where $n$ is the number of bits in the database. We also present an efficient block retrieval SPIR scheme....
Encryption Modes with Almost Free Message Integrity
Charanjit S. Jutla
Secret-key cryptography
We define a new mode of operation for block ciphers which in addition to providing confidentiality also ensures message integrity. In contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (MAC). The new mode of operation, called Integrity Aware Parallelizable Mode (IAPM),
requires a total of m+1 block cipher evaluations on a plain-text of length m blocks. For comparison, the well known CBC (cipher block chaining)...
Electronic Jury Voting Protocols
Alejandro Hevia, Marcos Kiwi
Cryptographic protocols
This work elicits the fact that all current
proposals for electronic voting schemes disclose the final
tally of the votes.
In certain situations, like jury voting, this may be undesirable.
We present a robust and universally verifiable
Membership Testing Scheme (MTS) that allows, among other things,
a collection of voters to cast votes and determine whether
their tally belongs to some pre--specified set (e.g., exceeds a
given threshold)
--- our scheme discloses no additional information than...
Anonymous Fingerprinting with Direct Non-Repudiation
Birgit Pfitzmann, Ahmad-Reza Sadeghi
Cryptographic protocols
Fingerprinting schemes support copyright protection by enabling the merchant of a data item to identify the original buyer of a
redistributed copy. In asymmetric schemes, the merchant can also convince an arbiter of this fact. Anonymous fingerprinting schemes enable buyers to purchase digital items anonymously; however, identification is possible if they redistribute the data item.
Recently, a concrete and reasonably efficient construction based on digital coins was proposed. A disadvantage...
Concrete Security Characterizations of PRFs and PRPs: Reductions and Applications
Anand Desai, Sara Miner
Secret-key cryptography
We investigate, in a concrete security setting, several alternate
characterizations of pseudorandom functions (PRFs) and pseudorandom
permutations (PRPs). By analyzing the concrete complexity of the
reductions between the standard notions and the alternate ones, we
show that the latter, while equivalent under polynomial-time
reductions, are weaker in the concrete security sense. With these
alternate notions, we argue that it is possible to get better
concrete security bounds for certain...
Authenticated Encryption: Relations among notions and analysis of the generic composition paradigm
Mihir Bellare, Chanathip Namprempre
An authenticated encryption scheme is a symmetric encryption scheme whose goal is to provide both privacy and integrity. We consider two possible notions of authenticity for such schemes, namely integrity of plaintexts and integrity of ciphertexts, and relate them (when coupled with IND-CPA) to the standard notions of privacy (IND-CCA, NM-CPA) by presenting implications and separations between all notions considered. We then analyze the security of authenticated encryption schemes designed...
ACE: The Advanced Cryptographic Engine
Thomas Schweinberger, Victor Shoup
Implementation
This document describes
the Advanced Cryptographic Engine (ACE).
It specifies a public key encryption
scheme as well as a
digital signature scheme
with enough detail to ensure interoperability between different
implementations.
These schemes are almost as efficient as commercially used schemes,
yet unlike such schemes, can be proven secure under reasonable
and well-defined
intractability assumptions.
A concrete security analysis of both schemes is presented.
Identification Protocols Secure Against Reset Attacks
Mihir Bellare, Marc Fischlin, Shafi Goldwasser, Silvio Micali
Cryptographic protocols
We provide identification protocols that are secure even
when the adversary can reset the internal state and/or randomization source of
the user identifying itself, and when executed in an asynchronous environment
like the Internet that gives the adversary concurrent access to instances of
the user. These protocols are suitable for use by devices (like smartcards)
which when under adversary control may not be able to reliably maintain their
internal state between invocations.
Authenticated Key Exchange Secure Against Dictionary Attacks
Mihir Bellare, David Pointcheval, Phillip Rogaway
Cryptographic protocols
This paper gives definitions and results about password-based
protocols for authenticated key exchange (AKE), mutual authentication
MA), and the combination of these goals (AKE, MA).
Such protocols are designed to work despite interference by an active
adversary and despite the use of passwords drawn from a space so small
that an adversary might well enumerate, off line,
a user's password.
While several such password-based protocols have been suggested,
the underlying theory has been...
Tailored Key Encryption (TaKE) Tailoring a key for a given pair of plaintext/ciphertext
Gideon Samid
Foundations
Abstract. The prevailing cryptographies are attacked on the basis of
the fact that only a single element in the key space will match a
plausible plaintext with a given ciphertext. Any cryptography that
would violate this unique-key assumption, will achieve added security
through deniability (akin to One Time Pad). Such cryptography is being
described. It is achieved by breaking away from the prevailing notion
that the key is a binary string of a fixed length. The described key is
random-size...
Efficient Protocols based on Probabilistic Encryption using Composite Degree Residue Classes
Ivan Damgård, Mads Jurik
Cryptographic protocols
We study various applications and variants of Paillier's probabilistic
encryption scheme. First, we propose a threshold variant of the scheme,
and also zero-knowledge protocols for proving that a given ciphertext
encodes a given plaintext, and for verifying multiplication of encrypted values.
We then show how these building blocks can be used for applying the
scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election,...
An Encryption Algorithm and Key-stream Generator for Chinese Text Messages by Character Internal Code Structure
Tak-Ming Law
Secret-key cryptography
This paper proposes an algorithm to encipher the Chinese plaintext message written in Big-5/GB Chinese character internal codes. Unlike the ordinary ciphers, the Crypto-key of our proposed algorithm consists of a pair of formulas and a set of parameter values. The senders can formulate and compose their own unique formulas and parameters for encryption. According to the character internal code structure, we apply the formulas in a Key-stream generator to encipher the Chinese plaintext...
Security of all RSA and Discrete Log Bits
Johan Hastad, Mats Naslund
We study the security of individual bits in an RSA
encrypted message E_N(x). We show that given E_N(x), predicting any
single bit in x with only a non-negligible advantage over the trivial
guessing strategy, is (through a polynomial time reduction) as hard as
breaking RSA. Moreover, we prove that blocks of O(log log N) bits of x
are computationally indistinguishable from random bits. The results
carry over to the Rabin encryption scheme.
Considering the discrete exponentiation function,...
Non-Malleable Encryption: Equivalence between Two Notions, and an Indistinguishability-Based Characterization
Mihir Bellare, Amit Sahai
We prove the equivalence of two definitions of non-malleable
encryption appearing in the literature--- the original one of Dolev, Dwork
and Naor and the later one of Bellare, Desai, Pointcheval and Rogaway. The
equivalence relies on a new characterization of non-malleable encryption in
terms of the standard notion of indistinguishability of Goldwasser and
Micali. We show that non-malleability is equivalent to indistinguishability
under a ``parallel chosen ciphertext attack,'' this being a...
Verifiable Encryption and Applications to Group Signatures and Signature Sharing
Jan Camenisch, Ivan Damgaard
We generalize and improve the security and efficiency of the
verifiable encryption scheme of Asokan et al., such that it can rely
on more general assumptions, and can be proven secure without
assuming random oracles. We show a new application of verifiable
encryption to group signatures with separability, these schemes do
not need special purpose keys but can work with a wide range of
signature, identification, and encryption schemes already in use.
Finally, we extend our basic primitive to...
DHAES: An Encryption Scheme Based on the Diffie-Hellman Problem
Michel Abdalla, Mihir Bellare, Phillip Rogaway
scheme, DHAES. The scheme is as efficient as ElGamal encryption, but has
stronger security properties. Furthermore, these security properties are proven
to hold under appropriate assumptions on the underlying primitive.
We show that DHAES has not only the ``basic'' property of secure encryption
(namely privacy under a chosen-plaintext attack) but also achieves privacy
under both non-adaptive and adaptive chosen-ciphertext attacks. (And hence
it also achieves non-malleability.)
DHAES is...
Lattice Based Cryptography: A Global Improvement
Daniele Micciancio
We describe a general technique to simplify as well as to improve
several lattice based cryptographic protocols.
The technique is rather straightforward and is easily applied to
the protocols, and gives both a simpler analysis and better
performance than the original protocols. The improvement is global:
the modified protocols are simpler, faster, require less storage,
use less bandwidth and need less random bits than the originals.
Moreover, the improvement is achieved without any loss in...
Public-key cryptography and password protocols
Shai Halevi, Hugo Krawczyk
We study protocols for strong authentication and key exchange in asymmetric
scenarios where the authentication server possesses a pair of private and
public keys while the client has only a weak human-memorizable password
as its authentication key. We present and analyze several simple password
protocols in this scenario, and show that the security of these protocols
can be formally proven based on standard cryptographic assumptions.
Remarkably, our analysis shows optimal resistance to...
Relations among Notions of Security for Public-Key Encryption Schemes
Mihir Bellare, Anand Desai, David Pointcheval, Phillip Rogaway
We compare the relative strengths of popular notions of security for
public key encryption schemes. We consider the goals of
indistinguishability and non-malleability, each under chosen plaintext
attack and two kinds of chosen ciphertext attack. For each of the
resulting pairs of definitions we prove either an implication (every
scheme meeting one notion must meet the other) or a separation (there
is a scheme meeting one notion but not the other, assuming the first
notion can be met at...
Many-to-one Trapdoor Functions and their Relation to Public-key Cryptosystems
Mihir Bellare, Shai Halevi, Amit Sahai, Salil Vadhan
The heart of the task of building public key cryptosystems is viewed
as that of ``making trapdoors;'' in fact, public key cryptosystems and
trapdoor functions are often discussed as synonymous. How accurate is
this view? In this paper we endeavor to get a better understanding of
the nature of ``trapdoorness'' and its relation to public key
cryptosystems, by broadening the scope of the investigation: we look
at general trapdoor functions; that is, functions that are not
necessarily injective...
The Random Oracle Methodology, Revisited
Ran Canetti, Oded Goldreich, Shai Halevi
Foundations
We take a critical look at the relationship between the security of
cryptographic schemes in the Random Oracle Model, and the security of the
schemes that result from implementing the random oracle by so called
"cryptographic hash functions".
The main result of this paper is a negative one: There exist signature and
encryption schemes that are secure in the Random Oracle Model, but for which
any implementation of the random oracle results in insecure schemes.
In the process of devising the...
A Practical Public Key Cryptosystem Provably Secure against Adaptive Chosen Ciphertext Attack
Ronald Cramer, Victor Shoup
A new public key cryptosystem is presented that is provably secure
against adaptive chosen ciphertext attack.
The scheme is quite practical, and the proof of security relies
only on standard intractability assumptions.
On Protocol Divertibility
Gerrit Bleumer
In this paper, we establish the notion of divertibility as a
protocol property
as opposed to the existing notion as a language property (see Okamoto,
Ohta). We give a definition of protocol divertibility that applies to
arbitrary 2-party protocols and is compatible with Okamoto and Ohta's
definition
in the case of interactive zero-knowledge proofs. Other important examples
falling under the new definition are blind signature protocols. A sufficient
criterion for divertibility is presented...
Optimistic fair Exchange of Digital Signatures
N. Asokan, V. Shoup, M. Waidner
We present a new protocol that allows two players to exchange digital
signatures (including RSA and DSS) over the Internet in a fair way, so
that either each player gets the other's signature, or neither player
does. One obvious application is where the signatures represent items
of value, for example, an electronic check or airline ticket; the
protocol can also be adapted to exchange encrypted data. The protocol
relies on a trusted third party, but is "optimistic," in that the
third...
Identity Escrow
Joe Kilian, Erez Petrank
We introduce the notion of escrowed identity, an application of
key-escrow ideas to the problem of identification. In escrowed
identity, one party, A, does not give his identity to another
party B, but rather gives him information that would allow an
authorized third party, E, to determine A's identity. However, B
receives a guarantee that E can indeed determine A's identity. We
give protocols for escrowed identity based on the El-Gamal (signature
and encryption) schemes and on the RSA...
Public-Key Cryptosystems from Lattice Reduction Problems
Oded Goldreich, Shafi Goldwasser, Shai Halevi
We present a new proposal for a trapdoor one-way function, from which
we derive public-key encryption and digital signatures.
The security of the new construction is based on the
conjectured computational difficulty of lattice-reduction problems,
providing a possible alternative to existing
public-key encryption algorithms
and digital signatures such as RSA and DSS.
Deniable Encryption
Ran Canetti, Cynthia Dwork, Moni Naor, Rafi Ostrovsky
Consider a situation in which the transmission of encrypted
messages is intercepted by an adversary who can later
ask the sender to reveal
the random choices (and also the secret key, if one exists)
used in generating
the ciphertext, thereby exposing the cleartext.
An encryption scheme is <B>deniable</B> if the sender can generate
`fake random choices' that will make the ciphertext `look like'
an encryption of a different cleartext, thus keeping the
real cleartext private.
Analogous...
-
« Previous
-
1
- ...
- 61
- 62
A new public key encryption scheme, along with several variants, is proposed and analyzed. The scheme and its variants are quite practical, and are proved secure against adaptive chosen ciphertext attack under standard intractability assumptions. These appear to be the first public-key encryption schemes in the literature that are simultaneously practical and provably secure.
We argue that threshold trust is not an option in most of the real-life electronic auctions. We then propose two new cryptographic Vickrey auction schemes that involve, apart from the bidders and the seller $S$, an auction authority $A$ so that unless $S$ and $A$ collude the outcome of auctions will be correct, and moreover, $S$ will not get any information about the bids, while $A$ will learn bid statistics. Further extensions make it possible to decrease damage that colluding $S$ and $A$...
We consider threshold cryptosystems over a composite modulus $N$ where the \emph{factors} of $N$ are shared among the participants as the secret key. This is a new paradigm for threshold cryptosystems based on a composite modulus, differing from the typical treatment of RSA-based systems where a ``decryption exponent'' is shared among the participants. Our approach yields solutions to some open problems in threshold cryptography; in particular, we obtain the following: 1. \emph{Threshold...
Many of the keystream generators which are used in practice are LFSR-based in the sense that they produce the keystream according to a rule $y=C(L(x))$, where $L(x)$ denotes an internal linear bitstream, produced by a small number of parallel linear feedback shift registers (LFSRs), and $C$ denotes some nonlinear compression function. We present an $n^{O(1)} 2^{(1-\alpha)/(1+\alpha)n}$ time bounded attack, the FBDD-attack, against LFSR-based generators, which computes the secret initial...
Canetti and Fischlin have recently proposed the security notion {\em universal composability} for commitment schemes and provided two examples. This new notion is very strong. It guarantees that security is maintained even when an unbounded number of copies of the scheme are running concurrently, also it guarantees non-malleability, resilience to selective decommitment, and security against adaptive adversaries. Both of their schemes uses $\Theta(k)$ bits to commit to one bit and can be...
We propose a fully functional identity-based encryption scheme (IBE). The scheme has chosen ciphertext security in the random oracle model assuming an elliptic curve variant of the computational Diffie-Hellman problem. Our system is based on bilinear maps between groups. The Weil pairing on elliptic curves is an example of such a map. We give precise definitions for secure identity based encryption schemes and give several applications for such systems.
A new family of broadcast encryption schemes (BESs), which will be called linear broadcast encryption schemes (LBESs), is presented in this paper by using linear algebraic techniques. This family generalizes most previous proposals and provide a general framework to the study of broadcast encryption schemes. We present a method to construct LBESs for a general specification structure in order to find schemes that fit in situations that have not been considered before.
The most important point in the design of broadcast encryption schemes (BESs) is obtain a good trade-off between the amount of secret information that must be stored by every user and the length of the broadcast message, which are measured, respectively, by the information rate $\rho$ and the broadcast information rate $\rho_B$. In this paper we present a simple method to combine two given BESs in order to improve the trade-off between $\rho$ and $\rho_B$ by finding BESs with good...
A family $(S_t)$ of sets is $p$-bounded Diophantine if $S_t$ has a representing $p$-bounded polynomial $R_{S,t}$, s.t. $x\in S_t \iff (\exists y)[R_{S}(x;y)=0]$. We say that $(S_t)$ is unbounded Diophantine if additionally, $R_{S,t}$ is a fixed $t$-independent polynomial. We show that $p$-bounded (resp., unbounded) Diophantine set has a polynomial-size (resp., constant-size) statistical zero-knowledge proof system that a committed tuple $x$ belongs to $S$. We describe efficient SZK proof...
We present several new and fairly practical public-key encryption schemes and prove them secure against adaptive chosen ciphertext attack. One scheme is based on Paillier's Decision Composite Residuosity (DCR) assumption, while another is based in the classical Quadratic Residuosity (QR) assumption. The analysis is in the standard cryptographic model, i.e., the security of our schemes does not rely on the Random Oracle model. We also introduce the notion of a universal hash proof ...
This note summarizes the results of Babbage's cryptanalysis of COS ciphers and shows that in fact COS ciphers are not weak as claimed. These ciphers have been designed according a novel concept of encryption directly determined by the context of use. This concept is here more precisely defined.
This paper addresses the security of authenticated encryption schemes in the public key setting. We present two new notions of authenticity that are stronger than the integrity notions given in the symmetric setting \cite{bn00}. We also show that chosen-ciphertext attack security (IND-CCA) in the public key setting is not obtained in general from the combination of chosen-plaintext security (IND-CPA) and integrity of ciphertext (INT-CTXT), which is in contrast to the results shown in the...
In this paper, we study the security of randomized CBC-MACs and propose a new construction that resists birthday paradox attacks and provably reaches full security. The size of the MAC tags in this construction is optimal, i.e., exactly twice the size of the block cipher. Up to a constant, the security of the proposed randomized CBC-MAC using an n-bit block cipher is the same as the security of the usual encrypted CBC-MAC using a 2n-bit block cipher. Moreover, this construction adds a...
In the trivial $n$-recipient public-key encryption scheme, a ciphertext is a concatenation of independently encrypted messages for $n$ recipients. In this paper, we say that an $n$-recipient scheme has a ``{\it shortened ciphertext}'' property if the length of the ciphertext is almost a half (or less) of the trivial scheme and the security is still almost the same as the underlying single-recipient scheme. We first present (multi-plaintext, multi-recipient) schemes with the ``{\it...
Informally, an {\em obfuscator} $O$ is an (efficient, probabilistic) ``compiler'' that takes as input a program (or circuit) $P$ and produces a new program $O(P)$ that has the same functionality as $P$ yet is ``unintelligible'' in some sense. Obfuscators, if they exist, would have a wide variety of cryptographic and complexity-theoretic applications, ranging from software protection to homomorphic encryption to complexity-theoretic analogues of Rice's theorem. Most of these applications are...
Stream ciphers are an important class of encryption algorithms, which are widely used in practice. In this paper the security of the WAKE stream cipher is investigated. We present two chosen plaintext attacks on this cipher. The complexities of these attacks can be estimated as 10^^19.2 and 10^^14.4.
We deal with the problem of a center sending a message to a group of users such that some subset of the users is considered revoked and should not be able to obtain the content of the message. We concentrate on the stateless receiver case, where the users do not (necessarily) update their state from session to session. We present a framework called the Subset-Cover framework, which abstracts a variety of revocation schemes including some previously known ones. We provide sufficient...
This paper is concerned with generalisations of Paillier's probabilistic encryption scheme from the integers modulo a square to elliptic curves over rings. Paillier himself described two public key encryption schemes based on anomalous elliptic curves over rings. It is argued that these schemes are not secure. A more natural generalisation of Paillier's scheme to elliptic curves is given.
Stream ciphers are often used in applications where high speed and low delay are a requirement. The ISAAC keystream generator is a fast software-oriented encryption algorithm. In this papers the security of the ISAAC keystream generator is investigated. Cryptanalytic algorithm is developed for a known plaintext attack where only a small segment of plaintext is assumed to be known. Keywords. ISAAC. Keystream generator. Cryptanalysis.
We address the problem of how to construct ideal cipher systems when the length of a key is much less than the length of an encrypted message. We suggest a new secret key cipher system in which firstly the message is transformed into two parts in such a way that the biggest part consists of independent and equiprobable letters. Secondly the relatively small second part is enciphered wholly by the Vernam cipher whereas only few bits from the biggest part are enciphered. This transformation...
We study the question of how to generically compose {\em symmetric} encryption and authentication when building ``secure channels'' for the protection of communications over insecure networks. We show that any secure channels protocol designed to work with any combination of secure encryption (against chosen plaintext attacks) and secure MAC must use the encrypt-then-authenticate method. We demonstrate this by showing that the other common methods of composing encryption and authentication,...
We present a formalism for the analysis of key-exchange protocols that combines previous definitional approaches and results in a definition of security that enjoys some important analytical benefits: (i) any key-exchange protocol that satisfies the security definition can be composed with symmetric encryption and authentication functions to provide provably secure communication channels; and (ii) the definition allows for simple modular proofs of security: one can design and prove security...
This paper provides a comprehensive treatment of forward-security in the context of shared-key based cryptographic primitives, as a practical means to mitigate the damage caused by key-exposure. We provide definitions of security, practical proven-secure constructions, and applications for the main primitives in this area. We identify forward-secure pseudorandom bit generators as the central primitive, providing several constructions and then showing how forward-secure message...
In [3], we present a new algorithm for computing an upper bound on the maximum average linear hull probability (MALHP) for the SPN symmetric cipher structure, a value required to make claims about provable security against linear cryptanalysis. This algorithm improves on existing work in that the resulting upper bound is a function of the number of encryption rounds (other upper bounds known to the authors are not), and moreover, it can be computed for an SPN with any linear transformation...
In a paper published at Asiacrypt 2000 a signature scheme that (apparently) cannot be abused for encryption is published. The problem is highly non-trivial and every solution should be looked upon with caution. What is especially hard to achieve is to avoid that the public key should leak some information, to be used as a possible "shadow" secondary public key. In the present paper we argument that the problem has many natural solutions within the framework of the multivariate...
We present a new family of public-key encryption schemes which combine modest computational demands with provable security guarantees under only general assumptions. The schemes may be realized with any one-way trapdoor permutation, and provide a notion of security corresponding to semantic security under the condition that the message space has sufficient entropy. Furthermore, these schemes can be implemented with very few applications of the underlying one-way permutation: schemes which...
This paper was prepared for NIST, which is considering new block-cipher modes of operation. It describes a parallelizable mode of operation that simultaneously provides both privacy and authenticity. "OCB mode" encrypts-and-authenticates an arbitrary message $M\in\bits^*$ using only $\lceil |M|/n\rceil + 2$ block-cipher invocations, where $n$ is the block length of the underlying block cipher. Additional overhead is small. OCB refines a scheme, IAPM, suggested by Jutla [IACR-2000/39],...
Two public key encryption schemes based on anomalous elliptic curves over rings are studied. It is argued that these schemes are not secure.
A credential system is a system in which users can obtain credentials from organizations and demonstrate possession of these credentials. Such a system is anonymous when transactions carried out by the same user cannot be linked. An anonymous credential system is of significant practical relevance because it is the best means of providing privacy for users. In this paper we propose a practical anonymous credential system that is based on the strong RSA assumption and the decisional...
Recently, Jutla suggested two new modes of operation for block ciphers. These modes build on traditional CBC and ECB modes, respectively, but add to them masking of the outputs and inputs. Jutla proved that these masking operations considerably strengthen CBC and ECB modes. In particular, together with a simple checksum, the modified modes ensure not only confidentiality, but also authenticity. Similar modes were also suggested by Gligor and Donsecu and by Rogaway. In Jutla's proposal (as...
Let $n$ be a large composite number. Without factoring $n$, the validation of $a^{2^t} (\bmod \, n)$ given $a$, $t$ with $gcd(a, n) = 1$ and $t < n$ can be done in $t$ squarings modulo $n$. For $t \ll n$ (e.g., $n > 2^{1024}$ and $t < 2^{100}$), no lower complexity than $t$ squarings is known to fulfill this task (even considering massive parallelisation). Rivest et al suggested to use such constructions as good candidates for realising timed-release crypto problems. We argue the necessity...
We introduce the problem of enciphering members of a finite set $M$ where $k=|M|$ is arbitrary (in particular, it need not be a power of two). We want to achieve this goal starting from a block cipher (which requires a message space of size $N=2^n$, for some $n$). We look at a few solutions to this problem, focusing on the case when $M=[0, k-1]$.
We propose a key-evolving paradigm to deal with the key exposure problem of public key encryption schemes. The key evolving paradigm is like the one used for forward-secure digital signature schemes. Let time be divided into time periods such that at time period $j$, the decryptor holds the secret key $SK_j$, while the public key PK is fixed during its lifetime. At time period $j$, a sender encrypts a message $m$ as $\langle j, c\rangle$, which can be decrypted only with the private key...
We review the arguments in favor of using so-called ``strong primes'' in the RSA public-key cryptosystem. There are two types of such arguments: those that say that strong primes are needed to protect against factoring attacks, and those that say that strong primes are needed to protect against ``cycling'' attacks (based on repeated encryption). We argue that, contrary to common belief, it is unnecessary to use strong primes in the RSA cryptosystem. That is, by using strong primes one...
Reliable broadcast protocols are a fundamental building block for implementing replication in fault-tolerant distributed systems. This paper addresses secure service replication in an asynchronous environment with a static set of servers, where a malicious adversary may corrupt up to a threshold of servers and controls the network. We develop a formal model using concepts from modern cryptography, present modular definitions for several broadcast problems, including reliable, atomic, and...
We present the first rigorous model for secure reactive systems in asynchronous networks with a sound cryptographic semantics, supporting abstract specifications and the composition of secure systems. This enables modular proofs of security, which is essential in bridging the gap between the rigorous proof techniques of cryptography and tool-supported formal proof techniques. The model follows the general simulatability approach of modern cryptography. A variety of network structures and...
Suppose that we wish to encrypt long messages with small overhead by a public key encryption scheme which is secure against adaptive chosen ciphertext attack (IND-CCA2). Then the previous schemes require either a large size one-way trapdoor permutation (OAEP) or both a large size symmetric encryption scheme and a small size asymmetric encryption scheme (hybrid encryption). In this paper, we show a scheme which requires only a small size asymmetric encryption scheme satisfying IND-CCA2 for...
TaKE cryptography offers subliminal marking of a digital stream so that any tampering, induces an unacceptable distortion of the primary information. Encrypted audio and video streams are decrypted by one key to the original content (e.g. music), and through another key to the digital watermark (e.g. name of legitimate user). Unlike the prevailing methods which are based on distorting the protected contents, or locking it through a digital signature, TaKE -- Tailored Key Encryption --...
The OAEP encryption scheme was introduced by Bellare and Rogaway at Eurocrypt '94. It converts any trapdoor permutation scheme into a public-key encryption scheme. OAEP is widely believed to provide resistance against adaptive chosen ciphertext attack. The main justification for this belief is a supposed proof of security in the random oracle model, assuming the underlying trapdoor permutation scheme is one way. This paper shows conclusively that this justification is invalid. First, it...
To a cryptographer the claim that “Shannon Security was achieved with keys smaller than the encrypted message" appears unworthy of attention, much as the claim of “perpetuum mobile” is to a physicist. Albeit, from an engineering point of view solar cells which power satellites exhibit an “essential perpetuum mobile” and are of great interest. Similarly for Shannon Security, as it is explored in this article. We discuss encryption schemes designed to confound a diligent cryptanalyst...
We introduce a new approach to multiparty computation (MPC) basing it on homomorphic threshold crypto-systems. We show that given keys for any sufficiently efficient system of this type, general MPC protocols for $n$ players can be devised which are secure against an active adversary that corrupts any minority of the players. The total number of bits sent is $O(nk|C|)$, where $k$ is the security parameter and $|C|$ is the size of a (Boolean) circuit computing the function to be securely...
In this paper we give single-round single-server symmetrically private information retrieval (SPIR) scheme, in which privacy of user follows from intractability of quadratic residuosity problem and and privacy of database follows from the number theoretic XOR assumption introduced in this paper. Proposed scheme achieves the communication complexity $O(n^{\e})$, for any $\e > 0$, where $n$ is the number of bits in the database. We also present an efficient block retrieval SPIR scheme....
We define a new mode of operation for block ciphers which in addition to providing confidentiality also ensures message integrity. In contrast, previously for message integrity a separate pass was required to compute a cryptographic message authentication code (MAC). The new mode of operation, called Integrity Aware Parallelizable Mode (IAPM), requires a total of m+1 block cipher evaluations on a plain-text of length m blocks. For comparison, the well known CBC (cipher block chaining)...
This work elicits the fact that all current proposals for electronic voting schemes disclose the final tally of the votes. In certain situations, like jury voting, this may be undesirable. We present a robust and universally verifiable Membership Testing Scheme (MTS) that allows, among other things, a collection of voters to cast votes and determine whether their tally belongs to some pre--specified set (e.g., exceeds a given threshold) --- our scheme discloses no additional information than...
Fingerprinting schemes support copyright protection by enabling the merchant of a data item to identify the original buyer of a redistributed copy. In asymmetric schemes, the merchant can also convince an arbiter of this fact. Anonymous fingerprinting schemes enable buyers to purchase digital items anonymously; however, identification is possible if they redistribute the data item. Recently, a concrete and reasonably efficient construction based on digital coins was proposed. A disadvantage...
We investigate, in a concrete security setting, several alternate characterizations of pseudorandom functions (PRFs) and pseudorandom permutations (PRPs). By analyzing the concrete complexity of the reductions between the standard notions and the alternate ones, we show that the latter, while equivalent under polynomial-time reductions, are weaker in the concrete security sense. With these alternate notions, we argue that it is possible to get better concrete security bounds for certain...
An authenticated encryption scheme is a symmetric encryption scheme whose goal is to provide both privacy and integrity. We consider two possible notions of authenticity for such schemes, namely integrity of plaintexts and integrity of ciphertexts, and relate them (when coupled with IND-CPA) to the standard notions of privacy (IND-CCA, NM-CPA) by presenting implications and separations between all notions considered. We then analyze the security of authenticated encryption schemes designed...
This document describes the Advanced Cryptographic Engine (ACE). It specifies a public key encryption scheme as well as a digital signature scheme with enough detail to ensure interoperability between different implementations. These schemes are almost as efficient as commercially used schemes, yet unlike such schemes, can be proven secure under reasonable and well-defined intractability assumptions. A concrete security analysis of both schemes is presented.
We provide identification protocols that are secure even when the adversary can reset the internal state and/or randomization source of the user identifying itself, and when executed in an asynchronous environment like the Internet that gives the adversary concurrent access to instances of the user. These protocols are suitable for use by devices (like smartcards) which when under adversary control may not be able to reliably maintain their internal state between invocations.
This paper gives definitions and results about password-based protocols for authenticated key exchange (AKE), mutual authentication MA), and the combination of these goals (AKE, MA). Such protocols are designed to work despite interference by an active adversary and despite the use of passwords drawn from a space so small that an adversary might well enumerate, off line, a user's password. While several such password-based protocols have been suggested, the underlying theory has been...
Abstract. The prevailing cryptographies are attacked on the basis of the fact that only a single element in the key space will match a plausible plaintext with a given ciphertext. Any cryptography that would violate this unique-key assumption, will achieve added security through deniability (akin to One Time Pad). Such cryptography is being described. It is achieved by breaking away from the prevailing notion that the key is a binary string of a fixed length. The described key is random-size...
We study various applications and variants of Paillier's probabilistic encryption scheme. First, we propose a threshold variant of the scheme, and also zero-knowledge protocols for proving that a given ciphertext encodes a given plaintext, and for verifying multiplication of encrypted values. We then show how these building blocks can be used for applying the scheme to efficient electronic voting. This reduces dramatically the work needed to compute the final result of an election,...
This paper proposes an algorithm to encipher the Chinese plaintext message written in Big-5/GB Chinese character internal codes. Unlike the ordinary ciphers, the Crypto-key of our proposed algorithm consists of a pair of formulas and a set of parameter values. The senders can formulate and compose their own unique formulas and parameters for encryption. According to the character internal code structure, we apply the formulas in a Key-stream generator to encipher the Chinese plaintext...
We study the security of individual bits in an RSA encrypted message E_N(x). We show that given E_N(x), predicting any single bit in x with only a non-negligible advantage over the trivial guessing strategy, is (through a polynomial time reduction) as hard as breaking RSA. Moreover, we prove that blocks of O(log log N) bits of x are computationally indistinguishable from random bits. The results carry over to the Rabin encryption scheme. Considering the discrete exponentiation function,...
We prove the equivalence of two definitions of non-malleable encryption appearing in the literature--- the original one of Dolev, Dwork and Naor and the later one of Bellare, Desai, Pointcheval and Rogaway. The equivalence relies on a new characterization of non-malleable encryption in terms of the standard notion of indistinguishability of Goldwasser and Micali. We show that non-malleability is equivalent to indistinguishability under a ``parallel chosen ciphertext attack,'' this being a...
We generalize and improve the security and efficiency of the verifiable encryption scheme of Asokan et al., such that it can rely on more general assumptions, and can be proven secure without assuming random oracles. We show a new application of verifiable encryption to group signatures with separability, these schemes do not need special purpose keys but can work with a wide range of signature, identification, and encryption schemes already in use. Finally, we extend our basic primitive to...
scheme, DHAES. The scheme is as efficient as ElGamal encryption, but has stronger security properties. Furthermore, these security properties are proven to hold under appropriate assumptions on the underlying primitive. We show that DHAES has not only the ``basic'' property of secure encryption (namely privacy under a chosen-plaintext attack) but also achieves privacy under both non-adaptive and adaptive chosen-ciphertext attacks. (And hence it also achieves non-malleability.) DHAES is...
We describe a general technique to simplify as well as to improve several lattice based cryptographic protocols. The technique is rather straightforward and is easily applied to the protocols, and gives both a simpler analysis and better performance than the original protocols. The improvement is global: the modified protocols are simpler, faster, require less storage, use less bandwidth and need less random bits than the originals. Moreover, the improvement is achieved without any loss in...
We study protocols for strong authentication and key exchange in asymmetric scenarios where the authentication server possesses a pair of private and public keys while the client has only a weak human-memorizable password as its authentication key. We present and analyze several simple password protocols in this scenario, and show that the security of these protocols can be formally proven based on standard cryptographic assumptions. Remarkably, our analysis shows optimal resistance to...
We compare the relative strengths of popular notions of security for public key encryption schemes. We consider the goals of indistinguishability and non-malleability, each under chosen plaintext attack and two kinds of chosen ciphertext attack. For each of the resulting pairs of definitions we prove either an implication (every scheme meeting one notion must meet the other) or a separation (there is a scheme meeting one notion but not the other, assuming the first notion can be met at...
The heart of the task of building public key cryptosystems is viewed as that of ``making trapdoors;'' in fact, public key cryptosystems and trapdoor functions are often discussed as synonymous. How accurate is this view? In this paper we endeavor to get a better understanding of the nature of ``trapdoorness'' and its relation to public key cryptosystems, by broadening the scope of the investigation: we look at general trapdoor functions; that is, functions that are not necessarily injective...
We take a critical look at the relationship between the security of cryptographic schemes in the Random Oracle Model, and the security of the schemes that result from implementing the random oracle by so called "cryptographic hash functions". The main result of this paper is a negative one: There exist signature and encryption schemes that are secure in the Random Oracle Model, but for which any implementation of the random oracle results in insecure schemes. In the process of devising the...
A new public key cryptosystem is presented that is provably secure against adaptive chosen ciphertext attack. The scheme is quite practical, and the proof of security relies only on standard intractability assumptions.
In this paper, we establish the notion of divertibility as a protocol property as opposed to the existing notion as a language property (see Okamoto, Ohta). We give a definition of protocol divertibility that applies to arbitrary 2-party protocols and is compatible with Okamoto and Ohta's definition in the case of interactive zero-knowledge proofs. Other important examples falling under the new definition are blind signature protocols. A sufficient criterion for divertibility is presented...
We present a new protocol that allows two players to exchange digital signatures (including RSA and DSS) over the Internet in a fair way, so that either each player gets the other's signature, or neither player does. One obvious application is where the signatures represent items of value, for example, an electronic check or airline ticket; the protocol can also be adapted to exchange encrypted data. The protocol relies on a trusted third party, but is "optimistic," in that the third...
We introduce the notion of escrowed identity, an application of key-escrow ideas to the problem of identification. In escrowed identity, one party, A, does not give his identity to another party B, but rather gives him information that would allow an authorized third party, E, to determine A's identity. However, B receives a guarantee that E can indeed determine A's identity. We give protocols for escrowed identity based on the El-Gamal (signature and encryption) schemes and on the RSA...
We present a new proposal for a trapdoor one-way function, from which we derive public-key encryption and digital signatures. The security of the new construction is based on the conjectured computational difficulty of lattice-reduction problems, providing a possible alternative to existing public-key encryption algorithms and digital signatures such as RSA and DSS.
Consider a situation in which the transmission of encrypted messages is intercepted by an adversary who can later ask the sender to reveal the random choices (and also the secret key, if one exists) used in generating the ciphertext, thereby exposing the cleartext. An encryption scheme is <B>deniable</B> if the sender can generate `fake random choices' that will make the ciphertext `look like' an encryption of a different cleartext, thus keeping the real cleartext private. Analogous...
- « Previous
- 1
- ...
- 61
- 62
