Pseudorandom sequences have many applications in fields such as wireless communication, cryptography and built-in self test of integrated circuits. Maximal length sequences (m-sequences) are commonly employed pseudorandom sequences because they have ideal randomness properties like balance, run and autocorrelation. However, the linear complexity of m-sequences is poor. This thesis considers the use of one-dimensional Cellular Automata (CA) to generate pseudorandom sequences that have high linear complexity and good randomness. The properties of these sequences are compared with those of the corresponding m-sequences to determine their suitability. / Graduate

Les cryptosystèmes sont présents dans de nombreux appareils utilisés dans la vie courante, tels que les cartes à puces, ordiphones, ou passeports. La sécurité de ces appareils est menacée par les attaques par canaux auxiliaires, où un attaquant observe leur comportement physique pour obtenir de l’information sur les secrets manipulés. L’évaluation de la résilience de ces produits contre de telles attaques est obligatoire afin de s’assurer la robustesse de la cryptographie embarquée. Dans cette thèse, nous exhibons une méthodologie pour évaluer efficacement le taux de succès d’attaques par canaux auxiliaires, sans avoirbesoin de les réaliser en pratique. En particulier, nous étendons les résultats obtenus par Rivain en 2009, et nous exhibons des formules permettant de calculer précisément le taux de succès d’attaques d’ordre supérieur. Cette approche permet une estimation rapide de la probabilité de succès de telles attaques. Puis, nous étudions pour la première fois depuis le papier séminal de Ishai, Sahai et Wagner en 2003 le problème de la quantité d’aléa nécessaire dans la réalisation sécurisée d’une multiplication de deux bits. Nous fournissons des constructions explicites pour des ordres pratiques de masquage, et prouvons leur sécurité et optimalité. Finalement, nous proposons un protocole permettant le calcul sécurisé d’un veto parmi un nombre de joueurs arbitrairement grand, tout en maintenant un nombre constant de bits aléatoires. Notre construction permet également la multiplication sécurisée de n’importe quel nombre d’éléments d’un corps fini. / Cryptosystems are present in a lot of everyday life devices, such as smart cards, smartphones, set-topboxes or passports. The security of these devices is threatened by side-channel attacks, where an attacker observes their physical behavior to learn information about the manipulated secrets. The evaluation of the resilience of products against such attacks is mandatory to ensure the robustness of the embedded cryptography. In this thesis, we exhibit a methodology to efficiently evaluate the success rate of side-channel attacks, without the need to actually perform them. In particular, we build upon a paper written by Rivainin 2009, and exhibit explicit formulaes allowing to accurately compute the success rate of high-order side-channel attacks. We compare this theoretical approach against practical experiments. This approach allows for a quick assessment of the probability of success of any attack based on an additive distinguisher. We then tackle the issue of countermeasures against side- channel attacks. To the best of our knowledge, we study for the first time since the seminal paper of Ishai, Sahai and Wagner in 2003 the issue of the amount of randomness in those countermeasures. We improve the state of the art constructions and show several constructions and bounds on the number of random bits needed to securely perform the multiplication of two bits. We provide specific constructions for practical orders of masking, and prove their security and optimality. Finally, we propose a protocolallowing for the private computation of a secure veto among an arbitrary large number of players, while using a constant number of random bits. Our construction also allows for the secure multiplication of any number of elements of a finite field.

京都大学 / 新制・課程博士 / 博士(人間・環境学) / 甲第23273号 / 人博第988号 / 新制||人||234(附属図書館) / 2020||人博||988(吉田南総合図書館) / 京都大学大学院人間・環境学研究科共生人間学専攻 / (主査)教授 角 大輝, 教授 上木 直昌, 准教授 木坂 正史 / 学位規則第4条第1項該当 / Doctor of Human and Environmental Studies / Kyoto University / DFAM

Error-corecting codes are used during most of data transmissions these days. To save space, we would like to use codes which are able to correct enough errors without extending the message too much. The expander codes look promising - they are asymptotically optimal, however, in practice they are just too long. Better expander constructions could be achieved via randomness con- ductors. In this thesis, we explain what conductors are and which constructions are possible for them. In the end we will convert them to expanders and almost get expander codes which are short enough for practical use but nevertheless good. 1

This thesis deals with the multi-stage stochastic programming problems. In the first part, there are introduced two-stage and multi-stage stochastic programming problems. Next, two methods how to generate scenarios are described in detail - the moment method and paths-based methods. The second chapter describes the flower-girl problem, its various formulations and other extensions using ro- bustness and endogenous randomness. The practical part follows, where several different formulations of the flower-girl problem are solved. First, the problem when the florist sells roses with an unlimited life for one week is solved. Then this problem is reformulated as a two-stage problem and the results are compared. Then a formulation with a limited rose life of 2 days is presented. The greatest attention is paid to the problem with a limited rose life of 4 days - the basic formulation of the problem and several extended formulations are solved. 1

Elements of randomness are a common factor inmodern digital games, from simple rolls of a die tocomplex AI systems. These elements have an impacton how the player experiences a game. We believe thatexploring the field of luck analysis can benefit designersthrough an developed understanding of how such elementsaffect players. The developers of the digital card gameSlay the Spire has released 77 millions of instances ofplay and sample of these are explored in this study. Withthe use of data mining, data clustering and correlationanalysis the effect of elements of randomness present inSlay the Spire are analyzed. In conclusion, three playerskill groups were identified with the use of clustering:Winners, Low skill losers and High skill losers. Weobserved that people who succeeded in beating the game,had an increased amount of randomness in the formof cards by a factor of 1.82. Showing that more skilledplayers do not shy away from randomness but insteadembrace it more than lower skilled players.

A k × n array with entries from an "alphabet" A = { 0, 1, ..., q - 1 } of size q is said to form a t-covering array (resp. orthogonal array) if each t × n submatrix of the array contains, among its columns, at least one (resp. exactly one) occurrence of each t-letter word from A (we must thus have n = qt for an orthogonal array to exist and n ≥ qt for a t -covering array). In this paper, we continue the agenda laid down in Godbole et al. (2009) in which the notion of consecutive covering arrays was defined and motivated; a detailed study of these arrays for the special case q = 2, has also carried out by the same authors. In the present article we use first a Markov chain embedding method to exhibit, for general values of q, the probability distribution function of the random variable W = Wk, n, t defined as the number of sets of t consecutive rows for which the submatrix in question is missing at least one word. We then use the Chen-Stein method (Arratia et al., 1989, 1990) to provide upper bounds on the total variation error incurred while approximating L (W) by a Poisson distribution Po (λ) with the same mean as W. Last but not least, the Poisson approximation is used as the basis of a new statistical test to detect run-based discrepancies in an array of q-ary data.

Security and privacy are of paramount importance in the modern information age. Secure multi-party computation and private information retrieval are canonical and representative problems in cryptography that capture the key challenges in understanding the fundamentals of security and privacy. In this dissertation, we use information theoretic tools to tackle these two classical cryptographic primitives. In the first part, we consider the secure multi-party computation problem, where multiple users, each holding an independent message, wish to compute a function on the messages without revealing any additional information. We present an efficient protocol in terms of randomness cost to securely compute a vector linear function. In the second part, we discuss the symmetric private information retrieval problem, where a user wishes to retrieve one message from a number of replicated databases while keeping the desired message index a secret from each individual database. Further, the user learns nothing about the other messages. We present an optimal protocol that achieves the minimum upload cost for symmetric private information retrieval, i.e., the queries sent from the user to the databases have the minimum number of bits.

京都大学 / 0048 / 新制・課程博士 / 博士(人間・環境学) / 甲第17837号 / 人博第658号 / 新制||人||158(附属図書館) / 25||人博||658(吉田南総合図書館) / 30652 / 京都大学大学院人間・環境学研究科共生人間学専攻 / (主査)教授 上木 直昌, 教授 森本 芳則, 教授 髙﨑 金久 / 学位規則第4条第1項該当 / Doctor of Human and Environmental Studies / Kyoto University / DFAM

京都大学 / 0048 / 新制・課程博士 / 博士(理学) / 甲第20886号 / 理博第4338号 / 新制||理||1623(附属図書館) / 京都大学大学院理学研究科数学・数理解析専攻 / (主査)教授 長谷川 真人, 教授 向井 茂, 准教授 照井 一成 / 学位規則第4条第1項該当 / Doctor of Science / Kyoto University / DFAM