19 September 2024, 2pm-3pm, LIFO meeting room, Bourges (Zoom)
Cryptographic Cryptid Protocols: How to play cryptid with cheaters.
Charlène Jojon
Abstract. (Presentation of an acceptance paper at CANS 2024). Cryptid is a board game in which the goal is to be the first player to locate the cryptid, a legendary creature, on a map. Each player knows a secret clue as to which cell on the map contains the cryptid. Players take it in turns to ask each other if the cryptid could be on a given cell according to their clue, until one of them guesses the cryptid cell. This game is great fun, but completely loses its interest if one of the players cheats by answering the questions incorrectly. For example, if a player answers negatively on the cryptid cell, the game continues for a long time until all the cells have been tested, and ends without a winner. We provide cryptographic protocols to prevent cheating in Cryptid. The main idea is to use encryption to commit the players’ clues, enabling them to show that they are answering correctly in accordance with their clue using zero-knowledge proofs. We give a security model which captures soundness (a player cannot cheat) and confidentiality (the protocol does not leak more information than the players’ answers about their clues), and prove the security of our protocols in this model. We also analyze the practical efficiency of our protocols, based on an implementation of the main algorithms in Rust. Finally, we extend our protocols to ensure that the game designer has correctly constructed the cryptid games, i.e., that the clues are well formed and converge on at least one cell.
|
28 June 2024, 2pm-3pm, LIFO meeting room, Bourges (Zoom)
Physical Ring Signature.
Xavier BULTEL
Abstract. (Presentation of an acceptance paper at FUN 2024). Ring signatures allow members of a group (called ring) to sign a message anonymously
within the group, which is chosen ad hoc at the time of signing (the members do not need to have
interacted before). In this paper, we propose a physical version of ring signatures. Our signature is based
on one-out-of-many signatures, a method used in many real cryptographic ring signatures. It consists
of boxes containing coins locked with padlocks that can only be opened by a particular group member.
To sign a message, a group member shakes the boxes of the other members of the group so that the
coins are in a random state (“heads” or “tails”, corresponding to bits 0 and 1), and opens their box to
arrange the coins so that the exclusive “or” of the coins corresponds to the bits of the message they
wish to sign. We present a prototype that can be used with coins, or with dice for messages encoded
in larger (non-binary) alphabets. We suggest that this system can be used to explain ring signatures
to the general public in a fun way.
|
15 April 2024, 1pm-1:45pm, LIFO meeting room, Bourges (Zoom)
A new PET for Data Collection via Forms with Data Minimization, Full Accuracy and Informed Consent.
Benjamin NGUYEN
Abstract. (Presentation of an acceptance paper at EDBT 2024). The advent of privacy laws and principles such as data minimization and informed consent are supposed to protect citizens from over-collection of personal data. Nevertheless, current processes, mainly through filling forms are still based on practices that lead to over-collection. Indeed, any citizen wishing to apply for a benefit (or service) will transmit all their personal data involved in the evaluation of the eligibility criteria. The resulting problem of over-collection affects millions of individuals, with considerable volumes of information collected. If this problem of compliance concerns both public and private organizations (e.g., social services, banks, insurance companies), it is because it faces non-trivial issues, which hinder the implementation of data minimization by developers. In this paper, we propose a new modeling approach that enables data minimization and informed choices for the users, for any decision problem modeled using classical logic, which covers a wide range of practical cases. Our data minimization solution uses game theoretic notions to explain and quantify the privacy payoff for the user. We show how our algorithms can be applied to practical cases study as a new PET for minimal, fully accurate (all due services must be preserved) and informed data collection.
|