CryptoDB

Aggelos Kiayias

Publications

Year
Venue
Title
2018
EUROCRYPT
2018
CRYPTO
Non-malleable codes were introduced by Dziembowski, Pietrzak and Wichs (ICS ’10) and its main application is the protection of cryptographic devices against tampering attacks on memory. In this work, we initiate a comprehensive study on non-malleable codes for the class of partial functions, that read/write on an arbitrary subset of codeword bits with specific cardinality. Our constructions are efficient in terms of information rate, while allowing the attacker to access asymptotically almost the entire codeword. In addition, they satisfy a notion which is stronger than non-malleability, that we call non-malleability with manipulation detection, guaranteeing that any modified codeword decodes to either the original message or to $\bot$⊥. Finally, our primitive implies All-Or-Nothing Transforms (AONTs) and as a result our constructions yield efficient AONTs under standard assumptions (only one-way functions), which, to the best of our knowledge, was an open question until now. In addition to this, we present a number of additional applications of our primitive in tamper resilience.
2018
PKC
The Bitcoin backbone protocol (Eurocrypt 2015) extracts basic properties of Bitcoin’s underlying blockchain data structure, such as “common prefix” and “chain quality,” and shows how fundamental applications including consensus and a robust public transaction ledger can be built on top of them. The underlying assumptions are “proofs of work” (POWs), adversarial hashing power strictly less than 1/2 and no adversarial pre-computation—or, alternatively, the existence of an unpredictable “genesis” block.In this paper we first show how to remove the latter assumption, presenting a “bootstrapped” Bitcoin-like blockchain protocol relying on POWs that builds genesis blocks “from scratch” in the presence of adversarial pre-computation. Importantly, the round complexity of the genesis block generation process is independent of the number of participants.Next, we consider applications of our construction, including a PKI generation protocol and a consensus protocol without trusted setup assuming an honest majority (in terms of computational power). Previous results in the same setting (unauthenticated parties, no trusted setup, POWs) required a round complexity linear in the number of participants.
2018
ASIACRYPT
Email communication is amongst the most prominent online activities, and as such, can put sensitive information at risk. It is thus of high importance that internet email applications are designed in a privacy-aware manner and analyzed under a rigorous threat model. The Snowden revelations (2013) suggest that such a model should feature a global adversary, in light of the observational tools available. Furthermore, the fact that protecting metadata can be of equal importance as protecting the communication context implies that end-to-end encryption may be necessary, but it is not sufficient.With this in mind, we utilize the Universal Composability framework [Canetti, 2001] to introduce an expressive cryptographic model for email “ecosystems” that can formally and precisely capture various well-known privacy notions (unobservability, anonymity, unlinkability, etc.), by parameterizing the amount of leakage an ideal-world adversary (simulator) obtains from the email functionality.Equipped with our framework, we present and analyze the security of two email constructions that follow different directions in terms of the efficiency vs. privacy tradeoff. The first one achieves optimal security (only the online/offline mode of the users is leaked), but it is mainly of theoretical interest; the second one is based on parallel mixing [Golle and Juels, 2004] and is more practical, while it achieves anonymity with respect to users that have similar amount of sending and receiving activity.
2017
PKC
2017
CRYPTO
2017
CRYPTO
2016
EUROCRYPT
2016
ASIACRYPT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
EPRINT
2015
TCC
2015
EUROCRYPT
2015
EUROCRYPT
2014
EPRINT
2014
JOFC
2014
ASIACRYPT
2013
ASIACRYPT
2011
ASIACRYPT
2010
PKC
2009
PKC
2009
EUROCRYPT
2009
EPRINT
The notion of Zero Knowledge Proofs (of knowledge) [ZKP] is central to cryptography; it provides a set of security properties that proved indispensable in concrete protocol design. These properties are defined for any given input and also for any auxiliary verifier private state, as they are aimed at any use of the protocol as a subroutine in a bigger application. Many times, however, moving the theoretical notion to practical designs has been quite problematic. This is due to the fact that the most efficient protocols fail to provide the above ZKP properties {\em for all} possible inputs and verifier states. This situation has created various problems to protocol designers who have often either introduced imperfect protocols with mistakes or with lack of security arguments, or they have been forced to use much less efficient protocols in order to achieve the required properties. In this work we address this issue by introducing the notion of protocol portability,'' a property that identifies input and verifier state distributions under which a protocol becomes a ZKP when called as a subroutine in a sequential execution of a larger application. We then concentrate on the very efficient and heavily employed Generalized Schnorr Proofs'' (GSP) and identify the portability of such protocols. We also point to previous protocol weaknesses and errors that have been made in numerous applications throughout the years, due to employment of GSP instances while lacking the notion of portability (primarily in the case of unknown order groups). This demonstrates that cryptographic application designers who care about efficiency need to consider our notion carefully. We provide a compact specification language for GSP protocols that protocol designers can employ. Our specification language is consistent with the ad-hoc notation that is currently widely used and it offers automatic derivation of the proof protocol while dictating its portability (i.e., the proper initial state and inputs) and its security guarantees. Thus, our language specifications can be used modularly in designs and proofs. This assures that the protocol implementation can indeed be used as a subroutine that is ZKP in its context. Finally, as a second alternative to designers wishing to use GSPs, we present a modification of GSP protocols that is unconditionally portable (i.e., ZKP) and is still quite efficient. Our constructions are the first such protocols proven secure in the standard model (while the previously known efficient constructions relied on the Random Oracle model).
2008
TCC
2008
EPRINT
The Universal Composability (UC) framework, introduced by Canetti, allows for the design of cryptographic protocols satisfying strong security properties, such as non-malleability and preservation of security under (concurrent) composition. In the UC framework (as in several other frameworks), the security of a protocol carrying out a given task is formulated via the trusted-party paradigm,'' where the protocol execution is compared with an ideal process where the outputs are computed by a trusted party that sees all the inputs. A protocol is said to securely carry out a given task if running the protocol with a realistic adversary amounts to emulating'' the ideal process with the appropriate trusted party. In the UC framework the program run by the trusted party is called an {\em ideal functionality}. However, while this simulation-based security formulation provides strong security guarantees, its usefulness is contingent on the properties and correct specification of the realized ideal functionality, which, as demonstrated in recent years by the coexistence of complex, multiple functionalities for the same task as well as by their unstable'' nature, does not seem to be an easy task. On the other hand, the more traditional, {\em gamed-based} definitions of cryptographic tasks, although providing a less satisfying level of security (stand-alone executions, or executions in very controlled settings), have been successful in terms of formalizing as well as capturing the underlying task's natural properties. In this paper we address this gap in the security modeling of cryptographic properties, and introduce a general methodology for translating game-based definitions of properties of cryptographic tasks to syntactically concise ideal functionality programs. Moreover, taking advantage of a suitable algebraic structure of the space of our ideal functionality programs, we are able to accumulate'' ideal functionalities based on many different game-based security notions. In this way, we can obtain a well-defined mapping of all the game-based security properties of a cryptographic task to its corresponding UC counterpart. In addition, the methodology allows us to debug'' existing ideal functionalities, establish relations between them, and make some critical observations about the modeling of the ideal process in the UC framework. We demonstrate the power of our approach by applying our methodology to a variety of basic cryptographic tasks, including commitments, digital signatures, public-key encryption, zero-knowledge proofs, and oblivious transfer. Instrumental in our translation methodology is the new notion of a {\em canonical functionality class} for a cryptographic task which is endowed with a bounded semilattice structure. This structure allows the grading of ideal functionalities according to the level of security they offer as well as their natural joining, enabling the modular combination of security properties.
2007
ASIACRYPT
2007
CRYPTO
2007
EPRINT
We present group encryption, a new cryptographic primitive which is the encryption analogue of a group signature. It possesses similar verifiability, security and privacy properties, but whereas a group signature is useful whenever we need to conceal the source (signer) within a group of legitimate users, a group encryption is useful whenever we need to conceal a recipient (decryptor) within a group of legitimate receivers. We introduce and model the new primitive and present sufficient as well as necessary conditions for its generic implementation. We then develop an efficient novel number theoretic construction for group encryption of discrete logarithms whose complexity is independent of the group size. To achieve this we construct a new public-key encryption for discrete logarithms that satisfies CCA2-key-privacy and CCA2-security in the standard model. Applications of group encryption include settings where a user wishes to hide her preferred trusted third party or even impose a hidden hierarchy of trusted parties, or settings where verifiable well-formed ciphertexts are kept in a untrusted storage server that must be prevented from both learning the content of records as well as analyzing the identities of their retrievers.
2007
EPRINT
We study the design of practical blind signatures in the universal composability (UC) setting against adaptive adversaries. We introduce a new property for blind signature schemes that is fundamental for managing adaptive adversaries: an {\em equivocal blind signature} is a blind signature protocol where a simulator can construct the internal state of the client so that it matches a simulated transcript even after a signature was released. % We present a general construction methodology for building practical adaptively secure blind signatures: the starting point is a 2-move lite blind signature'', a lightweight 2-party signature protocol that we formalize and implement both generically as well as number theoretically: formalizing a primitive as lite'' means that the adversary is required to show all private tapes of adversarially controlled parties; this enables us to conveniently separate zero-knowledge (ZK) related security requirements from the remaining security properties in the primitive's design methodology. % We then focus on the exact ZK requirements for building blind signatures. To this effect, we formalize two special ZK ideal functionalities, single-verifier-ZK (SVZK) and single-prover-ZK (SPZK) and we investigate the requirements for realizing them in a commit-and-prove fashion as building blocks for adaptively secure UC blind signatures. SVZK can be realized without relying on a multi-session UC commitment; as a result, we realize SVZK in a very efficient manner using number theoretic mixed commitments while employing a constant size common reference string and without the need to satisfy non-malleability. Regarding SPZK we find the rather surprising result that realizing it only for static adversaries is sufficient to obtain adaptive security for UC blind signatures. This important observation simplifies blind signature design substantially as one can realize SPZK very efficiently in a commit-and-prove fashion using merely an extractable commitment. We instantiate all the building blocks of our design methodology efficiently thus presenting the first practical UC blind signature that is secure against adaptive adversaries in the common reference string model. In particular, we present (1) a lite equivocal blind signature protocol that is based on elliptic curves and the 2SDH assumption of Okamoto, (2) efficient implementations of SPZK, SVZK for the required relations. % Our construction also takes advantage of a round optimization method we discuss and it results in a protocol that has an overall communication overhead of as little as 3Kbytes, employing six communication moves and a constant length common reference string. We also present alternative implementations for our equivocal lite blind signature thus demonstrating the generality of our approach. Finally we count the exact cost of realizing blind signatures with our protocol design by presenting the distance between the $\Fbsig$-hybrid world and the $\Fcrs$-hybrid world as a function of environment parameters. The distance calculation is facilitated by a basic lemma we prove about structuring UC proofs that may be of independent interest.
2007
EPRINT
This paper introduces Hidden Identity-based Signatures (Hidden-IBS), a type of digital signatures that provide mediated signer-anonymity on top of Shamir's Identity-based signatures. The motivation of our new signature primitive is to resolve an important issue with the kind of anonymity offered by group signatures'' where it is required that either the group membership list is {\em public} or that the opening authority is {\em dependent} on the group manager for its operation. Contrary to this, Hidden-IBS do not require the maintenance of a group membership list and they enable an opening authority that is totally independent of the group manager. As we argue this makes Hidden-IBS much more attractive than group signatures for a number of applications. In this paper, we provide a formal model of Hidden-IBS as well as two efficient constructions that realize the new primitive. Our elliptic curve construction that is based on the SDH/DLDH assumptions produces signatures that are merely half a Kbyte long and can be implemented very efficiently. To demonstrate the power of the new primitive, we apply it to solve a problem of current onion-routing systems focusing on the Tor system in particular. Posting through Tor is currently blocked by sites such as Wikipedia due to the real concern that anonymous channels can be used to vandalize online content. By injecting a Hidden-IBS inside the header of an HTTP POST request and requiring the exit-policy of Tor to forward only properly signed POST requests, we demonstrate how sites like Wikipedia may allow anonymous posting while being ensured that the recovery of (say) the IP address of a vandal would be still possible through a dispute resolution system. Using our new Hidden-IBS primitive in this scenario allows to keep the listing of identities (e.g., IP addresses) of Tor users computationally hidden while maintaining an independent Opening Authority which would not have been possible with previous approaches.
2007
EPRINT
We investigate the decoding problem of Reed-Solomon (RS) Codes, also known as the Polynomial Reconstruction Problem (PR), from a cryptographic hardness perspective. Namely, we deal with PR instances with parameter choices for which decoding is not known to be feasibly solvable and where part of the solution polynomial is the hidden input. We put forth a natural decisional intractability assumption that relates to this decoding problem: distinguishing between a single randomly chosen error-location and a single randomly chosen non-error location for a given corrupted RS codeword with random noise. We prove that under this assumption, PR-instances are entirely pseudorandom, i.e., they are indistinguishable from random vectors over the underlying finite field. Moreover, under the same assumption we show that it is hard to extract any partial information related to the hidden input encoded by the corrupted PR-instance, i.e., PR-instances hide their message polynomial solution in the semantic security sense. The above results lay a framework for the exploitation of PR as an intractability assumption for provable security of cryptographic primitives. Based on this framework, we present provably secure cryptographic constructions for (i) a pseudorandom extender, (ii) a semantically secure version of the Oblivious Polynomial Evaluation Protocol, and (iii) a stateful cipher with a set of interesting properties that include: semantic security, forward secrecy, error-correcting decryption and an array of random self-reducibility properties with respect to the plaintext choice, key choice and partial domain choice.
2006
PKC
2006
EPRINT
Copyrighting a function is the process of embedding hard-to-remove marks in the function's implementation while retaining its original functionality. Here we consider the above problem in the context of public-key encryption and we parallel the process of copyrighting a function to the process of designing traitor tracing schemes. We derive two copyrighted public-key encryption functions for the $2$-key setting, solving an open question left by earlier work with respect to copyrighting discrete-logarithm based functions. We then follow a modular design approach and show how to elevate the $2$-key case to the multi-user setting, employing collusion secure codes. Our methodology provides a general framework for constructing public-key traitor tracing schemes that has the interesting property that the transmission rate remains constant if the plaintext size can be calibrated to reach an appropriate minimal length. Achieving a constant rate, i.e., constant expansion in the size of ciphertexts and keys, is an important open problem in the area of traitor tracing schemes. Our design shows how one can solve it for settings that accommodate the required plaintext calibration (e.g., when a bulk of symmetric cipher keys can be encrypted in one message). Our constructions support black-box traitor tracing'', the setting Â where the tracer only accesses the decryption box in input/output queries/responses. For the first time here we provide a modeling of black-box traitor tracing that takes into account adversarially chosen plaintext distributions, a security notion we call {\em semantic black-box traceability}. In order to facilitate the design of schemes with semantic black-box traceability we introduce as part of our modular design approach a simpler notion called semantic user separability and we show that Â this notion implies semantic black-box traceability. In the multi-user setting our constructions also demonstrate how one can derive public-key traitor tracing by reducing the required marking assumption'' of collusion-secure codes to cryptographic hardness assumptions.
2005
EUROCRYPT
2005
EPRINT
A group signature is a basic privacy mechanism. The group joining operation is a critical component of such a scheme. To date all secure group signature schemes either employed a trusted-party aided join operation or a complex joining protocol requiring many interactions between the prospective user and the Group Manager (GM). In addition no efficient scheme employed a join protocol proven secure against adversaries that have the capability to dynamically initiate multiple concurrent join sessions during an attack. This work presents the first efficient group signature scheme with a simple Joining protocol that is based on a single message and signature response'' interaction between the prospective user and the GM. This single-message and signature-response registration paradigm where no other actions are taken, is the most efficient possible join interaction and was originally alluded to in 1997 by Camenisch and Stadler, but its efficient instantiation remained open till now. The fact that joining has two short communication flows and does not require secure channels is highly advantageous: for example, it allows users to easily join by a proxy (i.e., a security officer of a company can send a file with all registration requests in his company and get back their certificates for distribution back to members of the company). It further allows an easy and non-interactive global system re-keying operation as well as straightforward treatment of multi-group signatures. We present a strong security model for group signatures (the first explicitly taking into account concurrent join attacks) and an efficient scheme with a single-message and signature-response join protocol. The present manuscript is a full version containing proofs, minor corrections as well as a more flexible and efficient protocol construction compared to the proceedings version.
2005
EPRINT
We present a blind signature scheme that is efficient and provably secure without random oracles under concurrent attacks utilizing only four moves of short communication. The scheme is based on elliptic curve groups for which a bilinear map exists and on extractable and equivocable commitments. The unforgeability of the employed signature scheme is guaranteed by the LRSW assumption while the blindness property of our scheme is guaranteed by the Decisional Linear Diffie-Hellman assumption. We prove our construction secure under the above assumptions as well as Paillier's DCR assumption in the concurrent attack model of Juels, Luby and Ostrovsky from Crypto '97 using a common reference string. Our construction is the first efficient construction for blind signatures in such a concurrent model without random oracles. We present two variants of our basic protocol: first, a blind signature scheme where blindness still holds even if the public-key generation is maliciously controlled; second, a blind signature scheme that incorporates a public-tagging'' mechanism. This latter variant of our scheme gives rise to a partially blind signature with essentially the same efficiency and security properties as our basic scheme.
2004
ASIACRYPT
2004
EUROCRYPT
2004
EUROCRYPT
2004
EPRINT
We present, implement and apply a new privacy primitive that we call Traceable Signatures.'' To this end we develop the underlying mathematical and protocol tools, present the concepts and the underlying security model, and then realize the scheme and its security proof. Traceable signatures support an extended set of fairness mechanisms (mechanisms for anonymity management and revocation) when compared with the traditional group signature mechanism. We demonstrate that this extended function is needed for proper operation and adequate level of privacy in various settings and applications. For example, the new notion allows (distributed) tracing of all signatures by a single (misbehaving) party without opening signatures and revealing identities of any other user in the system. In contrast, if such tracing is implemented by a state of the art group signature system, such wide opening of all signatures of a single user is a (centralized) operation that requires the opening of {\em all} anonymous signatures and revealing the users associated with them, an act that violates the privacy of all users. Our work includes a novel modeling of security in privacy systems that leads to simulation-based proofs. Security notions in privacy systems are typically more complex than the traditional security of cryptographic systems, thus our modeling methodology may find future applications in other settings. To allow efficient implementation of our scheme we develop a number of basic tools, zero-knowledge proofs, protocols, and primitives that we use extensively throughout. These novel mechanisms work directly over a group of unknown order, contributing to the efficiency and modularity of our design, and may be of independent interest. The interactive version of our signature scheme yields the notion of traceable (anonymous) identification.''
2004
EPRINT
To date, a group signature construction which is efficient, scalable, allows dynamic adversarial joins, and proven secure in a formal model has not been suggested. In this work we give the first such construction in the random oracle model. The demonstration of an efficient construction proven secure in a formal model that captures all intuitive security properties of a certain primitive is a basic goal in cryptographic design. To this end we adapt a formal model for group signatures capturing all the basic requirements that have been identified as desirable in the area and we construct an efficient scheme and prove its security. Our construction is based on the Strong-RSA assumption (as in the work of Ateniese et al.). In our system, due to the requirements of provable security in a formal model, we give novel constructions as well as innovative extensions of the underlying mathematical requirements and properties. Our task, in fact, requires the investigation of some basic number-theoretic techniques for arguing security over the group of quadratic residues modulo a composite when its factorization is known. Along the way we discover that in the basic construction, anonymity does not depend on factoring-based assumptions, which, in turn, allows the natural separation of user join management and anonymity revocation authorities. Anonymity can, in turn, be shown even against an adversary controlling the join manager.
2004
EPRINT
Traitor Tracing Schemes constitute a very useful tool against piracy in the context of digital content broadcast. In such multi-recipient encryption schemes, each decryption key is fingerprinted and when a pirate decoder is discovered, the authorities can trace the identities of the users that contributed in its construction (called traitors). Public-key traitor tracing schemes allow for a multitude of non-trusted content providers using the same set of keys, which makes the scheme server-side scalable.'' To make such schemes also client-side scalable,'' i.e. long lived and usable for a large population of subscribers that changes dynamically over time, it is crucial to implement efficient Add-user and Remove-user operations. Previous work on public-key traitor tracing did not address this dynamic scenario thoroughly, and there is no efficient scalable public key traitor tracing scheme that allows an increasing number of Add-user and Remove-user operations. To address these issues, we introduce the model of Scalable Public-Key Traitor Tracing, and present the first construction of such a scheme. Our model mandates for deterministic traitor tracing and an unlimited number of efficient Add-user operations and Remove-user operations. A scalable system achieves an unlimited number of revocations while retaining high level of efficiency by dividing the run-time of the system into periods. Each period has a saturation level for the number of revocations. When a period becomes saturated, an _efficient_ New-period operation is issued by the system server that resets the saturation level. We present a formal adversarial model for our system taking into account its periodic structure, and we prove our construction secure, both against adversaries that attempt to cheat the revocation mechanism as well as against adversaries that attempt to cheat the traitor tracing mechanism.
2004
EPRINT
Recently, Augot and Finiasz presented a coding theoretic public key cryptosystem that suggests a new approach for designing such systems based on the Polynomial Reconstruction Problem. Their cryptosystem is an instantiation of this approach under a specific choice of parameters which, given the state of the art of coding theory, we show in this work to be sub-optimal. Coron showed how to attack the Augot and Finiasz cryptosystem. A question left open is whether the general approach suggested by the cryptosystem works or not. In this work, we show that the general approach (rather than only the instantiation) is broken as well. Our attack employs the recent powerful list-decoding mechanisms.
2003
EUROCRYPT
2002
EUROCRYPT
2002
PKC
2001
CRYPTO

TCC 2018
Eurocrypt 2017
Crypto 2016
Asiacrypt 2015
Crypto 2014
PKC 2014
Eurocrypt 2012
Crypto 2012
Crypto 2011
Asiacrypt 2011
Eurocrypt 2010
PKC 2009
Eurocrypt 2005