Tuesday was a short day with only two sessions; one on signatures, on which I will focus, and one on information-theoretic cryptography. The afternoon was then reserved for the social event, which was a walking tour in the historic centre of Tallinn.
The first talk of the day was by Sven Schäge from Bochum who talked about tight proofs for signatures schemes without random oracles. For many standard-model signatures schemes, the proof of unforgeability splits into two cases depending on whether or not the adversary recycles parts of a signature it obtained in a signing query for its forgery. For the recycle case, the simulator in the proof typically guesses which of the queries the forgery will relate to, which introduces a polynomial loss in the reduction. Having tighter security proofs now allows us to use smaller parameters for practical instantiations.
The rest of the session were Bristol papers: the first one by Dario Catalano and Fiore, and Bogdan. Dario II introduced the concept of adaptive pseudo-free groups. This is an abstraction of objects typically used in cryptography where certain operations are "hard". A pseudo-free group is a group with efficient group operations which behaves like a free group for computationally bounded adversaries, such as an RSA group. For cryptographic applications this concept might be too weak, as e.g. for signature schemes, the adversary is allowed to see solutions to non-trivial equations by making signing queries. Adaptive pseudo-free groups extend thus pseudo-free groups to adaptive adversaries.
The last talk of the session was by myself on a new primitive called commuting signatures. They extend the functionality of verifiably encrypted signatures, which enable encryption of signatures and/or messages while giving a publicly verifiable proof that the content is valid. Commuting signatures allow a signer, given an encryption of a message, to produce a verifiably encrypted signature on the plaintext. As an application I gave the currently most efficient instantiation of delegatable anonymous credentials, which can be non-interactively delegated.
Friday, May 20, 2011
Monday, May 16, 2011
Eurocrypt '11 - Tallinn - Day One
We started off with the best paper at the conference - and a strong candidate for "best talk" too!
Efficient Authentication from Hard Learning Problems looked at how you could do authentication in a RFID tag. Forget Moore's Law, this is state-of the art technology and we're talking about a few thousand gates total. Even AES is not an option, so the authors developed an authentication protocol based on the "Learning Parity with Noise" problem (LPN), building on the HB scheme and adding security against active adversaries.
The basic idea is that prover and verifier share a secret vector, the verifier picks a random challenge vector and the prover replies with the inner product of the challenge and the secret XOR some biased random bit - this can fail for both honest and dishonest provers but the difference in failure probabilities allows you to construct a secure protocol through repetition.
Next up, a variant of NTRU which comes with a proof that it really is as hard as finding short vectors in lattices and a great introduction to the field of lattice-based cryptography by Phong Nguyen (invited talk).
The afternoon was devoted to side channels and (fully) homomorphic cryptography, where among others we saw fast(er) implementations of pairings, AES and Gentry's FHE scheme.
One highlight on side channels: A Formal Study of Power Variability Issues and Side-Channel Attacks for Nanoscale Devices.
As processsors get smaller, variability between different chips - even of the same series - starts to influence measurements like power traces, so you can't measure one chip to construct a hypothesis then test it on another as you'd like - the more exactly your hypothesis fits the first chip, the worse variation will make it on the second. The authors showed how you get better results by aiming for robustness rather than precision.
As an aside, chip manufacturers may be able to thwart side-channel attacks better by putting less effort into reducing variability.
Efficient Authentication from Hard Learning Problems looked at how you could do authentication in a RFID tag. Forget Moore's Law, this is state-of the art technology and we're talking about a few thousand gates total. Even AES is not an option, so the authors developed an authentication protocol based on the "Learning Parity with Noise" problem (LPN), building on the HB scheme and adding security against active adversaries.
The basic idea is that prover and verifier share a secret vector, the verifier picks a random challenge vector and the prover replies with the inner product of the challenge and the secret XOR some biased random bit - this can fail for both honest and dishonest provers but the difference in failure probabilities allows you to construct a secure protocol through repetition.
Next up, a variant of NTRU which comes with a proof that it really is as hard as finding short vectors in lattices and a great introduction to the field of lattice-based cryptography by Phong Nguyen (invited talk).
The afternoon was devoted to side channels and (fully) homomorphic cryptography, where among others we saw fast(er) implementations of pairings, AES and Gentry's FHE scheme.
One highlight on side channels: A Formal Study of Power Variability Issues and Side-Channel Attacks for Nanoscale Devices.
As processsors get smaller, variability between different chips - even of the same series - starts to influence measurements like power traces, so you can't measure one chip to construct a hypothesis then test it on another as you'd like - the more exactly your hypothesis fits the first chip, the worse variation will make it on the second. The authors showed how you get better results by aiming for robustness rather than precision.
As an aside, chip manufacturers may be able to thwart side-channel attacks better by putting less effort into reducing variability.
Friday, March 18, 2011
Cryptography and Security in Clouds II (Zurich March 15-16 2011)
One of the highlights of the last week in Zurich was undoubtedly Rado Sion's (http://www.cs.sunysb.edu/~sion/) talk on the economics of cloud computing in relation to security. Measuring the cost of outsourcing in the cloud as cost of a single CPU cycle in "picocents", that is 10^-14$ allows one to weigh up the real economic cost of outsourcing. In particular, one can ask how many additional cloud cycles can we spend on cryptography, before its outsourcing becomes too expensive? Most talks after this, had members of the audience asking this very question. In particular, novel encryption schemes such as functional encryption may be very cool but aren't going to come cheap!
In 2009 Craig Gentry's construction of the first fully homomorphic scheme (i.e a scheme which supports unlimited computation on encrypted data) was hailed as a major theoretical breakthrough due to its obvious implications for secure computation in untrusted clouds, but could such a scheme ever be economical for anyone to deploy? Much of Sion's research has focused on answering questions like these in a far more concrete fasion than many cryptographers and cloud advocates would normally dare. The conclusions make fascinating reading. For example, http://www.cs.sunysb.edu/~sion/research/sion2010wpes-pcost.pdf analyses the cost (again, in picocents) of a variety of cryptographic schemes for home users up to large size data centres such as those provided by the Amazon cloud. Figures are calculated using the ECRYPT benchmarking (http://bench.cr.yp.to/) for AES, RSA encryption and DSA, ECDSA signatures. The authors also give figures for transferring data into the cloud and storage costs. Armed with these results they analyse various scenarios of outsourcing, namely simple storage such as that offered by Amazon S3, searching on encrypted data and secure SQL queries in the cloud. Suppose a user wants to store (but not compute on) data held in the cloud. Based on their figures they predict outsourced storage can be upwards of 2 orders of magnitude higher than local storage, even in the absence of security assurances. Searching on encrypted data turns out to only be economical in the cloud if the returned result is less than 36 bytes per query (and this doesn't take into account the cost of TCP overheads) and similarly damning conclusions are drawn for SQL queries based on current schemes.
Perhaps ironically, this doesn't imply a highly computationally expensive crypto-scheme such as FHE is economically unviable. We can envisage a scenario where a home user simply didnt have the necessary computational power on her desktop, but required computation (say a simple private information retrieval) from the database. For example, doctors requiring information on patients from a health database held remotely. It may be cheaper for the corresponding health service to provide PIR to their doctors and paying for the extra overhead that comes with outsourcing than maintaining their own IT infrastructure and still have the security guarentees provided by cryptographic schemes.
We conclude that whilst looking at the cost of outsourcing purely in terms of CPU cycles renders it useless for the most part, there are scenario-specific cases where it is economical. Businesses and home users alike will have to take a serious look at whether this is the case for them and not simply be taken in by the frenzied marketing surrounding "the cloud".
In 2009 Craig Gentry's construction of the first fully homomorphic scheme (i.e a scheme which supports unlimited computation on encrypted data) was hailed as a major theoretical breakthrough due to its obvious implications for secure computation in untrusted clouds, but could such a scheme ever be economical for anyone to deploy? Much of Sion's research has focused on answering questions like these in a far more concrete fasion than many cryptographers and cloud advocates would normally dare. The conclusions make fascinating reading. For example, http://www.cs.sunysb.edu/~sion/research/sion2010wpes-pcost.pdf analyses the cost (again, in picocents) of a variety of cryptographic schemes for home users up to large size data centres such as those provided by the Amazon cloud. Figures are calculated using the ECRYPT benchmarking (http://bench.cr.yp.to/) for AES, RSA encryption and DSA, ECDSA signatures. The authors also give figures for transferring data into the cloud and storage costs. Armed with these results they analyse various scenarios of outsourcing, namely simple storage such as that offered by Amazon S3, searching on encrypted data and secure SQL queries in the cloud. Suppose a user wants to store (but not compute on) data held in the cloud. Based on their figures they predict outsourced storage can be upwards of 2 orders of magnitude higher than local storage, even in the absence of security assurances. Searching on encrypted data turns out to only be economical in the cloud if the returned result is less than 36 bytes per query (and this doesn't take into account the cost of TCP overheads) and similarly damning conclusions are drawn for SQL queries based on current schemes.
Perhaps ironically, this doesn't imply a highly computationally expensive crypto-scheme such as FHE is economically unviable. We can envisage a scenario where a home user simply didnt have the necessary computational power on her desktop, but required computation (say a simple private information retrieval) from the database. For example, doctors requiring information on patients from a health database held remotely. It may be cheaper for the corresponding health service to provide PIR to their doctors and paying for the extra overhead that comes with outsourcing than maintaining their own IT infrastructure and still have the security guarentees provided by cryptographic schemes.
We conclude that whilst looking at the cost of outsourcing purely in terms of CPU cycles renders it useless for the most part, there are scenario-specific cases where it is economical. Businesses and home users alike will have to take a serious look at whether this is the case for them and not simply be taken in by the frenzied marketing surrounding "the cloud".
Thursday, March 17, 2011
Cryptography and Security in Clouds (Zurich March 15-16 2011)
"The Cloud" is supposed to let you run a virtual machine and abstract away all details like what physical processors or disks lie beneath. But we can't hope our adversaries will be nice and stick to this ...
In the first talk we saw some examples of what can go wrong from a security perspective when you ignore what lies beneath. If two virtual machines are executed on the same physical machine, we call them co-resident and if our adversary can get his VM co-resident to ours we may be in trouble. If he can take over the physical machine for example by exploiting a bug in the hypervisor (software layer that runs the VMs), he gains complete control of our VM. Even if he's confined to his VM, he can measure the latency of operations and possibly gain a side-channel from the fact that his code uses the same physical caches as ours. Using Amazon's cloud as an example, the speakers showed that it's surprisingly easy to get co-resident with a target of your choice and to detect if this was successful.
Another nice feature of VMs is they can be suspended to a disk image and restarted. A less nice feature is that the same image can be restarted several times, given a different query each time but may use the same randomness/PRG - practical examples were presented as our favourite browsers seed the PRG for TLS and co. when they start up. In other words, we can actually apply the "forking lemma" in practice! For a server VM, we saw practical examples of stealing the TLS master key this way.
Another security issue arises in cloud-based backup systems like dropbox. They use a trick called deduplication - if two users backup the same file, it only stores the file once and the second user doesn't even have to upload it again (the service can compare file hashes). It's pretty much the equivlent of UNIX hard links. It's estimated that deduplication saves 95%-99% of space for online backup systems, but we're still talking about petabytes.
Deduplication gives anyone an oracle to test whether a file has been backed up before and to brute-force test which version of a file has been backed up if only a small portion is unknown. Another problem is that knowing the hash of someone's file allows you to retrieve it - just pretend you have a file with that hash, deduplication means you get access to it without any further questions. As an aside, dropbox claims to encrypt all files with "military-grade encryption" (AES is mentioned too) but for deduplication to work at all, it seems like they encrypt everyone's files with the same key.
With problems like these out there, what can we do? Two main approaches were presented, both dealing with the fact that the client cannot fully trust the could provider. The first is based on secure hardware (mostly TPMs) and several talks gave scenarios for using hardware-based trust. The second approach is to use software-based cryptography - mostly some variation of MPC, although we heard some good arguments why general MPC won't make it into the real world. However, special cases (Voting and Linear Programming were mentioned) offer good opportunities for efficient MPC-like constructions. The principle of using two (or more) clouds also appeared in several talks.
In the first talk we saw some examples of what can go wrong from a security perspective when you ignore what lies beneath. If two virtual machines are executed on the same physical machine, we call them co-resident and if our adversary can get his VM co-resident to ours we may be in trouble. If he can take over the physical machine for example by exploiting a bug in the hypervisor (software layer that runs the VMs), he gains complete control of our VM. Even if he's confined to his VM, he can measure the latency of operations and possibly gain a side-channel from the fact that his code uses the same physical caches as ours. Using Amazon's cloud as an example, the speakers showed that it's surprisingly easy to get co-resident with a target of your choice and to detect if this was successful.
Another nice feature of VMs is they can be suspended to a disk image and restarted. A less nice feature is that the same image can be restarted several times, given a different query each time but may use the same randomness/PRG - practical examples were presented as our favourite browsers seed the PRG for TLS and co. when they start up. In other words, we can actually apply the "forking lemma" in practice! For a server VM, we saw practical examples of stealing the TLS master key this way.
Another security issue arises in cloud-based backup systems like dropbox. They use a trick called deduplication - if two users backup the same file, it only stores the file once and the second user doesn't even have to upload it again (the service can compare file hashes). It's pretty much the equivlent of UNIX hard links. It's estimated that deduplication saves 95%-99% of space for online backup systems, but we're still talking about petabytes.
Deduplication gives anyone an oracle to test whether a file has been backed up before and to brute-force test which version of a file has been backed up if only a small portion is unknown. Another problem is that knowing the hash of someone's file allows you to retrieve it - just pretend you have a file with that hash, deduplication means you get access to it without any further questions. As an aside, dropbox claims to encrypt all files with "military-grade encryption" (AES is mentioned too) but for deduplication to work at all, it seems like they encrypt everyone's files with the same key.
With problems like these out there, what can we do? Two main approaches were presented, both dealing with the fact that the client cannot fully trust the could provider. The first is based on secure hardware (mostly TPMs) and several talks gave scenarios for using hardware-based trust. The second approach is to use software-based cryptography - mostly some variation of MPC, although we heard some good arguments why general MPC won't make it into the real world. However, special cases (Voting and Linear Programming were mentioned) offer good opportunities for efficient MPC-like constructions. The principle of using two (or more) clouds also appeared in several talks.
Wednesday, March 9, 2011
More on PKC 2011
(Written by Georg)
Since Matthew Green from John Hopkins University was unable to come to PKC, I was asked to give the talk for him and I agreed. His paper is on Secure Blind Decryption, a cryptographic primitive which extends a public-key encryption scheme by the following functionality: a User, holding a ciphertext and a Decryptor holding the decryption key run a protocol upon which the User learns the encrypted message. Security demands on the one hand that the User does not learn anything more than the message and on the other that the Decryptor cannot distinguish which ciphertext the User asked to be decrypted.
This primitive has many applications from Oblivious Transfer (with additional properties) to Private Information Retrieval. A practical motivation is that when outsourcing data to an (untrusted) "cloud", not only must the data be protected, but it should also remain hidden which data is accessed. Examples include medical records or patents, where merely the information of which record is accessed can reveal much about a patient's status or a company's intentions.
The author constructs the first CCA-secure scheme with a blind decryption protocol by applying the CHK transform to a variant of a tag-based Cramer-Shoup-type cryptosystem based on DLIN and a new F-unforgeable one-time signature.
Another highlight of the day was Vinod Vaikuntanathan's invited talk on leakage-resilient cryptography. Whereas traditional cryptographic models assume that certain information (such as decryption keys) are completely secret, this is not true in practice: realisations of cryptographic schemes might succumb to side-channel attacks, which reveal parts of the secrets. Leakage-resilient cryptography tries to model these attacks formally and provide (provable) security against them.
Since Matthew Green from John Hopkins University was unable to come to PKC, I was asked to give the talk for him and I agreed. His paper is on Secure Blind Decryption, a cryptographic primitive which extends a public-key encryption scheme by the following functionality: a User, holding a ciphertext and a Decryptor holding the decryption key run a protocol upon which the User learns the encrypted message. Security demands on the one hand that the User does not learn anything more than the message and on the other that the Decryptor cannot distinguish which ciphertext the User asked to be decrypted.
This primitive has many applications from Oblivious Transfer (with additional properties) to Private Information Retrieval. A practical motivation is that when outsourcing data to an (untrusted) "cloud", not only must the data be protected, but it should also remain hidden which data is accessed. Examples include medical records or patents, where merely the information of which record is accessed can reveal much about a patient's status or a company's intentions.
The author constructs the first CCA-secure scheme with a blind decryption protocol by applying the CHK transform to a variant of a tag-based Cramer-Shoup-type cryptosystem based on DLIN and a new F-unforgeable one-time signature.
Another highlight of the day was Vinod Vaikuntanathan's invited talk on leakage-resilient cryptography. Whereas traditional cryptographic models assume that certain information (such as decryption keys) are completely secret, this is not true in practice: realisations of cryptographic schemes might succumb to side-channel attacks, which reveal parts of the secrets. Leakage-resilient cryptography tries to model these attacks formally and provide (provable) security against them.
Monday, March 7, 2011
Ciphertext Policy Attribute Based Encryption
Today at PKC 2011 a talk was given by Hakan Seyalioglu on the paper by Brent Waters, entitled "Ciphertext-Policy Attribute-Based Encryption: An Expressive, Efficient, and Provably Secure Realization".
First, let us consider what attribute based encryption is and why this may be useful. In standard public key cryptography, a file is encrypted under a user's public key. The corresponding secret key (and that key alone) can then be used to decrypt the ciphertext. Now, assume users each have various attributes associated to them. For example, Alice may be in a group called "internal affairs", she is female, and based in the USA office of her organisation. Thus we assign her the attributes "internal affairs", "female" and "USA". If Bob wants to encrypt a document so it can be decrypted by everyone who is a member of the "internal affairs" group, he could create an encryption of the document for every user in this group using their public key. However, what if Bob does not know who is in the group? What if users are added to this group at a later time? In this situation, we can not use standard public key cryptography, therefore we turn to attribute based encryption (ABE).
In ABE, a key authority is considered to be a trusted party who generates keys for users within a system. The key authority has a master secret key (MSK) and public key (PK). For each user in the system the key authority generates keys based on the users attributes, using the MSK. Each user is then given their corresponding secret key, SK. Now, when a user wants to encrypt a document they construct a policy for this document. The policy specifies which attributes are required to decrypt this document, for example ("internal affairs" OR ("female" AND "Canada")). Given the constructed policy and the PK (of the key authority for a system), documents can then be encrypted and distributed to everyone - but only decrypted by users which match the policy assigned to the ciphertext.
Note that if we have the policy ("internal affairs" AND "female" AND "Canada") neither Bob (given the attributes "male" and "Canada") nor Alice should be able to decrypt documents with this policy. We can see that together they meet the criteria - so crucially, we do not want collusion between users to allow them to decrypt documents - only a user who meets the criteria alone should be able to decrypt the document.
Waters introduces a new ciphertext-policy based (as opposed to key-policy based) ABE. When one constructs a new scheme, the security must be considered - formally one produces a proof reducing to some hard cryptographic problem. One consideration when constructing new schemes is what hard problem we wish the scheme to be reduced to. However, ultimately security may depend on whether the hard problem to which you reduce is truly hard. Therefore, Waters gives several different constructions, each reducing to a different problem. One scheme has a ciphertext size of O(n), private key size of O(A) and an encryption time of O(n), where n is the size of an access formula (i.e. the size of the policy), and A is the number of attributes in a user's key. The other schemes have worse complexities, but reduce to different (harder) assumptions. This paper demonstrates well the trade off between assumptions required and the efficiency of the resulting scheme.
Saturday, February 19, 2011
Privacy economics and risk perception workshop
Some of us spent Thursday discussing about privacy and what makes us give our precious personal information away, drawing on prospect and utility theories, econometric models, theories of cognitive bias in decision making as well as the impact of social class and political beliefs. The facilitator, Spyros Kokolakis from the University of Aegean, presented the case of the brand new Greek national ID scheme. This is based on smartcard technology and intended to be used to monitor every single financial transaction for reasons of tackling tax evasion - ambitious as much as controversial!
It was interesting to explore how perceptions of risk vary, depending on contextual anchors, personal experience etc. and consider how their understanding may have a fundamental role in the success of any technological platform, especially in our area of security and privacy. A key observation was that the planning of any intervention based on schemes such as the IDs above, not only does it require a robust technological platform, but also an appreciation for the factors that may facilitate or inhibit its use (or abuse!): perception of value, comfort, fear, perception of risk to name but a few. These are not always easily captured in quantitative or qualitative models and even then, it may be difficult to integrate those into the security design.
And as for the case of the new Greek IDs, if I had any reservations for their effectiveness against tax evasion before, well, those certainly didn't go away after our discussions. But I'll be certainly looking out for the results of Spyros' evaluative research of the scheme.
It was interesting to explore how perceptions of risk vary, depending on contextual anchors, personal experience etc. and consider how their understanding may have a fundamental role in the success of any technological platform, especially in our area of security and privacy. A key observation was that the planning of any intervention based on schemes such as the IDs above, not only does it require a robust technological platform, but also an appreciation for the factors that may facilitate or inhibit its use (or abuse!): perception of value, comfort, fear, perception of risk to name but a few. These are not always easily captured in quantitative or qualitative models and even then, it may be difficult to integrate those into the security design.
And as for the case of the new Greek IDs, if I had any reservations for their effectiveness against tax evasion before, well, those certainly didn't go away after our discussions. But I'll be certainly looking out for the results of Spyros' evaluative research of the scheme.
Subscribe to:
Posts (Atom)