Author: "Pascal Lafourcade" / Search Limiters: Full Text - Searchworks@Jio Institute Digital Library Search Results

Your search keyword '"Pascal Lafourcade"' showing total 148 results

Start Over Author "Pascal Lafourcade" Search Limiters Full Text

148 results on '"Pascal Lafourcade"'

1. History-based MAC Protocol for Low Duty-Cycle Wireless Sensor Networks: the SLACK-MAC Protocol

Author: Affoua Therese Aby, Alexandre Guitton, Pascal Lafourcade, and Michel Misson
Subjects: WSN, adaptive, asynchronous MAC protocol, duty-cycle, Telecommunication, TK5101-6720
Abstract: Wireless sensor networks (WSNs) are increasingly used in environmental monitoring applications. They are designed to operate for several months by featuring low activity cycles in order to save energy. In this paper, we propose a Medium Access Control (MAC) protocol for such WSNs with very low duty-cycles of 1% and less. Nodes are activated randomly and use a history of previous successful frame exchanges to decide their next activation time. We study the choice of the history size, and we compare the performance of our protocol with other protocols from the literature. We show by simulations and real experiments that with a limited history size of only six entries, our protocol achieves better performance than other protocols from the literature, while keeping the advantages of fully asynchronous protocols.
Published: 2017
Full Text: View/download PDF

2. Analysis of AES, SKINNY, and Others with Constraint Programming

Author: Siwei Sun, David Gerault, Pascal Lafourcade, Qianqian Yang, Yosuke Todo, Kexin Qiao, and Lei Hu
Subjects: Differential Cryptanalysis, Integral Cryptanalysis, Constraint Programming, AES, SKINNY, Computer engineering. Computer hardware, TK7885-7895
Abstract: Search for different types of distinguishers are common tasks in symmetrickey cryptanalysis. In this work, we employ the constraint programming (CP) technique to tackle such problems. First, we show that a simple application of the CP approach proposed by Gerault et al. leads to the solution of the open problem of determining the exact lower bound of the number of active S-boxes for 6-round AES-128 in the related-key model. Subsequently, we show that the same approach can be applied in searching for integral distinguishers, impossible differentials, zero-correlation linear approximations, in both the single-key and related-(twea)key model. We implement the method using the open source constraint solver Choco and apply it to the block ciphers PRESENT, SKINNY, and HIGHT (ARX construction). As a result, we find 16 related-tweakey impossible differentials for 12-round SKINNY-64-128 based on which we construct an 18-round attack on SKINNY-64-128 (one target version for the crypto competition https://sites.google.com/site/skinnycipher announced at ASK 2016). Moreover, we show that in some cases, when equipped with proper strategies (ordering heuristic, restart and dynamic branching strategy), the CP approach can be very efficient. Therefore, we suggest that the constraint programming technique should become a convenient tool at hand of the symmetric-key cryptanalysts.
Published: 2017
Full Text: View/download PDF

3. History-based MAC Protocol for Low Duty-Cycle Wireless Sensor Networks: the SLACK-MAC Protocol

Author: Affoua Thérèse Aby, Alexandre Guitton, Pascal Lafourcade, and Michel Misson
Subjects: WSN, adaptive, asynchronous MAC protocol, duty-cycle, Telecommunication, TK5101-6720
Abstract: Wireless sensor networks (WSNs) are increasingly used in environmental monitoring applications. They are designed to operate for several months by featuring low activity cycles in order to save energy. In this paper, we propose a Medium Access Control (MAC) protocol for suchWSNs with very low duty-cycles of 1% and less. Nodes are activated randomly and use a history of previous successful frame exchanges to decide their next activation time. We study the choice of the history size, and we compare the performance of our protocol with other protocols from the literature. We show by simulations and real experiments that with a limited history size of only six entries, our protocol achieves better performance than other protocols from the literature, while keeping the advantages of fully asynchronous protocols.
Published: 2016
Full Text: View/download PDF

4. Key Management in Wireless Sensor Networks

Author: Ismail Mansour, Gérard Chalhoub, and Pascal Lafourcade
Subjects: renewing, revocation, authentication, wireless sensor network, security, multihop, verification, formal proof, Technology
Abstract: Wireless sensor networks are a challenging field of research when it comes to security issues. Using low cost sensor nodes with limited resources makes it difficult for cryptographic algorithms to function without impacting energy consumption and latency. In this paper, we focus on key management issues in multi-hop wireless sensor networks. These networks are easy to attack due to the open nature of the wireless medium. Intruders could try to penetrate the network, capture nodes or take control over particular nodes. In this context, it is important to revoke and renew keys that might be learned by malicious nodes. We propose several secure protocols for key revocation and key renewal based on symmetric encryption and elliptic curve cryptography. All protocols are secure, but have different security levels. Each proposed protocol is formally proven and analyzed using Scyther, an automatic verification tool for cryptographic protocols. For efficiency comparison sake, we implemented all protocols on real testbeds using TelosB motes and discussed their performances.
Published: 2015
Full Text: View/download PDF

5. Evaluation of Secure Multi-Hop Node Authentication and Key Establishment Mechanisms for Wireless Sensor Networks

Author: Ismail Mansour, Gérard Chalhoub, and Pascal Lafourcade
Subjects: authentication, wireless sensor networks, security, overhead of protection, multi-hop, formal verification, Technology
Abstract: Designing secure authentication mechanisms in wireless sensor networks in order to associate a node to a secure network is not an easy task due to the limitations of this type of networks. In this paper, we propose different multi-hop node authentication protocols for wireless sensor networks. For each protocol, we provide a formal proof to verify the security of our proposals using Scyther, which is an automatic cryptographic protocols verification tool. We also provide implementation results in terms of execution time consumption obtained by real measurements on TelosB motes. These protocols offer different security mechanisms depending on the design of the protocol itself. Moreover, we evaluate the overhead of protection of each solution by studying the effect on execution time overhead of each protocol. Finally, we propose a mechanism to detect possible attack based on our evaluation results.
Published: 2014
Full Text: View/download PDF

6. How Did They Design This Game? Swish: Complexity and Unplayable Positions

Author: Antoine Dailly and Pascal Lafourcade and Gaël Marcadet, Dailly, Antoine, Lafourcade, Pascal, Marcadet, Gaël, Antoine Dailly and Pascal Lafourcade and Gaël Marcadet, Dailly, Antoine, Lafourcade, Pascal, and Marcadet, Gaël
Abstract: Swish is a competitive pattern recognition card-based game, in which players are trying to find a valid cards superposition from a set of cards, called a "swish". By the nature of the game, one may expect to easily recover the logic of the Swish’s designers. However, no justification appears to explain the number of cards, of duplicates, but also under which circumstances no player can find a swish. In this work, we formally investigate Swish. In the commercial version of the game, we observe that there exist large sets of cards with no swish, and find a construction to generate large sets of cards without swish. More importantly, in the general case with larger cards, we prove that Swish is NP-complete.
Published: 2024
Full Text: View/download PDF

7. Les monnaies virtuelles décentralisées sont-elles des dispositifs d’avenir ?

Author: Ariane Tichit, Pascal Lafourcade, and Vincent Mazenod
Subjects: decentralized virtual currencies, crypto-currencies, LETs, social currencies, monetary, Economic history and conditions, HC10-1085, Economics as a science, HB71-74
Abstract: In this paper we argue that decentralized virtual currencies can contribute to systemic change driven by SSE. We first show that they cumulate a number of the strengths of local currencies and SELs in their transformative power and provide solutions to some of their weaknesses, while obviously having their own limitations. Secondly, we emphasize that there is a great diversification within crypto-currencies and that some of them are now developing energy-saving protocols that are more useful to the community or based on cooperation, while others serve projects close to SSE. The fusion of these projects, that have a priori opposed values, could therefore create a movement of sufficient magnitude to begin to represent a true counter-power. However, we have some criticisms of these devices and finally propose an idea of crypto-coin with geolocalized demurrage that could meet certain limits encountered especially by local currencies in their definition of proximity.
Full Text: View/download PDF

8. Conflict Optimization for Binary CSP Applied to Minimum Partition into Plane Subgraphs and Graph Coloring

Author: Loïc Crombez, Guilherme D. Da Fonseca, Florian Fontan, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Benjamin Momège, Jack Spalding-Jamieson, Brandon Zhang, Da Wei Zheng, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), MAAD, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Chercheur indépendant, Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), MODélisation Géométrique (GMOD), David R. Cheriton School of Computer Science, University of Waterloo [Waterloo], University of Illinois at Urbana-Champaign [Urbana], University of Illinois System, ANR-19-CE48-0005,ADDS,Algorithmes pour les données multidimensionnelles(2019), ANR-19-CE19-0005,ACTIVmap,Assistance à la Conception de carTes pour défIcients Visuels(2019), ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), ANR-20-CE10-0002,COHERENCE4D,Cohérence des jumeaux numériques pour l'industrie du futur : Modélisation, visualisation et interaction de maquettes numériques 4D interfacées aux systèmes physiques(2020), ANR-18-CE39-0019,MobiS5,La sécurité et la privacy dans les réseaux 5G(2018), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), and ANR-20-CE39-0005,PRIVABIO,Vers des systèmes de reconnaissance biométrique respectueux de la vie privée(2020)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, Graph Coloring, Computer Science - Data Structures and Algorithms, Computer Science - Computational Geometry, Constraint Satisfaction Problems, [INFO]Computer Science [cs], Data Structures and Algorithms (cs.DS), CG:SHOP 2022, DIMACS, Theoretical Computer Science
Abstract: CG:SHOP is an annual geometric optimization challenge and the 2022 edition proposed the problem of coloring a certain geometric graph defined by line segments. Surprisingly, the top three teams used the same technique, called conflict optimization. This technique has been introduced in the 2021 edition of the challenge, to solve a coordinated motion planning problem. In this paper, we present the technique in the more general framework of binary constraint satisfaction problems (binary CSP). Then, the top three teams describe their different implementations of the same underlying strategy. We evaluate the performance of those implementations to vertex color not only geometric graphs, but also other types of graphs., Comment: To appear at ACM Journal of Experimental Algorithmics
Published: 2023
Full Text: View/download PDF

9. Shadoks Approach to Low-Makespan Coordinated Motion Planning

Author: Loïc Crombez, Guilherme D. da Fonseca, Yan Gerard, Aldo Gonzalez-Lorenzo, Pascal Lafourcade, Luc Libralesso, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), MAAD, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE), Algorithmique, Combinatoire et Recherche Opérationnelle (ACRO), Laboratoire d'Informatique et Systèmes (LIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS)-Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Centre National de la Recherche Scientifique (CNRS), Laboratoire des Sciences de l'Information et des Systèmes (LSIS), Aix Marseille Université (AMU)-Université de Toulon (UTLN)-Arts et Métiers Paristech ENSAM Aix-en-Provence-Centre National de la Recherche Scientifique (CNRS), MODélisation Géométrique (GMOD), French government research program ``Investissements d'Avenir' through the IDEX-ISITE initiative 16-IDEX-0001 (CAP 20-25), ANR-19-CE48-0005,ADDS,Algorithmes pour les données multidimensionnelles(2019), ANR-19-CE19-0005,ACTIVmap,Assistance à la Conception de carTes pour défIcients Visuels(2019), ANR-20-CE10-0002,COHERENCE4D,Cohérence des jumeaux numériques pour l'industrie du futur : Modélisation, visualisation et interaction de maquettes numériques 4D interfacées aux systèmes physiques(2020), ANR-18-CE39-0019,MobiS5,La sécurité et la privacy dans les réseaux 5G(2018), ANR-20-CE39-0005,PRIVABIO,Vers des systèmes de reconnaissance biométrique respectueux de la vie privée(2020), and ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018)
Subjects: Computational Geometry (cs.CG), FOS: Computer and information sciences, shortest path, Computer Science - Robotics, Computer Science - Computational Geometry, [INFO]Computer Science [cs], multi agent path finding, heuristics, motion planning, Robotics (cs.RO), Theoretical Computer Science
Abstract: This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge. This year's problem is to coordinate the motion of multiple robots in order to reach their targets without collisions and minimizing the makespan. It is a classical multi agent path finding problem with the specificity that the instances are highly dense in an unbounded grid. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them. The main ingredients include several different strategies to compute initial solutions coupled with a heuristic called Conflict Optimizer to reduce the makespan of existing solutions., Comment: Journal version to appear on ACM Journal on Algorithmics
Published: 2022
Full Text: View/download PDF

10. Local Search with Weighting Schemes for the CG:SHOP 2022 Competition (CG Challenge)

Author: Florian Fontan and Pascal Lafourcade and Luc Libralesso and Benjamin Momège, Fontan, Florian, Lafourcade, Pascal, Libralesso, Luc, Momège, Benjamin, Florian Fontan and Pascal Lafourcade and Luc Libralesso and Benjamin Momège, Fontan, Florian, Lafourcade, Pascal, Libralesso, Luc, and Momège, Benjamin
Abstract: This paper describes the heuristics used by the LASAOFOOFUBESTINNRRALLDECA team for the CG:SHOP 2022 challenge. We introduce a new greedy algorithm that exploits information about the challenge instances, and hybridize two classical local-search schemes with weighting schemes. We found 211/225 best-known solutions. Hence, with the algorithms presented in this article, our team was able to reach the 3rd place of the challenge, among 40 participating teams.
Published: 2022
Full Text: View/download PDF

11. Beedroids: How Luminous Autonomous Swarms of UAVs Can Save the World?

Author: Quentin Bramas and Stéphane Devismes and Anaïs Durand and Pascal Lafourcade and Anissa Lamani, Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, Lamani, Anissa, Quentin Bramas and Stéphane Devismes and Anaïs Durand and Pascal Lafourcade and Anissa Lamani, Bramas, Quentin, Devismes, Stéphane, Durand, Anaïs, Lafourcade, Pascal, and Lamani, Anissa
Abstract: Bee extinction is a great risk for humanity. To circumvent this ineluctable disaster, we propose to develop beedroids, i.e., small UAVs mimicking the behaviors of real bees. Those beedroids are endowed with very weak capabilities (short-range visibility sensors, no GPS, light with a few colors, ...). Like real bees, they have to self-organize together into swarms. Beedroid swarms will be deployed in cuboid-shaped greenhouse. Each beedroid swarm will have to indefinitely search for flowers to pollinate in its greenhouse. We model this problem as a perpetual exploration of a 3D grid by a swarm of beedroids. In this paper, we propose two optimal solutions to solve this problem and so to save humanity.
Published: 2022
Full Text: View/download PDF

12. Improved Constructions of Anonymous Credentials From Structure-Preserving Signatures on Equivalence Classes

Author: Aisling Connolly, Pascal Lafourcade, Octavio Perez Kempner, DFINITY Foundation [Zurich], Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), and Lafourcade, Pascal
Subjects: [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Mercurial signatures, Anonymous credentials, SPS-EQ, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: International audience; Anonymous attribute-based credentials (ABCs) are a powerful tool allowing users to authenticate while maintaining privacy. When instantiated from structure-preserving signatures on equivalence classes (SPS-EQ) we obtain a controlled form of malleability, and hence increased functionality and privacy for the user. Existing constructions consider equivalence classes on the message space, allowing the joint randomization of credentials and the corresponding signatures on them. In this work, we additionally consider equivalence classes on the signingkey space. In this regard, we obtain a signer-hiding notion, where the issuing organization is not revealed when a user shows a credential. To achieve this, we instantiate the ABC framework of Fuchsbauer, Hanser, and Slamanig (FHS, Journal of Cryptology '19) with a recent SPS-EQ scheme (ASIACRYPT '19) modified to support a fully adaptive NIZK from the framework of Couteau and Hartmann (CRYPTO '20). We also show how to obtain Mercurial Signatures (CT-RSA, 2019), extending the application of our construction to anonymous delegatable credentials. To further increase functionality and efficiency, we augment the setcommitment scheme of FHS19 to support openings on attribute sets disjoint from those possessed by the user, while integrating a proof of exponentiation to allow for a more efficient verifier. Instantiating in the CRS model, we obtain an efficient credential system, anonymous under malicious organization keys, with increased expressiveness and privacy, proven secure in the standard model.
Published: 2022

13. SAMBA: A Generic Framework for Secure Federated Multi-Armed Bandits

Author: Radu Ciucanu, Pascal Lafourcade, Gael Marcadet, Marta Soare, Laboratoire d'Informatique de Grenoble (LIG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), ANR-19-P3IA-0003,MIAI,MIAI @ Grenoble Alpes(2019), European Project: H2020,INODE, and European Project: 952215,TAILOR(2020)
Subjects: reinforcement learning, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], machine learning, [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], [INFO.INFO-LG]Computer Science [cs]/Machine Learning [cs.LG], Artificial Intelligence, distributed AI, ComputingMethodologies_ARTIFICIALINTELLIGENCE, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Abstract: International audience; The multi-armed bandit is a reinforcement learning model where a learning agent repeatedly chooses an action (pull a bandit arm) and the environment responds with a stochastic outcome (reward) coming from an unknown distribution associated with the chosen arm. Bandits have a wide-range of application such as Web recommendation systems. We address the cumulative reward maximization problem in a secure federated learning setting, where multiple data owners keep their data stored locally and collaborate under the coordination of a central orchestration server. We rely on cryptographic schemes and propose SAMBA, a generic framework for Secure federAted Multi-armed BAndits. Each data owner has data associated to a bandit arm and the bandit algorithm has to sequentially select which data owner is solicited at each time step. We instantiate SAMBA for five bandit algorithms. We show that SAMBA returns the same cumulative reward as the non-secure versions of bandit algorithms, while satisfying formally proven security properties. We also show that the overhead due to cryptographic primitives is linear in the size of the input, which is confirmed by our proof-of-concept implementation.https://www.jair.org/index.php/jair/article/view/13163
Published: 2022

14. Les blockchains en 50 questions

Author: Jean-Guillaume Dumas, pascal lafourcade, Ariane Tichit, and Sébastien Varette
Subjects: Computer science [C05] [Engineering, computing & technology], blockchains, Sciences informatiques [C05] [Ingénierie, informatique & technologie]
Abstract: La création du bitcoin en 2009 est remarquable à plus d’un titre, tout d’abord parce qu’elle repose sur le mécanisme novateur de la blockchain qui permet d’enregistrer de manière distribuée des informations de façon irréversible et vérifiable par tout le monde. Aujourd’hui les blockchains ne se limitent plus aux cryptomonnaies, et touchent de nombreux autres domaines (contrats intelligents, NFT…). Ce livre est conçu pour répondre non seulement aux questions que vous vous posez sur l’univers des blockchains… mais aussi à celles que vous ne vous étiez pas encore posées. Qu’est-ce qu’une blockchain ? Quel est le lien entre le bitcoin et les blockchains ? Qui sont les mineurs et que font-ils ? Qu’est-ce qu’un consensus ? Qu’est-ce qu’un contrat intelligent ? Peut-on faire une blockchain sans bloc ? Quelle est la part des cryptomonnaies dans l’économie mondiale ? Comment les blockchains vont-elles révolutionner le monde ? Les réponses à toutes ces questions (et à 42 autres) sont dans ce livre. 2eme edition
Published: 2022

15. Physical Zero-Knowledge Proof and NP-completeness Proof of Suguru Puzzle ⋆

Author: Léo Robert, Daiki Miyahara, Pascal Lafourcade, Luc Libralesso, Takaaki Mizuki, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), University of Electro-Communications [Tokyo] (UEC), National Institute of Advanced Industrial Science and Technology (AIST), Cyberscience Center, Tohoku University, ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), ANR-18-CE39-0019,MobiS5,La sécurité et la privacy dans les réseaux 5G(2018), and ANR-20-CE39-0009,SEVERITAS,Systèmes de tests et evaluations sûrs et vérifiables(2020)
Subjects: Completeness, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Computational Theory and Mathematics, Suguru, Security, Zero-knowledge, Physical zero-knowledge proof, Extractability, Computer Science Applications, Information Systems, Theoretical Computer Science
Abstract: International audience; Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fill a grid with numbers between 1 and 5 while respecting three simple constraints. We first prove the NP-completeness of Suguru puzzle. For this we design gadgets to encode the PLANAR-CIRCUIT-SAT in a Suguru grid. We then design a physical Zero-Knowledge Proof (ZKP) protocol for Suguru. This ZKP protocol allows a prover to prove that he knows a solution of a Suguru grid to a verifier without leaking any information on the solution. To construct such a physical ZKP protocol, we only rely on a few physical cards and adapted encoding. For a Suguru grid with n cells, we only use 5n + 5 cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.
Published: 2022
Full Text: View/download PDF

16. Card-Based ZKP for Connectivity: Applications to Nurikabe, Hitori, and Heyawake

Author: Léo Robert, Daiki Miyahara, Pascal Lafourcade, Takaaki Mizuki, Robert, Léo, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), National Institute of Advanced Industrial Science and Technology (AIST), University of Electro-Communications [Tokyo] (UEC), and Cyberscience Center, Tohoku University
Subjects: Connectivity, Puzzle, Computer Networks and Communications, MathematicsofComputing_GENERAL, Nurikabe, Card-based secure two-party protocols, Hitori, Theoretical Computer Science, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Hardware and Architecture, Heyawake, Zero-knowledge proofs, Software, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: During the last years, several card-based Zero-Knowledge Proof (ZKP) protocols for Nikoli’s puzzles have been designed. Although there are relatively simple card-based ZKP protocols for a number of puzzles, such as Sudoku and Kakuro, some puzzles face difficulties in designing simple protocols. For example, Slitherlink requires novel and elaborate techniques to construct a protocol. In this study, we focus on three Nikoli puzzles: Nurikabe, Hitori, and Heyawake. To date, no card-based ZKP protocol for these puzzles has been developed, partially because they have a relatively tricky rule that colored cells should form a connected area (namely a polyomino); this rule, sometimes referred to as “Bundan-kin” (in Japanese), complicates the puzzles, as well as facilitating difficulties in designing card-based ZKP protocols. We address this challenging task and propose a method for verifying the connectivity of hidden colored cells in a ZKP manner, such that we construct card-based ZKP protocols for the three puzzles.
Published: 2022

17. Fast Cramer-Shoup Cryptosystem

Author: Demba Sow, Pascal Lafourcade, Léo Robert, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)
Subjects: Scheme (programming language), Public Key Encryption, business.industry, Computer science, Cramer–Shoup cryptosystem, Encryption, Public-key cryptography, Cramer-Shoup, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], IND-CCA2, ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS, business, Algorithm, computer, computer.programming_language
Abstract: International audience; Cramer-Shoup was the first practical adaptive CCA-secure public key encryption scheme. We propose a faster version of this encryption scheme, called Fast Cramer-Shoup. We show empirically and theoretically that our scheme is faster than three versions proposed by Cramer-Shoup in 1998. We observe an average gain of 60% for the decryption algorithm. We prove the IND-CCA2 security of our scheme. The proof only relies on intractability assumptions like DDH.
Published: 2021
Full Text: View/download PDF

18. Interactive Physical Zero-Knowledge Proof for Norinori

Author: Jean, Guillaume Dumas, Pascal, Lafourcade, Daiki, Miyahara, Takaaki, Mizuki, Tatsuya, Sasaki, and Hideaki, Sone
Published: 2019
Full Text: View/download PDF

19. How to construct physical zero-knowledge proofs for puzzles with a 'single loop' condition

Author: Léo Robert, Hideaki Sone, Pascal Lafourcade, Daiki Miyahara, Tatsuya Sasaki, Takaaki Mizuki, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Tohoku University [Sendai], Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), ANR-18-CE39-0019,MobiS5,La sécurité et la privacy dans les réseaux 5G(2018), and ANR-20-CE39-0009,SEVERITAS,Systèmes de tests et evaluations sûrs et vérifiables(2020)
Subjects: Property (philosophy), General Computer Science, Computer science, business.industry, Cryptography, 0102 computer and information sciences, 02 engineering and technology, Construct (python library), 01 natural sciences, Theoretical Computer Science, Loop (topology), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Simple (abstract algebra), 0202 electrical engineering, electronic engineering, information engineering, Calculus, Feature (machine learning), 020201 artificial intelligence & image processing, Zero-knowledge proof, business, Single loop
Abstract: International audience; We propose a technique to construct physical Zero-Knowledge Proof (ZKP) protocols for puzzles that require a single loop draw feature. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, which is visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. We illustrate our technique by applying it to construct physical ZKP protocols for two Nikoli puzzles: Slitherlink and Masyu.
Published: 2021
Full Text: View/download PDF

20. From Relay Attacks to Distance-Bounding Protocols

Author: Gerhard P. Hancke, Gildas Avoine, Ioana Boureanu, Cristina Onete, Pascal Lafourcade, and David Gerault
Subjects: 021110 strategic, defence & security studies, Authentication, business.industry, Computer science, Dimension (graph theory), 0211 other engineering and technologies, 02 engineering and technology, law.invention, Bounding overwatch, Relay, law, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, business, Countermeasure (computer), Computer network
Abstract: We present the concept of relay attacks, and discuss distance-bounding schemes as the main countermeasure. We give details on relaying mechanisms, we review canonical distance-bounding protocols, as well as their threat-model (i.e., covering attacks beyond relaying) stemming from the authentication dimension in distance bounding. Advanced aspects of distance-bounding security are also covered. We conclude by presenting what we consider to be the most important challenges in distance bounding.
Published: 2021
Full Text: View/download PDF

21. Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Robots Without Common Chirality

Author: Quentin Bramas, Pascal Lafourcade, Arthur Rauch, Anissa Lamani, Stéphane Devismes, Devismes, Stéphane, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), ANR-16-CE25-0009,ESTATE,Auto-stabilisation et amélioration de la sûreté dans les environnements distribués évoluant dans le temps(2016), and ANR-16-CE40-0023,DESCARTES,Abstraction modulaire pour le calcul distribué(2016)
Subjects: Physics, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], Robot, Chirality (chemistry), Grid, Topology, ComputingMilieux_MISCELLANEOUS
Abstract: International audience
Published: 2021
Full Text: View/download PDF

22. Optimal Exclusive Perpetual Grid Exploration by Luminous Myopic Opaque Robots with Common Chirality

Author: Stéphane Devismes, Quentin Bramas, Pascal Lafourcade, Laboratoire des sciences de l'ingénieur, de l'informatique et de l'imagerie (ICube), Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS)-École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Réseau nanophotonique et optique, Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Matériaux et nanosciences d'Alsace (FMNGE), Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS)-Institut de Chimie du CNRS (INC)-Université de Strasbourg (UNISTRA)-Institut National de la Santé et de la Recherche Médicale (INSERM)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), VERIMAG (VERIMAG - IMAG), Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), École Nationale du Génie de l'Eau et de l'Environnement de Strasbourg (ENGEES)-Université de Strasbourg (UNISTRA)-Institut National des Sciences Appliquées - Strasbourg (INSA Strasbourg), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Les Hôpitaux Universitaires de Strasbourg (HUS)-Centre National de la Recherche Scientifique (CNRS)-Matériaux et Nanosciences Grand-Est (MNGE), Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Institut National de la Santé et de la Recherche Médicale (INSERM)-Institut de Chimie du CNRS (INC)-Centre National de la Recherche Scientifique (CNRS)-Réseau nanophotonique et optique, Université de Strasbourg (UNISTRA)-Université de Haute-Alsace (UHA) Mulhouse - Colmar (Université de Haute-Alsace (UHA))-Centre National de la Recherche Scientifique (CNRS)-Université de Strasbourg (UNISTRA)-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and Lafourcade, Pascal
Subjects: Opacity, Computer science, ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION, chirality, Context (language use), 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Computer Science::Robotics, exclusiveness, [INFO.INFO-NI]Computer Science [cs]/Networking and Internet Architecture [cs.NI], Compass, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], ComputingMethodologies_COMPUTERGRAPHICS, perpetual exploration, [INFO.INFO-NI] Computer Science [cs]/Networking and Internet Architecture [cs.NI], [INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO], Visibility (geometry), opacity, Grid, Chirality (electromagnetism), [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation, Range (mathematics), 010201 computation theory & mathematics, Robot, 020201 artificial intelligence & image processing, finite grid, [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, Algorithm, Luminous myopic robots
Abstract: International audience; We consider swarms of luminous myopic opaque robots that run in synchronous Look-Compute-Move cycles. These robots have no global compass, but agree on a common chirality. In this context, we propose optimal solutions to the perpetual exploration of a finite grid. Precisely, we investigate optimality in terms of the visibility range, number of robots, and number of colors. In more detail, under the optimal visibility range one, we give an algorithm which is optimal w.r.t. both the number of robots and colors: it uses two robots and three colors. Under visibility two, we design two algorithms: the first one uses three robots with an optimal number of colors (i.e., one), the second one achieves the best trade-off between the number of robots and colors, i.e., it uses two robots and two colors.
Published: 2021
Full Text: View/download PDF

23. Interactive Physical ZKP for Connectivity: Applications to Nurikabe and Hitori

Author: Daiki Miyahara, Takaaki Mizuki, Léo Robert, and Pascal Lafourcade
Subjects: Theoretical computer science, Computer science, Novelty, Zero-knowledge proof
Abstract: During the last years, many Physical Zero-knowledge Proof (ZKP) protocols for Nikoli’s puzzles have been designed. In this paper, we propose two ZKP protocols for the two Nikoli’s puzzles called Nurikabe and Hitori. These two puzzles have some similarities, since in their rules at least one condition requires that some cells are connected to each other, horizontally or vertically. The novelty in this paper is to propose two techniques that allow us to prove such connectivity without leaking any information about a solution.
Published: 2021
Full Text: View/download PDF

24. Authentication Attacks on Projection-based Cancelable Biometric Schemes

Author: Axel Durbet, Paul-Marie Grollemund, Pascal Lafourcade, Denis Migdal, Kevin Thiry-Atighehchi, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), and ANR-20-CE39-0005,PRIVABIO,Vers des systèmes de reconnaissance biométrique respectueux de la vie privée(2020)
Subjects: FOS: Computer and information sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Computer Science - Cryptography and Security, Computer Vision and Pattern Recognition (cs.CV), Data_MISCELLANEOUS, Computer Science - Computer Vision and Pattern Recognition, Cryptography and Security (cs.CR)
Abstract: Cancelable biometric schemes aim at generating secure biometric templates by combining user specific tokens, such as password, stored secret or salt, along with biometric data. This type of transformation is constructed as a composition of a biometric transformation with a feature extraction algorithm. The security requirements of cancelable biometric schemes concern the irreversibility, unlinkability and revocability of templates, without losing in accuracy of comparison. While several schemes were recently attacked regarding these requirements, full reversibility of such a composition in order to produce colliding biometric characteristics, and specifically presentation attacks, were never demonstrated to the best of our knowledge. In this paper, we formalize these attacks for a traditional cancelable scheme with the help of integer linear programming (ILP) and quadratically constrained quadratic programming (QCQP). Solving these optimization problems allows an adversary to slightly alter its fingerprint image in order to impersonate any individual. Moreover, in an even more severe scenario, it is possible to simultaneously impersonate several individuals., Comment: arXiv admin note: text overlap with arXiv:1910.01389 by other authors
Published: 2021
Full Text: View/download PDF

25. Automatic Generation of Declarative Models For Differential Cryptanalysis

Author: Luc Libralesso and François Delobel and Pascal Lafourcade and Christine Solnon, Libralesso, Luc, Delobel, François, Lafourcade, Pascal, Solnon, Christine, Luc Libralesso and François Delobel and Pascal Lafourcade and Christine Solnon, Libralesso, Luc, Delobel, François, Lafourcade, Pascal, and Solnon, Christine
Abstract: When designing a new symmetric block cipher, it is necessary to evaluate its robustness against differential attacks. This is done by computing Truncated Differential Characteristics (TDCs) that provide bounds on the complexity of these attacks. TDCs are often computed by using declarative approaches such as CP (Constraint Programming), SAT, or ILP (Integer Linear Programming). However, designing accurate and efficient models for these solvers is a difficult, error-prone and time-consuming task, and it requires advanced skills on both symmetric cryptography and solvers. In this paper, we describe a tool for automatically generating these models, called Tagada (Tool for Automatic Generation of Abstraction-based Differential Attacks). The input of Tagada is an operational description of the cipher by means of black-box operators and bipartite Directed Acyclic Graphs (DAGs). Given this description, we show how to automatically generate constraints that model operator semantics, and how to generate MiniZinc models. We experimentally evaluate our approach on two different kinds of differential attacks (e.g., single-key and related-key) and four different symmetric block ciphers (e.g., the AES (Advanced Encryption Standard), Craft, Midori, and Skinny). We show that our automatically generated models are competitive with state-of-the-art approaches. These automatically generated models constitute a new benchmark composed of eight optimization problems and eight enumeration problems, with instances of increasing size in each problem. We experimentally compare CP, SAT, and ILP solvers on this new benchmark.
Published: 2021
Full Text: View/download PDF

26. Proof of Behavior (Short Paper)

Author: Paul-Marie Grollemund and Pascal Lafourcade and Kevin Thiry-Atighehchi and Ariane Tichit, Grollemund, Paul-Marie, Lafourcade, Pascal, Thiry-Atighehchi, Kevin, Tichit, Ariane, Paul-Marie Grollemund and Pascal Lafourcade and Kevin Thiry-Atighehchi and Ariane Tichit, Grollemund, Paul-Marie, Lafourcade, Pascal, Thiry-Atighehchi, Kevin, and Tichit, Ariane
Abstract: Our aim is to change the Proof of Work paradigm. Instead of wasting energy in dummy computations with hash computations, we propose a new approach based on the behavior of the users. Our idea is to design a mechanism that replaces the Proof of Work and that has a positive impact on the world and a social impact on the behaviors of the citizens. For this, we introduce the notion of Proof of Behavior. Based on this notion, we present a new cryptocurrency, called EcoMobiCoin, that encourages the ecological behavior in the mobility of the citizens.
Published: 2021
Full Text: View/download PDF

27. Shadoks Approach to Low-Makespan Coordinated Motion Planning (CG Challenge)

Author: Loïc Crombez and Guilherme D. da Fonseca and Yan Gerard and Aldo Gonzalez-Lorenzo and Pascal Lafourcade and Luc Libralesso, Crombez, Loïc, da Fonseca, Guilherme D., Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, Libralesso, Luc, Loïc Crombez and Guilherme D. da Fonseca and Yan Gerard and Aldo Gonzalez-Lorenzo and Pascal Lafourcade and Luc Libralesso, Crombez, Loïc, da Fonseca, Guilherme D., Gerard, Yan, Gonzalez-Lorenzo, Aldo, Lafourcade, Pascal, and Libralesso, Luc
Abstract: This paper describes the heuristics used by the Shadoks team for the CG:SHOP 2021 challenge on motion planning. Using the heuristics outlined in this paper, our team won first place with the best solution to 202 out of 203 instances and optimal solutions to at least 105 of them.
Published: 2021
Full Text: View/download PDF

28. Fast Short and Fast Linear Cramer-Shoup

Author: Demba Sow, Léo Robert, Pascal Lafourcade, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Laboratoire d'Algèbre, de Cryptologie, de Géométrie Algébrique et Applications (LACGAA), Université Cheikh Anta Diop [Dakar, Sénégal] (UCAD), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), and Robert, Léo
Subjects: Scheme (programming language), business.industry, Computer science, Linear Assumption, 020206 networking & telecommunications, Short Cramer-Shoup, 0102 computer and information sciences, 02 engineering and technology, Encryption, IND-CCA, 01 natural sciences, Linear Cramer-Shoup, IND-PCA, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, 0202 electrical engineering, electronic engineering, information engineering, ComputerSystemsOrganization_SPECIAL-PURPOSEANDAPPLICATION-BASEDSYSTEMS, business, Algorithm, computer, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR], computer.programming_language
Abstract: International audience; A linear Cramer-Shoup encryption scheme version was proposed by Shacham in 2007. Short Cramer-Shoup encryption scheme was designed by Abdalla et al. in 2014. This scheme is a variant of the Cramer-Shoup encryption scheme that has a smaller size. They proved that it is an IND-PCA secure encryption under DDH and the collisionresistance assumptions. We design a faster version of Short Cramer-Shoup encryption scheme denoted Fast Short Cramer-Shoup encryption. We also, proposed a faster version of linear Cramer-Shoup encryption called Fast Linear Cramer-Shoup. We prove that the Fast Short Cramer-Shoup is IND-PCA secure under DDH and the collision-resistance assumptions. We also, show that our linear encryption is CCA secure under the Linear assumption. Finally we run an evaluation of performances of our schemes.
Published: 2020

29. Physical Zero-Knowledge Proof for Suguru Puzzle

Author: Léo Robert, Daiki Miyahara, pascal lafourcade, Takaaki Mizuki, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Tohoku University [Sendai], Lafourcade, Pascal, Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Completeness, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Suguru, Security, Physical zero-knowledge proof, Extractability, Zero-knowledge proof, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: International audience; Suguru is a paper and pencil puzzle invented by Naoki Inaba. The goal of the game is to fulfil a grid with numbers between 1 and 5 and to respect three simple constraints. In this paper we design a physical Zero-Knowledge Proof (ZKP) protocol for Suguru. A ZKP protocol allows a prover (P) to prove that he knows a solution of a Suguru grid to a verifier (V) without leaking any information on the solution. For constructing such a physical ZKP protocol, we only rely on a small number of physical cards and an adapted encoding. For a grid of Suguru with n cells, we only use 5n + 5 cards. Moreover, we prove the three classical security properties of a ZKP: completeness, extractability, and zero-knowledge.
Published: 2020

30. A Faster Cryptographer's Conspiracy Santa

Author: Pascal Lafourcade, Jean-Guillaume Dumas, Xavier Bultel, Jannik Dreier, Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Sécurité des Données et des Systèmes (SDS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Proof techniques for security protocols (PESTO), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: FOS: Computer and information sciences, Cryptocurrency, Computer Science - Cryptography and Security, General Computer Science, ComputerApplications_COMPUTERSINOTHERSYSTEMS, 0102 computer and information sciences, 02 engineering and technology, Computer security, computer.software_genre, 01 natural sciences, Sharing expenses, Theoretical Computer Science, Social group, Physical Cryptography, Privacy-preserving Protocols, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, Formal Security Models, business.industry, Group (mathematics), Secure Multi-Party Computation, Trusted third party, 16. Peace & justice, Secret Santa, Conspiracy Santa, 010201 computation theory & mathematics, Secure multi-party computation, 020201 artificial intelligence & image processing, The Internet, business, Cryptography and Security (cs.CR), computer, Database transaction
Abstract: International audience; In Conspiracy Santa, a variant of Secret Santa, a group of people offer each other Christmas gifts, where each member of the group receives a gift from the other members of the group. To that end, the members of the group form conspiracies, to decide on appropriate gifts, and usually divide the cost of each gift among all participants of that conspiracy. This requires to settle the shared expenses per conspiracy, so Conspiracy Santa can actually be seen as an aggregation of several shared expenses problems. First, we show that the problem of finding a minimal number of transaction when settling shared expenses is NP-complete. Still, there exist good greedy approximations. Second, we present a greedy distributed secure solution to Conspiracy Santa. This solution allows a group of n people to share the expenses for the gifts in such a way that no participant learns the price of his gift, but at the same time notably reduces the number of transactions to 2 · n + 1 with respect to a naïve aggregation of n · (n − 2). Furthermore, our solution does not require a trusted third party, and can either be implemented physically (the participants are in the same room and exchange money using envelopes) or, over Internet, using a cryptocurrency.
Published: 2020
Full Text: View/download PDF

31. About blockchain interoperability

Author: Pascal Lafourcade, Marius Lombard-Platet, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Blockchain, Computer science, Interoperability, 0102 computer and information sciences, 02 engineering and technology, Limiting, Computer security, computer.software_genre, 01 natural sciences, Computer Science Applications, Theoretical Computer Science, 010201 computation theory & mathematics, Signal Processing, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, [INFO]Computer Science [cs], computer, Information Systems
Abstract: A blockchain is designed to be a self-sufficient decentralised ledger: a peer verifying the validity of past transactions only needs to download the blockchain (the ledger) and nothing else. However, it might be of interest to make two different blockchains interoperable, i.e., to allow one to transmit information from one blockchain to another blockchain. In this paper, we give a formalisation of this problem, and we prove that blockchain interoperability is impossible according to the classical definition of a blockchain. Under a weaker definition of blockchain, we demonstrate that two blockchains are interoperable is equivalent to creating a ‘2-in-1’ blockchain containing both ledgers, thus limiting the theoretical interest of making interoperable blockchains in the first place. We also observe that all practical existing interoperable blockchain frameworks work indeed by exchanging already created tokens between two blockchains and not by offering the possibility to transfer tokens from one blockchain to another one, which implies a modification of the balance of total created tokens on both blockchains. It confirms that having interoperability is only possible by creating a ‘2-in-1’ blockchain containing both ledgers.
Published: 2020
Full Text: View/download PDF

32. A Silver Bullet? A Comparison of Accountants and Developers Mental Models in the Raise of Blockchain

Author: Marius Lombard-Platet, Pascal Lafourcade, Claudia Negri-Ribalta, Rose Esmander, ESCP-EAP (ESCP-EAP), Ecole Supérieure de Commerce de Paris, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Informatique de Paris 1 (CRI), Université Paris 1 Panthéon-Sorbonne (UP1), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), École normale supérieure - Paris (ENS Paris), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Département d'informatique de l'École normale supérieure (DI-ENS)
Subjects: blockchain, transparency, 021110 strategic, defence & security studies, Blockchain, Knowledge management, business.industry, Computer science, 0211 other engineering and technologies, accounting, trust, 02 engineering and technology, Audit, Transparency (behavior), [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], mental models, Silver bullet, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Formal concept analysis, Relevance (information retrieval), business
Abstract: International audience; This exploratory paper intends to drive preliminary insights on the different mental models accountants and blockchain developers have on the implementation of blockchain for accounting. Based on the question of whether blockchain applications for accounting could be revolutionary, this paper employs a ground theory methodology based on semi-structured interviews and concept analysis to highlight the different approaches to transparency and trust between the selected groups, the challenges of blockchain and the potential effects of this technology in accounting. Although deeper studies are needed, the conclusions highlight the socio-technical nature of accounting; the relevance and changes of the concepts of trust and transparency when marrying both disciplines; and the real relevance of this technology for the processes of auditing and accounting.
Published: 2020
Full Text: View/download PDF

33. Linear Generalized ElGamal Encryption Scheme

Author: Pascal Lafourcade, Demba Sow, Léo Robert, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Algèbre, de Cryptologie, de Géométrie Algébrique et Applications (LACGAA), Université Cheikh Anta Diop [Dakar, Sénégal] (UCAD), Lafourcade, Pascal, Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])
Subjects: Scheme (programming language), Theoretical computer science, business.industry, Computer science, Probabilistic logic, Homomorphic encryption, Linear Assumption, ElGamal encryption scheme, Partial homomorphic encryption, Encryption, Public-key cryptography, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Computer Science::Multimedia, Cryptography, business, computer, ElGamal encryption, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR], computer.programming_language, Computer Science::Cryptography and Security
Abstract: International audience; ElGamal public key encryption scheme has been designed in the 80's. It is one of the first partial homomorphic encryption and one of the first IND-CPA probabilistic public key encryption scheme. A linear version has been recently proposed by Boneh et al. In this paper, we present a linear encryption based on a generalized version of ElGamal encryption scheme. We prove that our scheme is IND-CPA secure under linear assumption. We design a generalized ElGamal scheme from the generalized linear. We also run an evaluation of performances of our scheme. We show that the decryption algorithm is slightly faster than the existing versions.
Published: 2020

34. Optimal Threshold Padlock Systems

Author: Jannik Dreier, Jean-Guillaume Dumas, Pascal Lafourcade, Léo Robert, Proof techniques for security protocols (PESTO), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne)
Subjects: FOS: Computer and information sciences, Computer Science - Cryptography and Security, Packings, Computer Networks and Communications, Physical Secret Sharing, 020206 networking & telecommunications, 0102 computer and information sciences, 02 engineering and technology, 16. Peace & justice, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Hardware and Architecture, Block Designs, [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], FOS: Mathematics, 0202 electrical engineering, electronic engineering, information engineering, Mathematics - Combinatorics, Threshold Cryptography, Combinatorics (math.CO), Safety, Risk, Reliability and Quality, Cryptography and Security (cs.CR), Software
Abstract: In 1968, Liu described the problem of securing documents in a shared secret project. In an example, at least six out of eleven participating scientists need to be present to open the lock securing the secret documents. Shamir proposed a mathematical solution to this physical problem in 1979, by designing an efficient $k$-out-of-$n$ secret sharing scheme based on Lagrange's interpolation. Liu and Shamir also claimed that the minimal solution using physical locks is clearly impractical and exponential in the number of participants. In this paper we relax some implicit assumptions in their claim and propose an optimal physical solution to the problem of Liu that uses physical padlocks, but the number of padlocks is not greater than the number of participants. Then, we show that no device can do better for $k$-out-of-$n$ threshold padlock systems as soon as $k\geq{\sqrt{2n}}$, which holds true in particular for Liu's example. More generally, we derive bounds required to implement any threshold system and prove a lower bound of $\mathcal{O}{\log(n)}$ padlocks for any threshold larger than $2$. For instance we propose an optimal scheme reaching that bound for $2$-out-of-$n$ threshold systems and requiring less than $2\log_2(n)$ padlocks. We also discuss more complex access structures, a wrapping technique, and other sublinear realizations like an algorithm to generate $3$-out-of-$n$ systems with $2.5\sqrt{n}$ padlocks. Finally we give an algorithm building $k$-out-of-$n$ threshold padlock systems with only $\mathcal{O}{\log(n)^{k-1}}$ padlocks. Apart from the physical world, our results also show that it is possible to implement secret sharing over small fields.
Published: 2020
Full Text: View/download PDF

35. Computing AES related-key differential characteristics with constraint programming

Author: Christine Solnon, Marine Minier, David Gerault, Pascal Lafourcade, Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Cryptology, arithmetic : algebraic methods for better algorithms (CARAMBA), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Algorithms, Computation, Image and Geometry (LORIA - ALGO), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Geometry Processing and Constrained Optimization (M2DisCo), Laboratoire d'InfoRmatique en Image et Systèmes d'information (LIRIS), Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Université de Lyon-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-École Centrale de Lyon (ECL), Université de Lyon-Université Lumière - Lyon 2 (UL2)-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Université Lumière - Lyon 2 (UL2), This research was conducted with the support of the FEDER program of 2014-2020, the region council of Auvergne-Rhône-Alpes, the GDR-IA, and the ANR (DeCrypt ANR-18-CE39-0007). We thank the reviewers for their comments that helped us improving the paper, Jérémie Detrey for implementing the C code that checks the completeness of the sets xorEq_l, Charles Prud’homme and Jean-Guillaume Fages for their technical support on the use of Choco, and Neng-Fa Zhou for his technical support on the use of Picat., ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), ANR-18-CE39-0007,DeCrypt,Langage Déclaratif pour la cryptographie symétrique(2018), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), Université de Lyon-Université de Lyon-Université Claude Bernard Lyon 1 (UCBL), Université de Lyon-Institut National des Sciences Appliquées de Lyon (INSA Lyon), Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)-Université Lumière - Lyon 2 (UL2)-École Centrale de Lyon (ECL), and Université de Lyon-Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Centre National de la Recherche Scientifique (CNRS)
Subjects: Linguistics and Language, Differential cryptanalysis, Theoretical computer science, Optimization problem, Computer science, 02 engineering and technology, Encryption, Language and Linguistics, law.invention, Constraint Programming, [INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI], [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Artificial Intelligence, law, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, Constraint programming, Block cipher, AES, business.industry, Advanced Encryption Standard, Key (cryptography), 020201 artificial intelligence & image processing, Cryptanalysis, business
Abstract: International audience; Cryptanalysis aims at testing the properties of encryption processes, and this usually implies solving hard optimization problems. In this paper, we focus on related-key differential attacks for the Advanced Encryption Standard (AES), which is the encryption standard for block ciphers. To mount these attacks, cryptanalysts need to solve the optimal related-key differential characteristic problem. Dedicated approaches do not scale well for this problem, and need weeks to solve its hardest instances. In this paper, we improve existing Constraint Programming (CP) approaches for computing optimal related-key differential characteristics: we add new constraints that detect inconsistencies sooner, and we introduce a new decomposition of the problem in two steps. These improvements allow us to compute all optimal related-key differential characteristics for AES-128, AES-192 and AES-256 in a few hours.
Published: 2020
Full Text: View/download PDF

36. Card-Based ZKP Protocols for Takuzu and Juosan

Author: Daiki Miyahara and Léo Robert and Pascal Lafourcade and So Takeshige and Takaaki Mizuki and Kazumasa Shinagawa and Atsuki Nagao and Hideaki Sone, Miyahara, Daiki, Robert, Léo, Lafourcade, Pascal, Takeshige, So, Mizuki, Takaaki, Shinagawa, Kazumasa, Nagao, Atsuki, Sone, Hideaki, Daiki Miyahara and Léo Robert and Pascal Lafourcade and So Takeshige and Takaaki Mizuki and Kazumasa Shinagawa and Atsuki Nagao and Hideaki Sone, Miyahara, Daiki, Robert, Léo, Lafourcade, Pascal, Takeshige, So, Mizuki, Takaaki, Shinagawa, Kazumasa, Nagao, Atsuki, and Sone, Hideaki
Abstract: Takuzu and Juosan are logical Nikoli games in the spirit of Sudoku. In Takuzu, a grid must be filled with 0’s and 1’s under specific constraints. In Juosan, the grid must be filled with vertical and horizontal dashes with specific constraints. We give physical algorithms using cards to realize zero-knowledge proofs for those games. The goal is to allow a player to show that he/she has the solution without revealing it. Previous work on Takuzu showed a protocol with multiple instances needed. We propose two improvements: only one instance needed and a soundness proof. We also propose a similar proof for Juosan game.
Published: 2020
Full Text: View/download PDF

37. Finding Water on Poleless Using Melomaniac Myopic Chameleon Robots

Author: Quentin Bramas and Pascal Lafourcade and Stéphane Devismes, Bramas, Quentin, Lafourcade, Pascal, Devismes, Stéphane, Quentin Bramas and Pascal Lafourcade and Stéphane Devismes, Bramas, Quentin, Lafourcade, Pascal, and Devismes, Stéphane
Abstract: In 2042, the exoplanet exploration program, launched in 2014 by NASA, finally discovers a new exoplanet so-called Poleless, due to the fact that it is not subject to any magnetism. A new generation of autonomous mobile robots, called M2C (for Melomaniac Myopic Chameleon), have been designed to find water on Poleless. To address this problem, we investigate optimal (w.r.t., visibility range and number of used colors) solutions to the infinite grid exploration problem (IGE) by a small team of M2C robots. Our first result shows that minimizing the visibility range and the number of used colors are two orthogonal issues: it is impossible to design a solution to the IGE problem that is optimal w.r.t. both parameters simultaneously. Consequently, we address optimality of these two criteria separately by proposing two algorithms; the former being optimal in terms of visibility range, the latter being optimal in terms of number of used colors. It is worth noticing that these two algorithms use a very small number of robots, respectively six and eight.
Published: 2020
Full Text: View/download PDF

38. Get-your-ID: Decentralized Proof of Identity

Author: Pascal Lafourcade, Marius Lombard-Platet, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Département d'informatique de l'École normale supérieure (DI-ENS), École normale supérieure - Paris (ENS Paris), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Département d'informatique - ENS Paris (DI-ENS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS-PSL), Lafourcade, Pascal, and CAP 20-25 - - CAP 20-252016 - ANR-16-IDEX-0001 - IDEX - VALID
Subjects: Scheme (programming language), Computer science, media_common.quotation_subject, 0211 other engineering and technologies, 02 engineering and technology, Computer security, computer.software_genre, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Voting, 0202 electrical engineering, electronic engineering, information engineering, Identity (object-oriented programming), 020201 artificial intelligence & image processing, computer, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR], 021101 geological & geomatics engineering, computer.programming_language, media_common
Abstract: International audience; In most systems without a centralised authority, users are free to create as many accounts as they please, without any harmful effect on the system. However, in the case of e-voting, for instance, proof of identity is crucial, as sybil identities can be used to breach the intended role of the system. We explore the conditions under which a decentralised proof of identity system can exist. We also propose such a scheme, called Get-your-ID (GYID), and prove its security. Our system allows a user to generate and revoke keys, via an endorsement mechanism, and we prove that under some conditions which we discuss, no user can have more than one active key. We then show how voting protocols can be adapted on top of our system, thus ensuring that no user is able to cast a valid vote more than once.
Published: 2019

39. Secure Multi-Party Matrix Multiplication Based on Strassen-Winograd Algorithm

Author: Pascal Lafourcade, Julio López Fenner, Jean-Guillaume Dumas, Jean-Baptiste Orfila, David Lucas, Clément Pernet, Maxime Puys, Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Universidad de la frontera [Chile], VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Nuttapong Attrapadung and Takeshi Yagi, ANR-15-IDEX-0002,UGA,IDEX UGA(2015), European Project: 676541,H2020,H2020-EINFRA-2015-1,OpenDreamKit(2015), Laboratoire Jean Kuntzmann (LJK), Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP ), Université Grenoble Alpes (UGA), and Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes (UGA)-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )
Subjects: Product matrix, business.industry, Computer science, Computation, Homomorphic encryption, 020206 networking & telecommunications, 02 engineering and technology, Encryption, Matrix multiplication, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Strassen algorithm, 0202 electrical engineering, electronic engineering, information engineering, Secure multi-party computation, 020201 artificial intelligence & image processing, business, Algorithm, Computer Science::Cryptography and Security
Abstract: International audience; This paper presents a secure multiparty computation protocol for the Strassen-Winograd matrix multiplication algorithm. We focus on the setting in which any given player knows only one row (or one block of rows) of both input matrices and learns the corresponding row (or block of rows) of the resulting product matrix. Neither the player initial data, nor the intermediate values, even during the recurrence part of the algorithm, are ever revealed to other players. We use a combination of partial homomorphic encryption schemes and additive masking techniques together with a novel schedule for the location and encryption layout of all intermediate computations to preserve privacy. Compared to state of the art protocols, the asymptotic communication volume of our construction is reduced from O(n^3) to O(n^{2.81}). This improvement in terms of communication volume arises with matrices of dimension as small as n=96 which is confirmed by experiments.
Published: 2019
Full Text: View/download PDF

40. Interactive Physical Zero-Knowledge Proof for Norinori

Author: Jean-Guillaume Dumas, Daiki Miyahara, Takaaki Mizuki, Pascal Lafourcade, Hideaki Sone, Tatsuya Sasaki, Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Tohoku University [Sendai], and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Theoretical computer science, Puzzle, Computer science, Value (computer science), Proof of knowledge, 020206 networking & telecommunications, Card-based secure two-party protocols, 02 engineering and technology, Grid, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Position (vector), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Enhanced Data Rates for GSM Evolution, Zero-knowledge proof, Element (category theory), Zero-knowledge proofs, Norinori
Abstract: International audience; Norinori is a logic game similar to Sudoku. In Norinori, a grid of cells has to be filled with either black or white cells so that the given areas contain exactly two black cells, and every black cell shares an edge with exactly one other black cell. We propose a secure interactive physical algorithm, relying only on cards, to realize a zero-knowledge proof of knowledge for Norinori. It allows a player to show that he or she knows a solution without revealing it. For this, we show in particular that it is possible to physically prove that a particular element is present in a list, without revealing any other value in the list, and without revealing the actual position of that element in the list.
Published: 2019
Full Text: View/download PDF

41. Brief Announcement: Infinite Grid Exploration by Disoriented Robots

Author: Quentin Bramas, Stéphane Devismes, pascal lafourcade, Université de Strasbourg (UNISTRA), Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), and Lafourcade, Pascal
Subjects: [INFO.INFO-RB] Computer Science [cs]/Robotics [cs.RO], [INFO.INFO-RB]Computer Science [cs]/Robotics [cs.RO], [INFO.INFO-MO] Computer Science [cs]/Modeling and Simulation, [INFO.INFO-MO]Computer Science [cs]/Modeling and Simulation
Abstract: International audience; We deal with a set of autonomous robots moving on an infinite grid. Those robots are opaque, have limited visibility capabilities, and run using synchronous Look-Compute-Move cycles. They all agree on a common chirality, but have no global compass. Finally, they may use lights of different colors, but except from that, robots have neither persistent memories, nor communication mean. We consider the infinite grid exploration (IGE) problem. We first show that two robots are not sufficient in our settings to solve the problem, even when robots have a common coordinate system. We then show that if the robots' coordinate systems are not self-consistent, three or four robots are not sufficient to solve the problem neither. Finally, we present three algorithms that solve the IGE problem in various settings. The first algorithm uses six robots with constant colors and a visibility range of one. The second one uses the minimum number of robots, i.e., five, as well as five modifiable colors, still under visibility one. The last algorithm requires seven oblivious anonymous robots, yet assuming visibility two. Notice that the two last algorithms also achieve exclusiveness.
Published: 2019

42. No Such Thing as a Small Leak: Leakage-Abuse Attacks Against Symmetric Searchable Encryption

Author: Alexandre Anzala-Yamajako, Pascal Lafourcade, Matthieu Giraud, Olivier Bernard, THALES COMMUNICATIONS & SECURITY, THALES [France], Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Université Clermont Auvergne (UCA)-Université Clermont Auvergne (UCA), ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), THALES, Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne (UCA)-Institut national polytechnique Clermont Auvergne (INP Clermont Auvergne), Lafourcade, Pascal, and CAP 20-25 - - CAP 20-252016 - ANR-16-IDEX-0001 - IDEX - VALID
Subjects: 0303 health sciences, Leak, Hierarchy (mathematics), Computer science, business.industry, passive attacks, 05 social sciences, leakage, Computer security, computer.software_genre, Encryption, symmetric searchable encryption, Outsourcing, Set (abstract data type), 03 medical and health sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0509 other social sciences, 050904 information & library sciences, business, computer, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR], 030304 developmental biology, Leakage (electronics)
Abstract: Symmetric Searchable Encryption ($\mathrm {SSE}$) schemes enable clients to securely outsource their data while maintaining the ability to perform keywords search over it. The security of these schemes is based on an explicit leakage profile [1], has initiated the investigation into how much information could be deduced in practice from this leakage. In this paper, after recalling the leakage hierarchy introduced in 2015 by Cash et al. and the passive attacks of [1] on $\mathrm {SSE}$ schemes. We demonstrate the effectiveness of these attacks on a wider set of real-world datasets than previously shown. On the other hand, we show that the attacks are inefficient against some types of datasets. Finally, we used what we learned from the unsuccessful datasets to give insight into future countermeasures.
Published: 2019

43. LocalPKI: An Interoperable and IoT Friendly PKI

Author: Jean-Baptiste Orfila, Pascal Thoniel, Jean-Guillaume Dumas, Pascal Lafourcade, Francis Melemedjian, Calcul Algébrique et Symbolique, Sécurité, Systèmes Complexes, Codes et Cryptologie (CASC), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), and NTX Research SA (NTX Research SA)
Subjects: education.field_of_study, business.industry, Computer science, End user, Population, 020206 networking & telecommunications, Public key infrastructure, Context (language use), 02 engineering and technology, Cryptographic protocol, Computer security, computer.software_genre, Public-key cryptography, Registration authority, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Certificate authority, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, business, education, computer
Abstract: International audience; A public-key infrastructure (PKI) binds public keys to identities of entities. Usually, this binding is established through a process of registration and issuance of certificates by a certificate authority (CA) where the validation of the registration is performed by a registration authority. In this paper, we propose an alternative scheme, called LOCALPKI, where the binding is performed by a local authority and the issuance is left to the end user or to the local authority. The role of a third entity is then to register this binding and to provide up-to-date status information on this registration. The idea is that many more local actors could then take the role of a local authority, thus allowing for an easier spread of public-key certificates in the population. Moreover, LOCALPKI represents also an appropriate solution to be deployed in the Internet of Things context. Our scheme's security is formally proven with the help of Tamarin, an automatic verification tool for cryptographic protocols.
Published: 2019
Full Text: View/download PDF

44. DABSTERS: Distributed Authorities using Blind Signature to Effect Robust Security in e-Voting

Author: Pascal Lafourcade, Souheib Yousfi, Riadh Robbana, Marwa Chaieb, Mirko Koscina, Lafourcade, Pascal, Faculté des Sciences Mathématiques, Physiques et Naturelles de Tunis (FST), Université de Tunis El Manar (UTM), Département d'informatique - ENS Paris (DI-ENS), École normale supérieure - Paris (ENS-PSL), Université Paris sciences et lettres (PSL)-Université Paris sciences et lettres (PSL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS), Laboratoire d'Informatique, de Parallélisme et de Productique (LIP2), Université de Tunis El Manar (UTM)-Université de Tunis El Manar (UTM), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), École normale supérieure - Paris (ENS Paris), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Département d'informatique de l'École normale supérieure (DI-ENS), and Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Receipt, Emerging technologies, Electronic voting, Computer science, media_common.quotation_subject, ComputingMilieux_LEGALASPECTSOFCOMPUTING, Computer security, computer.software_genre, Fully-Decentralized, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], E-voting, Voting, Secrecy, Permissioned Blockchain, Blind signature, Blind Signature, computer, Protocol (object-oriented programming), Byzantine fault tolerance, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR], media_common
Abstract: International audience; Creating an online electronic voting system that meets all legal requirements of election organizers and voters has constituted a real challenge for a long period of time. Permissioned Blockchains (also called Private Blockchains) are a cutting-edge invention, introduced as a security breakthrough for many existing and emerging technologies. One potential application of private Blockchain concerns e-voting systems. We propose a fully-decentralized e-voting system based on permissioned Blockchain, called DABSTERS in e-voting. Our system uses a blinded signature consensus algorithm, which is a modified version of Practical Byzantine Fault Tolerance (PBFT), to preserve voter's privacy. Our protocol ensures several security properties: voter's eligibility , vote integrity, vote secrecy, fairness, receipt freeness, individual and universal verifiability.
Published: 2019
Full Text: View/download PDF

45. Secure Trick-Taking Game Protocols How to Play Online Spades with Cheaters

Author: Pascal Lafourcade, Xavier Bultel, Lafourcade, Pascal, Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique Bretagne-Pays de la Loire (IMT Atlantique), Institut Mines-Télécom [Paris] (IMT)-Institut Mines-Télécom [Paris] (IMT), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-IMT Atlantique (IMT Atlantique), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Scheme (programming language), 050101 languages & linguistics, Computer science, 05 social sciences, ComputingMilieux_PERSONALCOMPUTING, 02 engineering and technology, Computer security model, Computer security, computer.software_genre, Bridge (interpersonal), Random oracle, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, 0501 psychology and cognitive sciences, computer, computer.programming_language, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: International audience; Trick-Taking Games (TTGs) are card games in which each player plays one of his cards in turn according to a given rule. The player with the highest card then wins the trick, i.e., he gets all the cards that have been played during the round. For instance, Spades is a famous TTG proposed by online casinos, where each player must play a card that follows the leading suit when it is possible. Otherwise, he can play any of his cards. In such a game, a dishonest user can play a wrong card even if he has cards of the leading suit. Since his other cards are hidden, there is no way to detect the cheat. Hence, the other players realize the problem later, i.e., when the cheater plays a card that he is not supposed to have. In this case, the game is biased and is canceled. Our goal is to design protocols that prevent such a cheat for TTGs. We give a security model for secure Spades protocols, and we design a scheme called SecureSpades. This scheme is secure under the Decisional Diffie-Hellman assumption in the random oracle model. Our model and our scheme can be extended to several other TTGs, such as Belotte, Whist, Bridge, etc.
Published: 2019

46. Physical Zero-Knowledge Proof for Makaro

Author: Kazumasa Shinagawa, Tatsuya Sasaki, Jannik Dreier, Hideaki Sone, Takaaki Mizuki, Xavier Bultel, Jean-Guillaume Dumas, Pascal Lafourcade, Atsuki Nagao, Daiki Miyahara, Laboratoire d'Informatique, de Modélisation et d'optimisation des Systèmes (LIMOS), Université Blaise Pascal - Clermont-Ferrand 2 (UBP)-Université d'Auvergne - Clermont-Ferrand I (UdA)-SIGMA Clermont (SIGMA Clermont)-Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Centre National de la Recherche Scientifique (CNRS), Proof techniques for security protocols (PESTO), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), Calculs Algébriques et Systèmes Dynamiques (CASYS), Laboratoire Jean Kuntzmann (LJK ), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019])-Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), VERIMAG (VERIMAG - IMAG), Institut polytechnique de Grenoble - Grenoble Institute of Technology (Grenoble INP )-Centre National de la Recherche Scientifique (CNRS)-Université Grenoble Alpes [2016-2019] (UGA [2016-2019]), Tohoku University [Sendai], National Institute of Advanced Industrial Science and Technology (AIST), Ochanomizu University, Tokyo Institute of Technology [Tokyo] (TITECH), ANR-16-IDEX-0001,CAP 20-25,CAP 20-25(2016), and SIGMA Clermont (SIGMA Clermont)-Université d'Auvergne - Clermont-Ferrand I (UdA)-Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Blaise Pascal - Clermont-Ferrand 2 (UBP)
Subjects: Discrete mathematics, Puzzle, Computer science, Proof of knowledge, Card-based secure two-party protocols, 0102 computer and information sciences, 02 engineering and technology, Grid, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], 010201 computation theory & mathematics, Privacy, Makaro, 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Zero-knowledge proof, Zero-knowledge proofs
Abstract: International audience; Makaro is a logic game similar to Sudoku. In Makaro, a grid has to be filled with numbers such that: given areas contain all the numbers up to the number of cells in the area, no adjacent numbers are equal and some cells provide restrictions on the largest adjacent number. We propose a proven secure physical algorithm, only relying on cards, to realize a zero-knowledge proof of knowledge for Makaro. It allows a player to show that he knows a solution without revealing it.
Published: 2018
Full Text: View/download PDF

47. Secure Grouping and Aggregation with MapReduce

Author: Pascal Lafourcade, Matthieu Giraud, Radu Ciucanu, Lihua Ye, Université Blaise Pascal - Clermont-Ferrand 2 (UBP), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Lafourcade, Pascal, and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Focus (computing), business.industry, Computer science, Process (engineering), Big data, Data_MISCELLANEOUS, Database Queries, Cloud computing, Aggregation, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Cloud provider, Grouping, Programming paradigm, Key (cryptography), Security, MapReduce, business, Computer network, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR]
Abstract: International audience; MapReduce programming paradigm allows to process big data sets in parallel on a large cluster. We focus on a scenario where the data owner outsources her data on an honest-but-curious server. Our aim is to evaluate grouping and aggregation with SUM, COUNT, AVG, MIN, and MAX operations for an authorized user. For each of these five operations, we assume that the public cloud provider and the user do not collude i.e., the public cloud does not know the secret key of the user. We prove the security of our approach for each operation.
Published: 2018

48. Security analysis and psychological study of authentication methods with PIN codes

Author: Vincent Marlin, Marie Izaute, Pascal Lafourcade, Matthieu Giraud, Ladislav Mota, Timothee Kheyrkhah, Jannik Dreier, Xavier Bultel, Dounia Lakhzoum, Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Centre National de la Recherche Scientifique (CNRS)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Proof techniques for security protocols (PESTO), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Laboratoire de Psychologie Sociale et Cognitive (LAPSCO), Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Centre de Recherche en Psychologie de la Connaissance, du Langage et de l'Émotion (PsyCLÉ), Aix Marseille Université (AMU), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Password, Authentication, 021110 strategic, defence & security studies, Security analysis, Computer science, Pin code, 0211 other engineering and technologies, [SHS.PSY]Humanities and Social Sciences/Psychology, 020206 networking & telecommunications, 02 engineering and technology, Login, Computer security, computer.software_genre, Identifier, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Attack model, Brute-force attack, Security, 0202 electrical engineering, electronic engineering, information engineering, Code (cryptography), [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], computer
Abstract: International audience; Touch screens have become ubiquitous in the past few years, like for instance in smartphones and tablets. These devices are often the entry door to numerous information systems, hence having a secure and practical authentication mechanism is crucial. In this paper, we examine the complexity of different authentication methods specifically designed for such devices. We study the widely spread technology to authenticate a user using a Personal Identifier Number code (PIN code). Entering the code is a critical moment where there are several possibilities for an attacker to discover the secret. We consider the three attack models: a Bruteforce Attack (BA) model , a Smudge Attack (SA) model, and an Observation Attack (OA) model where the attacker sees the user logging in on his device. The aim of the intruder is to learn the secret code. Our goal is to propose alternative methods to enter a PIN code. We compare such different methods in terms of security. Some methods require more intentional resources than other, this is why we performed a psychological study on the different methods to evaluate the users' perception of the different methods and their usage.
Published: 2018
Full Text: View/download PDF

49. Secure Joins with MapReduce

Author: Xavier Bultel, Matthieu Giraud, Lihua Ye, Pascal Lafourcade, Radu Ciucanu, Ciucanu, Radu, EMbedded SEcurity and Cryptography (EMSEC), SYSTÈMES LARGE ÉCHELLE (IRISA-D1), Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Université de Rennes 1 (UR1), Université de Rennes (UNIV-RENNES)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes 1 (UR1), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Université de Rennes (UNIV-RENNES)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA), Laboratoire d'Informatique Fondamentale d'Orléans (LIFO), Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA), Sécurité des Données et des Systèmes (SDS), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université d'Orléans (UO)-Institut National des Sciences Appliquées - Centre Val de Loire (INSA CVL), Laboratoire d'Informatique, de Modélisation et d'Optimisation des Systèmes (LIMOS), Ecole Nationale Supérieure des Mines de St Etienne-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS), Université Clermont Auvergne [2017-2020] (UCA [2017-2020]), Harbin Institute of Technology (HIT), Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Université de Rennes (UR)-Institut National des Sciences Appliquées - Rennes (INSA Rennes), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS)-Institut de Recherche en Informatique et Systèmes Aléatoires (IRISA), Institut National des Sciences Appliquées (INSA)-Institut National des Sciences Appliquées (INSA)-Université de Bretagne Sud (UBS)-École normale supérieure - Rennes (ENS Rennes)-Institut National de Recherche en Informatique et en Automatique (Inria)-Télécom Bretagne-CentraleSupélec-Centre National de la Recherche Scientifique (CNRS), and Ecole Nationale Supérieure des Mines de St Etienne (ENSM ST-ETIENNE)-Université Clermont Auvergne [2017-2020] (UCA [2017-2020])-Centre National de la Recherche Scientifique (CNRS)
Subjects: Computer science, Big data, Data_MISCELLANEOUS, Joins, Cloud computing, 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR], Natural Joins, 020204 information systems, 0202 electrical engineering, electronic engineering, information engineering, [INFO.INFO-DB] Computer Science [cs]/Databases [cs.DB], MapReduce, [INFO.INFO-CR] Computer Science [cs]/Cryptography and Security [cs.CR], [INFO.INFO-DB]Computer Science [cs]/Databases [cs.DB], business.industry, 010201 computation theory & mathematics, Programming paradigm, Key (cryptography), Security, Join (sigma algebra), Standard algorithms, Hypercube, Database Query, business, Computer network
Abstract: International audience; MapReduce is one of the most popular programming paradigms that allows a user to process Big data sets. Our goal is to add privacy guarantees to the two standard algorithms of join computation for MapReduce: the cascade algorithm and the hypercube algorithm. We assume that the data is externalized in an honest-but-curious server and a user is allowed to query the join result. We design, implement, and prove the security of two approaches: (i) Secure-Private, assuming that the public cloud and the user do not collude, (ii) Collision-Resistant-Secure-Private, which resists to collusions between the public cloud and the user i.e., when the public cloud knows the secret key of the user.
Published: 2018

50. Unlinkable and Strongly Accountable Sanitizable Signatures from Verifiable Ring Signatures

Author: Xavier Bultel and Pascal Lafourcade
Subjects: Discrete mathematics, Computer science, Group (mathematics), 0102 computer and information sciences, 02 engineering and technology, Computer security model, 01 natural sciences, Random oracle, Ring signature, 010201 computation theory & mathematics, Scheme (mathematics), 0202 electrical engineering, electronic engineering, information engineering, 020201 artificial intelligence & image processing, Verifiable secret sharing, Signature (topology), Computer Science::Databases, Computer Science::Cryptography and Security, Sign (mathematics)
Abstract: An Unlinkable Sanitizable Signature scheme (USS) allows a sanitizer to modify some parts of a signed message in such away that nobody can link the modified signature to the original one. A Verifiable Ring Signature scheme (VRS) allows the users to sign messages anonymously within a group where a user can prove a posteriori to a verifier that it is the author of a given signature. In this paper, we first revisit the notion of VRS: we improve the proof capabilities of the users, we give a complete security model for VRS and we give an efficient and secure scheme called $\mathrm {EVeR}$. Our main contribution is $\mathrm {GUSS}$, a Generic USS based on a VRS scheme and an unforgeable signature scheme. We show that $\mathrm {GUSS}$ instantiated with $\mathrm {EVeR}$ and Schnorr’s signature is twice as efficient as the best USS scheme of the literature. Moreover, we propose a stronger definition of accountability: an USS is accountable when the signer can prove whether a signature is sanitized. We formally define the notion of strong accountability where the sanitizer can also prove the origin of a signature. We show that the notion of strong accountability is important in practice. Finally, we prove the security properties of $\mathrm {GUSS}$ (including strong accountability) and $\mathrm {EVeR}$ under the Decisional Diffie-Hellman (DDH) assumption in the random oracle model.
Published: 2018
Full Text: View/download PDF

Catalog

Books, media, physical & digital resources

See catalog results

Searchworks

Select search scope, currently: Articles Catalog books, media & more in Jio Institute collections Articles journal articles & other e-resources

Search

Search Constraints

Refine your results

Search Limiters

Topic

Publication Year Range

Language

Publication Type

Journal

Database

Publisher

148 results on '"Pascal Lafourcade"'

Search Results

Catalog

Select search scope, currently: Articles

Catalog

books, media & more in Jio Institute collections

Articles

journal articles & other e-resources