CAKE - CAKE And Knowledge Exchange

ACTS - Aarhus Cryptography Theory Seminar

Seminars list 2010/2011

• 22/11/2010, 14.00, Turing 014 - Tomas Toft
  Computationally Secure Pattern Matching in the Presence of Malicious Adversaries
  Abstract: We propose a dedicated protocol for the highly motivated problem of secure two-party pattern matching: Alice holds a text $t\in \bitstr{}$ of length $n$, while Bob has a pattern $p\in\bitstr$ of length $m$. The goal is for Bob to learn where his pattern occurs in Alice's text. Our construction guarantees full simulation in the presence of malicious, polynomial-time adversaries (assuming that ElGamal encryption is semantically secure) and exhibits computation and communication costs of $O(n+m)$ in a constant round complexity. In addition to the above, we propose a collection of protocols for variations of the secure pattern matching problem: The pattern may contain wildcards ($O(n m)$ communication in $O(1)$ rounds). The matches may be approximated, i.e., Hamming distance less than some threshold ($O(n m)$ communication in $O(1)$ rounds). The length, $m$, of Bob's pattern is secret ($O(n m)$ communication in $O(1)$ rounds). The length, $n$, of Alice's text is secret ($O(n+m)$ communication in $O(1)$ rounds).


• 10/11/2010 at 10.00 and 15/11/2010 at 14.00, Turing 014 - Rikke Bendlin, Ivan Damgård, Claudio Orlandi and Sarah Zakarias
  Semi-Homomorphic Encryption and Multiparty Computation
  Abstract: An additively-homomorphic encryption scheme enables us to compute linear functions of an encrypted input by manipulating only the ciphertexts. We define the relaxed notion of a semi-homomorphic encryption scheme, where the plaintext can be recovered as long as the computed function does not increase the size of the input "too much". We show that a number of existing cryptosystems are captured by our relaxed notion. In particular, we give examples of semi-homomorphic encryption schemes based on lattices, subset sum and factoring. We then demonstrate how semi-homomorphic encryption schemes allow us to construct an efficient multiparty computation protocol for arithmetic circuits, UC-secure against a dishonest majority. The protocol consists of a preprocessing phase and an online phase. Neither the inputs nor the function to be computed have to be known during preprocessing. Moreover, the online phase is extremely efficient as it requires no cryptographic operations: the parties only need to exchange additive shares and verify information theoretic MACs. Our contribution is therefore twofold: from a theoretical point of view, we can base multiparty computation on a variety of different assumptions, while on the practical side we offer a protocol with better efficiency than any previous solution.


• 12/11/2010, 14.00, Turing 014 - Claude Crépeau (McGill University)
  Oblivious Transfer from weakly homomorphic encryption schemes.
  Abstract: Recently, a number of new cryptographic assumptions were invented as a response to Shor's algorithm. Many of these new assumptions have some homomorphic properties, giving rise to the very first "fully homomorphic" encryption scheme by Gentry. On the other hand, most of these new assumptions do not have the general structures used in the past to securely implement Oblivious Transfer. We show in this work, that a new construction allows us to demonstrate that several of these assumptions are nevertheless sufficient for Oblivious Transfer. Joint work with Raza Ali Kazmi.


• 11/11/2010, 15.00, Turing 014 - Christian Schaffner (CWI)
  Position-Based Quantum Cryptography: Impossibility and Constructions
  Abstract: We study position-based cryptography in the quantum setting. The aim is to use the geographical position of a party as its only credential. On the negative side, we show that if adversaries are allowed to share an arbitrarily large entangled quantum state, no secure position-verification is possible at all. We show a distributed protocol for computing any unitary operation on a state shared between the different users, using local operations and one round of classical communication. Using this surprising result, we break any position-verification scheme of a very general form. On the positive side, we show that if adversaries do not share any entangled quantum state but can compute arbitrary quantum operations, secure position-verification is achievable. Jointly, these results suggest the interesting question whether secure position-verification is possible in case of a bounded amount of entanglement. Our positive result can be interpreted as resolving this question in the simplest case, where the bound is set to zero. In models where secure positioning is achievable, it has a number of interesting applications. For example, it enables secure communication over an insecure channel without having any pre-shared key, with the guarantee that only a party at a specific location can learn the content of the conversation. More generally, we show that in settings where secure position-verification is achievable, other position-based cryptographic schemes are possible as well, such as secure position-based authentication and position-based key agreement. joint work with Harry Buhrman, Nishanth Chandran, Serge Fehr, Ran Gelles, Vipul Goyal and Rafail Ostrovsky.


• 11/10/2010 and 25/10/2010, 14.00, Turing 014 - Arpita Patra
  The Round Complexity of Verifiable Secret Sharing: the Statistical Case
  Abstract: We consider the round complexity of a basic cryptographic task: verifiable secret sharing (VSS). This well-studied primitive provides a good ``test case'' for our understanding of round complexity in general; moreover, VSS is important in its own right as a central building block for, e.g., Byzantine agreement and secure multi-party computation. The round complexity of perfect VSS was settled by Gennaro et al. in STOC2001 and Fitzi et al. in TCC 2006. In a surprising result, Patra et al. in Crypto 2009 recently showed that if a negligible probability of error is allowed, the previous bounds no longer apply. We settle the key questions left open by their work, and in particular determine the exact round complexity of statistical VSS with optimal threshold. Let n denote the number of parties, at most t of whom are malicious. The work of Patra et al. showed that 2-round statistical VSS is impossible for t > n/3. We show that 3-round statistical VSS is possible iff t < n/2 (the upper bound is shown by an inefficient 3-round VSS protocol). We also give an efficient 4-round protocol for t < n/2.


• 04/10/2010, 14.00, Ada 018 - Claudio Orlandi
  On Invertible Sampling and Adaptive Security
  Abstract: Secure multiparty computation (MPC) is one of the most general and well studied problems in cryptography. We focus on MPC protocols that are required to be secure even when the adversary can adaptively corrupt parties during the protocol, and under the assumption that honest parties cannot reliably erase their secrets prior to corruption. Previous feasibility results for adaptively secure MPC in this setting applied either to deterministic functionalities or to randomized functionalities which satisfy a certain technical requirement. The question whether adaptive security is possible for all functionalities was left open. We provide the first convincing evidence that the answer to this question is negative, namely that some (randomized) functionalities cannot be realized with adaptive security. This is joint work with Yuval Ishai, Abishekk Kumarasubramanian, and Amit Sahai.


• 27/09/2010, 14.00, Ada 018 - Carmit Hazay
  Efficient Set Operations in the Presence of Malicious Adversaries
  Abstract: We revisit the problem of constructing efficient secure two-party protocols for the problems of set intersection and set-union, focusing on the model of malicious parties. Our main results are constant round protocols that exhibit linear communication and a (practically) linear number of exponentiations with simulation based security. In the heart of these constructions is a technique based on a combination of a perfectly hiding commitment and an oblivious pseudorandom function evaluation protocol. Our protocols readily transform into protocols that are UC-secure, and we discuss how to perform these transformations. This is a joint work with Kobbi Nissim.


• 07/09/2010, 13.00, IT Huset 129 - Carmit Hazay
  On Compression of Data Encrypted with Block Ciphers
  Abstract: Traditionally in communication systems, data from a source is first compressed and then encrypted before it is transmitted over a channel to the receiver. While in many cases this approach is befitting, there exist scenarios where there is a need to reverse the order in which data encryption and compression are performed. Still, it was long believed that encrypted data is practically incompressible. In a surprising result, Johnson et al. broke this paradigm and show that the problem of compressing one-time pad encrypted data translates to the problem of compressing correlated sources, which was solved by Slepian and Wolf. Specifically, compression is practically achievable due to a simple symbol-wise correlation between the key (one-time pad) and the encrypted message. However, when such correlation is more complex, as is the case with block ciphers, the approach to Slepian-Wolf coding utilized by Jonson et al. is not directly applicable. We investigate the problem of compression encrypted data where the encryption procedure utilizes block ciphers such as the Advanced Encryption Standard (AES) and Data Encryption Standard (DES). We show that such data can be feasibly compressed without knowledge of the secret key. We consider block ciphers operating in various chaining modes and show how compression can be achieved without compromising the security of the encryption scheme. Furthermore, we show that there exists a fundamental limitation to the practical compressibility of block ciphers when no chaining is used between blocks. This is a joint work with Demijan Klinc, Ashish Jagmohan, Hugo Krawczyk, and Tal Rabin.


• 26/08/2010, 14.00, Turing 014 - Roel Peeters (K.U. Leuven)
  Increased Resilience in Threshold Cryptography: Sharing a Secret with Devices That Cannot Store Shares
  Abstract: Threshold cryptography increases security and resilience by sharing a private cryptographic key over different devices. Many personal devices, however, are not suited for threshold schemes, because they do not offer secure storage, which is needed to store shares of the private key. We present a solution that allows to include devices without them having to store their share. Shares are stored in protected form, possibly externally, which makes our solution suitable for low-cost devices with a factory-embedded key, e.g., car keys and access cards. By using pairings we achieve public verifiability in a wide range of protocols, which removes the need for private channels. We demonstrate how to modify existing discrete-log based threshold schemes to work in this setting. Our core result is a new publicly verifiable distributed key generation protocol that is provably secure against static adversaries and does not require all devices to be present. some version of this paper can be found on eprint http://eprint.iacr.org/2010/207


• 20/08/2010, 14.00, Turing 014 - Jens Groth (UCL London)
  TBA
  Abstract: TBA

Seminars list 2009/2010

• 25/06/2010, 14.00, Turing 014 - Marius Silaghi (Florida Tech)
  TBA
  Abstract: TBA


• 20/05/2010, 15.00, Turing 014 - Ashish Choudhary
  TBA
  Abstract: TBA


• 20/05/2010, 14.00, Turing 014 - Arpita Patra
  TBA
  Abstract: TBA


• 19/05/2010, 14.00, Turing 014 - Ivan Damgård
  TBA
  Abstract: TBA


• 11/05/2010, 11.00, Turing 014 - Benny Pinkas
  Oblivious RAM Revisited
  Abstract: We reinvestigate the oblivious RAM concept introduced by Goldreich and Ostrovsky, which enables a client, that can store locally only a constant amount of data, to store remotely n data items, and access them while hiding the identities of the items which are being accessed. Oblivious RAM is often cited as a powerful tool, but it is also commonly considered to be impractical due to its overhead, which is asymptotically efficient but is quite high: each data request is replaced by O(log^4 n) requests, or by O(log^3 n) requests where the constant in the “O” notation is a few thousands. In addition, O(n log n) external memory is required in order to store the n data items. We redesign the oblivious RAM protocol using modern tools, namely Cuckoo hashing and a new oblivious sorting algorithm. The resulting protocol uses only O(n) external memory, and replaces each data request by only O(log^2 n) requests (with a small constant). Joint work with Tzachy Reinman.


• 23/04/2010, 14.00, Turing 014 - Margus Niitsoo
  Cryptography based on deterministic randomness
  Abstract: We show how the methods of algorithmic (deterministic) randomness can be used in cryptography by showing that an algorithmically random oracle allows us to prove results quite analogous to those usually achieved in the standard (probabilistic) random oracle model. Namely, we show that given an algorithmically random oracle, one-way functions exist that are secure against polynomial non-uniform adversaries.


• 14/04/2010, 14.00, Ada 333 - Jonas Kolker
  TBA
  Abstract: TBA


• 14/04/2010, 11.00, Ada 018 - Angela Zottarel
  Cryptography from weaker assumptions.
  Abstract: We study the relationship between the computational n-linear problems and the computational DH problem in Generic Groups. We then give the construction of some schemes that are CPA secure in the random oracle model under the computa- tional n-linear assumption. We also use the twin technique to build a scheme that is CCA secure under the computational n-linear assumption.


• 17/03/2010, 14.00, TBA - Carmit Hazay (Bar Ilan University)
  Secure Pattern Matching
  Abstract: This paper presents an efficient protocol for securely computing the fundamental and highly motivated problem of {\em pattern matching}. This problem is defined in the two-party setting, where party $P_1$ holds a keyword and party $P_2$ holds a text. The goal of $P_1$ is to learn where the keyword appears in the text, without revealing it to $P_2$ or learning anything else about $P_2$'s text.
  Our protocol is the first to address this problem with {\em full security} in the face of malicious adversaries. The construction is based on a novel protocol for {\em secure oblivious automata evaluation} which is of independent interest. In this problem party $P_1$ holds an automaton and party $P_2$ holds an input string, and they need to decide if the automaton accepts the input, without learning anything else.
  This is a joint work with Rosario Gennaro and Jeffrey S. Sorensen.


• 11/03/2010, 14.00, Turing 014 - Jakob Løvstad Funder
  Quantum Bit Commitment in an Interesting Model
  


• 02/03/2010, 14.00, Turing-014 - Andy Rupp
  TBA


• 02/02/2010, 14.00, Ada-018 - Rikke Bendlin
  Threshold Decryption and Zero-Knowledge Proofs for Lattice-Based Cryptosystems
  Abstract We present a variant of Regev’s cryptosystem first presented in [Reg05], but with a new choice of parameters. By a recent classical reduction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active adversaries corrupting less than one third of the players. We also describe how one can build a distributed key generation protocol. In the final part of the paper we show how one can, in zero-knowledge - prove knowledge of the plaintext contained in a given ciphertext from Regev’s original cryptosystem or our variant. The proof is of size only a constant times the size of the public key.


• 02/02/2010, 14.00, Ada-018 - Martin Geisler
  From Passive to Covert Security at Low Cost
  Abstract: Aumann and Lindell defined security against covert attacks, where the adversary is malicious, but is only caught cheating with a certain probability. The idea is that in many real-world cases, a large probability of being caught is sufficient to prevent the adversary from trying to cheat. In this paper, we show how to compile a passively secure protocol for honest majority into one that is secure against covert attacks, again for honest majority and catches cheating with probability 1/4. The cost of the modified protocol is essentially twice that of the original plus an overhead that only depends on the number of inputs.


• 09/12/2009, 14.00, Ada-018 - Daniele Mazotti
  Design of a Trusted Computing Based Platform for Executing Encrypted Code
  


• 01/12/2009, 10.00, Turing-014 - Carolin Lunemann
  Quantum-Secure Coin-Flipping and Applications
  Abstract: In this paper, we prove classical coin-flipping secure in the presence of quantum adversaries. The proof uses a recent result of Watrous [20] that allows quantum rewinding for protocols of a certain form. We then discuss two applications. First, the combination of coin-flipping with any non-interactive zero-knowledge protocol leads to an easy transformation from non-interactive zero-knowledge to interactive quantum zero-knowledge. Second, we discuss how our protocol can be applied to a recently proposed method for improving the security of quantum protocols [4], resulting in an implementation without set-up assumptions. Finally, we sketch how to achieve efficient simulation for an extended construction in the common-reference-string model.


• 20/11/2009, 15.00, Ada-018 - Jesper Buus Nielsen
  Oblivious Ram with Unconditional Security (part III)
  


• 30/10/2009, 10.00, Turing-130 - Ivan Damgård, Sigurd Meldgaard and Jesper Buus Nielsen
  Oblivious Ram with Unconditional Security (part I)
  


• 23/10/2009, 10.00, Turing-014 - Tomas Toft and Zekeriya Erkin
  Efficient privacy preserving user clustering in a social network
  


• 10/09/2009, 13.00 - Rikke Bendlin
  Lattice-based Threshold Cryptography.
  Abstract: We present a variant of Regev's cryptosystem, but with a new choice of parameters. By a recent classical reduction by Peikert we prove the scheme semantically secure based on the worst-case lattice problem GapSVP. From this we construct a threshold cryptosystem which has a very efficient and non-interactive decryption protocol. We prove the threshold cryptosystem secure against passive adversaries corrupting all but one of the players, and againts active adversaries corrupting less than one third of the players. We also sketch how one can build a distributed key generation protocol. In the final part of the paper, we show how one can, in zero-knowledge - prove knowledge of the plaintext contained in a given ciphertext from Regev's original cryptosystem or our variant. The proof is of size only a constant times the size of a ciphertext.


• 13/08/2009, 13.00 - Gert Læssøe Mikkelsen
  Efficient, Robust and Constant-Round Distributed RSA Key Generation
  Abstract: We present the first protocol for distributed RSA key generation which is constant round, secure against malicious adversaries and has a negligibly small bound on the error probability, even using only one iteration of the underlying primality test on each candidate number.

Seminars list 2008/2009

• 02/07/2009, 13.00, IT-Huset 112 - Tomas Toft
  Shared, Secret Datastructures
  Abstract: Secure multiparty computation (MPC) allows mutually mistrusting parties to perform a joint computation on private data without leaking information. So far, the main focus in the litterature has been on obtaining general computation or performing some specific task efficiently. However, many of the general techniques for MPC also allows some secret, joint state -- say, a database -- to be maintained. With this in mind, it is natural to ask if the secret data can be stored in a manner that allows it to be both queried and updated efficiently, i.e. "Is it possible to construct datastructures where the operations are implemented using MPC primitives?" This is of course possible, however, it is not clear that a solution can be non-trivial in the sense that it can avoid "touching everything" all the time. The crux of this problem is that the data is secret -- indeed it may be the outcome of some secure computation and thus not even known by a single party. Any operation performed must therefore be oblivious in the sense that the actions taken may not depend on the input. By constructing a secure priority queue, it is demonstrated that non-trivial, shared, secret datastructures are possible. The structure allows adding elements to the queue as well as extracting the one with minimal priority. Both operations require only $O(\log^2 n)$ MPC operations amortized (secure multiplications and comparisons), where $n$ is the size of the structure.


• 25/06/2009, 11.00, IT-Huset 112 - Jakob Løvstad Funder
  Entropic Uncertainty Relations
  Abstract: An entropic uncertainty relation is a way of stating Heisenberg's uncertainty principle in terms of entropy instead of the standard deviation. In other words, such a relation sets a lower limit on the entropy on some properties, or observables, of the quantum system. In Heisenbergs original paper these were position and momentum. This is very useful in quantum cryptography (see e.g. Secure Identification in the Bounded-Quantum-Storage Model). While exact relations are known for 2-D quantum systems (qubits) only loose bounds are known for most other dimensions. The talk is in large part an introduction to the subject but will also contain some new results.


• 18/06/2009, 13.00, IT-Huset 112 - Claudio Orlandi
  On the Necessary and Sufficient Assumptions for UC Computation
  Abstract: We study the necessary and sufficient assumptions for universally composable (UC) computation, both in terms of setup and computational assumptions. We look at the common reference string model, the common random string model and the public-key infrastructure (PKI) model, and provide new result for all of them. Perhaps most interestingly we show that: - For even the minimal meaningful PKI, where we only assume that the secret key is a value which is hard to compute from the public key, one can UC securely compute any poly-time functionality if there exists a passive secure oblivious-transfer protocol for the stand-alone model. Since a PKI where the secret keys can be computed from the public keys is useless, and some setup assumption is needed for UC secure computation, this establishes the best we could hope for the PKI model: any non-trivial PKI is sufficient for UC computation. - We show that in the PKI model one-way functions are sufficient for UC commitment and UC zero-knowledge. These are the first examples of UC secure protocols for non-trivial tasks which do not assume the existence of public-key primitives. In particular, the protocols show that non-trivial UC computation is possible in Minicrypt.


• 11/06/2009, 13.00, IT-Huset 112 - Gert Mikkelsen
  Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products
  Abstract: The paper "Efficient Computation Modulo a Shared Secret with Application to the Generation of Shared Safe-Prime Products", by Joy Algesheimer, Jan Camenisch and Victor Shoup. (CRYPTO 2002) will be presented. Available at http://eprint.iacr.org/2002/029.pdf.


• 07/05/2009, 13.00, Turing 014 - Ivan Damgård
  Share conversion and pseudorandom secret sharing revisited
  Abstract: we show a generalization of a lower bound from the original paper on pseudorandom secret sharing, the generalization demonstrates that the only way to have PRSS that scales polynomially with the number of players is to make non black-box use of the pseudorandom functions used in the scheme. We specify an open problem regarding which type of correlated information can be locally converted to shares in a linear secret-sharing scheme.


• 23/04/2009, 13.00, IT-Huset 112 - Asgeir Bertelsen Steine (NTNU, Norway)
  Rerandomizable Encryption
  Abstract: The standard security requirements for encryption schemes only require that encryption hides the messages from attackers. In this talk I will define the notions of rerandomizable encryption and key indistinguishability. These notions are very natural when anonymity is in focus. After defining the notions I will give a survey of the rerandomizable schemes that exsist.


• 26/03/2009, 13.00, Turing 014 - Claudio Orlandi
  UC Commitments with Minimal Assumptions (in the CRS model)
  Abstract: In this talk I show how to build UC commitments from any encryption scheme and any trapdoor commitment scheme. UC commitments (in the CRS) imply PKE and trapdoor commitment schemes, so the assumptions are minimal. The techniques we use are essentially the same as in "LEGO for Two-Party Secure Computation"


• 19/03/2009, 16.00, Turing 014 - Louis Salvail
  Oblivious Transfer a la Merkle
  Abstract: Oblivious transfer (OT) is a fundamental primitive in cryptography. It is known that unconditionally secure OT is impossible, even with the help of quantum mechanics. Furthermore, no classical OT scheme has been proven to offer computational security in the usual super-polynomial model, and there is evidence that such schemes cannot be based on one-way permutations. Nevertheless, inspired by Ralph Merkle's 1974 key distribution scheme, we offer a novel classical OT scheme based on one-way permutations and prove its polynomial security: the effort to cheat it scales as t^{3/2}, where $t$ is the legitimate effort needed to implement it. Unfortunately, our scheme melts down under the onslaught of a quantum adversary after an effort merely in the order of t^{5/6}, so that it is actually easier to subvert it than to use it legitimately! By allowing the honest parties to use quantum computation as well, however, it may be that our OT scheme can be repaired so as to resist modest quantum attacks. I will also talk about key distribution in the same model.


• 12/03/2009, 13.00, Turing 014 - Jakob Løvstad Funder
  Variants of the McEliece Cryptosystem
  


• 05/03/2009, 13.00, Turing 014 - Sigurd Torkel Meldgaard
  Breaking RSA Generically is Equivalent to Factoring
  See http://eprint.iacr.org/2008/260


• 26/02/2009, 13.00, Turing 014 - Jesper Buus Nielsen
  Randomness Extraction
  


• 19/02/2009, 13.00, Turing 014 - Kristian Gjøsteen (NTNU, Norway)
  An elementary approach to proving security with formal methods
  Abstract: When we want to prove a system secure, we often need to prove that the behaviour of one system of interacting Turing machines can be replicated by a second system. For instance, in the universal composability framework we want to prove that any observable behaviour in the real system can be replicated in an ideal system. This talk will describe an elementary approach to proving such theorems. Briefly, we consider a system as a state machine recognizing a language built from messages sent between the interactive Turing machines. We then prove that behaviour in one system can be replicated in a second system by showing that the language recognized by the first system is "essentially" contained in the language recognized by the second system.


• 12/02/2009, 13.00, IT-Huset 112 - Martin Geisler
  Security against Covert Adversaries
  See http://eprint.iacr.org/2007/060


• 05/02/2009, 13.00, Turing 014 - Tomas Toft
  A Sub-linear Protocol for Two Millionaires
  


• 26/01/2009, 14.00, Turing 014 - Martin Geisler
  Asynchronous Multiparty Computation: Theory and Implementation
  See http://eprint.iacr.org/2008/415


• 18/12/2008, 11.00, Turing 014 - Jesus Fernando Almansa Guerra
  Simple Proofs and Formal Semantics for Game Transformation
  Abstract: In this talk, we will provide a non-technical view of our work in formalizing the notion of game and associated proof-technique called game-transformation for cryptography, that aims at making simple proofs of security.
  We will point out the three fundamental concepts that are the key to provide a semantics, and that have been present since the outset of cryptographic research in the 80´s; however we will focus on how they are used, rather than in their meaning.
  This work is foundational in character, and it is a first step toward simpler analyses of general protocols; we will provide evidence that such goal is achievable.
  No specific prerequisites are needed to attend this talk.


• 15/12/2008, 13.00, Turing 014 - Carolin Lunemann
  Quantum Protocols with Hybrid Security
  Abstract: We introduce a methodology that allows improving the security of several protocols designed for the bounded-quantum-storage model, such that the modified protocol we construct is secure if either the adversary's quantum memory size is bounded or if he is computationally bounded. We show how our technique can be applied to the recent quantum identification protocols of Damgård et al.


• 24/11/2008, 14.00, Turing 014 - Claudio Orlandi
  LEGO for Two-Party Secure Computation
  Joint work with Jesper Buus Nielsen. Abstract/paper: http://eprint.iacr.org/2008/427


• [CAGT seminar] 18/11/2008, 14.15, Turing 014 - Jesper Buus Nielsen
  Privacy-enhancing first-price auctions using rational cryptography
  More info here


• 10/11/2008, 13.00, Turing 014 - Nikos Triandopoulos
  Authenticated hash tables
  Abstract: Suppose a client stores $n$ elements in a hash table that is outsourced at a remote server, so that the client can save space or achieve load balancing. We propose a new protocol for optimally authenticating membership queries on hash tables: for any fixed constant $00$. An evaluation of our solution shows good scalability. Joint work with Charalampos Papamanthou and Roberto Tamassia.


• 28/10/2008, 13.00, Turing 014 - Ivan Damgård
  On the Amortized Complexity of Zero-knowledge Protocols
  Joint work with Ronald Cramer. Abstract: We propose a general technique that allows improving the complexity of zero-knowlege protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instance $x$ and error probability $2^{-n}$ was $O(|x| n)$ bits. By using our technique to prove $n$ instances simultaneously, we can bring down the proof size per instance to $O(|x| + n)$ bits for the same error probability. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, and proofs of plaintext knowledge for various types of homomorphic encryptions schemes. The generality of our method stems from a somewhat surprising application of black-box secret sharing schemes.


• 24/10/2008, 11.00, IT-Huset 112 - Tord Ingolf Reistad (NTNU)
  Sub-Linear Constant Round Comparison for Shamir Secret Sharing Scheme
  


• 07/10/2008, 13.00, Turing 014 - Gert Mikkelsen
  On Theory and Practice of Personal Digital Signature
  


• 30/09/2008, 13.00, Turing 014 - Martin Geisler
  Integrity Protection for Revision Control
  Abstract: Users of online-collaboration tools and network storage services place considerable trust in their providers. This paper presents a novel approach for protecting data integrity in revision control systems hosted by an untrusted provider. It guarantees atomic read and write operations on the shared data when the service is correct and preserves fork-linearizability when the service is faulty. A prototype has been implemented on top of the Subversion revision control system; benchmarks show that the approach is practical.


• 16/09/2008, 13.15, Turing 230 - Mikkel Krøigård
  Scalable Multiparty Computation with Nearly Optimal Work and Resilience
  


• 09/09/2008, 13.15, Turing 130 - Miroslava Sotakova
  Limits of secure two-party quantum computation
  Abstract: In the talk we present a framework for two-party quantum cryptography with the adversaries restricted to be quantum honest-but-curious, allowing us to determine how much "forbidden" information is accessible to a dishonest player in any quantum protocol implementing the desired primitive correctly. We show that in such model the only two-party primitives admitting perfectly secure quantum protocol are the trivial ones, and on the other hand, any non-trivial primitive can be implemented by a quantum protocol which in terms of information leaked cannot be matched by any protocol in the classical honest-but-curious model. Furthermore, we discuss the question of self-composability of quantum protocols, where we have shown that the only weakly self-composable two-party quantum protocols are in fact, equivalent to the protocols in the classical honest-but-curious model.

Seminars list 2007/2008

• 21/08/2008, 13.15, Turing 014 - Marcel Keller (ETH)
  On Assumptions Sufficient for Private Information Retrieval
  Abstract: In the speech, private information retrieval (PIR) will be introduced and relations to one-way permutations (TDP) will be presented. The protocol by Kushilevitz and Ostrovsky to construct PIR from a one-way permutation will be shown in detail. This protocol uses a very strong definition of a TDP. Therefore, three different ways to construct PIR from weaker definitions of TDP will be presented.


• 29/05/2008, 13.15, Turing 014 - Serge Fehr (CWI)
  Secure Deterministic Encryption for High-Entropy Messages
  Abstract: In recent work, Bellare et al. introduced a new security notion for deterministic public-key encryption schemes, and they proposed a couple of schemes satisfying the security notion in the random oracle model. The security notion is essentially that of semantical security for multi-message encryption under the assumption that each encrypted message has some lower bounded min-entropy. This solves an important problem in the context of database encryption: finding encryption schemes that allow for fast searching on encrypted data, and which at the same time offer strong security. We consider a similar but slightly weaker notion. The notion is still in the same spirit: semantical security for multi-message encryption of messages with lower bounded entropy; the difference is that we require the lower bound on the entropy to hold for each message even when given the other messages, i.e., each new message needs to have ``fresh" entropy. The advantage of the weaker notion is that it is much handier to work with: We show the equivalence to a single-message indistinguishability-based security notion, and, based on that, we propose a deterministic encryption scheme satisfying our notion in the standard model, based on the DCR assumption. The scheme is length preserving and compares to standard Paillier encryption in its performance.


• 25/04/2008, 10.15, Turing 014 - Rune Thorbek
  Encryption and stuff
  Abstract: We formally define the primitive of public-key encryption with non-interactive opening (PKENO), where the receiver of a ciphertext \ctxt can, convincingly and without interaction, reveal what the result was of decrypting \ctxt, without compromising the scheme's security. This has numerous applications in cryptographic protocol design, e.g., when the receiver wants to demonstrate that some information he was sent privately was not correctly formed. We give a definition based on the UC framework as well as an equivalent game-based definition. The PKENO concept was informally introduced by Damg{\aa}rd and Thorbek who suggested that it could be implemented based on Identity-Based Encryption. In this paper, we give direct and optimized implementations, that work without having to keep state information, unlike what one obtains from directly using IBE.


• 04/04/2008, 11.15, Turing 014 - Tomas Toft (CWI and TU/e)
  Improved Costant Round Bit Decomposition


• 12/03/2008, 14.30, Turing 230 - Jesper Buus Nielsen
  Cryptographic Broadcast
  Abstract: a new lower bound on the number of synchronous rounds needed for cryptographic broadcast. Joint work with Matthias Fitzi.


• 04/03/2008, 13.00, Turing 014 - Melissa Chase (Brown University)
  Delegatable Anonymous Credentials
  Abstract: Anonymous credential systems allow users to obtain credentials from organizations, and to anonymously and unlinkably prove possesion of valid credentials. Often in practice, however, a user authenticates using some credential chain: a root organization gives a credential to an intermediate party who can in turn use this to issue credentials to users. We address this by presenting the first efficient delegatable anonymous credential scheme. In such a scheme, a party can anonymously and unlinkably receive credentials from an organization, issue delegated credentials to other users, and prove possession of a credential L levels away from a given organization. This talk will describe our result and outline some of the main techniques used to achieve it. In particular, we identify rerandomizable NIZK proof of knowledge systems as a key building block, and show that such proofs systems, in combination with an appropriate authentication scheme, can be used to realize delegatable anonymous credentials. Finally, we instantiate these building blocks under appropriate assumptions about groups with bilinear maps, using the proof system due to Groth and Sahai that, as we show, has the necessary randomization properties. This is joint work with Mira Belenkiy, Jan Camenisch, Markulf Kohlweiss, Anna Lysyanskaya, and Hovav Shacham.


• 29/02/2008, 11.00, Turing 014 - Nikos Triandopoulos
  Towards optimal set-membership authentication
  Abstract: In this talk, I will present a recent result on cryptographic protocols for verifying membership in dynamic sets, in particular, a protocol where set updates take logarithmic time in the size of the set and membership proofs have communication and time costs that are independent of it. The technique is based on a new cryptographic primitive for efficiently verifying the set-membership relation and its complement. This is joint work with Ivan Damgård.


• 15/02/2008, 11.00, Turing 014 - Christian Schafnner (CWI)
  1-2 Oblivious Transfer and Secure Identification in the Bounded-Quantum-Storage Model
  Abstract: This talk is about two papers from last CRYPTO 2007.
  
  Ivan Damgård, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner
  A Tight High-Order Entropic Quantum Uncertainty Relation with Applications
  In Advances in Cryptology - CRYPTO 2007, pages 360-378, 2007
  
  Ivan Damgård, Serge Fehr, Louis Salvail, and Christian Schaffner
  Secure Identification and QKD in the Bounded-Quantum-Storage Model
  In Advances in Cryptology - CRYPTO 2007, pages 342-359, 2007