Thursday marks the fourth and final day of Crypto presentations. The morning consisted of three sessions: Codes and Secret Sharing, Signatures and Authentication, and Quantum Security.
The general theme of the first two sessions seemed to be authentication. The first talk was given by Maciej Obremski on Non-Malleable Codes from Two-Source extractors. The application that he mentioned was the storage of data on some device, where an adversary might tamper with it. He talked about ways to encode this data (using non-malleable codes) such that if an adversary tampers with the encoded data, either the result will still decode to the original data, or it decodes to some data that is independent of the original data (i.e., a constant function). Finally, Maciej talked a little bit about the notion of leakage-resilience of the resulting scheme. It is still secure even if the adversary has access to some (bounded) leakage of the encoding function and is able to use this information while tampering with the encoded data.
The second talk was on Optimal Coding for Streaming Authentication and Interactive Communication, given by Ran Gelles. He talked about a combination of error-correction and authentication of data streams, in the setting where the adversary can introduce some (globally bounded) noise on the channel. The usual approach is to use a Message Authentication Code and Error Correcting Codes on the whole of the data, but that is not feasible in a setting where the data is a stream and comes in bit-by-bit. The next possibility would be to divide the data into chunks and applying the previous method to each of the chunks. However, in this case the adversary might be able to attack certain blocks completely while still maintaining low global noise. Furthermore, the authentication guarantee is only per block. The solution that Ran described made use of two interesting tools: blueberry codes and tree codes. The blueberry codes are codes where each bit of the stream is mapped to some random symbol based on the authentication key. This means that, when the adversary changes a symbol, it might no longer correspond to one of the possible symbols for that position. Thus, it is revealed that the symbol was altered and it can be treated as an erasure. The tree codes are binary trees where each node has a label such that two different paths of equal length have labels of a large Hamming distance. These trees have a so-called self-recovery property, which allows for the recovery of most of the message, but unfortunately this can take exponential time. To get around this, the authors propose splitting up the tree in several trees of logarithmic size. Ran also mentioned several extensions to the security, where the user can decide to abort (which occurs with polynomially small probability) such that the probability that the user decodes incorrectly occurs with negligible probability. Finally, he showed that Blueberry codes are useful in other settings as well, such as the interactive communication setting where both users of the system want to transmit data to each other.
The last talk of the session did not contain any authentication, but was instead on the limits of certain proof techniques in the area of secret sharing. Carles Padro talked about Secret Sharing, Rank Inequalities and Information Inequalities. He described the conjecture in secret sharing that there exist certain bad families of access structures where the size of the shares in a secret sharing scheme grow exponentially in the number of users. For linear secret sharing schemes, the lower bound is known to be super-polynomial, but no such bound exists for general secret sharing schemes. All current progress on this result comes from proofs using information inequalities. Previously it was shown that for a limited number of variables (up to 5) such lower bounds could not be bigger than linear in the number of users. In this work the authors show that for any bounded number of variables r, the lower bound can not be bigger than a polynomial of degree r-2 in the number of users.
In the second session, Thomas Peters spoke about Linearly Homomorphic Structure-Preserving Signatures and their applications. I will not go into detail here, but Thomas showed that the combination of these two notions--Linearly Homomorphic Signatures, which are useful for computing on authenticated data, and Structure-Preserving Signatures, which allow composition with algebraic tools such as Groth Sahai proofs--results in possible applications beyond just the sum of the application of its parts. Specifically, Thomas mentioned verifiable computation mechanisms for encrypted data as well as non-malleable structure-preserving commitments.
The last talk before the coffee break was given by Daniel Masny, who talked about Man-in-the-Middle Secure Authentication Schemes from LPN and Weak PRFs. These kinds of authentication schemes are designed for constrained devices, where having a regular PRF may be too costly. Instead, they use the weaker notion of a weak PRF and attempt to design protocols that still remain secure against adversaries. Daniel described two solutions, the first of which is based on the LPN problem. He showed that, in comparison to a previous solution using MACs their solution results in smaller key sizes at the cost of one extra round of communication. The other solution consists of adding one extra secret element to the key of a weak PRF-based scheme, which results in security against Man-in-the-Middle attacks.
After the authentic coffee break we entered the world of Quantum Security. Although there is no fully functional quantum computer that has all the desired properties, people have been extending cryptographic models to the quantum world. For example, Frédéric Dupuis talked about Achieving the limits of the noisy-storage model using entanglement sampling. By looking at the information that a party holds about a certain quantum system before and after a transformation, they were able to provide lower bounds for specific transformations. These lower bounds then allowed the authors to prove a weak string erasure protocol secure in the bounded quantum storage model.
Douglas Stebila talked about Quantum one-time programs, which are programs that can only be run once and then 'self-destruct', preventing them from being run again. Because classical memory can be copied, classical solutions require special assumptions such as secure hardware tokens. Since quantum states cannot be copied due to the no cloning theorem, it appears that such an application would be easier in a quantum world. However, the authors show that this is not the case, and that it is only possible for certain trivial quantum programs.
Most of the cryptographic community considers quantum adversaries interacting with classical users. An adversary might use his quantum computer to break the classical RSA of the users, for example. In contrast, Mark Zhandry talked about quantum adversaries interacting with quantum users in his talk on Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In their model of a quantum signature scheme, the adversary may decide to request a signature on a superposition of all messages and receive a superposition of signatures for all messages. Measuring then gives the adversary a valid signature. Now, the challenge for the adversary is to output more signatures than he queried (and possibly measured). Mark also described a new technique called intermediate measurement, where you measure some small subset of the qubits (thus collapsing the superposition) and continue the algorithm. This is a useful tool in showing the security of schemes in this quantum model.
The last talk of the morning was about Everlasting Multi-Party Computation, given by Dominique Unruh. Everlasting secure protocols remain secure against adversaries that have unlimited computation power as soon as the protocol ends. As long as the protocol is secure against computationally bounded adversaries now, i.e., while running, it remains secure forever. In the face of several impossibility results (even when using trusted set-up information), Dominique showed a solution for everlasting MPC in the quantum model using signature cards.
The general theme of the first two sessions seemed to be authentication. The first talk was given by Maciej Obremski on Non-Malleable Codes from Two-Source extractors. The application that he mentioned was the storage of data on some device, where an adversary might tamper with it. He talked about ways to encode this data (using non-malleable codes) such that if an adversary tampers with the encoded data, either the result will still decode to the original data, or it decodes to some data that is independent of the original data (i.e., a constant function). Finally, Maciej talked a little bit about the notion of leakage-resilience of the resulting scheme. It is still secure even if the adversary has access to some (bounded) leakage of the encoding function and is able to use this information while tampering with the encoded data.
The second talk was on Optimal Coding for Streaming Authentication and Interactive Communication, given by Ran Gelles. He talked about a combination of error-correction and authentication of data streams, in the setting where the adversary can introduce some (globally bounded) noise on the channel. The usual approach is to use a Message Authentication Code and Error Correcting Codes on the whole of the data, but that is not feasible in a setting where the data is a stream and comes in bit-by-bit. The next possibility would be to divide the data into chunks and applying the previous method to each of the chunks. However, in this case the adversary might be able to attack certain blocks completely while still maintaining low global noise. Furthermore, the authentication guarantee is only per block. The solution that Ran described made use of two interesting tools: blueberry codes and tree codes. The blueberry codes are codes where each bit of the stream is mapped to some random symbol based on the authentication key. This means that, when the adversary changes a symbol, it might no longer correspond to one of the possible symbols for that position. Thus, it is revealed that the symbol was altered and it can be treated as an erasure. The tree codes are binary trees where each node has a label such that two different paths of equal length have labels of a large Hamming distance. These trees have a so-called self-recovery property, which allows for the recovery of most of the message, but unfortunately this can take exponential time. To get around this, the authors propose splitting up the tree in several trees of logarithmic size. Ran also mentioned several extensions to the security, where the user can decide to abort (which occurs with polynomially small probability) such that the probability that the user decodes incorrectly occurs with negligible probability. Finally, he showed that Blueberry codes are useful in other settings as well, such as the interactive communication setting where both users of the system want to transmit data to each other.
The last talk of the session did not contain any authentication, but was instead on the limits of certain proof techniques in the area of secret sharing. Carles Padro talked about Secret Sharing, Rank Inequalities and Information Inequalities. He described the conjecture in secret sharing that there exist certain bad families of access structures where the size of the shares in a secret sharing scheme grow exponentially in the number of users. For linear secret sharing schemes, the lower bound is known to be super-polynomial, but no such bound exists for general secret sharing schemes. All current progress on this result comes from proofs using information inequalities. Previously it was shown that for a limited number of variables (up to 5) such lower bounds could not be bigger than linear in the number of users. In this work the authors show that for any bounded number of variables r, the lower bound can not be bigger than a polynomial of degree r-2 in the number of users.
In the second session, Thomas Peters spoke about Linearly Homomorphic Structure-Preserving Signatures and their applications. I will not go into detail here, but Thomas showed that the combination of these two notions--Linearly Homomorphic Signatures, which are useful for computing on authenticated data, and Structure-Preserving Signatures, which allow composition with algebraic tools such as Groth Sahai proofs--results in possible applications beyond just the sum of the application of its parts. Specifically, Thomas mentioned verifiable computation mechanisms for encrypted data as well as non-malleable structure-preserving commitments.
The last talk before the coffee break was given by Daniel Masny, who talked about Man-in-the-Middle Secure Authentication Schemes from LPN and Weak PRFs. These kinds of authentication schemes are designed for constrained devices, where having a regular PRF may be too costly. Instead, they use the weaker notion of a weak PRF and attempt to design protocols that still remain secure against adversaries. Daniel described two solutions, the first of which is based on the LPN problem. He showed that, in comparison to a previous solution using MACs their solution results in smaller key sizes at the cost of one extra round of communication. The other solution consists of adding one extra secret element to the key of a weak PRF-based scheme, which results in security against Man-in-the-Middle attacks.
After the authentic coffee break we entered the world of Quantum Security. Although there is no fully functional quantum computer that has all the desired properties, people have been extending cryptographic models to the quantum world. For example, Frédéric Dupuis talked about Achieving the limits of the noisy-storage model using entanglement sampling. By looking at the information that a party holds about a certain quantum system before and after a transformation, they were able to provide lower bounds for specific transformations. These lower bounds then allowed the authors to prove a weak string erasure protocol secure in the bounded quantum storage model.
Douglas Stebila talked about Quantum one-time programs, which are programs that can only be run once and then 'self-destruct', preventing them from being run again. Because classical memory can be copied, classical solutions require special assumptions such as secure hardware tokens. Since quantum states cannot be copied due to the no cloning theorem, it appears that such an application would be easier in a quantum world. However, the authors show that this is not the case, and that it is only possible for certain trivial quantum programs.
Most of the cryptographic community considers quantum adversaries interacting with classical users. An adversary might use his quantum computer to break the classical RSA of the users, for example. In contrast, Mark Zhandry talked about quantum adversaries interacting with quantum users in his talk on Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In their model of a quantum signature scheme, the adversary may decide to request a signature on a superposition of all messages and receive a superposition of signatures for all messages. Measuring then gives the adversary a valid signature. Now, the challenge for the adversary is to output more signatures than he queried (and possibly measured). Mark also described a new technique called intermediate measurement, where you measure some small subset of the qubits (thus collapsing the superposition) and continue the algorithm. This is a useful tool in showing the security of schemes in this quantum model.
The last talk of the morning was about Everlasting Multi-Party Computation, given by Dominique Unruh. Everlasting secure protocols remain secure against adversaries that have unlimited computation power as soon as the protocol ends. As long as the protocol is secure against computationally bounded adversaries now, i.e., while running, it remains secure forever. In the face of several impossibility results (even when using trusted set-up information), Dominique showed a solution for everlasting MPC in the quantum model using signature cards.
No comments:
Post a Comment