Archive of Gee Law’s Blog
“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出，Wee 在 2017 年改进，Agrawal、Libert、Monosij、Titiu 在 2020 年完善的内积加密算法。本篇是前半部分的最后一篇，叙述 ALS 公钥内积加密方案并证明它的 SIM-CPA 安全性。它的构造思想既可以理解为光滑投影哈希（也叫“哈希证明系统”）加换元法，也可以理解为双系统加密。
“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出，Wee 在 2017 年改进，Agrawal、Libert、Monosij、Titiu 在 2020 年完善的内积加密算法。在这一篇里我们讨论公钥 IPFE 的语法、语义、安全性，为此我们需要引入计算意义下的不可区分性，并练习多项式时间归约和过渡证明法。
Microsoft Edge (Chromium) can pin websites to Taskbar in an undocumented way. I did some observation fun and this entry tells you how to programmatically pin/unpin Shortcuts to/from Taskbar (as of 1909). You should not abuse this knowledge.
Since Edge (Chromium) has its first stable release available, I decided to give it a try, and I am particularly interested in how it behaves under High Contrast mode and what its Live Tiles look like. Aside from being unsatisfied by the current implementation of the two, I got into much larger trouble by installing the stable version of Edge (Chromium), especially via MSI!
最近有网友发现自己的 Windows 锁屏壁纸被修改成了百度云管家的广告。（一开始大家觉得是百度云管家乱搞，后来发现实际上是联想的 OEM 软件乱搞。）无论怎样，这说明一些软件用正常方式运行总让人不够放心，采取措施隔离一些 app 很有必要。一些网友提出可以给 app 准备一个专门的虚拟机，不过这有点大炮打蚊子了，其实可以用 Windows 的多用户和“以其他用户身份运行”解决。这个方法适用于很多 Windows 桌面 app。
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for homework 3, homework 4 and lecture note 5.
I was on eduroam (or any WPA2-Enterprise Wi-Fi network). I wanted to install UW CSE printers (or access any other domain resources). I got ‘Logon failure: the user has not been granted the requested logon type at this computer.’ Here’s why it happens and how to avoid it.
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for homework 2.
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 4, Coppersmith, cryptanalysis.
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for homework 1.
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 3, LLL, Coppersmith.
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 2, SVP, Gram–Schmidt, LLL.
Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 1, mathematical background.
Finally, this happened to me… I ran something close to ‘rm -rf ~’ by accident, and pressed Ctrl+C as soon as I realised something wrong was going on. This blog entry is about how I recovered from this mistake.
本系列旨在忠实提供 1980 版的《悲惨世界》概念版音乐剧的歌词。第十七篇记录了 La nuit de l'angoisse 和 Valjean à la barricade 的歌词。此外，我还发现 ina.fr 有一段 Valjean chez les Thénardier 和 La valse de la fourberie 的录像（可免费观看），以及一个付费视频可能包含更多现场录像。
You might expect PowerShell ConvertTo-Json cmdlet produce a JSON representation of a ‘POD’ that can be parsed (in particular, by ConvertFrom-Json cmdlet) into a POD object that equals to the previously serialised one. However, this is not true for many cases, the most surprising among which are double-precision numbers.
WeChat has this function to distribute red envelopes of random amount of money. The natural question to ask is how to sample the amount of money each person who opens the envelope should receive.
Two (equivalent) definitions of computational indistinguishability, two (isomorphic) ways of doing hybrids
It wasn’t until recently did I realise there are two isomorphic ways (different styles) of writing hybrid proofs. They actually correspond to the two equivalent definitions of computational indistinguishability — one based on guessing and the other based on distinguishing. Actually, I’ve been writing both kinds of proofs subconciously.
I learnt how to write uniform hybrid reductions in my rudimentary cryptography course, which are beasty beauties that wrap an adversary, trying break each of the many underlying cryptographic assumptions simultaneously. However, those constructions are less easy to write and read than using the transitivity of computational indistinguishability up to polynomially many times. The latter involves writing out the (perhaps polynomially many) hybrids and arguing that adjacent hybrids are indistinguishable. I also learnt non-uniform reductions, noticeably the technique to only work with deterministic adversaries. I’m writing a proof using hybrid argument lately, and I asked my advisor about whether I should write the beast or just the hybrids…
There are two asymptotically equivalent definitions of IND-CPA for secret-key encryption schemes. I think the one-challenge one makes the proof neater.
Kowalczyk 和 Wee 在 EUROCRYPT 2019（欧密会）上发表的文章 Compact Adaptively Secure ABE for NC¹ from 𝑘-Lin 可以说是彻底解决了 NC¹ 访问策略的属性加密问题。我在最近的密码学读书会上将讲述该文，这篇博文算是我用母语对该文章的总结（感觉我脑内思考语言仍然是汉语），也算是在中文密码学社区里传播知识。
It is not the cmdlet that truncated the string. It’s the formatting. By the way, you can change the default if you want, and it’s all documented.
When you paste a URL of a YouTube video into OneNote, the cover image and the title are fetched by OneNote, the text of the link becomes the title, and an online video object (with the cover image) is inserted following the link. How can you disable this feature?
Ever since I used Windows NT (for me, the first Windows NT I used is Windows XP), I’ve been familiar with the importance of Ctrl+Alt+Delete. The combination is known as the secure attention sequence for Windows. In an uninfected copy of Windows, the sequence is handled exclusively by Windows, and is used to thwart trojan dialogs luring users’ credentials. Requiring SAS before Welcome Screen is a quite usable security feature. However, it is not the case for Credential User Interface.
PowerShell 在众 shell 中最突出的特色就是面向对象；然而，世界上还有很多命名是专为字节流管道设计的（兼容性大坑）。PowerShell 对待字节流管道那是十分 nasty！我写的这个小工具可以在对象和字节流之间做完美的润滑。更新：Aloxaf 实现了 Linux 版本的 Use-RawPipeline，起名 Use-PosixPipeline。
Nyuwa, the mother goddess of Chinese mythology, mends the sky according to an ancient Chinese legend. Today, Nyuwa is asked to mend the epigraph of a continuous function over an open set so that the function becomes convex. What can we say about this?
It is widely spoken that the Equation Editor of Word (OneNote / Office) is inferior and harder to use than LaTeX. While this is true for a hardcore user, a lot of people spreading the word aren’t really understanding the thing and are just parroting others. I suspect that for a lot of them, the ability to efficiently typeset beautiful mathematical formulae is limited by knowledge and carefulness. People don’t seem to care enough to learn and correctly employ the tools at hand.
Having received my MacBook Pro 13-inch, I started to alternate between my Surface Book and MacBook, to get used to macOS and keep everything synchronised. Today when I was transcribing my notes to OneNote, I noticed a rendering problem on the screen. Propaganda (from Apple fanboys) has it that macOS supports high DPI displays well (of course including its very own screen), it turns out the story isn’t as true as the propaganda claims. Later, it was revealed that the reason is font smoothing is on (by default for me), and turning it off resolves the problem.
Update: I misunderstood how the app was sideloaded. See my further investigation and I apologise for the wrong blames. Hands down! The usage is legitimate and a perfect example of installation on demand (advertisement). Embarrassingly bad is for myself.
I had a maths-related nightmare that (initially) was concerned about counting solutions of a linear equation modulo M with integral coefficients. Though the whole detail of the dream cannot be written down due to privacy reasons, at least I can write a simple introduction on solving this specific problem here. Update: An error in the original solution has been corrected. Another update the same day: The original solution is correct.
A commit to Ant Design, an enterprise-oriented open-source Web UI library by Ant Financial (蚂蚁金服), on 10 September 2018 buried an Easter egg for Christmas, which has caused a heck of havoc since Christmas. This entry also talks about not-so-obvious features in my blog.
As a perfectionist, I have been struggling to have a perfect PIM (personal information management) solution. For the personal part, I currently use (Exchange-based) Outlook.com. For the professional (institutional) part, things have been so hard. This entry records some of the problems I have encountered so far, and for certain ones, a solution. Expect this entry to be a mess and full of complaints.
Sharing data among apps is a common task in modern operating system. Both iOS and Windows Runtime provides central means of transmitting data from one app to another beyond the clipboard. In this entry, I will look at the sharing functionalities in both systems.
Group presentation is a method to express groups as a quotient of a free group and a normal subgroup. In a presentation, there are generators and relators, and the presentation yields a ‘minimalist implementation’ of these generators and relations. Some cases of special interests are finitely generated/related/presented groups. From the definition, finite generation + finite relation is not linguistically equivalent to finite presentation. There has been some discussion on the relation of the three properties for several other algebraic structures. This entry proves that finite generation + finite relation implies finite presentation for groups.
What goes wrong when arrows are reversed in the diagrams for direct product/sum universal properties?
I’m taking an algebra course and regaining my algebra sense (non-sense?). Familiar to us is that direct products [resp. sums] of groups [resp. abelian groups] possess their versions of universal properties. When reviewing these things, I went curious on what would go wrong if the arrows were reversed. Let’s try and see.
PowerShell 6.1.0 (preview) messes verbs of directories, causing Previous Versions to open previous verions of a directory in PowerShell
Issue #6799 in PowerShell repository on GitHub raises the question why Previous Versions is opening previous versions of a directory in PowerShell, instead of File Explorer as expected. The reason is that PowerShell 6.1.0 (preview) installer creates a context menu to open the shell on any folder. However, it unfortunately names the verbs as open/runas, which is very dangerous since they are canonical and do not make much sense for a folder. Related is issue #7815, where shortcuts to a folder are opened in PowerShell.
Outlook 2016 GUI creates an appointment with extraneous attendee, causing Outlook.com and Outlook for iOS to show it as a meeting
Outlook 2016 GUI always creates an event with at least one attendee, which makes Outlook.com and Outlook for iOS have difficulty correctly interpreting the appointment. Instead, they think it is a meeting. However, if you create the event with Outlook object model, there is a good chance the event is created neatly. In addition, events created on Outlook.com or in Outlook for iOS are always neat.
Continuing ‘Hosting a preview handler in WPF, part 1: UI and file associations’, we will do the major COM interop in this entry. Many people have failed to host the handler correctly because of careless implementation, so look carefully! Also, we will demonstrate some broken preview handlers, including ‘Adobe PDF Preview Handler for Vista’, ‘Microsoft Word previewer’ and ‘Microsoft PowerPoint previewer’.
As a fanboy of Raymond Chen, I’m always intrigued by Windows Shell. After his three interesting examples of Reading a Contract From the Other Side, I decided to write one myself. Our victim is Preview Handlers and Shell Preview Host. Today’s entry will prepare UI and file association information retrieval for our little program.
我之前在知乎问题“为什么很多人要禁止 Windows 10 自动更新”下多个回答的评论区宣传 ShutdownBlockReasonCreate 这个 API，尝试“教育”开发者正确处（阻）理（止）Windows 10 自动更新重启带来的关键任务被终止的问题，还因为这个被人挂了。一开始我抱着怀疑的态度提出的方法，之后不知什么原因就假设这个 API 确实有效了——我当时已经知道该 API 不能其效果的情况，但是我没料到“大更新”的时候 Windows 真的会用那么暴力的方法重启电脑。本文记录了一些我的观察，并从使用者的角度给出一些关于 Windows 10 自动更新处理上的建议。
Opening online-only shortcuts (.lnk files) with empty initial working directory ends up inheriting the current directory of the parent process, disregarding the specified working directory
A curious problem I encountered when using Windows PowerShell to backup my Outlook signatures.
Have you ever tried using UseNewEnvironment switch when invoking Start-Process cmdlet? Intuitively, turning it on makes the newly created process use the default environment instead of that of the parent process. However, its semantics is way more complicated, obscure and buggy than the intuition. TL; DR: You rarely want to use this switch.
Someone wanted to know how to create a file that denies itself from being removed, yet found he could still remove the file even denying DELETE access from Everyone. The reason is that there is DELETE_CHILD access on its containing directory. How does this relate to ‘the directory is not empty’?
Clear-RecycleBin is a cmdlet that clears your recycle bin. Internally, it calls SHEmptyRecycleBin function. It has been malfunctioning for a long time: when you run the cmdlet for the first time in a PowerShell session with Force switch on, it produces an ErrorRecord. Further investigation shows that it is detecting error status of SHEmptyRecycleBin the wrong way. To make things worse, SHEmptyRecycleBin is really bad at error handling.
Having accepted an offer to a Doctor of Philosophy program, I have finished my final admission to a higher degree (‘升学’) as doctorate is the highest possible degree. It’s time to review my road to knowledge and thank those who have helped and shaped me.
a.k.a. How to be disappointed again by UA. I was visiting New York University and Carnegie Mellon University. Flying from Beijing to New York, from New York to Pittsburgh, from Pittsburgh to Beijing via Chicago, I chose United Airlines, one that suffers from previous scandals on ‘violently reaccomodating a customer’. It turns out that their in-flight entertainment system is also torturing! This entry was written during the flight from Chicago to Beijing.
I have heard about λ-calculus as a computational model for long, but never got a chance to have an even recreational look at it. Today’s entry simply records the creating of the parser.
When you open VS2015 Command Prompt from a newly installed instance of Visual Studio 2017 Community, the prompt fails to initialise the variables. Telling you to ‘make sure either Visual Studio or C++ Build SKU is installed’. Searching the Internet, this seems to be a known and persisting issue. Here I propose an elegant workaround for it.
Base conversion is the conversion between notations of number, and NOT the numbers themselves. I discuss a common mistake on methods of base conversion, and a common mistake in thinking about ‘base conversion’ in computer programs.
Lagrange’s four-square theorem is a beautiful result in number theory. However, to the best of my knowledge, I haven’t encountered it often in theoretical computer science. Today’s entry discusses two interesting stories related to this theorem.
姚栋想要知道如何在 Windows 中使用命令解压缩 ZIP 文件夹。他表示如果要用 .NET Framework 提供的 API，则需要 4.5，但环境要求 4.0；如果用 PowerShell Expand-Archive 命令，则需要 5.1，但环境只允许 2.0；想用 cmd，但不知道怎么做。然而应该时刻记住：Windows 自带的 GUI 实际上经常是 COM 的图形版，在 COM 中寻找几乎总是可以找到你想要的图形操作的命令版本。
Starting from the classic puzzles of finding patterns in a sequence, this entry explores the framework to define persuasive patterns. The framework is found to be quite self-contained in the sense that it is ‘asymptotically invariant’ to the choice of ‘language of expression’. The only short-coming of this framework is that it works only for computable sequences, yet the process of pattern discovery is uncomputable.
In this entry, I discuss a pathological construction of general terms of a class of integer-valued sequences with the widely accepted concept of ‘elementary functions’. The idea here is to simply ‘concatenate’ the integers in a real number, then extract the appropriate digits for each term. It turns out that this definition characterises the elementariness very well (note that the definition is also self-referencing). The extended inspection leaves a problem open: Are all integer-valued sequences elementary? Update: The question is solved with an affirmative answer.
In this entry, I discuss a kind of widely posed exam problems for elementary calculus learners. It concerns a technique of application of (differential) mean value theorems. Specifically, a class of such problems can be solved dogmatically if the equation to prove resembles a ‘factorisable’ linear differential equation.
I allowed myself some CHANEL products to ‘reward’ myself for the acceptance of my first cryptography paper. I also consider spending money at its best value an interesting game. A commonly-seen discount aux Galeries Lafayette Xidan (Beijing) leads to an obviously NP-complete problem. Haha!
An algorithmic imagination of how Sina Weibo could implement Frequented Visitees, a feature that gives users the serveral accounts which they visit the most often.
Groove Music allows the user to store their music collection, including songs available via Music Pass subscription, those purchased from the Store, those stored on your OneDrive and those stored locally. This gives the users false impression that purchased music are secured by Microsoft’s service so they’re never lost.
This entry explores an interesting case of CRTP (curiously recurring template pattern) in C♯ that allows us to use operators. The other topic is elegant implementation of generic parameters that are (semantically) values instead of types.
Let me explain the classic idea that ‘the algorithm of a crypto system should be considered and made public’ to you. Particularly, I will discuss what it means by ‘crypto system’, which tells us what information should be no secret at all.
A practical problem I encountered in 2016, which I insisted on implementing with pure CSS as long as it was possible. At first it was solved with mathematical logic tricks but later it turned out there was a much simpler solution.
I was participating Advanced Assessment for Admission (AAA) of Tsinghua Union, passed the first phase and was interviewed by Insititute for Interdisciplinary Information Sciences of Tsinghua University. Here is a transcript of the interview.