Archive of Gee Law’s Blog
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). Embarassingly 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 imples 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 intialise 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 incomputable.
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. Speficially, 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.